Show that it is possible to color the points of $\mathbb Q\times\mathbb Q$ in two colors in such a way that any two points having distance $1$ have distinct colors.

Two integers $0 < k < n$ and distinct real numbers $a_1, a_2, \dots ,a_n$ are given. Define the sets as the following, where all indices are modulo $n$. \begin{align*} A &= \{ 1 \le i \le n : a_i > a_{i-k}, a_{i-1}, a_{i+1}, a_{i+k} \text{ or } a_i < a_{i-k}, a_{i-1}, a_{i+1}, a_{i+k} \} \\ B &= \{ 1 \le i \le n : a_i > a_{i-k}, a_{i+k} \text{ and } a_i < a_{i-1}, a_{i+1} \} \\ C &= \{ 1 \le i \le n ; a_i > a_{i-1}, a_{i+1} \text{ and } a_i < a_{i-k}, a_{i+k} \} \end{align*} Prove that $\lvert A \rvert \ge \lvert B \rvert + \lvert C \rvert$.

On a circular billiard table a ball rebounds from the rails as if the rail was the tangent to the circle at the point of impact. A regular hexagon with its vertices on the circle is drawn on a circular billiard table. A (point-shaped) ball is placed somewhere on the circumference of the hexagon, but not on one of its edges. Describe a periodical track of this ball with exactly four points at the rails. With how many different directions of impact can the ball be brought onto such a track?

The king assembled 300 wizards and gave them the following challenge. For this challenge, 25 colors can be used, and they are known to the wizards. Each of the wizards receives a hat of one of those 25 colors. If for each color the number of used hats would be written down then all these number would be different, and the wizards know this. Each wizard sees what hat was given to each other wizard but does not see his own hat. Simultaneously each wizard reports the color of his own hat. Is it possible for the wizards to coordinate their actions beforehand so that at least 150 of them would report correctly?

You have the following pieces: one $4\times 1$ rectangle, two $3\times 1$ rectangles, three $2\times 1$ rectangles, and four $1\times 1$ squares. Ariel and Bernardo play the following game on a board of $n\times n$, where $n$ is a number that Ariel chooses. In each move, Bernardo receives a piece $R$ from Ariel. Next, Bernardo analyzes if he can place $R$ on the board so that it has no points in common with any of the previously placed pieces (not even a common vertex). If there is such a location for $R$, Bernardo must choose one of them and place $R$. The game stops if it is impossible to place $R$ in the way explained, and Bernardo wins. Ariel wins only if all $10$ pieces have been placed on the board. a) Suppose Ariel gives Bernardo the pieces in decreasing order of size. What is the smallest n that guarantees Ariel victory? b) For the $n$ found in a), if Bernardo receives the pieces in increasing order of size, is Ariel guaranteed victory? Note: Each piece must cover exactly a number of unit squares on the board equal to its own size. The sides of the pieces can coincide with parts of the edge of the board.

Suppose there are $n$ boxes in a row and place $n$ balls in them one in each. The balls are colored red, blue or green. In how many ways can we place the balls subject to the condition that any box $B$ has at least one adjacent box having a ball of the same color as the ball in $B$? [Assume that balls in each color are available abundantly.]

Each day, the price of the shares of the corporation “Soap Bubble, Limited” either increases or decreases by $n$ percent, where $n$ is an integer such that $0 < n < 100$. The price is calculated with unlimited precision. Does there exist an $n$ for which the price can take the same value twice?

Let $n$ be a positive integer. Define a chameleon to be any sequence of $3n$ letters, with exactly $n$ occurrences of each of the letters $a, b,$ and $c$. Define a swap to be the transposition of two adjacent letters in a chameleon. Prove that for any chameleon $X$ , there exists a chameleon $Y$ such that $X$ cannot be changed to $Y$ using fewer than $3n^2/2$ swaps.

consider $n\geq 6$ points $x_1,x_2,\dots,x_n$ on the plane such that no three of them are colinear. We call graph with vertices $x_1,x_2,\dots,x_n$ a "road network" if it is connected, each edge is a line segment, and no two edges intersect each other at points other than the vertices. Prove that there are three road networks $G_1,G_2,G_3$ such that $G_i$ and $G_j$ don't have a common edge for $1\leq i,j\leq 3$. Proposed by Morteza Saghafian

We have erasers, four pencils, two note books and three pens and we want to divide them between two persons so that every one receives at least one of the above stationery. In how many ways is this possible? [Note that the are not distinct.]

Arrange the positive integers into two lines as follows: \begin{align*} 1 \quad 3 \qquad 6 \qquad\qquad\quad 11 \qquad\qquad\qquad\qquad\quad\ 19\qquad\qquad32\qquad\qquad 53\ldots\\ \mbox{\ \ } 2 \quad 4\ \ 5 \quad 7\ \ 8\ \ 9\ \ 10\quad\ 12\ 13\ 14\ 15\ 16\ 17\ 18\quad\ 20 \mbox{ to } 31\quad\ 33 \mbox{ to } 52\quad\ \ldots\end{align*} We start with writing $1$ in the upper line, $2$ in the lower line and $3$ again in the upper line. Afterwards, we alternately write one single integer in the upper line and a block of integers in the lower line. The number of consecutive integers in a block is determined by the first number in the previous block. Let $a_1$, $a_2$, $a_3$, $\ldots$ be the numbers in the upper line. Give an explicit formula for $a_n$.

For each fixed positiver integer $n$, $n\geq 4$ and $P$ an integer, let $(P)_n \in [1, n]$ be the smallest positive residue of $P$ modulo $n$. Two sequences $a_1, a_2, \dots, a_k$ and $b_1, b_2, \dots, b_k$ with the terms in $[1, n]$ are defined as equivalent, if there is $t$ positive integer, gcd$(t,n)=1$, such that the sequence $(ta_1)_n, \dots, (ta_k)_n$ is a permutation of $b_1, b_2, \dots, b_k$. Let $\alpha$ a sequence of size $n$ and your terms are in $[1, n]$, such that each term appears $h$ times in the sequence $\alpha$ and $2h\geq n$. Show that $\alpha$ is equivalent to some sequence $\beta$ which contains a subsequence such that your size is(at most) equal to $h$ and your sum is exactly equal to $n$.

We divide $999\times 999$ square into the angles with $3$ cells. Prove, that number of ways is divided by $2^7$.( Angle is a figure, that we can get if we remove one cell from $2 \times 2$ square).

Every cell of a $4\times 4$ square grid net, has $1\times 1$ size. Is it possible to represent this net as a union of the following sets: a) Eight broken lines of length five each? b) Five broken lines of length eight each?

Consider the numbers from $1$ to $32$. A game is made by placing all the numbers in pairs and replacing each pair with the largest prime divisor of the sum of the numbers of that couple. For example, if we match the $32$ numbers as: $(1, 2), (3,4),(5, 6), (7, 8),..., (27, 28),(29, 30), (31,32)$, we get the following list of $16$ numbers: $3,7,11,5,...,11,59,7$. where there are repetitions. The game continues in a similar way until in the end only one number remains. Determine the highest possible value from the number that remains at the end.

Nair and Yuli play the following game: $1.$ There is a coin to be moved along a horizontal array with $203$ cells. $2.$ At the beginning, the coin is at the first cell, counting from left to right. $3.$ Nair plays first. $4.$ Each of the players, in their turns, can move the coin $1$, $2$, or $3$ cells to the right. $5.$ The winner is the one who reaches the last cell first. What strategy does Nair need to use in order to always win the game?

Consider a $25\times25$ chessboard with cells $C(i,j)$ for $1\le i,j\le25$. Find the smallest possible number $n$ of colors with which these cells can be colored subject to the following condition: For $1\le i<j\le25$ and for $1\le s<t\le25$, the three cells $C(i,s)$, $C(j,s)$, $C(j,t)$ carry at least two different colors. (Proposed by Gerhard Woeginger, Austria)

The set Φ consists of a finite number of points on the plane. The distance between any two points from Φ is at least $\sqrt{2}$. It is known that a regular triangle with side lenght $3$ cut out of paper can cover all points of Φ. What is the greatest number of points that Φ can consist of?

A circular disk is partitioned into $ 2n$ equal sectors by $ n$ straight lines through its center. Then, these $ 2n$ sectors are colored in such a way that exactly $ n$ of the sectors are colored in blue, and the other $ n$ sectors are colored in red. We number the red sectors with numbers from $ 1$ to $ n$ in counter-clockwise direction (starting at some of these red sectors), and then we number the blue sectors with numbers from $ 1$ to $ n$ in clockwise direction (starting at some of these blue sectors). Prove that one can find a half-disk which contains sectors numbered with all the numbers from $ 1$ to $ n$ (in some order). (In other words, prove that one can find $ n$ consecutive sectors which are numbered by all numbers $ 1$, $ 2$, ..., $ n$ in some order.) [hide="Problem 8 from CWMO 2007"]$ n$ white and $ n$ black balls are placed at random on the circumference of a circle.Starting from a certain white ball,number all white balls in a clockwise direction by $ 1,2,\dots,n$. Likewise number all black balls by $ 1,2,\dots,n$ in anti-clockwise direction starting from a certain black ball.Prove that there exists a chain of $ n$ balls whose collection of numbering forms the set $ \{1,2,3\dots,n\}$.[/hide]

Natural numbers $1, 2, 3,.., 100$ are contained in the union of $N$ geometric progressions (not necessarily with integer denominations). Prove that $N \ge 31$

The streets of a town are arranged in three directions , dividing the town into blocks which are equilateral triangles of equal area. Traffic , when reaching an intersection, may only go straight ahead, or turn left or right through $120^0$ , as shown in the diagram. [img]https://cdn.artofproblemsolving.com/attachments/3/6/a100a5c39bf15116582bc0bceb76fcbae28af9.png[/img] No turns are permitted except the ones at intersections . One car departs for a certain nearby intersection and when it reaches it a second car starts moving toward it. From then on both cars continue travelling at the same speed (but do not necessarily take the same turns). Is it possible that there will be a time when they will encounter each other somewhere? ( N . N . Konstantinov , Moscow )

The vertices of a connected graph cannot be coloured with less than $n+1$ colours (so that adjacent vertices have different colours). Prove that $\dfrac{n(n-1)}{2}$ edges can be removed from the graph so that it remains connected. [i]V. Dolnikov[/i] [b]EDIT.[/b] It is confirmed by the official solution that the graph is tacitly assumed to be [b]finite[/b].

The head of the Mint wants to release 12 coins denominations (each - a natural number rubles) so that any amount from 1 to 6543 rubles could be paid without having to pass, using no more than 8 coins. Can he do it? (If the payment amount you can use a few coins of the same denomination.)

Eric rolls a ten-sided die (with sides labeled $1$ through $10$) repeatedly until it lands on $3, 5$, or $7$. Conditional on all of Eric’s rolls being odd, the expected number of rolls can be expressed as $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Compute $m + n$.

Each square of a $5 \times 5$ board is painted red or blue, in such a way that the following condition is fulfilled: “For any two rows and two columns, of the $4$ squares that are in their intersections, there are $4$, $2$ or $0$ painted red.” How many ways can the board be painted?