Question bank IMO Shortlist 2013

Let $n$ be a positive integer and let $a_{1}, \ldots, a_{n-1}$ be arbitrary real numbers. Define the sequences $u_{0}, \ldots, u_{n}$ and $v_{0}, \ldots, v_{n}$ inductively by $u_{0}=u_{1}=v_{0}=v_{1}=1$, and

$$
u_{k+1}=u_{k}+a_{k} u_{k-1}, \quad v_{k+1}=v_{k}+a_{n-k} v_{k-1} \quad \text { for } k=1, \ldots, n-1 .
$$

Prove that $u_{n}=v_{n}$.

Prove that in any set of 2000 distinct real numbers there exist two pairs $a\gt b$ and $c\gt d$ with $a \neq c$ or $b \neq d$, such that

$$
\left|\frac{a-b}{c-d}-1\right|\lt \frac{1}{100000}
$$

Let $\mathbb{Q}_{\gt 0}$ be the set of positive rational numbers. Let $f: \mathbb{Q}_{\gt 0} \rightarrow \mathbb{R}$ be a function satisfying the conditions

$$
\begin{aligned}
& f(x) f(y) \geqslant f(x y) \\
& f(x+y) \geqslant f(x)+f(y)
\end{aligned}
$$

for all $x, y \in \mathbb{Q}_{\gt 0}$. Given that $f(a)=a$ for some rational $a\gt 1$, prove that $f(x)=x$ for all $x \in \mathbb{Q}_{\gt 0}$.

Let $n$ be a positive integer, and consider a sequence $a_{1}, a_{2}, \ldots, a_{n}$ of positive integers. Extend it periodically to an infinite sequence $a_{1}, a_{2}, \ldots$ by defining $a_{n+i}=a_{i}$ for all $i \geqslant 1$. If

$$
a_{1} \leqslant a_{2} \leqslant \cdots \leqslant a_{n} \leqslant a_{1}+n
$$

and

$$
a_{a_{i}} \leqslant n+i-1 \quad \text { for } i=1,2, \ldots, n
$$

prove that

$$
a_{1}+\cdots+a_{n} \leqslant n^{2} .
$$

Let $\mathbb{Z}_{\geqslant 0}$ be the set of all nonnegative integers. Find all the functions $f: \mathbb{Z}_{\geqslant 0} \rightarrow \mathbb{Z}_{\geqslant 0}$ satisfying the relation

$$
f(f(f(n)))=f(n+1)+1
$$

for all $n \in \mathbb{Z}_{\geqslant 0}$.

Let $m \neq 0$ be an integer. Find all polynomials $P(x)$ with real coefficients such that

$$
\left(x^{3}-m x^{2}+1\right) P(x+1)+\left(x^{3}+m x^{2}+1\right) P(x-1)=2\left(x^{3}-m x+1\right) P(x)
$$

for all real numbers $x$.

Let $n$ be a positive integer. Find the smallest integer $k$ with the following property: Given any real numbers $a_{1}, \ldots, a_{d}$ such that $a_{1}+a_{2}+\cdots+a_{d}=n$ and $0 \leqslant a_{i} \leqslant 1$ for $i=1,2, \ldots, d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most 1 .

In the plane, 2013 red points and 2014 blue points are marked so that no three of the marked points are collinear. One needs to draw $k$ lines not passing through the marked points and dividing the plane into several regions. The goal is to do it in such a way that no region contains points of both colors.

Find the minimal value of $k$ such that the goal is attainable for every possible configuration of 4027 points.

A crazy physicist discovered a new kind of particle which he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.

(i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.

(ii) At any moment, he may double the whole family of imons in his lab by creating a copy $I^{\prime}$ of each imon $I$. During this procedure, the two copies $I^{\prime}$ and $J^{\prime}$ become entangled if and only if the original imons $I$ and $J$ are entangled, and each copy $I^{\prime}$ becomes entangled with its original imon $I$; no other entanglements occur or disappear at this moment.

Prove that the physicist may apply a sequence of such operations resulting in a family of imons, no two of which are entangled.

Let $n$ be a positive integer, and let $A$ be a subset of $\{1, \ldots, n\}$. An $A$-partition of $n$ into $k$ parts is a representation of $n$ as a sum $n=a_{1}+\cdots+a_{k}$, where the parts $a_{1}, \ldots, a_{k}$ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}$.

We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r\lt k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6 n}$ different parts.

Let $r$ be a positive integer, and let $a_{0}, a_{1}, \ldots$ be an infinite sequence of real numbers. Assume that for all nonnegative integers $m$ and $s$ there exists a positive integer $n \in[m+1, m+r]$ such that

$$
a_{m}+a_{m+1}+\cdots+a_{m+s}=a_{n}+a_{n+1}+\cdots+a_{n+s}
$$

Prove that the sequence is periodic, i. e. there exists some $p \geqslant 1$ such that $a_{n+p}=a_{n}$ for all $n \geqslant 0$.

In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is defined to be the least possible number of flights required to go from one of them to the other. It is known that for any city there are at most 100 cities at distance exactly three from it. Prove that there is no city such that more than 2550 other cities have distance exactly four from it.

Let $n \geqslant 2$ be an integer. Consider all circular arrangements of the numbers $0,1, \ldots, n$; the $n+1$ rotations of an arrangement are considered to be equal. A circular arrangement is called beautiful if, for any four distinct numbers $0 \leqslant a, b, c, d \leqslant n$ with $a+c=b+d$, the chord joining numbers $a$ and $c$ does not intersect the chord joining numbers $b$ and $d$.

Let $M$ be the number of beautiful arrangements of $0,1, \ldots, n$. Let $N$ be the number of pairs $(x, y)$ of positive integers such that $x+y \leqslant n$ and $\operatorname{gcd}(x, y)=1$. Prove that

$$
M=N+1
$$

Players $A$ and $B$ play a paintful game on the real line. Player $A$ has a pot of paint with four units of black ink. A quantity $p$ of this ink suffices to blacken a (closed) real interval of length p. In every round, player $A$ picks some positive integer $m$ and provides $1 / 2^{m}$ units of ink from the pot. Player $B$ then picks an integer $k$ and blackens the interval from $k / 2^{m}$ to $(k+1) / 2^{m}$ (some parts of this interval may have been blackened before). The goal of player $A$ is to reach a situation where the pot is empty and the interval $[0,1]$ is not completely blackened.

Decide whether there exists a strategy for player $A$ to win in a finite number of moves.

Let $A B C$ be an acute-angled triangle with orthocenter $H$, and let $W$ be a point on side $B C$. Denote by $M$ and $N$ the feet of the altitudes from $B$ and $C$, respectively. Denote by $\omega_{1}$ the circumcircle of $B W N$, and let $X$ be the point on $\omega_{1}$ which is diametrically opposite to $W$. Analogously, denote by $\omega_{2}$ the circumcircle of $C W M$, and let $Y$ be the point on $\omega_{2}$ which is diametrically opposite to $W$. Prove that $X, Y$ and $H$ are collinear.

Let $\omega$ be the circumcircle of a triangle $A B C$. Denote by $M$ and $N$ the midpoints of the sides $A B$ and $A C$, respectively, and denote by $T$ the midpoint of the $\operatorname{arc} B C$ of $\omega$ not containing $A$. The circumcircles of the triangles $A M T$ and $A N T$ intersect the perpendicular bisectors of $A C$ and $A B$ at points $X$ and $Y$, respectively; assume that $X$ and $Y$ lie inside the triangle $A B C$. The lines $M N$ and $X Y$ intersect at $K$. Prove that $K A=K T$.

In a triangle $A B C$, let $D$ and $E$ be the feet of the angle bisectors of angles $A$ and $B$, respectively. A rhombus is inscribed into the quadrilateral $A E D B$ (all vertices of the rhombus lie on different sides of $A E D B$ ). Let $\varphi$ be the non-obtuse angle of the rhombus. Prove that $\varphi \leqslant \max \{\angle B A C, \angle A B C\}$.

Let $A B C$ be a triangle with $\angle B\gt \angle C$. Let $P$ and $Q$ be two different points on line $A C$ such that $\angle P B A=\angle Q B A=\angle A C B$ and $A$ is located between $P$ and $C$. Suppose that there exists an interior point $D$ of segment $B Q$ for which $P D=P B$. Let the ray $A D$ intersect the circle $A B C$ at $R \neq A$. Prove that $Q B=Q R$.

Let $A B C D E F$ be a convex hexagon with $A B=D E, B C=E F, C D=F A$, and $\angle A-\angle D=\angle C-\angle F=\angle E-\angle B$. Prove that the diagonals $A D, B E$, and $C F$ are concurrent.

Let the excircle of the triangle $A B C$ lying opposite to $A$ touch its side $B C$ at the point $A_{1}$. Define the points $B_{1}$ and $C_{1}$ analogously. Suppose that the circumcentre of the triangle $A_{1} B_{1} C_{1}$ lies on the circumcircle of the triangle $A B C$. Prove that the triangle $A B C$ is right-angled.