% © 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 1999 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 1999 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
A set $S$ of points from the space will be called
completely symmetric if it has at least three elements
and fulfills the condition that for every two distinct points
$A$ and $B$ from $S$,
the perpendicular bisector plane of the segment $AB$
is a plane of symmetry for $S$.
Prove that if a completely symmetric set is finite,
then it consists of the vertices of either a regular polygon,
or a regular tetrahedron or a regular octahedron.
\item %% Problem 2
Find the least constant $C$ such that
for any integer $n > 1$ the inequality
\[\sum_{1 \le i < j \le n} x_i x_j (x_i^2 + x_j^2)
\le C \left( \sum_{1 \le i \le n} x_i \right)^4\]
holds for all real numbers $x_1$, \dots, $x_n \ge 0$.
Determine the cases of equality.
\item %% Problem 3
Let $n$ be an even positive integer.
Find the minimal number of cells on the $n \times n$ board
that must be marked so that any cell
(marked or not marked) has a marked neighboring cell.
\item %% Problem 4
Find all pairs of positive integers $(x,p)$
such that $p$ is a prime and $x^{p-1}$ is a divisor of $ (p-1)^{x}+1$.
\item %% Problem 5
Two circles $\Omega_{1}$ and $\Omega_{2}$ touch internally the circle
$\Omega$ in $M$ and $N$ and the center of $\Omega_{2}$ is on $\Omega_{1}$.
The common chord of the circles $\Omega_{1}$ and $\Omega_{2}$
intersects $\Omega$ in $A$ and $B$
Lines $MA$ and $MB$ intersects $\Omega_{1}$ in $C$ and $D$.
Prove that $\Omega_{2}$ is tangent to $CD$.
\item %% Problem 6
Find all the functions $f \colon \RR \to \RR$ such that
\[f(x-f(y))=f(f(y))+xf(y)+f(x)-1\]
for all $x,y \in \RR$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{IMO 1999/1}
\textsl{Available online at \url{https://aops.com/community/p131833}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A set $S$ of points from the space will be called
completely symmetric if it has at least three elements
and fulfills the condition that for every two distinct points
$A$ and $B$ from $S$,
the perpendicular bisector plane of the segment $AB$
is a plane of symmetry for $S$.
Prove that if a completely symmetric set is finite,
then it consists of the vertices of either a regular polygon,
or a regular tetrahedron or a regular octahedron.
\end{mdframed}
Let $G$ be the centroid of $S$.
\begin{claim*}
All points of $S$ lie on a sphere $\Gamma$ centered at $G$.
\end{claim*}
\begin{proof}
Each perpendicular bisector plane passes through $G$.
So if $A,B \in S$ it follows $GA = GB$.
\end{proof}
\begin{claim*}
Consider any plane passing through three or more points of $S$.
The points of $S$ in the plane form a regular polygon.
\end{claim*}
\begin{proof}
The cross section is a circle because we are intersecting
a plane with sphere $\Gamma$.
Now if $A$, $B$, $C$ are three adjacent points on this circle,
by taking the perpendicular bisector we have $AB=BC$.
\end{proof}
If the points of $S$ all lie in a plane, we are done.
Otherwise, the points of $S$ determine a polyhedron
$\Pi$ inscribed in $\Gamma$.
All of the faces of $\Pi$ are evidently regular polygons,
of the same side length $s$.
\begin{claim*}
Every face of $\Pi$ is an equilateral triangle.
\end{claim*}
\begin{proof}
Suppose on the contrary some face $A_1 A_2 \dots A_n$
has $n > 3$.
Let $B$ be any vertex adjacent to $A_1$ in $\Pi$
other than $A_2$ or $A_n$.
Consider the plane determined by $\triangle A_1 A_3 B$.
This is supposed to be a regular polygon,
but arc $A_1 A_3$ is longer than arc $A_1 B$,
and by construction there are no points inside these arcs.
This is a contradiction.
\end{proof}
Hence, $\Pi$ has faces all congruent equilateral triangles.
This implies it is a regular polyhedron --- either
a regular tetrahedron, regular octahedron,
or regular icosahedron.
We can check the regular icosahedron fails by
taking two antipodal points as our counterexample.
This finishes the problem.
\pagebreak
\subsection{IMO 1999/2}
\textsl{Available online at \url{https://aops.com/community/p131846}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find the least constant $C$ such that
for any integer $n > 1$ the inequality
\[\sum_{1 \le i < j \le n} x_i x_j (x_i^2 + x_j^2)
\le C \left( \sum_{1 \le i \le n} x_i \right)^4\]
holds for all real numbers $x_1$, \dots, $x_n \ge 0$.
Determine the cases of equality.
\end{mdframed}
Answer: $C = \frac 18$, with equality when two $x_i$ are equal
and the remaining $x_i$ are equal to zero.
We present two proofs of the bound.
\paragraph{First solution by smoothing}
Fix $\sum x_i = 1$.
The sum on the left-hand side can be interpreted as
$\sum_{i=1}^n x_i^3 \sum_{j \neq i} x_j =
\sum_{i=1}^n x_i^3(1-x_i)$,
so we may rewrite the inequality as:
Then it becomes \[ \sum_i (x_i^3 - x_i^4) \le C. \]
\begin{claim*}
[Smoothing]
Let $f(x) = x^3 - x^4$.
If $u + v \le \frac 34$, then $f(u) + f(v) \le f(0) + f(u+v)$.
\end{claim*}
\begin{proof}
Note that
\begin{align*}
(u^3-u^4)+(v^3-v^4) &\le (u+v)^3-(u+v)^4 \\
\iff uv(4u^2+4v^2+6uv) &\le 3uv(u+v)
\end{align*}
If $u+v\le \frac 34$ this is obvious as
$4u^2+4v^2+6uv \le 4(u+v)^2$.
\end{proof}
Observe that if three nonnegative reals have pairwise sums
exceeding $\frac34$ then they have sum at least $\frac 98$.
Hence we can smooth until $n-2$ of the terms are zero.
Hence it follows
\[ C = \max_{a+b=1} (a^3+b^3-a^4-b^4) \]
which is routine computation giving $C = \frac18$.
\paragraph{Second solution by AM-GM (Nairit Sarkar)}
Write
\begin{align*}
\text{LHS}
&\le \left( \sum_{1 \le k \le n} x_k^2 \right)
\left( \sum_{1 \le i < j \le n} x_i x_j \right)
= \half \left( \sum_{1 \le k \le n} x_k^2 \right)
\left( \sum_{1 \le i < j \le n} 2 x_i x_j \right) \\
&\le \half \left( \frac{\sum_k x_k^2 + 2 \sum_{i 1$ and let $q$ be smallest prime divisor of $x$.
We have $q > 2$ since $(p-1)^x+1$ is odd.
Then
\[ (p-1)^x \equiv -1 \pmod q \implies (p-1)^{2x} \equiv 1 \pmod q \]
so the order of $p-1 \bmod q$ is even and divides $\gcd(q-1,2x) \le 2$.
This means that
\[ p-1 \equiv -1 \pmod q \implies p = q. \]
In other words $p \mid x$ and we get $x^{p-1} \mid (p-1)^{x}+1$.
By exponent lifting lemma, we now have
\[ 0 < (p-1) \nu_{p}(x) \le 1 + \nu_p(x). \]
This forces $p=3$,
which we already addressed.
\pagebreak
\subsection{IMO 1999/5}
\textsl{Available online at \url{https://aops.com/community/p131838}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Two circles $\Omega_{1}$ and $\Omega_{2}$ touch internally the circle
$\Omega$ in $M$ and $N$ and the center of $\Omega_{2}$ is on $\Omega_{1}$.
The common chord of the circles $\Omega_{1}$ and $\Omega_{2}$
intersects $\Omega$ in $A$ and $B$
Lines $MA$ and $MB$ intersects $\Omega_{1}$ in $C$ and $D$.
Prove that $\Omega_{2}$ is tangent to $CD$.
\end{mdframed}
Let $P$ and $Q$ be the centers of $\Omega_1$ and $\Omega_2$.
Let line $MQ$ meet $\Omega_1$ again at $W$,
the homothetic image of $Q$ under $\Omega_1 \to \Omega$.
Meanwhile, let $T$ be the intersection of segment $PQ$
with $\Omega_2$, and let $L$ be its homothetic image on $\Omega$.
Since $\ol{PTQ} \perp \ol{AB}$, it follows $\ol{LW}$
is a diameter of $\Omega$.
Let $O$ be its center.
\begin{center}
\begin{asy}
size(10cm);
pen xfqqff = rgb(0.49803,0.,1.); pen qqffff = rgb(0.,1.,1.); pen cqcqcq = rgb(0.75294,0.75294,0.75294);
pair O = (0.,0.), M = (-0.54799,0.83648), P = (-0.16957,0.25884), Q = (-0.16861,-0.43170), A = (-0.97449,-0.22439), B = (0.97512,-0.22166), C = (-0.84251,0.10388), D = (0.50379,0.10577), T = (-0.16936,0.10483), L = (-0.00139,0.99999);
draw(circle(O, 1.), linewidth(0.6));
draw(circle(P, 0.69055), linewidth(0.6) + xfqqff);
draw(circle(Q, 0.53653), linewidth(0.6) + xfqqff);
draw(O--M, linewidth(0.6) + red);
draw(M--A, linewidth(0.6) + qqffff);
draw(M--B, linewidth(0.6) + qqffff);
draw(O--(-0.36380,-0.93147), linewidth(0.6) + red);
draw(P--Q, linewidth(0.6));
draw(M--(0.00139,-0.99999), linewidth(0.6) + green);
draw((0.00139,-0.99999)--L, linewidth(0.6));
draw(L--(-0.36380,-0.93147), linewidth(0.6) + green);
draw(M--(-0.36380,-0.93147), linewidth(0.6));
draw(A--B, linewidth(0.6));
dot("$O$", O, dir((1.868, -2.897)));
dot("$N$", (-0.36380,-0.93147), dir((-5.700, -12.058)));
dot("$M$", M, dir((-8.656, 10.478)));
dot("$P$", P, dir((-2.789, 6.521)));
dot("$Q$", Q, dir((3.600, -6.558)));
dot("$A$", A, dir((-15.478, -5.915)));
dot("$B$", B, dir((4.982, -4.507)));
dot("$C$", C, dir((-8.023, -3.199)));
dot("$D$", D, dir((1.442, 0.454)));
dot("$T$", T, dir((-7.133, 1.989)));
dot("$W$", (0.00139,-0.99999), dir((-2.113, -15.052)));
dot("$L$", L, dir((1.046, 1.812)));
dot("$E$", midpoint(A--B), dir(-45));
\end{asy}
\end{center}
\begin{claim*}
$MNTQ$ is cyclic.
\end{claim*}
\begin{proof}
By Reim: $\dang TQM = \dang LWM = \dang LNM = \dang TNM$.
\end{proof}
Let $E$ be the midpoint of $\ol{AB}$.
\begin{claim*}
$OEMN$ is cyclic.
\end{claim*}
\begin{proof}
By radical axis, the lines $MM$, $NN$, $AEB$ meet at a point $R$.
Then $OEMN$ is on the circle with diameter $\ol{OR}$.
\end{proof}
\begin{claim*}
$MTE$ are collinear.
\end{claim*}
\begin{proof}
$\dang NMT = \dang TQN = \dang LON = \dang NOE = \dang NME$.
\end{proof}
Now consider the homothety mapping $\triangle WAB$
to $\triangle QCD$.
It should map $E$ to a point on line $ME$
which is also on the line through $Q$ perpendicular to $\ol{AB}$;
that is, to point $T$.
Hence $TCD$ are collinear,
and it's immediate that $T$ is the desired tangency point.
\pagebreak
\subsection{IMO 1999/6}
\textsl{Available online at \url{https://aops.com/community/p131856}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all the functions $f \colon \RR \to \RR$ such that
\[f(x-f(y))=f(f(y))+xf(y)+f(x)-1\]
for all $x,y \in \RR$.
\end{mdframed}
The answer is $f(x) = -\half x^2+1$
which obviously works.
For the other direction, first note that
\[ P(f(y),y) \implies 2f(f(y)) + f(y)^2 - 1 = f(0). \]
We introduce the notation $c = \frac{f(0)-1}{2}$,
and $S = \opname{img} f$.
Then the above assertion says
\[ f(s) = -\half s^2 + (c + 1). \]
Thus, the given functional equation can be rewritten as
\[ Q(x,s) : f(x-s)=-\half s^2 + sx + f(x) - c. \]
\begin{claim*}
[Main claim]
We can find a function $g \colon \RR \to \RR$ such that
\[ f(x-z) = zx + f(x) + g(z). \qquad (\spadesuit). \]
\end{claim*}
\begin{proof}
If $z \neq 0$,
the idea is to fix a nonzero value $s_0 \in S$ (it exists)
and then choose $x_0$ such that $- \half s_0^2 + s_0 x_0 - c = z$.
Then, $Q(x_0, s)$ gives an pair $(u,v)$ with $u-v = z$.
But now for any $x$, using $Q(x+v,u)$ and $Q(x,-v)$ gives
\begin{align*}
f(x-z)-f(x) &= f(x-u+v)-f(x)
= f(x+v)-f(x) + u(x+v) - \half u^2 + c \\
&= -vx-\half s^2-c + u(x+v) - \half u^2 + c \\
&= -vx-\half v^2 + u(x+v) - \half u^2 = zx + g(z)
\end{align*}
where $g(z) = -\half(u^2+v^2)$ depends only on $z$.
\end{proof}
Now, let
\[ h(x) \coloneqq \half x^2 + f(x) - (2c+1), \]
so $h(0) = 0$.
\begin{claim*}
The function $h$ is additive.
\end{claim*}
\begin{proof}
We just need to rewrite $(\spadesuit)$.
Letting $x=z$ in $(\spadesuit)$,
we find that actually $g(x)=f(0)-x^2-f(x)$.
Using the definition of $h$ now gives
\[ h(x-z) = h(x) + h(z). \qedhere \]
\end{proof}
To finish, we need to remember that $f$, hence $h$, is known
on the image
\[ S = \left\{ f(x) \mid x \in \RR \right\}
= \left\{ h(x) - \half x^2 + (2c+1) \mid x \in \RR \right\}. \]
Thus, we derive
\[ h\left( h(x)-\half x^2+(2c+1) \right) = -c
\qquad \forall x \in \RR. \qquad(\heartsuit) \]
We can take the following two instances of $\heartsuit$:
\begin{align*}
h\left( h(2x)-2x^2+(2c+1) \right) &= -c \\
h\left( 2h(x)-x^2+2(2c+1) \right) &= -2c.
\end{align*}
Now subtracting these and using $2h(x)=h(2x)$ gives
\[ c = h\left( -x^2 - (2c+1) \right). \]
Together with $h$ additive, this implies readily $h$ is constant.
That means $c=0$ and the problem is solved.
\pagebreak
\end{document}