Question bank IMO Shortlist 2010

Determine all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that the equality

$$
f([x] y)=f(x)[f(y)] .
$$

holds for all $x, y \in \mathbb{R}$. Here, by $[x]$ we denote the greatest integer not exceeding $x$.

Let the real numbers $a, b, c, d$ satisfy the relations $a+b+c+d=6$ and $a^{2}+b^{2}+c^{2}+d^{2}=12$. Prove that

$$
36 \leq 4\left(a^{3}+b^{3}+c^{3}+d^{3}\right)-\left(a^{4}+b^{4}+c^{4}+d^{4}\right) \leq 48
$$

Let $x_{1}, \ldots, x_{100}$ be nonnegative real numbers such that $x_{i}+x_{i+1}+x_{i+2} \leq 1$ for all $i=1, \ldots, 100$ (we put $x_{101}=x_{1}, x_{102}=x_{2}$ ). Find the maximal possible value of the sum

$$
S=\sum_{i=1}^{100} x_{i} x_{i+2}
$$

A sequence $x_{1}, x_{2}, \ldots$ is defined by $x_{1}=1$ and $x_{2 k}=-x_{k}, x_{2 k-1}=(-1)^{k+1} x_{k}$ for all $k \geq 1$. Prove that $x_{1}+x_{2}+\cdots+x_{n} \geq 0$ for all $n \geq 1$.

Denote by $\mathbb{Q}^{+}$the set of all positive rational numbers. Determine all functions $f: \mathbb{Q}^{+} \rightarrow \mathbb{Q}^{+}$ which satisfy the following equation for all $x, y \in \mathbb{Q}^{+}$:

$$
f\left(f(x)^{2} y\right)=x^{3} f(x y)
$$

Suppose that $f$ and $g$ are two functions defined on the set of positive integers and taking positive integer values. Suppose also that the equations $f(g(n))=f(n)+1$ and $g(f(n))=$ $g(n)+1$ hold for all positive integers. Prove that $f(n)=g(n)$ for all positive integer $n$.

Let $a_{1}, \ldots, a_{r}$ be positive real numbers. For $n\gt r$, we inductively define

$$
a_{n}=\max _{1 \leq k \leq n-1}\left(a_{k}+a_{n-k}\right)
$$

Prove that there exist positive integers $\ell \leq r$ and $N$ such that $a_{n}=a_{n-\ell}+a_{\ell}$ for all $n \geq N$.

Given six positive numbers $a, b, c, d, e, f$ such that $a\lt b\lt c\lt d\lt e\lt f$. Let $a+c+e=S$ and $b+d+f=T$. Prove that

$$
2 S T\gt \sqrt{3(S+T)(S(b d+b f+d f)+T(a c+a e+c e))}
$$

In a concert, 20 singers will perform. For each singer, there is a (possibly empty) set of other singers such that he wishes to perform later than all the singers from that set. Can it happen that there are exactly 2010 orders of the singers such that all their wishes are satisfied?

On some planet, there are $2^{N}$ countries $(N \geq 4)$. Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1$, each field being either yellow or blue. No two countries have the same flag.

We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set.

2500 chess kings have to be placed on a $100 \times 100$ chessboard so that
(i) no king can capture any other one (i.e. no two kings are placed in two squares sharing a common vertex);
(ii) each row and each column contains exactly 25 kings.

Find the number of such arrangements. (Two arrangements differing by rotation or symmetry are supposed to be different.)

Six stacks $S_{1}, \ldots, S_{6}$ of coins are standing in a row. In the beginning every stack contains a single coin. There are two types of allowed moves:
Move 1: If stack $S_{k}$ with $1 \leq k \leq 5$ contains at least one coin, you may remove one coin from $S_{k}$ and add two coins to $S_{k+1}$.
Move 2: If stack $S_{k}$ with $1 \leq k \leq 4$ contains at least one coin, then you may remove one coin from $S_{k}$ and exchange stacks $S_{k+1}$ and $S_{k+2}$.
Decide whether it is possible to achieve by a sequence of such moves that the first five stacks are empty, whereas the sixth stack $S_{6}$ contains exactly $2010^{2010^{2010}}$ coins.

Variant C4′. Same as Problem C4, but the constant $2010^{2010^{2010}}$ is replaced by $2010^{2010}$.

$n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players bad if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_{i}$ and $\ell_{i}$ be respectively the number of wins and losses of the $i$ th player. Prove that

$$
\sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)^{3} \geq 0
$$

Given a positive integer $k$ and other two integers $b\gt w\gt 1$. There are two strings of pearls, a string of $b$ black pearls and a string of $w$ white pearls. The length of a string is the number of pearls on it.

One cuts these strings in some steps by the following rules. In each step:
(i) The strings are ordered by their lengths in a non-increasing order. If there are some strings of equal lengths, then the white ones precede the black ones. Then $k$ first ones (if they consist of more than one pearl) are chosen; if there are less than $k$ strings longer than 1 , then one chooses all of them.
(ii) Next, one cuts each chosen string into two parts differing in length by at most one.
(For instance, if there are strings of $5,4,4,2$ black pearls, strings of $8,4,3$ white pearls and $k=4$, then the strings of 8 white, 5 black, 4 white and 4 black pearls are cut into the parts $(4,4),(3,2),(2,2)$ and $(2,2)$, respectively.)

The process stops immediately after the step when a first isolated white pearl appears. Prove that at this stage, there will still exist a string of at least two black pearls.

Let $P_{1}, \ldots, P_{s}$ be arithmetic progressions of integers, the following conditions being satisfied:
(i) each integer belongs to at least one of them;
(ii) each progression contains a number which does not belong to other progressions.

Denote by $n$ the least common multiple of steps of these progressions; let $n=p_{1}^{\alpha_{1}} \ldots p_{k}^{\alpha_{k}}$ be its prime factorization. Prove that

$$
s \geq 1+\sum_{i=1}^{k} \alpha_{i}\left(p_{i}-1\right)
$$

Let $A B C$ be an acute triangle with $D, E, F$ the feet of the altitudes lying on $B C, C A, A B$ respectively. One of the intersection points of the line $E F$ and the circumcircle is $P$. The lines $B P$ and $D F$ meet at point $Q$. Prove that $A P=A Q$.

Point $P$ lies inside triangle $A B C$. Lines $A P, B P, C P$ meet the circumcircle of $A B C$ again at points $K, L, M$, respectively. The tangent to the circumcircle at $C$ meets line $A B$ at $S$. Prove that $S C=S P$ if and only if $M K=M L$.

Let $A_{1} A_{2} \ldots A_{n}$ be a convex polygon. Point $P$ inside this polygon is chosen so that its projections $P_{1}, \ldots, P_{n}$ onto lines $A_{1} A_{2}, \ldots, A_{n} A_{1}$ respectively lie on the sides of the polygon. Prove that for arbitrary points $X_{1}, \ldots, X_{n}$ on sides $A_{1} A_{2}, \ldots, A_{n} A_{1}$ respectively,

$$
\max \left\{\frac{X_{1} X_{2}}{P_{1} P_{2}}, \ldots, \frac{X_{n} X_{1}}{P_{n} P_{1}}\right\} \geq 1
$$

Let $I$ be the incenter of a triangle $A B C$ and $\Gamma$ be its circumcircle. Let the line $A I$ intersect $\Gamma$ at a point $D \neq A$. Let $F$ and $E$ be points on side $B C$ and $\operatorname{arc} B D C$ respectively such that $\angle B A F=\angle C A E\lt \frac{1}{2} \angle B A C$. Finally, let $G$ be the midpoint of the segment $I F$. Prove that the lines $D G$ and $E I$ intersect on $\Gamma$.

Let $A B C D E$ be a convex pentagon such that $B C \| A E, A B=B C+A E$, and $\angle A B C=$ $\angle C D E$. Let $M$ be the midpoint of $C E$, and let $O$ be the circumcenter of triangle $B C D$. Given that $\angle D M O=90^{\circ}$, prove that $2 \angle B D A=\angle C D E$.