Question bank IMO Shortlist 2004

Let $ n \geq 3 $ be an integer and $ t_1, t_2, \ldots, t_n $ positive real numbers such that

$$ n^{2}+1 \gt \left(t_{1}+t_{2}+\cdots+t_{n}\right)\left(\frac{1}{t_{1}}+\frac{1}{t_{2}}+\cdots+\frac{1}{t_{n}}\right). $$

Show that $t_i, t_j, t_k$ are the side lengths of a triangle for all $i, j, k$ with $1 \leq i \lt j \lt k \leq n$.

An infinite sequence $ a_{0}, a_{1}, a_{2}, \ldots $ of real numbers satisfies the condition

$$ a_{n}=\left|a_{n+1}-a_{n+2}\right|\text{for every}n\geq0 $$

with $a_{0}$ and $a_{1}$ positive and distinct. Can this sequence be bounded?

Does there exist a function $ s\colon \mathbb{Q} \to \{-1,1\} $ such that if $ x $ and $ y $ are distinct rational numbers satisfying $ xy = 1 $ or $ x + y \in \{0,1\} $, then $ s(x)s(y) = -1 $? Justify your answer.

Find all polynomials $P(x)$ with real coefficients that satisfy the equality

$$ P(a-b)+P(b-c)+P(c-a)=2P(a+b+c) $$

for all triples $a, b, c$ of real numbers such that $ab + bc + ca = 0$.

Let $a,b,c\gt 0$ and $ ab + bc + ca = 1 $. Prove the inequality

$$ \sqrt[3]{\frac{1}{a}+6b}+\sqrt[3]{\frac{1}{b}+6c}+\sqrt[3]{\frac{1}{c}+6a}\leq\frac{1}{abc}. $$

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

$$ f\left(x^{2}+y^{2}+2f(x y)\right)=\left(f(x+y)\right)^{2}\quad\text{for all }\quad x,y\in\mathbb{R}. $$

Let $a_{1}, a_{2}, \ldots, a_{n}$ be positive real numbers, $n \gt 1$. Denote by $g_{n}$ their geometric mean, and by $A_{1}, A_{2}, \ldots, A_{n}$ the sequence of arithmetic means defined by $A_{k} = \frac{a_{1} + a_{2} + \cdots + a_{k}}{k}$, $k = 1, 2, \ldots, n$. Let $G_{n}$ be the geometric mean of $A_{1}, A_{2}, \ldots, A_{n}$. Prove the inequality

$$ n\sqrt[n]{\frac{G_{n}}{A_{n}}}+\frac{g_{n}}{G_{n}}\leq n+1 $$

and establish the cases of equality.

There are 10001 students at a university. Some students join together to form several clubs (a student may belong to different clubs). Some clubs join together to form several societies (a club may belong to different societies). There are a total of k societies. Suppose that the following conditions hold:

(i) Each pair of students are in exactly one club.

(ii) For each student and each society, the student is in exactly one club of the society.

(iii) Each club has an odd number of students. In addition, a club with $ 2m+1 $ students (m is a positive integer) is in exactly m societies. Find all possible values of k.

Let $n$ and $k$ be positive integers. There are given $n$ circles in the plane. Every two of them intersect at two distinct points, and all points of intersection they determine are distinct. Each intersection point must be colored with one of $n$ distinct colors so that each color is used at least once, and exactly $k$ distinct colors occur on each circle. Find all values of $n \geq 2$ and $k$ for which such a coloring is possible.

The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer $ n \geq 4 $, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on n vertices (where each pair of vertices are joined by an edge).

Consider a matrix of size $ n \times n $ whose entries are real numbers of absolute value not exceeding 1, and the sum of all entries is 0. Let n be an even positive integer. Determine the least number C such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding C in absolute value.

Let $N$ be a positive integer. Two players $A$ and $B$, taking turns, write numbers from the set $\{1, \ldots, N\}$ on a blackboard. $A$ begins the game by writing 1 on his first move. Then, if a player has written $n$ on

a certain move, his adversary is allowed to write $ n+1 $ or 2n (provided the number he writes does not exceed N). The player who writes N wins. We say that N is of type A or of type B according as A or B has a winning strategy.

(a) Determine whether N = 2004 is of type A or of type B.

(b) Find the least N > 2004 whose type is different from that of 2004.

For an $ n \times n $ matrix $ A $, let $ X_i $ be the set of entries in row $ i $, and $ Y_j $ the set of entries in column $ j $, $ 1 \leq i, j \leq n $. We say that $ A $ is golden if $ X_1, \ldots, X_n, Y_1, \ldots, Y_n $ are distinct sets. Find the least integer $ n $ such that there exists a $ 2004 \times 2004 $ golden matrix with entries in the set $ \{1, 2, \ldots, n\} $.

Determine all $ m \times n $ rectangles that can be covered with hooks made up of 6 unit squares, as in the figure:



Rotations and reflections of hooks are allowed. The rectangle must be covered without gaps and overlaps. No part of a hook may cover area outside the rectangle.

For a finite graph $G$, let $f(G)$ be the number of triangles and $g(G)$ the number of tetrahedra formed by edges of $G$. Find the least constant $c$ such that

$$ g(G)^{3}\leq c\cdot f(G)^{4}{\mathrm{~f o r~e v e r y~g r a p h~}}G. $$

Let $ ABC $ be an acute-angled triangle with $ AB \ne AC $. The circle with diameter $ BC $ intersects the sides $ AB $ and $ AC $ at $ M $ and $ N $, respectively. Denote by $ O $ the midpoint of $ BC $. The bisectors of the angles $ BAC $ and $ MON $ intersect at $ R $. Prove that the circumcircles of the triangles $ BMR $ and $ CNR $ have a common point lying on the line segment $ BC $.

The circle $\Gamma$ and the line $\ell$ do not intersect. Let $AB$ be the diameter of $\Gamma$ perpendicular to $\ell$, with $B$ closer to $\ell$ than $A$. An arbitrary point $C \neq A$, $B$ is chosen on $\Gamma$. The line $AC$ intersects $\ell$ at $D$. The line $DE$ is tangent to $\Gamma$ at $E$, with $B$ and $E$ on the same side of $AC$. Let $BE$ intersect $\ell$ at $F$, and let $AF$ intersect $\Gamma$ at $G \neq A$. Prove that the reflection of $G$ in $AB$ lies on the line $CF$.

Let $O$ be the circumcenter of an acute-angled triangle $ABC$ with $\angle B \lt \angle C$. The line $AO$ meets the side $BC$ at $D$. The circumcenters of the triangles $ABD$ and $ACD$ are $E$ and $F$, respectively. Extend the sides $BA$ and $CA$ beyond $A$, and choose on the respective extension points $G$ and $H$ such that $AG = AC$ and $AH = AB$. Prove that the quadrilateral $EFGH$ is a rectangle if and only if $\angle ACB - \angle ABC = 60^\circ$.

In a convex quadrilateral $ ABCD $ the diagonal $ BD $ does not bisect the angles $ ABC $ and $ CDA $. The point $ P $ lies inside $ ABCD $ and satisfies

$$ \angle PBC=\angle DBA\quad\text{and}\quad\angle PDC=\angle BDA. $$

Prove that ABCD is a cyclic quadrilateral if and only if AP = CP.

Let $ A_1A_2\ldots A_n $ be a regular n-gon. The points $ B_1,\ldots,B_{n-1} $ are defined as follows:

(i) If i = 1 or i = n - 1, then $B_{i}$ is the midpoint of the side $A_{i}A_{i+1}$.

(ii) If $ i \neq 1 $, $ i \neq n-1 $, and S is the intersection point of $ A_1A_{i+1} $ and $ A_nA_i $, then $ B_i $ is the intersection point of the bisector of the angle $ A_iSA_{i+1} $ with $ A_iA_{i+1} $.

Prove the equality

$$ \angle A_{1}B_{1}A_{n}+\angle A_{1}B_{2}A_{n}+\cdots+\angle A_{1}B_{n-1}A_{n}=180^{\circ}. $$