% © 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.
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
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<j} x_i x_j}{2}  \right)^2
  = \frac 18 \left( \sum_{1 \le i < n} x_i \right)^4
\end{align*}
as desired.
\pagebreak

\subsection{IMO 1999/3}
\textsl{Available online at \url{https://aops.com/community/p131873}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
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.
\end{mdframed}
For every marked cell, consider the marked cell adjacent
to it; in this way we have a \emph{domino} of two cells.
For each domino, its \emph{aura} consists of all the cells
which are adjacent to a cell of the domino.
There are up to eight squares in each aura,
but some auras could be cut off by the boundary of the board,
which means that there could be as few as five squares.

We will prove that $\half n (n+2)$
is the minimum number of auras
needed to cover the board
(the auras need not be disjoint).
\begin{itemize}
  \ii A construction is shown on the left below,
  showing that $\half n (n+2)$.
  \ii Color the board as shown to the right into ``rings''.
  Every aura takes covers exactly (!) four blue cells.
  Since there are $2n(n+2)$ blue cells, this implies the lower bound.
\end{itemize}

\begin{center}
\begin{asy}
size(11cm);

path aura = (1,0)--(2,0)--(2,1)--(3,1)--(3,3)--(2,3)--(2,4)--(1,4)--(1,3)--(0,3)--(0,1)--(1,1)--cycle;
picture aura_up(pen fill) {
  picture pic = new picture;
  fill(pic, aura, fill);
  draw(pic, (1,1)--(2,1), lightgrey );
  draw(pic, (1,3)--(2,3), lightgrey );
  draw(pic, (0,2)--(3,2), lightgrey );
  draw(pic, (1,1)--(1,3), lightgrey );
  draw(pic, (2,1)--(2,3), lightgrey );
  draw(pic, aura, blue+1.25);
  return pic;
}

picture aura_right(pen fill) {
  return shift(0,3) * rotate(-90) * aura_up(fill);
}

add(shift(-1,-1)*aura_up(palegreen));
add(shift(-1,3)*aura_up(palegreen));
add(shift(-1,7)*aura_up(palegreen));
add(shift(1,1)*aura_up(palegreen));
add(shift(1,5)*aura_up(palegreen));
add(shift(3,3)*aura_up(palegreen));
add(shift(6,3)*aura_up(palegreen));
add(shift(8,1)*aura_up(palegreen));
add(shift(8,5)*aura_up(palegreen));
add(shift(10,-1)*aura_up(palegreen));
add(shift(10,3)*aura_up(palegreen));
add(shift(10,7)*aura_up(palegreen));

add(shift(4,6)*aura_right(palered));
add(shift(2,8)*aura_right(palered));
add(shift(6,8)*aura_right(palered));
/*
add(shift(0,10)*aura_right(palered));
add(shift(4,10)*aura_right(palered));
add(shift(8,10)*aura_right(palered));
*/
add(shift(4,1)*aura_right(palered));
add(shift(2,-1)*aura_right(palered));
add(shift(6,-1)*aura_right(palered));
add(shift(0,-3)*aura_right(palered));
add(shift(4,-3)*aura_right(palered));
add(shift(8,-3)*aura_right(palered));

draw(shift(0,-2)*scale(12)*unitsquare, black+2);

path cell = shift(16,-2)*unitsquare;
for (int i = 0; i <= 11; ++i) {
for (int j = 0; j <= 11; ++j) {
  if (max(abs(i-5.5), abs(j-5.5)) == 5.5)
    filldraw(shift(i,j)*cell, paleblue, grey);
  else if (max(abs(i-5.5), abs(j-5.5)) == 3.5)
    filldraw(shift(i,j)*cell, paleblue, grey);
  else if (max(abs(i-5.5), abs(j-5.5)) == 1.5)
    filldraw(shift(i,j)*cell, paleblue, grey);
  else draw(shift(i,j)*cell, grey);
}
}
\end{asy}
\end{center}

Note that this proves that a partition into disjoint auras
actually always has exactly $\half n (n+2)$ auras,
thus also implying EGMO 2019/2.
\pagebreak

\section{Solutions to Day 2}
\subsection{IMO 1999/4}
\textsl{Available online at \url{https://aops.com/community/p131811}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
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$.
\end{mdframed}
If $p = 2$ then $x \in \{1,2\}$,
and if $p = 3$ then $x \in \{1,3\}$, since this is IMO 1990/3.
Also, $x = 1$ gives a solution for any prime $p$.
We show that there are no other solutions.

Assume $x > 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}
