% © 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 2002 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2002 IMO.
Some of the solutions are my own work,
but many are from the official solutions provided by the organizers
(for which they hold any copyrights),
and others were found by users on the Art of Problem Solving forums.
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
Let $n$ be a positive integer.
Let $T$ be the set of points $(x,y)$ in the plane
where $x$ and $y$ are non-negative integers with $x+y 2n$
and let $0 < r < 1$ be the unique real number
with $r^n+r^2 = 1$, hence $r^m+r = 1$.
But now
\begin{align*}
0 &= r^m + r - 1 < r(r^n)^2 + r - 1 = r\left( (1-r^2)^2+1 \right) - 1 \\
&= -(1-r)\left( r^4+r^3-r^2-r+1 \right).
\end{align*}
As $1-r > 0$ and $r^4+r^3-r^2-r+1 > 0$, this is a contradiction
\end{proof}
Now for the algebraic part.
Obviously $m > n$.
\begin{align*}
a^n+a^2-1 &\mid a^m+a-1 \\
\iff a^n+a^2-1 &\mid (a^m+a-1)(a+1) = a^m(a+1) + (a^2-1) \\
\iff a^n+a^2-1 &\mid a^m(a+1) - a^n \\
\iff a^n+a^2-1 &\mid a^{m-n}(a+1) - 1.
\end{align*}
The right-hand side has degree $m-n+1 \le n+1$,
and the leading coefficients are both $+1$.
So the only possible situations are
\begin{align*}
a^{m-n}(a+1) - 1 &= (a+1)\left( a^n+a^2-1 \right) \\
a^{m-n}(a+1) + 1 &= a^n+a^2-1.
\end{align*}
The former fails by just taking $a=-1$;
the latter implies $(m,n) = (5,3)$.
As our work was reversible, this also implies $(m,n) = (5,3)$ works, done.
\pagebreak
\section{Solutions to Day 2}
\subsection{IMO 2002/4}
\textsl{Available online at \url{https://aops.com/community/p118687}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n \ge 2$ be a positive integer
with divisors $1 = d_1 < d_2 < \dots < d_k = n$.
Prove that $d_1d_2 + d_2d_3 + \dots + d_{k-1} d_k$ is always less than $n^2$,
and determine when it is a divisor of $n^2$.
\end{mdframed}
We always have
\begin{align*}
d_k d_{k-1} + d_{k-1} d_{k-2} + \dots + d_2 d_1
&< n \cdot \frac n2 + \frac n2 \cdot \frac n3 + \dots \\
&= \left( \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots \right) n^2 = n^2.
\end{align*}
This proves the first part.
For the second, we claim that this only happens
when $n$ is prime (in which case we get $d_1 d_2 = n$).
Assume $n$ is not prime (equivalently $k \ge 2$)
and let $p$ be the smallest prime dividing $n$.
Then
\[ d_k d_{k-1} + d_{k-1} d_{k-2} + \dots + d_2 d_1
> d_k d_{k-1} = \frac{n^2}{p} \]
exceeds the largest proper divisor of $n^2$,
but is less than $n^2$, so does not divide $n^2$.
\pagebreak
\subsection{IMO 2002/5}
\textsl{Available online at \url{https://aops.com/community/p118703}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all functions $f \colon \RR \to \RR$ such that
\[ \left(f(x)+f(z)\right)\left(f(y)+f(t)\right)
= f(xy-zt)+f(xt+yz) \]
for all real numbers $x$, $y$, $z$, $t$.
\end{mdframed}
The answer is $f(x) \equiv 0$, $f(x) \equiv 1/2$
and $f(x) \equiv x^2$ which are easily seen to work.
Let's prove they are the only ones;
we show two solutions.
\paragraph{First solution (multiplicativity)}
Let $P(x,y,z,t)$ denote the given statement.
\begin{itemize}
\ii By comparing $P(x,1,0,0)$ and $P(0,0,1,x)$
we get $\boxed{f \text{ even}}$.
\ii By $P(0,y,0,t)$ we get for nonconstant $f$
that $f(0) = 0$.
If $f$ is constant we get the solutions earlier,
so in the sequel assume $\boxed{f(0) = 0}$.
\ii By $P(x,y,0,0)$ we get $\boxed{f(xy) = f(x) f(y)}$.
Note in particular that for any real number $x$ we now have
\[ f(x) = f(|x|) = f\left( \sqrt{|x|} \right)^2 \ge 0 \]
that is, $f \ge 0$.
\end{itemize}
From $P(x,y,y,x)$ we now have
\[ f(x^2 + y^2) = \left( f(x) + f(y) \right)^2
= f(x^2) + 2f(x)f(y) + f(y^2) \ge f(x^2) \]
so $f$ is weakly increasing.
Combined with $f$ multiplicative and nonconstant,
this implies $f(x) = |x|^r$ for some real number $r$.
Finally, $P(1,1,1,1)$ gives $f(2) = 4f(1)$,
so $f(x) \equiv x^2$.
\paragraph{Second solution (ELMO)}
Let $P(x,y,z,t)$ denote the statement.
Assume $f$ is nonconstant,
as before we derive that $f$ is even, $f(0) = 0$,
and $f(x) \ge 0$ for all $x$.
Now comparing $P(x,y,z,t)$ and $P(z,y,x,t)$ we obtain
\[ f(xy-zt) + f(xt+yz) =
\left( f(x)+f(z) \right)
\left( f(y)+f(t) \right)
= f(xy+zt) + f(xt-yz) \]
which in particular implies that
\[ f(a-d) + f(b+c) = f(a+d) + f(b-c)
\qquad \text{ if } ad=bc \text{ and } a,b,c,d > 0. \]
Thus the restriction of $f$ to $(0,\infty)$ satisfies
\textbf{ELMO 2011, problem 4}
which implies that $f(x) = kx^2+\ell$ for constants $k$ and $\ell$.
From here we recover the original.
(Minor note: technically ELMO 2011/4 is $f \colon (0,\infty) \to (0,\infty)$
but we only have $f \ge 0$,
however the proof for the ELMO problem
works as long as $f$ is bounded below;
we could also just apply the ELMO problem to $f+0.01$ instead.)
\pagebreak
\subsection{IMO 2002/6}
\textsl{Available online at \url{https://aops.com/community/p118677}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n \ge 3$ be a positive integer.
Let $C_1$, $C_2$, \dots, $C_n$ be unit circles in the plane,
with centers $O_1$, $O_2$, \dots, $O_n$ respectively.
If no line meets more than two of the circles, prove that
\[ \sum_{1 \le i < j \le n } \frac{1}{O_i O_j}
\le \frac{(n-1)\pi}{4}. \]
\end{mdframed}
For brevity, let $d_{ij}$ be the length of $O_{ij}$
and let $\angle(ijk)$ be shorthand for $\angle O_i O_j O_k$
(or its measure in radians).
First, we eliminate the circles completely
and reduce the problem to angles using the following fact
(which is in part motivated by the mysterious
presence of $\pi$ on right-hand side,
and also brings $d_{ij}\inv$ into the picture).
\begin{lemma*}
For any indices $i$, $j$, $m$ we have the inequalities
\[ \angle (imj) \ge
\max \left( \frac{2}{d_{mi}}, \frac{2}{d_{mj}} \right)
\quad\text{and}\quad
\pi - \angle (imj) \ge
\max \left( \frac{2}{d_{mi}}, \frac{2}{d_{mj}} \right). \]
\end{lemma*}
\begin{proof}
We first prove the former line.
Consider the altitude from $O_i$ to $O_m O_j$.
The altitude must have length at least $2$,
otherwise its perpendicular bisector passes
intersects all of $C_i$ , $C_m$, $C_j$.
Thus
\[ 2 \le d_{mi} \sin \angle(imj) \le \angle(imj) \]
proving the first line.
The second line follows by considering the external
angle formed by lines $O_m O_i$ and $O_m O_j$
instead of the internal one.
\end{proof}
Our idea now is for any index $m$
we will make an estimate on
$\sum_{\substack{1 \le i \le n \\ i \neq b}} \frac{1}{d_{bi}}$
for each index $b$.
If the centers formed a convex polygon,
this would be much simpler,
but because we do not have this assumption some more care is needed.
\begin{claim*}
Suppose $O_a$, $O_b$, $O_c$ are consecutive vertices
of the convex hull.
Then
\[ \frac{n-1}{n-2} \dang(abc) \ge \frac{2}{d_{1b}} + \frac{2}{d_{2b}}
+ \dots + \frac{2}{d_{nb}} \]
where the term $\frac{2}{d_{bb}}$ does not appear (obviously).
\end{claim*}
\begin{proof}
WLOG let's suppose $(a,b,c) = (2,1,n)$ and
that rotating ray $O_2 O_1$ hits $O_3$, $O_4$, \dots, $O_n$
in that order.
We have
\begin{align*}
\frac{2}{d_{12}} &\le \angle(213) \\
\frac{2}{d_{13}} &\le \min \left\{ \angle(213), \angle(314) \right\} \\
\frac{2}{d_{14}} &\le \min \left\{ \angle(314), \angle(415) \right\} \\
&\vdotswithin= \\
\frac{2}{d_{1(n-1)}} &\le
\min \left\{ \angle((n-2)1(n-1)), \angle((n-1)1n) \right\} \\
\frac{2}{d_{1n}} &\le \angle\left( (n-1) 1 n \right).
\end{align*}
Of the $n-1$ distinct angles appearing on the right-hand side,
we let $\kappa$ denote the smallest of them.
We have $\kappa \le \frac{1}{n-2} \angle(21n)$
by pigeonhole principle.
Then we pick the minimums on the right-hand side in
the unique way such that summing gives
\begin{align*}
\sum_{i=2}^n \frac{2}{d_{1i}}
&\ge \left( \angle(213)+\angle(314)+\dots+\angle( (n-1)1n ) \right)
+ \kappa \\
&\ge \angle(21n) + \frac{1}{n-2} \angle(21n) = \frac{n-1}{n-2} \angle(21n)
\end{align*}
as desired.
\end{proof}
Next we show a bound that works for any center,
even if it does not lie on the convex hull $\mathcal H$.
\begin{claim*}
For any index $b$ we have
\[ \frac{n-1}{n-2} \pi \ge \frac{2}{d_{1b}} + \frac{2}{d_{2b}}
+ \dots + \frac{2}{d_{nb}} \]
where the term $\frac{2}{d_{bb}}$ does not appear (obviously).
\end{claim*}
\begin{proof}
This is the same argument as in the previous proof,
with the modification that
because $O_b$ could lie inside the convex hull now,
our rotation argument should use lines instead of rays
(in order for the angle to be $\pi$ rather than $2\pi$).
This is why the first lemma is stated with two cases;
we need it now.
Again WLOG $b=1$.
Consider line $O_{1} O_2$ (rather than just the ray)
and imagine rotating it counterclockwise through $O_2$;
suppose that this line passes through $O_3$, $O_4$, \dots, $O_{n}$
in that order before returning to $O_{2}$ again.
We let $\dang (i1j) \in \{ \angle (i1j), \pi-\angle(i1j) \} \in [0, \pi)$ %chktex 9
be the counterclockwise rotations obtained in this way,
so that
\[ \dang(21n) = \dang(213) + \dang(314) +
+ \dots + \dang((n-1)1n). \]
(This is not ``directed angles'', but related.)
Then we get bounds
\begin{align*}
\frac{2}{d_{12}} &\le \dang(213) \\
\frac{2}{d_{13}} &\le \min \left\{ \dang(213), \dang(314) \right\} \\
&\vdotswithin= \\
\frac{2}{d_{1(n-1)}} &\le
\min \left\{ \dang((n-2)1(n-1)), \dang((n-1)1n) \right\} \\
\frac{2}{d_{1n}} &\le \dang\left\{ (n-1) 1 n \right\}
\end{align*}
as in the last proof, and so as before we get
\[ \sum_{i=1}^n \frac{2}{d_{1i}} \le \frac{n-1}{n-2} \dang(21n) \]
which is certainly less than $\frac{n-1}{n-2} \pi$.
\end{proof}
Now suppose there were $r$ vertices in the convex hull.
If we sum the first claim across all $b$ on the hull,
and the second across all $b$ not on the hull (inside it),
we get
\begin{align*}
\sum_{1 \le i