IMO 2014

Let $a_0 < a_1 < a_2 < \dots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n\geq 1$ such that $$a_n < \frac{a_0+a_1+a_2+\cdots+a_n}{n} \leq a_{n+1}.$$

Proposed by Gerhard Wöginger, Austria.

Let $n \ge 2$ be an integer. Consider an $n \times n$ chessboard consisting of $n^2$ unit squares. A configuration of $n$ rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that, for each peaceful configuration of $n$ rooks, there is a $k \times k$ square which does not contain a rook on any of its $k^2$ unit squares.

Convex quadrilateral $A B C D$ has $\angle A B C = \angle C D A = 90^{\circ}$ . Point $H$ is the foot of the perpendicular from $A$ to $\overline{{B D}}$ . Points $S$ and $T$ lie on sides $A B$ and $A D$ , respectively, such that $H$ lies inside triangle $S C T$ and

$$\angle C H S - \angle C S B = 90^{\circ}, \angle T H C - \angle D T C = 90^{\circ}.$$

Prove that line $B D$ is tangent to the circumcircle of triangle $T S H$

Let $P$ and $Q$ be on segment $BC$ of an acute triangle $ABC$ such that $\angle PAB=\angle BCA$ and $\angle CAQ=\angle ABC$ . Let $M$ and $N$ be the points on $AP$ and $AQ$ , respectively, such that $P$ is the midpoint of $AM$ and $Q$ is the midpoint of $AN$ . Prove that the intersection of $BM$ and $CN$ is on the circumference of triangle $ABC$ .

Proposed by Giorgi Arabidze, Georgia.

For each positive integer $n$ , the Bank of Cape Town issues coins of denomination $\frac1n$ . Given a finite collection of such coins (of not necessarily different denominations) with total value at most most $99+\frac12$ , prove that it is possible to split this collection into $100$ or fewer groups, such that each group has total value at most $1$ .

A set of lines in the plane is in general position if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its finite regions. Prove that for all sufficiently large $n$ , in any set of $n$ lines in general position it is possible to colour at least $\sqrt{n}$ lines blue in such a way that none of its finite regions has a completely blue boundary.

Note: Results with $\sqrt{n}$ replaced by $c\sqrt{n}$ will be awarded points depending on the value of the constant $c$ .