Found problems: 800
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.
What is the greatest number of positive integers lesser than or equal to 2016 we can choose such that it doesn't have two of them differing by 1,2, or 6?
Let $ n$ be a positive integer and let $ a_1,a_2,a_3,\ldots,a_k$ $ ( k\ge 2)$ be distinct integers in the set $ { 1,2,\ldots,n}$ such that $ n$ divides $ a_i(a_{i + 1} - 1)$ for $ i = 1,2,\ldots,k - 1$. Prove that $ n$ does not divide $ a_k(a_1 - 1).$
[i]Proposed by Ross Atkins, Australia [/i]
A [i]domino[/i] is a $2 \times 1$ or $1 \times 2$ tile. Determine in how many ways exactly $n^2$ dominoes can be placed without overlapping on a $2n \times 2n$ chessboard so that every $2 \times 2$ square contains at least two uncovered unit squares which lie in the same row or column.
Find all positive integers $n$ with the following property: the $k$ positive divisors of $n$ have a permutation $(d_1,d_2,\ldots,d_k)$ such that for $i=1,2,\ldots,k$, the number $d_1+d_2+\cdots+d_i$ is a perfect square.
There are $n \ge 3$ distinct positive real numbers. Show that there are at most $n-2$ different integer power of three that can be written as the sum of three distinct elements from these $n$ numbers.
Let $n$ be a positive integer relatively prime to $6$. We paint the vertices of a regular $n$-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.
Let $n$ be a positive integer relatively prime to $6$. We paint the vertices of a regular $n$-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.
Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$.
Suppose that $1000$ students are standing in a circle. Prove that there exists an integer $k$ with $100 \leq k \leq 300$ such that in this circle there exists a contiguous group of $2k$ students, for which the first half contains the same number of girls as the second half.
[i]Proposed by Gerhard Wöginger, Austria[/i]
Let $ABCDE$ be a convex pentagon with $CD= DE$ and $\angle EDC \ne 2 \cdot \angle ADB$.
Suppose that a point $P$ is located in the interior of the pentagon such that $AP =AE$ and $BP= BC$.
Prove that $P$ lies on the diagonal $CE$ if and only if area $(BCD)$ + area $(ADE)$ = area $(ABD)$ + area $(ABP)$.
(Hungary)
You are given a set of $n$ blocks, each weighing at least $1$; their total weight is $2n$. Prove that for every real number $r$ with $0 \leq r \leq 2n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r + 2$.
There are $n$ students $ A_1 , A_2 , \cdots , A_n $ and some of them shaked hands with each other. ($ A_i $ and $ A_j$ can shake hands more than one time.) Let the student $ A_i $ shaked hands $ d_i $ times. Suppose $ d_1 + d_2 + \cdots + d_n > 0 $. Prove that there exist $ 1 \le i < j \le n $ satisfying the following conditions:
(a) Two students $ A_i $ and $ A_j $ shaked hands each other.
(b) $ \frac{(d_1 + d_2 + \cdots + d_n ) ^2 }{n^2 } \le d_i d_j $
The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$.
[i]Proposed by Croatia[/i]
The system of equations
\begin{eqnarray*}\log_{10}(2000xy) - (\log_{10}x)(\log_{10}y) & = & 4 \\
\log_{10}(2yz) - (\log_{10}y)(\log_{10}z) & = & 1 \\
\log_{10}(zx) - (\log_{10}z)(\log_{10}x) & = & 0 \\
\end{eqnarray*}
has two solutions $ (x_{1},y_{1},z_{1})$ and $ (x_{2},y_{2},z_{2}).$ Find $ y_{1} + y_{2}.$
In a company of people some pairs are enemies. A group of people is called [i]unsociable[/i] if the number of members in the group is odd and at least $3$, and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most $2015$ unsociable groups, prove that it is possible to partition the company into $11$ parts so that no two enemies are in the same part.
[i]Proposed by Russia[/i]
Let $P$ be a point inside triangle $ABC$. Let $AP$ meet $BC$ at $A_1$, let $BP$ meet $CA$ at $B_1$, and let $CP$ meet $AB$ at $C_1$. Let $A_2$ be the point such that $A_1$ is the midpoint of $PA_2$, let $B_2$ be the point such that $B_1$ is the midpoint of $PB_2$, and let $C_2$ be the point such that $C_1$ is the midpoint of $PC_2$. Prove that points $A_2, B_2$, and $C_2$ cannot all lie strictly inside the circumcircle of triangle $ABC$.
(Australia)
A sequence of real numbers $a_1,a_2,\ldots$ satisfies the relation
$$a_n=-\max_{i+j=n}(a_i+a_j)\qquad\text{for all}\quad n>2017.$$
Prove that the sequence is bounded, i.e., there is a constant $M$ such that $|a_n|\leq M$ for all positive integers $n$.
A country has 1001 cities, and each two cities are connected by a one-way street. From each city exactly 500 roads begin, and in each city 500 roads end. Now an independent republic splits itself off the country, which contains 668 of the 1001 cities. Prove that one can reach every other city of the republic from each city of this republic without being forced to leave the republic.
Let $n\geq3$ be an integer. We say that an arrangement of the numbers $1$, $2$, $\dots$, $n^2$ in a $n \times n$ table is [i]row-valid[/i] if the numbers in each row can be permuted to form an arithmetic progression, and [i]column-valid[/i] if the numbers in each column can be permuted to form an arithmetic progression. For what values of $n$ is it possible to transform any row-valid arrangement into a column-valid arrangement by permuting the numbers in each row?
Let $S$ be a nonempty set of positive integers. We say that a positive integer $n$ is [i]clean[/i] if it has a unique representation as a sum of an odd number of distinct elements from $S$. Prove that there exist infinitely many positive integers that are not clean.
What is the number of ways the numbers from $1$ to $14$ can be split into $7$ pairs such that for each pair, the greater number is at least $2$ times the smaller number?
$\textbf{(A) }108\qquad\textbf{(B) }120\qquad\textbf{(C) }126\qquad\textbf{(D) }132\qquad\textbf{(E) }144$
A [i]word[/i] is a finite sequence of letters from some alphabet. A word is [i]repetitive[/i] if it is a concatenation of at least two identical subwords (for example, $ababab$ and $abcabc$ are repetitive, but $ababa$ and $aabb$ are not). Prove that if a word has the property that swapping any two adjacent letters makes the word repetitive, then all its letters are identical. (Note that one may swap two adjacent identical letters, leaving a word unchanged.)
[i]Romania (Dan Schwarz)[/i]
A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes a colouring of the cells with finitely many colours. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cell that it has not visited before (two cells are adjacent if they share an edge). The hunter wins if after some finite time either:[list][*]the rabbit cannot move; or
[*]the hunter can determine the cell in which the rabbit started.[/list]Decide whether there exists a winning strategy for the hunter.
[i]Proposed by Aron Thomas[/i]
We are given an infinite deck of cards, each with a real number on it. For every real number $x$, there is exactly one card in the deck that has $x$ written on it. Now two players draw disjoint sets $A$ and $B$ of $100$ cards each from this deck. We would like to define a rule that declares one of them a winner. This rule should satisfy the following conditions:
1. The winner only depends on the relative order of the $200$ cards: if the cards are laid down in increasing order face down and we are told which card belongs to which player, but not what numbers are written on them, we can still decide the winner.
2. If we write the elements of both sets in increasing order as $A =\{ a_1 , a_2 , \ldots, a_{100} \}$ and $B= \{ b_1 , b_2 , \ldots , b_{100} \}$, and $a_i > b_i$ for all $i$, then $A$ beats $B$.
3. If three players draw three disjoint sets $A, B, C$ from the deck, $A$ beats $B$ and $B$ beats $C$ then $A$ also beats $C$.
How many ways are there to define such a rule? Here, we consider two rules as different if there exist two sets $A$ and $B$ such that $A$ beats $B$ according to one rule, but $B$ beats $A$ according to the other.
[i]Proposed by Ilya Bogdanov, Russia[/i]