International Mathematical Olympiad 1993

Let $f(x) = x^n + 5x^{n-1} + 3$, where $n > 1$ is an integer. Prove that $f(x)$ cannot be expressed as the product of two nonconstant polynomials with integer coefficients.

Let $D$ be a point inside acute triangle $ABC$ such that $\angle ADB = \angle ACB + \pi/2$ and $AC \cdot BD = AD \cdot BC$.

(a) Calculate the ratio $(AB \cdot CD)/(AC \cdot BD)$.

(b) Prove that the tangents at $C$ to the circumcircles of $\triangle ACD$ and $\triangle BCD$ are perpendicular.

On an infinite chessboard, a game is played as follows. At the start, $n^2$ pieces are arranged on the chessboard in an $n$ by $n$ block of adjoining squares, one piece in each square. A move in the game is a jump in a horizontal or vertical direction over an adjacent occupied square to an unoccupied square immediately beyond. The piece which has been jumped over is removed.

Find those values of $n$ for which the game can end with only one piece remaining on the board.

For three points $P, Q, R$ in the plane, we define $m(PQR)$ as the minimum length of the three altitudes of $\triangle PQR$. (If the points are collinear, we set $m(PQR) = 0$.)

Prove that for points $A, B, C, X$ in the plane, $$m(ABC) \leq m(ABX) + m(AXC) + m(XBC).$$

Does there exist a function $f: \mathbf{N} \to \mathbf{N}$ such that $f(1) = 2$, $f(f(n)) = f(n) + n$ for all $n \in \mathbf{N}$, and $f(n) < f(n + 1)$ for all $n \in \mathbf{N}$?

There are $n$ lamps $L_0, \ldots, L_{n-1}$ in a circle ($n > 1$), where we denote $L_{n+k} = L_k$. (A lamp at all times is either on or off.) Perform steps $s_0, s_1, \ldots$ as follows: at step $s_i$, if $L_{i-1}$ is lit, switch $L_i$ from on to off or vice versa, otherwise do nothing. Initially all lamps are on. Show that:

(a) There is a positive integer $M(n)$ such that after $M(n)$ steps all the lamps are on again;

(b) If $n = 2^k$, we can take $M(n) = n^2 - 1$;

(c) If $n = 2^k + 1$, we can take $M(n) = n^2 - n + 1$.