Question bank IMO Shortlist 2003

Let $a_{ij}$, $i=1,2,3$; $j=1,2,3$ be real numbers such that $a_{ij}$ is positive for $i=j$ and negative for $i\neq j$.

Prove that there exist positive real numbers $c_{1}, c_{2}, c_{3}$ such that the numbers

$$ a_{11}c_{1}+a_{12}c_{2}+a_{13}c_{3},\qquad a_{21}c_{1}+a_{22}c_{2}+a_{23}c_{3},\qquad a_{31}c_{1}+a_{32}c_{2}+a_{33}c_{3} $$

are all negative, all positive, or all zero.

Find all nondecreasing functions $ f\colon \mathbb{R} \longrightarrow \mathbb{R} $ such that

(i) $ f(0)=0, f(1)=1; $

(ii) $ f(a) + f(b) = f(a)f(b) + f(a + b - ab) $ for all real numbers a, b such that a < 1 < b.

Consider pairs of sequences of positive real numbers

$$ a_{1}\geq a_{2}\geq a_{3}\geq\cdots,\qquad b_{1}\geq b_{2}\geq b_{3}\geq\cdots $$

and the sums

$$ A_{n}=a_{1}+\cdots+a_{n},\quad B_{n}=b_{1}+\cdots+b_{n};\qquad n=1,2,\ldots. $$

For any pair define $ c_i = \min\{a_i, b_i\} $ and $ C_n = c_1 + \cdots + c_n $, $ n = 1, 2, \ldots $.

(1) Does there exist a pair $(a_{i})_{i\geq1}$, $(b_{i})_{i\geq1}$ such that the sequences $(A_{n})_{n\geq1}$ and $(B_{n})_{n\geq1}$ are unbounded while the sequence $(C_{n})_{n\geq1}$ is bounded?

(2) Does the answer to question (1) change by assuming additionally that $b_{i}=1/i$, $i=1,2,\ldots?$

Justify your answer.

Let $n$ be a positive integer and let $x_{1} \leq x_{2} \leq \cdots \leq x_{n}$ be real numbers.

(1) Prove that

$$ \left(\sum_{i,j=1}^{n}\left|x_{i}-x_{j}\right|\right)^{2}\leq\frac{2(n^{2}-1)}{3}\sum_{i,j=1}^{n}(x_{i}-x_{j})^{2}. $$

(2) Show that the equality holds if and only if $x_{1}, \ldots, x_{n}$ is an arithmetic sequence.

Let $\mathbb{R}^{+}$ be the set of all positive real numbers. Find all functions $f\colon \mathbb{R}^{+} \longrightarrow \mathbb{R}^{+}$ that satisfy the following conditions:

(i) $$ f(x y z)+f(x)+f(y)+f(z)=f(\sqrt{x y})f(\sqrt{y z})f(\sqrt{z x}){\text{for all }}x,y,z\in\mathbb{R}^{+} $$

(ii) $ f(x) \lt f(y) $ for all $ 1 \leq x \lt y $.

Let $n$ be a positive integer and let $(x_1, \ldots, x_n)$, $(y_1, \ldots, y_n)$ be two sequences of positive real numbers. Suppose $(z_2, \ldots, z_{2n})$ is a sequence of positive real numbers such that

$$ z_{i+j}^{2}\geq x_{i}y_{j}\qquad\text{for all }1\leq i,j\leq n. $$

Let $ M = \max\{z_2, \ldots, z_{2n}\} $. Prove that

$$ \left(\frac{M+z_{2}+\cdots+z_{2n}}{2n}\right)^{2}\geq\left(\frac{x_{1}+\cdots+x_{n}}{n}\right)\left(\frac{y_{1}+\cdots+y_{n}}{n}\right). $$

Let $A$ be a 101-element subset of the set $S = \{1,2,\ldots,1000000\}$. Prove that there exist numbers $t_{1}, t_{2}, \ldots, t_{100}$ in $S$ such that the sets

$$ A_{j}=\{x+t_{j}\mid x\in A\},\qquad j=1,2,\ldots,100 $$

are pairwise disjoint.

Let $D_{1}, \ldots, D_{n}$ be closed discs in the plane. (A closed disc is the region limited by a circle, taken jointly with this circle.) Suppose that every point in the plane is contained in at most 2003 discs $D_{i}$. Prove that there exists a disc $D_{k}$ which intersects at most $7\cdot2003-1$ other discs $D_{i}$.

Let $n \geq 5$ be a given integer. Determine the greatest integer $k$ for which there exists a polygon with $n$ vertices (convex or not, with non-selfintersecting boundary) having $k$ internal right angles.

Let $x_{1}, \ldots, x_{n}$ and $y_{1}, \ldots, y_{n}$ be real numbers. Let $A = (a_{ij})_{1 \leq i,j \leq n}$ be the matrix with entries

$$ a_{ij}=\begin{cases}1,&\text{if } x_{i}+y_{j}\geq0;\\0,&\text{if } x_{i}+y_{j} \lt 0.\end{cases} $$

Suppose that $B$ is an $n \times n$ matrix with entries 0, 1 such that the sum of the elements in each row and each column of $B$ is equal to the corresponding sum for the matrix $A$. Prove that $A = B$.

Every point with integer coordinates in the plane is the centre of a disc with radius 1/1000.

(1) Prove that there exists an equilateral triangle whose vertices lie in different discs.

(2) Prove that every equilateral triangle with vertices in different discs has side-length greater than 96.

Let $f(k)$ be the number of integers $n$ that satisfy the following conditions:

(i) $ 0 \leq n \lt 10^k $, so n has exactly k digits (in decimal notation), with leading zeroes allowed;

(ii) the digits of n can be permuted in such a way that they yield an integer divisible by 11.

Prove that $ f(2m) = 10f(2m - 1) $ for every positive integer m.

Let $ABCD$ be a cyclic quadrilateral. Let $P, Q, R$ be the feet of the perpendiculars from $D$ to the lines $BC, CA, AB$, respectively. Show that $PQ = QR$ if and only if the bisectors of $\angle ABC$ and $\angle ADC$ are concurrent with $AC$.

Three distinct points $A$, $B$, $C$ are fixed on a line in this order. Let $\Gamma$ be a circle passing through $A$ and $C$ whose centre does not lie on the line $AC$. Denote by $P$ the intersection of the tangents to $\Gamma$ at $A$ and $C$. Suppose $\Gamma$ meets the segment $PB$ at $Q$. Prove that the intersection of the bisector of $\angle AQC$ and the line $AC$ does not depend on the choice of $\Gamma$.

Let $ABC$ be a triangle and let $P$ be a point in its interior. Denote by $D$, $E$, $F$ the feet of the perpendiculars from $P$ to the lines $BC$, $CA$, $AB$, respectively. Suppose that

$$ AP^{2}+PD^{2}=BP^{2}+PE^{2}=CP^{2}+PF^{2}. $$

Denote by $ I_{A} $, $ I_{B} $, $ I_{C} $ the excentres of the triangle ABC. Prove that P is the circumcentre of the triangle $ I_{A}I_{B}I_{C} $.

Let $\Gamma_{1}$, $\Gamma_{2}$, $\Gamma_{3}$, $\Gamma_{4}$ be distinct circles such that $\Gamma_{1}$, $\Gamma_{3}$ are externally tangent at $P$, and $\Gamma_{2}$, $\Gamma_{4}$ are externally tangent at the same point $P$. Suppose that $\Gamma_{1}$ and $\Gamma_{2}$; $\Gamma_{2}$ and $\Gamma_{3}$; $\Gamma_{3}$ and $\Gamma_{4}$; $\Gamma_{4}$ and $\Gamma_{1}$ meet at $A$, $B$, $C$, $D$, respectively, and that all these points are different from $P$.

Prove that

$$ \frac{AB\cdot BC}{AD\cdot DC}=\frac{PB^{2}}{PD^{2}}. $$

Let $ABC$ be an isosceles triangle with $AC = BC$, whose incentre is $I$. Let $P$ be a point on the circumcircle of the triangle $AIB$ lying inside the triangle $ABC$. The lines through $P$ parallel to $CA$ and $CB$ meet $AB$ at $D$ and $E$, respectively. The line through $P$ parallel to $AB$ meets $CA$ and $CB$ at $F$ and $G$, respectively. Prove that the lines $DF$ and $EG$ intersect on the circumcircle of the triangle $ABC$.

Each pair of opposite sides of a convex hexagon has the following property:

the distance between their midpoints is equal to $\sqrt{3}/2$ times the sum of their lengths.

Prove that all the angles of the hexagon are equal.

Let $ABC$ be a triangle with semiperimeter $s$ and inradius $r$. The semicircles with diameters $BC$, $CA$, $AB$ are drawn on the outside of the triangle $ABC$. The circle tangent to all three semicircles has radius $t$. Prove that

$$ \frac{s}{2} \lt t\leq\frac{s}{2}+\left(1-\frac{\sqrt{3}}{2}\right)r. $$

Let m be a fixed integer greater than 1. The sequence $ x_{0}, x_{1}, x_{2}, \ldots $ is defined as follows:

$$ x_{i}=\begin{cases}2^{i},&\text{if }0\leq i\leq m-1;\\\sum_{j=1}^{m}x_{i-j},&\text{if } i\geq m.\end{cases} $$

Find the greatest k for which the sequence contains k consecutive terms divisible by m.