International Mathematical Olympiad 1997 — Official contest

In the plane there is an infinite chessboard. For any pair of positive integers $m$ and $n$, consider a right-angled triangle with vertices at lattice points 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 12 \max \{m,n\}$ for all $m$ and $n$.

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

Let $ABC$ be a triangle with $\angle A \lt \min(\angle B, \angle C)$. 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$, …, $x_n$ be real numbers satisfying the conditions: $$
\begin{aligned}|x_1 + x_2 + \dots + x_n| &= 1 \\
|x_i| &\le \frac{n+1}{2} \qquad \text{for } i= 1,2, \dots, n\end{aligned}
$$ Show that there exists a permutation $y_1$, $y_2$, …, $y_n$ of $x_1$, $x_2$, …, $x_n$ such that $$
| y_1 + 2 y_2 + \dotsb + n y_n | \leq \frac {n + 1}{2}.
$$

An $n \times n$ matrix whose entries come from the set $S = \{1, 2, \dots , 2n - 1\}$ is called a *silver* matrix if, for each $i = 1, 2, \dots , 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 positive integers satisfying $$
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$ we have $2^{\frac{n^2}{4}} \lt f(2^n) \lt 2^{\frac{n^2}2}$.