IMO 2007 — Complete Shortlist

Given a sequence $a_{1}, a_{2}, \ldots, a_{n}$ of real numbers. For each $i(1 \leq i \leq n)$ define

$$
d_{i}=\max \left\{a_{j}: 1 \leq j \leq i\right\}-\min \left\{a_{j}: i \leq j \leq n\right\}
$$

and let

$$
d=\max \left\{d_{i}: 1 \leq i \leq n\right\}
$$

(a) Prove that for arbitrary real numbers $x_{1} \leq x_{2} \leq \ldots \leq x_{n}$,

$$
\max \left\{\left|x_{i}-a_{i}\right|: 1 \leq i \leq n\right\} \geq \frac{d}{2}
$$

(b) Show that there exists a sequence $x_{1} \leq x_{2} \leq \ldots \leq x_{n}$ of real numbers such that we have equality in (1).

Consider those functions $f: \mathbb{N} \rightarrow \mathbb{N}$ which satisfy the condition

$$
f(m+n) \geq f(m)+f(f(n))-1
$$

for all $m, n \in \mathbb{N}$. Find all possible values of $f(2007)$.

($\mathbb{N}$ denotes the set of all positive integers.)

Let $n$ be a positive integer, and let $x$ and $y$ be positive real numbers such that $x^{n}+y^{n}=1$. Prove that

$$
\left(\sum_{k=1}^{n} \frac{1+x^{2 k}}{1+x^{4 k}}\right)\left(\sum_{k=1}^{n} \frac{1+y^{2 k}}{1+y^{4 k}}\right)\lt \frac{1}{(1-x)(1-y)}
$$

Find all functions $f: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$such that

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

for all $x, y \in \mathbb{R}^{+}$. (Symbol $\mathbb{R}^{+}$denotes the set of all positive real numbers.)

Let $c\gt 2$, and let $a(1), a(2), \ldots$ be a sequence of nonnegative real numbers such that

$$
a(m+n) \leq 2 a(m)+2 a(n) \text { for all } m, n \geq 1 \text {, }
$$

and

$$
a\left(2^{k}\right) \leq \frac{1}{(k+1)^{c}} \quad \text { for all } k \geq 0
$$

Prove that the sequence $a(n)$ is bounded.

Let $a_{1}, a_{2}, \ldots, a_{100}$ be nonnegative real numbers such that $a_{1}^{2}+a_{2}^{2}+\ldots+a_{100}^{2}=1$. Prove that

$$
a_{1}^{2} a_{2}+a_{2}^{2} a_{3}+\ldots+a_{100}^{2} a_{1}\lt \frac{12}{25}
$$

Let $n\gt 1$ be an integer. In the space, consider the set

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

Find the smallest number of planes that jointly contain all $(n+1)^{3}-1$ points of $S$ but none of them passes through the origin.

Let $n\gt 1$ be an integer. Find all sequences $a_{1}, a_{2}, \ldots, a_{n^{2}+n}$ satisfying the following conditions:

(a) $a_{i} \in\{0,1\}$ for all $1 \leq i \leq n^{2}+n$;

(b) $a_{i+1}+a_{i+2}+\ldots+a_{i+n}\lt a_{i+n+1}+a_{i+n+2}+\ldots+a_{i+2 n}$ for all $0 \leq i \leq n^{2}-n$.

A unit square is dissected into $n\gt 1$ rectangles such that their sides are parallel to the sides of the square. Any line, parallel to a side of the square and intersecting its interior, also intersects the interior of some rectangle. Prove that in this dissection, there exists a rectangle having no point on the boundary of the square.

Find all positive integers $n$, for which the numbers in the set $S=\{1,2, \ldots, n\}$ can be colored red and blue, with the following condition being satisfied: the set $S \times S \times S$ contains exactly 2007 ordered triples $(x, y, z)$ such that (i) $x, y, z$ are of the same color and (ii) $x+y+z$ is divisible by $n$.

Let $A_{0}=\left(a_{1}, \ldots, a_{n}\right)$ be a finite sequence of real numbers. For each $k \geq 0$, from the sequence $A_{k}=\left(x_{1}, \ldots, x_{n}\right)$ we construct a new sequence $A_{k+1}$ in the following way.

1. We choose a partition $\{1, \ldots, n\}=I \cup J$, where $I$ and $J$ are two disjoint sets, such that the expression

$$
\left|\sum_{i \in I} x_{i}-\sum_{j \in J} x_{j}\right|
$$

attains the smallest possible value. (We allow the sets $I$ or $J$ to be empty; in this case the corresponding sum is 0 .) If there are several such partitions, one is chosen arbitrarily.

2. We set $A_{k+1}=\left(y_{1}, \ldots, y_{n}\right)$, where $y_{i}=x_{i}+1$ if $i \in I$, and $y_{i}=x_{i}-1$ if $i \in J$.

Prove that for some $k$, the sequence $A_{k}$ contains an element $x$ such that $|x| \geq n / 2$.

In the Cartesian coordinate plane define the strip $S_{n}=\{(x, y) \mid n \leq x\lt n+1\}$ for every integer $n$. Assume that each strip $S_{n}$ is colored either red or blue, and let $a$ and $b$ be two distinct positive integers. Prove that there exists a rectangle with side lengths $a$ and $b$ such that its vertices have the same color.

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. The number of members in a clique is called its size.

It is known that the largest size of cliques is even. Prove that the competitors can be arranged in two rooms such that the largest size of cliques in one room is the same as the largest size of cliques in the other room.

Let $\alpha\lt \frac{3-\sqrt{5}}{2}$ be a positive real number. Prove that there exist positive integers $n$ and $p\gt \alpha \cdot 2^{n}$ for which one can select $2 p$ pairwise distinct subsets $S_{1}, \ldots, S_{p}, T_{1}, \ldots, T_{p}$ of the set $\{1,2, \ldots, n\}$ such that $S_{i} \cap T_{j} \neq \varnothing$ for all $1 \leq i, j \leq p$.

Given a convex $n$-gon $P$ in the plane. For every three vertices of $P$, consider the triangle determined by them. Call such a triangle good if all its sides are of unit length.

Prove that there are not more than $\frac{2}{3} n$ good triangles.

In triangle $A B C$, the angle bisector at vertex $C$ intersects the circumcircle and the perpendicular bisectors of sides $B C$ and $C A$ at points $R, P$, and $Q$, respectively. The midpoints of $B C$ and $C A$ are $S$ and $T$, respectively. Prove that triangles $R Q T$ and $R P S$ have the same area.

Given an isosceles triangle $A B C$ with $A B=A C$. The midpoint of side $B C$ is denoted by $M$. Let $X$ be a variable point on the shorter arc $M A$ of the circumcircle of triangle $A B M$. Let $T$ be the point in the angle domain $B M A$, for which $\angle T M X=90^{\circ}$ and $T X=B X$. Prove that $\angle M T B-\angle C T M$ does not depend on $X$.

The diagonals of a trapezoid $A B C D$ intersect at point $P$. Point $Q$ lies between the parallel lines $B C$ and $A D$ such that $\angle A Q D=\angle C Q B$, and line $C D$ separates points $P$ and $Q$. Prove that $\angle B Q P=\angle D A Q$.

Consider five points $A, B, C, D, E$ such that $A B C D$ is a parallelogram and $B C E D$ is a cyclic quadrilateral. Let $\ell$ be a line passing through $A$, and let $\ell$ intersect segment $D C$ and line $B C$ at points $F$ and $G$, respectively. Suppose that $E F=E G=E C$. Prove that $\ell$ is the bisector of angle $D A B$.

Let $A B C$ be a fixed triangle, and let $A_{1}, B_{1}, C_{1}$ be the midpoints of sides $B C, C A, A B$, respectively. Let $P$ be a variable point on the circumcircle. Let lines $P A_{1}, P B_{1}, P C_{1}$ meet the circumcircle again at $A^{\prime}, B^{\prime}, C^{\prime}$ respectively. Assume that the points $A, B, C, A^{\prime}, B^{\prime}, C^{\prime}$ are distinct, and lines $A A^{\prime}, B B^{\prime}, C C^{\prime}$ form a triangle. Prove that the area of this triangle does not depend on $P$.