% © Evan Chen
% Downloaded from https://web.evanchen.cc/

\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\href{http://web.evanchen.cc}{\ttfamily web.evanchen.cc},
    updated \today}
\title{IMO 1997 Solution Notes}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 1997 IMO.
The ideas of the solution are a mix of my own work,
the solutions provided by the competition organizers,
and solutions found by the community.
However, all the writing is maintained by me.

These notes will tend to be a bit more advanced and terse than the ``official''
solutions from the organizers.
In particular, if a theorem or technique is not known to beginners
but is still considered ``standard'', then I often prefer to
use this theory anyways, rather than try to work around or conceal it.
For example, in geometry problems I typically use directed angles
without further comment, rather than awkwardly work around configuration issues.
Similarly, sentences like ``let $\mathbb{R}$ denote the set of real numbers''
are typically omitted entirely.

Corrections and comments are welcome!
\end{abstract}

\tableofcontents
\newpage

\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
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 |$.


\begin{enumerate}[(a)]
  \ii Calculate $f(m,n)$ for all positive integers $m$ and $n$
  which are either both even or both odd.
  \ii Prove that $f(m,n) \leq \frac 12 \max \{m,n\}$ for all $m$ and $n$.
  \ii Show that there is no constant $C$
  such that $f(m,n) < C$ for all $ m$ and $ n$.
\end{enumerate}

\item %% Problem 2
Let $ABC$ be a triangle with $\angle A < \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$.

\item %% Problem 3
Let $x_1$, $x_2$, \dots, $x_n$ be real numbers satisfying the conditions:
\begin{align*}
  |x_1 + x_2 + \dots + x_n| &= 1 \\
  |x_i| &\le \frac{n+1}{2} \qquad \text{for } i= 1,2, \dots, n
\end{align*}
Show that there exists a permutation $y_1$, $y_2$, \dots, $y_n$
of $x_1$, $x_2$, \dots, $x_n$ such that
\[ | y_1 + 2 y_2 + \dotsb + n y_n | \leq \frac {n + 1}{2}. \]

\item %% Problem 4
An $n \times n$ matrix whose entries come
from the set $S = \{1, 2, \dots , 2n - 1\}$
is called a \emph{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:
\begin{enumerate}[(a)]
\ii there is no silver matrix for $n = 1997$;
\ii silver matrices exist for infinitely many values of $n$.
\end{enumerate}

\item %% Problem 5
Find all pairs $(a,b)$ of positive integers satisfying
\[ a^{b^2} = b^a. \]

\item %% Problem 6
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}} < f(2^n) < 2^{\frac{n^2}2}$.

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{IMO 1997/1}
\textsl{Available online at \url{https://aops.com/community/p356696}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
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 |$.


\begin{enumerate}[(a)]
  \ii Calculate $f(m,n)$ for all positive integers $m$ and $n$
  which are either both even or both odd.
  \ii Prove that $f(m,n) \leq \frac 12 \max \{m,n\}$ for all $m$ and $n$.
  \ii Show that there is no constant $C$
  such that $f(m,n) < C$ for all $ m$ and $ n$.
\end{enumerate}
\end{mdframed}
In general, we say the \emph{discrepancy} of a region in the plane
equals its black area minus its white area.
We allow negative discrepancies,
so discrepancy is additive and $f(m,n)$ equals the absolute value
of the discrepancy of a right triangle with legs $m$ and $n$.

For (a), the answers are $0$ and $1/2$ respectively.
To see this, consider the figure shown below.
\begin{center}
\begin{asy}
  size(8cm);
  pair A = (0,5);
  pair B = (9,0);
  pair M = midpoint(A--B);
  for (int i=0; i<=5; ++i) {
    draw( (0,i)--(9,i), grey );
  }
  for (int j=0; j<=9; ++j) {
    draw( (j,0)--(j,5), grey );
  }
  dot("$M$", M, dir(50));
  dot("$A$", A, dir(90));
  dot("$B$", B, dir(0));
  dot("$C$", (0,0), dir(180));
  filldraw(A--B--(0,0)--cycle, opacity(0.1)+yellow, black+1.5);
  pair P = (0,2.5);
  pair Q = (9,2.5);
  dot("$P$", P, dir(180));
  dot("$Q$", Q, dir(0));
  draw(P--Q--B, blue+1.5);
\end{asy}
\end{center}
Notice that triangles $APM$ and $BQM$ are congruent,
and when $m \equiv n \pmod 2$, their colorings actually coincide.
Consequently, the discrepancy of the triangle
is exactly equal to the discrepancy of $CPQB$, which is an $m \times n/2$
rectangle and hence equal to $0$ or $1/2$ according to parity.

For (b), note that a triangle with legs $m$ and $n$, with $m$ even and $n$ odd,
can be dissected into one right triangle with legs $m$ and $n-1$
plus a thin triangle of area $1/2$ which has height $m$ and base $1$.
The former region has discrepancy $0$ by (a),
and the latter region obviously has discrepancy at most its area of $m/2$,
hence $f(m,n) \le m/2$ as needed.
(An alternative slower approach, which requires a few cases,
is to prove that two adjacent columns have at most discrepancy $1/2$.)

For (c), we prove:
\begin{claim*}
  For each $k \ge 1$, we have
  \[ f(2k, 2k+1)  = \frac{2k-1}{6}. \]
\end{claim*}
\begin{proof}
An illustration for $k=2$ is shown below,
where we use $(0,0)$, $(0,2k)$, $(2k+1,0)$ as the three vertices.
\begin{center}
\begin{asy}
  size(8cm);
  fill( (0,4)--(5,0)--(5,4)--cycle, palered );
  draw(box( (0,0), (5,4) ), black);
  fill( (0,3)--(1,3)--(1,3.2)--(0,4)--cycle, grey);
  fill( (1,2)--(2,2)--(2,2.4)--(1.25,3)--(1,3)--cycle, grey);
  fill( (2,1)--(3,1)--(3,1.6)--(2.50,2)--(2,2)--cycle, grey);
  fill( (3,0)--(4,0)--(4,0.8)--(3.75,1)--(3,1)--cycle, grey);
  fill(shift(1,0)*unitsquare, grey);
  fill(shift(0,1)*unitsquare, grey);
  for (int i=1; i<4; ++i) {
    draw( (0,i)--(5,i), grey );
  }
  for (int i=1; i<5; ++i) {
    draw( (i,0)--(i,4), grey );
  }
  draw( (0,4)--(5,0)--(0,0)--cycle, blue+2 );
\end{asy}
\end{center}
WLOG, the upper-left square is black, as above.
The $2k$ small white triangles just below the diagonal have area sum
\[ \frac12 \cdot \frac{1}{2k+1} \cdot \frac{1}{2k}
  \left[ 1^2 + 2^2 + \dots + (2k)^2 \right] = \frac{4k+1}{12} \]
The area of the $2k$ black polygons sums just below the diagonal to
\[ \sum_{i=1}^{2k} \left( 1
    - \frac12 \cdot \frac{1}{2k+1} \cdot \frac{1}{2k} \cdot i^2 \right)
  = 2k - \frac{4k+1}{12} = \frac{20k-1}{12}. \]
Finally, in the remaining $1+2+\dots+2k$ squares,
there are $k$ more white squares than black squares.
So, it follows
\[ f(2k, 2k+1)
    = \left\lvert -k + \frac{20k-1}{12} - \frac{4k+1}{12} \right\rvert
    = \frac{2k-1}{6}. \]
\end{proof}
\pagebreak

\subsection{IMO 1997/2}
\textsl{Available online at \url{https://aops.com/community/p356701}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a triangle with $\angle A < \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$.
\end{mdframed}
Let $\ol{BTV}$ meet the circle again at $U_1$,
so that $AU_1 UB$ is an isosceles trapezoid.
Define $U_2$ similarly.

\begin{center}
\begin{asy}
pair A = dir(110);
pair B = dir(230);
pair C = dir(310);
pair U = dir(250);
pair U_1 = A*B/U;
pair U_2 = A*C/U;
pair T = extension(B, U_1, C, U_2);
filldraw(unitcircle, opacity(0.1)+lightcyan, blue);
filldraw(A--B--C--cycle, opacity(0.1)+lightred, red);
draw(A--U, deepgreen);
draw(C--U_2, deepgreen);
draw(B--U_1, deepgreen);
draw(B--U_2, red);
draw(U_1--U--U_2, red);

dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$U$", U, dir(U));
dot("$U_1$", U_1, dir(U_1));
dot("$U_2$", U_2, dir(U_2));
dot("$T$", T, dir(T));

/* TSQ Source:

A = dir 110
B = dir 230
C = dir 310
U = dir 250
U_1 = A*B/U
U_2 = A*C/U
T = extension B U_1 C U_2
unitcircle 0.1 lightcyan / blue
A--B--C--cycle 0.1 lightred / red
A--U deepgreen
C--U_2 deepgreen
B--U_1 deepgreen

*/
\end{asy}
\end{center}
Now from the isosceles trapezoids we get
\[ AU = BU_1 = BT + TU_1 = BT + TC \]
as desired.
\pagebreak

\subsection{IMO 1997/3}
\textsl{Available online at \url{https://aops.com/community/p356706}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $x_1$, $x_2$, \dots, $x_n$ be real numbers satisfying the conditions:
\begin{align*}
  |x_1 + x_2 + \dots + x_n| &= 1 \\
  |x_i| &\le \frac{n+1}{2} \qquad \text{for } i= 1,2, \dots, n
\end{align*}
Show that there exists a permutation $y_1$, $y_2$, \dots, $y_n$
of $x_1$, $x_2$, \dots, $x_n$ such that
\[ | y_1 + 2 y_2 + \dotsb + n y_n | \leq \frac {n + 1}{2}. \]
\end{mdframed}
WLOG $\sum x_i = 1$ (by negating $x_i$) and $x_1 \le x_2 \le \dots \le x_n$.
Notice that
\begin{itemize}
\ii The largest possible value of the sum in question is
\[ A = x_1 + 2x_2 + 3x_3 + \dots + nx_n. \]
while the smallest value is
\[ B = nx_1 + (n-1)x_2 + \dots + x_n. \]
\ii Meanwhile, the \emph{average} value across all permutations is
\[ 1 \cdot \frac{n+1}{2} + 2 \cdot \frac{n+1}{2} + \dots
  + n \cdot \frac{n+1}{2} = \frac{n+1}{2}. \]
\end{itemize}

Now imagine we transform the sum $A$ to the sum $B$,
one step at a time, by swapping adjacent elements.
Every time we do a swap of two neighboring $u < v$, the sum decreases by
\[ (iu + (i+1)v) - (iv + (i+1)u) = v-u < n+1. \]

We want to prove we land in the interval
\[ I = \left[ -\frac{n+1}{2}, \frac{n+1}{2} \right] \]
at some point during this transformation.
But since $B \le \frac{n+1}{2} \le A$ (since $\frac{n+1}{2}$ was the average)
and our step sizes were at most the length of the interval $I$,
this is clear.
\pagebreak

\section{Solutions to Day 2}
\subsection{IMO 1997/4}
\textsl{Available online at \url{https://aops.com/community/p611}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
An $n \times n$ matrix whose entries come
from the set $S = \{1, 2, \dots , 2n - 1\}$
is called a \emph{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:
\begin{enumerate}[(a)]
\ii there is no silver matrix for $n = 1997$;
\ii silver matrices exist for infinitely many values of $n$.
\end{enumerate}
\end{mdframed}
For (a), define a \emph{cross} to be the union
of the $i$th row and $i$th column.
Every cell of the matrix not on the diagonal is
contained in exactly two crosses,
while each cell on the diagonal is contained in one cross.

On the other hand, if a silver matrix existed for $n=1997$,
then each element of $S$ is in all $1997$ crosses,
so it must appear at least once on the diagonal since $1997$ is odd.
However, $|S| = 3993$ while there are only $1997$ diagonal cells.
This is a contradiction.

For (b), we construct a silver matrix $M_e$ for $n = 2^e$ for each $e \ge 1$.
We write the first three explicitly for concreteness:
\begin{align*}
  M_1 &= \begin{bmatrix}
    1 & 2 \\ 3 & 1
  \end{bmatrix} \\
  M_2 &= \begin{bmatrix}
    {\color{red}1} & {\color{red}2} & 4 & 5 \\
    {\color{red}3} & {\color{red}1} & 6 & 7 \\
    7 & 5 & {\color{red}1} & {\color{red}2} \\
    6 & 4 & {\color{red}3} & {\color{red}1}
  \end{bmatrix} \\
  M_3 &= \begin{bmatrix}
    {\color{red}1} & {\color{red}2} & {\color{red}4} & {\color{red}5} & 8 & 9 & 11 & 12\\
    {\color{red}3} & {\color{red}1} & {\color{red}6} & {\color{red}7} & 10 & 15 & 13 & 14 \\
    {\color{red}7} & {\color{red}5} & {\color{red}1} & {\color{red}2} & 14 & 12 & 8 & 9 \\
    {\color{red}6} & {\color{red}4} & {\color{red}3} & {\color{red}1} & 13 & 11 & 10 & 15 \\
    15 & 9 & 11 & 12 & {\color{red}1} & {\color{red}2} & {\color{red}4}
    & {\color{red}5} \\
    10 & 8 & 13 & 14 & {\color{red}3} & {\color{red}1} & {\color{red}6}
    & {\color{red}7} \\
    14 & 12 & 15 & 9 & {\color{red}7} & {\color{red}5} & {\color{red}1}
    & {\color{red}2} \\
    13 & 11 & 10 & 8 & {\color{red}6} & {\color{red}4} & {\color{red}3}
    & {\color{red}1} \\
  \end{bmatrix}
\end{align*}
The construction is described recursively as follows.
Let
\[
  M_e' = \left[
  \begin{array}{c|c}
    {\color{red}M_{e-1}} & M_{e-1} + (2^e-1) \\ \hline
    M_{e-1} + (2^e-1) & {\color{red}M_{e-1}} \\
  \end{array}
  \right].
\]
Then to get from $M_e'$ to $M_e$,
replace half of the $2^e$'s with $2^{e+1}-1$:
in the northeast quadrant, the even-indexed ones,
and in the southwest quadrant, the odd-indexed ones.

\begin{remark*}
  In fact, it turns out silver matrices exist for all even dimensions.
  A claimed proof is outlined at \url{https://aops.com/community/p7375020}.
\end{remark*}
\pagebreak

\subsection{IMO 1997/5}
\textsl{Available online at \url{https://aops.com/community/p3845}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all pairs $(a,b)$ of positive integers satisfying
\[ a^{b^2} = b^a. \]
\end{mdframed}
The answer is $(1,1)$, $(16,2)$ and $(27,3)$.

We assume $a,b > 1$ for convenience.
Let $T$ denote the set of non perfect powers other than $1$.
\begin{claim*}
Every integer greater than $1$
is uniquely of the form $t^n$ for some $t \in T$, $n \in \NN$.
\end{claim*}
\begin{proof}
  Clear.
\end{proof}

Let $a = s^m$, $b = t^n$.
\[ s^{m \cdot (t^n)^2} = t^{n \cdot s^m}. \]
Hence $s = t$ and we have
\[ m \cdot t^{2n} = n \cdot t^m
  \implies t^{2n-m} = \frac nm. \]
Let $n = t^e m$ and $2 \cdot t^e m - m = e$, or
\[ e + m = 2t^e \cdot m. \]
We resolve this equation by casework
\begin{itemize}
  \ii If $e > 0$, then $2t^e \cdot m > 2e \cdot m > e+m$.
  \ii If $e=0$ we have $m=n$ and $m = 2m$, contradiction.
  \ii If $e = -1$ we apparently have
  \[ \frac{2}{t} \cdot m = m-1 \implies
    m = \frac{t}{t-2} \]
  so $(t,m) = (3,3)$ or $(t,m) = (4,2)$.
  \ii If $e = -2$ we apparently have
  \[ \frac{2}{t^2} \cdot m = m - 2
    \implies m = \frac{2}{1 - 2/t^2} = \frac{2t^2}{t^2-2}. \]
  This gives $(t,m) = (2,2)$.
  \ii If $e \le -3$ then let $k = -e \ge 3$, so the equation is
  \[ m-k = \frac{2m}{t^k}
  \iff m = \frac{k \cdot t^k}{t^k-2}
    = k + \frac{2k}{t^k-2}. \]
  However, for $k \ge 3$ and $t \ge 2$,
  we always have $2k \le t^k - 2$,
  with equality only when $(t,k) = (2,3)$;
  this means $m=4$, which is not a new solution.
\end{itemize}
\pagebreak

\subsection{IMO 1997/6}
\textsl{Available online at \url{https://aops.com/community/p356713}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
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}} < f(2^n) < 2^{\frac{n^2}2}$.
\end{mdframed}
It's clear that $f$ is non-decreasing.
By sorting by the number of $1$'s we used,
we have the equation
\[ f(N) =
  f\left( \left\lfloor \frac N2 \right\rfloor \right)
  +  f\left( \left\lfloor \frac N2 \right\rfloor -1 \right)
  +  f\left( \left\lfloor \frac N2 \right\rfloor -2 \right)
  + \dots
  + f(1) + f(0). \quad (\bigstar)
\]

\paragraph{Upper bound.}
We now prove the upper bound by induction.
Indeed, the base case is trivial and for the inductive step
we simply use $(\bigstar)$:
\[ f(2^n) = f(2^{n-1}) + f(2^{n-1}-1) + \dots
  < 2^{n-1} f(2^{n-1})
  < 2^{n-1} \cdot 2^{\frac{(n-1)^2}{2}}
  = 2^{\frac{n^2}{2} - \half}.
\]

\paragraph{Lower bound.}
First, we contend that $f$ is convex.
We'll first prove this in the even case
to save ourselves some annoyance:
\begin{claim*}
  [$f$ is basically convex]
  If $2 \mid a+b$ then
  we have $f(2a) + f(2b) \ge 2 f\left( a+b \right)$.
\end{claim*}
\begin{proof}
  Since $f(2k+1) = f(2k)$, we will only prove the first equation.
  Assume WLOG $a \ge b$ and use
  $(\bigstar)$ on all three $f$ expressions here;
  after subtracting repeated terms, the inequality then rewrites as
  \[ \sum_{(a+b)/2 \le x \le a} f(x)
    \ge \sum_{b \le x \le (a+b)/2} f(x). \]
  This is true since there are an equal number of terms on each side
  and $f$ is nondecreasing.
\end{proof}
\begin{claim*}
  For each $1 \le k < 2^{n-1}$, we have
  \[ f(2^{n-1} - k) + f(k+1) \ge 2f(2^{n-2}) \]
\end{claim*}
\begin{proof}
  Use the fact that $f(2t+1)=f(2t)$ for all $t$
  and then apply convexity as above.
\end{proof}
Now we can carry out the induction:
\[ f(2^n) = f(2^{n-1}) + f(2^{n-1}-1) + \dots
  > 2^{n-1} f(2^{n-2}) + f(0)
  > 2^{n-1} 2^{\frac{(n-2)^2}{4}} = 2^{\frac{n^2}{4}}.
\]
\pagebreak


\end{document}
