International Mathematical Olympiad 1997

In the plane the points with integer coordinates are the vertices of unit squares. The squares are colored alternately black and white (as on a chessboard).

For any pair of positive integers $m$ and $n$, consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths $m$ and $n$, lie along edges of the squares.

Let $S_1$ be the total area of the black part of the triangle and $S_2$ be the total area of the white part. Let

$$f(m,n) = |S_1 - S_2|.$$

(a) Calculate $f(m,n)$ for all positive integers $m$ and $n$ which are either both even or both odd.

(b) Prove that $f(m,n) \leq \frac{1}{2}\max\{m,n\}$ for all $m$ and $n$.

(c) Show that there is no constant $C$ such that $f(m,n) < C$ for all $m$ and $n$.

The angle at $A$ is the smallest angle of triangle $ABC$. The points $B$ and $C$ divide the circumcircle of the triangle into two arcs. Let $U$ be an interior point of the arc between $B$ and $C$ which does not contain $A$. The perpendicular bisectors of $AB$ and $AC$ meet the line $AU$ at $V$ and $W$, respectively. The lines $BV$ and $CW$ meet at $T$. Show that

$$AU = TB + TC.$$

Let $x_1, x_2, \ldots, x_n$ be real numbers satisfying the conditions

$$|x_1 + x_2 + \cdots + x_n| = 1$$

and

$$|x_i| \leq \frac{n+1}{2} \qquad i = 1, 2, \ldots, n.$$

Show that there exists a permutation $y_1, y_2, \ldots, y_n$ of $x_1, x_2, \ldots, x_n$ such that

$$|y_1 + 2y_2 + \cdots + ny_n| \leq \frac{n+1}{2}.$$

An $n \times n$ matrix whose entries come from the set $S = \{1, 2, \ldots, 2n - 1\}$ is called a silver matrix if, for each $i = 1, 2, \ldots, n$, the $i$th row and the $i$th column together contain all elements of $S$. Show that

(a) there is no silver matrix for $n = 1997$;

(b) silver matrices exist for infinitely many values of $n$.

Find all pairs $(a, b)$ of integers $a, b \geq 1$ that satisfy the equation

$$a^{b^2} = b^a.$$

For each positive integer $n$, let $f(n)$ denote the number of ways of representing $n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $f(4) = 4$, because the number 4 can be represented in the following four ways:

$$4; 2 + 2; 2 + 1 + 1; 1 + 1 + 1 + 1.$$

Prove that, for any integer $n \geq 3$,

$$2^{n^2/4} < f(2^n) < 2^{n^2/2}.$$