IMO 2005 — Complete Shortlist

Find all monic polynomials $p(x)$ with integer coefficients of degree two for which there exists a polynomial $q(x)$ with integer coefficients such that $p(x)q(x)$ is a polynomial having all coefficients $\pm1$.

Let $ \mathbb{R}^+ $ denote the set of positive real numbers. Determine all functions $ f: \mathbb{R}^+\to \mathbb{R}^+ $ such that

$$ f(x)f(y)=2f(x+y f(x)) $$

for all positive real numbers x and y.

Four real numbers $p,q,r,s$ satisfy

$$ p+q+r+s=9\quad\text{and}\quad p^{2}+q^{2}+r^{2}+s^{2}=21. $$

Prove that $ab - cd \geq 2$ holds for some permutation $(a,b,c,d)$ of $(p,q,r,s)$.

Find all functions $ f: \mathbb{R} \to \mathbb{R} $ satisfying the equation

$$ f(x+y)+f(x)f(y)=f(xy)+2xy+1 $$

for all real x and y.

Let $x,y,z$ be positive real numbers such that $xyz\geq1$. Prove that

$$ \frac{x^{5}-x^{2}}{x^{5}+y^{2}+z^{2}}+\frac{y^{5}-y^{2}}{y^{5}+z^{2}+x^{2}}+\frac{z^{5}-z^{2}}{z^{5}+x^{2}+y^{2}}\geq0. $$

A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off.

Let k be a fixed positive integer. A company has a special method to sell sombreros. Each customer can convince two persons to buy a sombrero after he/she buys one; convincing someone already convinced does not count. Each

of these new customers can convince two others and so on. If each one of the two customers convinced by someone makes at least k persons buy sombreros (directly or indirectly), then that someone wins a free instructional video. Prove that if n persons bought sombreros, then at most $ n/(k+2) $ of them got videos.

In an $ m \times n $ rectangular board of mn unit squares, adjacent squares are ones with a common edge, and a path is a sequence of squares in which any two consecutive squares are adjacent. Each square of the board can be colored black or white. Let N denote the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge, and let M denote the number of colorings in which there exist at least two non-intersecting black paths from the left edge to the right edge. Prove that $ N^2 \geq 2^{mn}M $.

Let $ n \geq 3 $ be a given positive integer. We wish to label each side and each diagonal of a regular $ n $-gon $ P_1 \ldots P_n $ with a positive integer less than or equal to r so that:

(i) every integer between 1 and r occurs as a label;

(ii) in each triangle $P_{i}P_{j}P_{k}$ two of the labels are equal and greater than the third. Given these conditions:

(a) Determine the largest positive integer r for which this can be done.

(b) For that value of r, how many such labellings are there?

There are $n$ markers, each with one side white and the other side black, aligned in a row so that their white sides are up. In each step, if possible, we choose a marker with the white side up (but not one of outermost markers), remove it and reverse the closest marker to the left and the closest marker to the right of it. Prove that one can achieve the state with only two markers remaining if and only if $n-1$ is not divisible by 3.

In a mathematical competition 6 problems were posed to the contestants. Each pair of problems was solved by more than 2/5 of the contestants. Nobody solved all 6 problems. Show that there were at least 2 contestants who each solved exactly 5 problems.

Let $ n \geq 1 $ be a given integer, and let $ a_1, \ldots, a_n $ be a sequence of integers such that $ n $ divides the sum $ a_1 + \cdots + a_n $. Show that there exist permutations $ \sigma $ and $ \tau $ of 1, 2, $ \ldots $, $ n $ such that $ \sigma(i) + \tau(i) \equiv a_i \pmod{n} $ for all $ i = 1, \ldots, n $.

Let $M$ be a convex $n$-gon, $n \geq 4$. Some $n-3$ of its diagonals are colored green and some other $n-3$ diagonals are colored red, so that no two diagonals of the same color meet inside $M$. Find the maximum possible number of intersection points of green and red diagonals inside $M$.

In a triangle $ ABC $ satisfying $ AB + BC = 3AC $ the incircle has center $ I $ and touches the sides $ AB $ and $ BC $ at $ D $ and $ E $, respectively. Let $ K $ and $ L $ be the symmetric points of $ D $ and $ E $ with respect to $ I $. Prove that the quadrilateral $ ACKL $ is cyclic.

Six points are chosen on the sides of an equilateral triangle ABC: $ A_1, A_2 $ on BC; $ B_1, B_2 $ on CA; $ C_1, C_2 $ on AB. These points are vertices of a convex hexagon $ A_1A_2B_1B_2C_1C_2 $ with equal side lengths. Prove that the lines $ A_1B_2, B_1C_2 $ and $ C_1A_2 $ are concurrent.

Let ABCD be a parallelogram. A variable line $l$ passing through the point $A$ intersects the rays $BC$ and $DC$ at points $X$ and $Y$, respectively. Let $K$ and $L$ be the centers of the excircles of triangles $ABX$ and $ADY$, touching the sides $BX$ and $DY$, respectively. Prove that the size of angle $KCL$ does not depend on the choice of the line $l$.

Let ABCD be a given convex quadrilateral with sides BC and AD equal in length and not parallel. Let E and F be interior points of the sides BC and AD respectively such that BE = DF. The lines AC and BD meet at P, the lines BD and EF meet at Q, the lines EF and AC meet at R. Consider all the triangles PQR as E and F vary. Show that the circumcircles of these triangles have a common point other than P.

Let $ABC$ be an acute-angled triangle with $AB \ne AC$, let $H$ be its orthocenter and $M$ the midpoint of $BC$. Points $D$ on $AB$ and $E$ on $AC$ are such that $AE = AD$ and $D,H,E$ are collinear. Prove that $HM$ is orthogonal to the common chord of the circumcircles of triangles $ABC$ and $ADE$.

The median AM of a triangle ABC intersects its incircle $ \omega $ at K and L. The lines through K and L parallel to BC intersect $ \omega $ again at X and Y. The lines AX and AY intersect BC at P and Q. Prove that BP = CQ.

In an acute triangle $ ABC $, let $ D $, $ E $, $ F $, $ P $, $ Q $, $ R $ be the feet of perpendiculars from $ A $, $ B $, $ C $, $ A $, $ B $, $ C $ to $ BC $, $ CA $, $ AB $, $ EF $, $ FD $, $ DE $, respectively. Prove that $ p(ABC)p(PQR) \geq p(DEF)^2 $, where $ p(T) $ denotes the perimeter of triangle $ T $.