International Mathematical Olympiad 2003

$S$ is the set $\{1,2,3,\ldots,1000000\}$. Show that for any subset $A$ of $S$ with 101 elements we can find 100 distinct elements $x_i$ of $S$, such that the sets $\{a + x_i | a \in A\}$ are all pairwise disjoint.

Find all pairs $(m,n)$ of positive integers such that $\frac{m^2}{2mn^2 - n^3 + 1}$ is a positive integer.

A convex hexagon has the property that for any pair of opposite sides the distance between their midpoints is $\sqrt{3}/2$ times the sum of their lengths. Show that all the hexagon's angles are equal.

$ABCD$ is cyclic. The feet of the perpendicular from $D$ to the lines $AB, BC, CA$ are $P, Q, R$ respectively. Show that the angle bisectors of $ABC$ and $CDA$ meet on the line $AC$ iff $RP = RQ$.

Given $n > 2$ and reals $x_1 \leq x_2 \leq \cdots \leq x_n$, show that $(\sum_{i,j} |x_i - x_j|)^2 \leq \frac{2}{3}(n^2 - 1)\sum_{i,j}(x_i - x_j)^2$. Show that we have equality iff the sequence is an arithmetic progression.

Show that for each prime $p$, there exists a prime $q$ such that $n^p - p$ is not divisible by $q$ for any positive integer $n$.