International Mathematical Olympiad 2007

Real numbers $a_1, a_2, \ldots, a_n$ are given. For each $i$ ($1 \leq i \leq n$) define

$$d_i = \max\{a_j : 1 \leq j \leq i\} - \min\{a_j : i \leq j \leq n\}$$

and let

$$d = \max\{d_i : 1 \leq i \leq n\}.$$

(a) Prove that, for any real numbers $x_1 \leq x_2 \leq \cdots \leq x_n$,

$$\max\{|x_i - a_i| : 1 \leq i \leq n\} \geq \frac{d}{2}. \quad (*)$$

(b) Show that there are real numbers $x_1 \leq x_2 \leq \cdots \leq x_n$ such that equality holds in $(*)$.

Consider five points $A, B, C, D$ and $E$ such that $ABCD$ is a parallelogram and $BCED$ is a cyclic quadrilateral. Let $\ell$ be a line passing through $A$. Suppose that $\ell$ intersects the interior of the segment $DC$ at $F$ and intersects line $BC$ at $G$. Suppose also that $EF = EG = EC$. Prove that $\ell$ is the bisector of angle $DAB$.

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged in two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

In triangle $ABC$ the bisector of angle $BCA$ intersects the circumcircle again at $R$, the perpendicular bisector of $BC$ at $P$, and the perpendicular bisector of $AC$ at $Q$. The midpoint of $BC$ is $K$ and the midpoint of $AC$ is $L$. Prove that the triangles $RPK$ and $RQL$ have the same area.

Let $a$ and $b$ be positive integers. Show that if $4ab - 1$ divides $(4a^2 - 1)^2$, then $a = b$.

Let $n$ be a positive integer. Consider

$$S = \{(x, y, z) : x, y, z \in \{0, 1, \ldots, n\}, x + y + z > 0\}$$

as a set of $(n + 1)^3 - 1$ points in three-dimensional space. Determine the smallest possible number of planes, the union of which contains $S$ but does not include $(0,0,0)$.