% © 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 2020 Solution Notes}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2020 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
Consider the convex quadrilateral $ABCD$.
The point $P$ is in the interior of $ABCD$.
The following ratio equalities hold:
\[\angle PAD:\angle PBA:\angle DPA
  = 1:2:3
  = \angle CBP:\angle BAP:\angle BPC.\]
Prove that the following three lines meet in a point:
the internal bisectors of angles $\angle ADP$ and $\angle PCB$
and the perpendicular bisector of segment $AB$.

\item %% Problem 2
The real numbers $a, b, c, d$
are such that $a\geq b\geq c\geq d>0$ and $a+b+c+d=1$.
Prove that
\[ (a+2b+3c+4d) a^a b^b c^c d^d < 1. \]

\item %% Problem 3
There are $4n$ pebbles of weights $1, 2, 3, \dots, 4n$.
Each pebble is coloured in one of $n$ colours
and there are four pebbles of each colour.
Show that we can arrange the pebbles into two piles
the total weights of both piles are the same,
and each pile contains two pebbles of each colour.

\item %% Problem 4
There is an integer $n > 1$.
There are $n^2$ stations on a slope of a mountain, all at different altitudes.
Each of two cable car companies, $A$ and $B$, operates $k$ cable cars;
each cable car provides a transfer from one of the stations
to a higher one (with no intermediate stops).
The $k$ cable cars of $A$ have $k$ different starting points
and $k$ different finishing points, and a cable car which starts higher also finishes higher.
The same conditions hold for $B$.
We say that two stations are linked by a company if one can start from the lower station
and reach the higher one by using one or more cars of that company
(no other movements between stations are allowed).
Determine the smallest positive integer $k$ for which one can guarantee
that there are two stations that are linked by both companies.

\item %% Problem 5
A deck of $n > 1$ cards is given.
A positive integer is written on each card.
The deck has the property that the arithmetic mean of the
numbers on each pair of cards is also the
geometric mean of the numbers on some collection of one or more cards.
For which $n$ does it follow that the numbers on the cards are all equal?

\item %% Problem 6
Consider an integer $n > 1$, and a set $\mathcal S$ of $n$ points
in the plane such that the distance between any two different points
in $\mathcal S$ is at least $1$.
Prove there is a line $\ell$ separating $\mathcal S$
such that the distance from any point of $\mathcal S$ to $\ell$
is at least $\Omega(n^{-1/3})$.

(A line $\ell$ separates a set of points $S$
if some segment joining two points in $\mathcal S$ crosses $\ell$.)

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{IMO 2020/1, proposed by Dominik Burek (POL)}
\textsl{Available online at \url{https://aops.com/community/p17821635}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Consider the convex quadrilateral $ABCD$.
The point $P$ is in the interior of $ABCD$.
The following ratio equalities hold:
\[\angle PAD:\angle PBA:\angle DPA
  = 1:2:3
  = \angle CBP:\angle BAP:\angle BPC.\]
Prove that the following three lines meet in a point:
the internal bisectors of angles $\angle ADP$ and $\angle PCB$
and the perpendicular bisector of segment $AB$.
\end{mdframed}
Let $O$ denote the circumcenter of $\triangle PAB$.
We claim it is the desired concurrency point.
\begin{center}
\begin{asy}
pair O = origin;
pair P = dir(118);
pair A = dir(190);
pair B = dir(350);
pair C = extension(P/dir(64), B, P, B*dir(192));
pair D = extension(P*dir(36), A, P, A/dir(108));

filldraw(unitcircle, opacity(0.1)+lightcyan, blue+dotted);
filldraw(A--B--C--D--cycle, opacity(0.1)+yellow, grey);
filldraw(P--A--B--cycle, opacity(0.1)+lightcyan, blue);
draw(circumcircle(P, O, B), lightred);
draw(circumcircle(P, O, D), lightred);
draw(D--P--C, grey);

draw(D--O--C, dashed+red);

dot("$O$", O, dir(270));
dot("$P$", P, dir(P));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(D));

/* TSQ Source:

O = origin R270
P = dir 118
A = dir 190
B = dir 350
C = extension P/dir(64) B P B*dir(192)
D = extension P*dir(36) A P A/dir(108)

unitcircle 0.1 lightcyan / blue dotted
A--B--C--D--cycle 0.1 yellow / grey
P--A--B--cycle 0.1 lightcyan / blue
circumcircle P O B lightred
circumcircle P O D lightred
D--P--C grey

D--O--C dashed red

*/
\end{asy}
\end{center}
Indeed, $O$ obviously lies on the perpendicular bisector of $AB$.
Now
\begin{align*}
  \dang BCP &= \dang CBP + \dang BPC \\
  &= 2\dang BAP = \dang BOP
\end{align*}
it follows $BOPC$ are cyclic.
And since $OP = OB$, it follows that $O$ is on
the bisector of $\angle PCB$, as needed.

\begin{remark*}
  The angle equality is only used insomuch $\angle BAP$
  is the average of $\angle CBP$ and $\angle BPC$,
  i.e.\ only $\frac{1+3}{2} = 2$ matters.
\end{remark*}
\pagebreak

\subsection{IMO 2020/2, proposed by Belarus}
\textsl{Available online at \url{https://aops.com/community/p17821569}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
The real numbers $a, b, c, d$
are such that $a\geq b\geq c\geq d>0$ and $a+b+c+d=1$.
Prove that
\[ (a+2b+3c+4d) a^a b^b c^c d^d < 1. \]
\end{mdframed}
By weighted AM-GM we have
\[ a^a b^b c^c d^d \le \sum_{\text{cyc}} \frac{a}{a+b+c+d} \cdot a
  = a^2+b^2+c^2+d^2. \]
Consequently, it is enough to prove that
\[ (a^2+b^2+c^2+d^2)(a+2b+3c+4d) \le 1 = (a+b+c+d)^3. \]
Expand both sides to get
\[
  \begin{array}{cccc}
    +a^3 &+ b^2a &+ c^2a & +d^2a \\
    +2a^2b &+ 2b^3 &+ 2bc^2  & +2d^2b \\
    +3a^2c & + 3b^2c & + 3c^3 & + 3d^2c \\
    +4a^2d &+ 4b^2d & + 4c^2d & + 4d^3
  \end{array}
  <
  \begin{array}{cccc}
    +a^3 &+ 3b^2a &+ 3c^2a & +3d^2a \\
    +3a^2b &+ b^3 &+ 3bc^2  & +3d^2b \\
    +3a^2c &+ 3b^2c &+ c^3 &+ 3d^2c \\
    +3a^2d &+ 3b^2d &+ 3c^2d &+ d^3 \\
    +6abc &+ 6bcd &+ 6cda &+ 6dab
  \end{array}
\]
In other words, we need to prove that
\[
  \begin{array}{cccc}
    & && \\
    &+ b^3 & & \\
    & & +2c^3 & \\
    +a^2d &+ b^2d & + c^2d & + 3d^3 \\
  \end{array}
  <
  \begin{array}{cccc}
    &+ 2b^2a &+ 2c^2a & +2d^2a \\
    +a^2b & &+ bc^2  & +d^2b \\
    &&& \\
    &&& \\
    +6abc &+ 6bcd &+ 6cda &+ 6dab
  \end{array}
\]

This follows since
\begin{align*}
  2b^2a &\ge b^3 + b^2d \\
  2c^2a &\ge 2c^3 \\
  2d^2a &\ge 2d^3  \\
  a^2b &\ge a^2d \\
  bc^2 &\ge c^2d  \\
  d^2b &\ge d^3
\end{align*}
and $6(abc+bcd+cda+dab) > 0$.

\begin{remark*}
  Fedor Petrov provides the following motivational comments
  for why the existence of this solution is not surprising:
  \begin{quote}
    Better to think about mathematics.
    You have to bound from above a product $(a+2b+3c+4d)(a^2+b^2+c^2+d^2)$,
    the coefficients $1,2,3,4$ are increasing and so play on your side,
    so plausibly $(a+b+c+d)^3$ should majorize this term-wise,
    you check it and this appears to be true.
  \end{quote}
\end{remark*}
\pagebreak

\subsection{IMO 2020/3, proposed by Milan Haiman (HUN), Carl Schildkraut (USA)}
\textsl{Available online at \url{https://aops.com/community/p17821656}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
There are $4n$ pebbles of weights $1, 2, 3, \dots, 4n$.
Each pebble is coloured in one of $n$ colours
and there are four pebbles of each colour.
Show that we can arrange the pebbles into two piles
the total weights of both piles are the same,
and each pile contains two pebbles of each colour.
\end{mdframed}
The first key idea is the deep fact that
\[ 1+4n = 2+(4n-1) = 3+(4n-2) = \dots. \]
So, place all four pebbles of the same colour in a box (hence $n$ boxes).
For each  $k=1,2,\dots,2n$
we tape a piece of string between pebble $k$ and $4n+1-k$.
To solve the problem, it suffices to paint each string
either blue or green such that each box has two blue strings
and two green strings
(where a string between two pebbles in the same box counts double).
\begin{center}
\begin{asy}
size(12cm);
// picture box;

pair A = 0.5*dir(135);
pair C = 0.5*dir(225);
pair D = 0.5*dir(315);
pair B = 0.5*dir(45);

path boxoutline = (dir(135)+dir(200)*0.4)--dir(135)--dir(225)
    --dir(315)--dir(45)--(dir(45)+dir(-20)*0.4);

transform[] t = new transform[5];
for (int i=0; i<5; ++i) {
  t[i] = shift(3.4*dir(90+72*i));
  draw(t[i]*boxoutline, brown+1.5);
  label("Box " + array("ABCDE")[i], t[i]*dir(-90), brown);
}

void rope(pair X, pair Y, string s1, string s2, pen p) {
  draw(X--Y, p);
  dot(s1, X, dir(-90), p + fontsize(9pt));
  dot(s2, Y, dir(-90), p + fontsize(9pt));
}
rope(t[0]*A, t[0]*B, "1", "20", blue);
rope(t[0]*C, t[1]*A, "4", "17", deepgreen);
rope(t[0]*D, t[3]*D, "3", "18", deepgreen);
rope(t[1]*B, t[4]*A, "8", "13", blue);
rope(t[1]*D, t[4]*C, "7", "14", deepgreen);
rope(t[4]*B, t[2]*A, "15", "6", deepgreen);
rope(t[1]*C, t[2]*B, "11", "10", blue);
rope(t[4]*D, t[3]*B, "9", "12", blue);
rope(t[2]*C, t[3]*A, "19", "2", blue);
rope(t[2]*D, t[3]*C, "5", "16", deepgreen);

/*
for (int i=0; i<=3; ++i) {
  dot(box, 0.5*dir(45+90*i));
}
*/
\end{asy}
\end{center}

We can therefore rephrase the problem as follows,
if we view boxes as vertices and strings as edges:
\begin{claim*}
  Given a $4$-regular multigraph on $n$ vertices
  (where self-loops are allowed and have degree $2$),
  one can color the edges blue and green
  such that each vertex has two blue and two green edges.
\end{claim*}
\begin{proof}
  Each connected component of the graph can be decomposed
  into an Eulerian circuit, since $4$ is even.
  A connected component with $k$ vertices has $2k$
  edges in its Eulerian circuit,
  so we may color the edges in this circuit alternating green and blue.
  This may be checked to work.
\end{proof}
\pagebreak

\section{Solutions to Day 2}
\subsection{IMO 2020/4, proposed by Tejaswi Navilarekallu (IND)}
\textsl{Available online at \url{https://aops.com/community/p17821585}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
There is an integer $n > 1$.
There are $n^2$ stations on a slope of a mountain, all at different altitudes.
Each of two cable car companies, $A$ and $B$, operates $k$ cable cars;
each cable car provides a transfer from one of the stations
to a higher one (with no intermediate stops).
The $k$ cable cars of $A$ have $k$ different starting points
and $k$ different finishing points, and a cable car which starts higher also finishes higher.
The same conditions hold for $B$.
We say that two stations are linked by a company if one can start from the lower station
and reach the higher one by using one or more cars of that company
(no other movements between stations are allowed).
Determine the smallest positive integer $k$ for which one can guarantee
that there are two stations that are linked by both companies.
\end{mdframed}
Answer: $k = n^2 - n + 1$.

When $k = n^2-n$,
the construction for $n=4$ is shown below which generalizes readily.
(We draw $A$ in red and $B$ in blue.)
\begin{center}
\begin{asy}
  pair P(int i, int j) { return (i+j/10, j+i/10); }
  dotfactor *= 2;
  for (int i=0; i<4; ++i) {
  for (int j=0; j<4; ++j) {
    dot( P(i,j) );
    if (j!=0) {
      draw(P(i,j-1)--P(i,j), red, EndArrow, Margin(4,4));
    }
    if (i != 0) {
      draw(P(i-1,j)--P(i,j), blue, EndArrow, Margin(4,4));
    }
  }
  }
\end{asy}
\end{center}

To see this is sharp, view $A$ and $B$ as graphs
whose connected components are paths (possibly with $0$ edges;
the direction of these edges is irrelevant).
Now, if $k = n^2-n+1$ it follows that $A$ and $B$
each have exactly $n-1$ connected components.

But in particular some component of $A$ has at least $n+1$ vertices.
This component has two vertices in the same component of $B$, as desired.

\begin{remark*}
  The main foothold for this problem is the hypothesis
  that the number of stations should be $n^2$ rather than, say, $n$.
  This gives a big hint towards finding the construction
  which in turn shows how the bound can be computed.

  On the other hand, the hypothesis that
  ``a cable car which starts higher
  also finishes higher'' appears to be superfluous.
\end{remark*}
\pagebreak

\subsection{IMO 2020/5, proposed by Oleg Ko\v{s}ik (EST)}
\textsl{Available online at \url{https://aops.com/community/p17821528}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A deck of $n > 1$ cards is given.
A positive integer is written on each card.
The deck has the property that the arithmetic mean of the
numbers on each pair of cards is also the
geometric mean of the numbers on some collection of one or more cards.
For which $n$ does it follow that the numbers on the cards are all equal?
\end{mdframed}
The assertion is true for all $n$.

\bigskip

\textbf{Setup (boilerplate).}
Suppose that $a_1$, \dots, $a_n$ satisfy the required properties
but are not all equal.
Let $d = \gcd(a_1, \dots, a_n) > 1$
then replace $a_1$, \dots, $a_n$ by
$\frac{a_1}{d}$, \dots, $\frac{a_n}{d}$.
Hence without loss of generality we may assume
\[ \gcd(a_1, a_2, \dots, a_n) = 1. \]
WLOG we also assume \[ a_1 \ge a_2 \ge \dots \ge a_n. \]

\bigskip

\textbf{Main proof.}
As $a_1 \ge 2$, let $p$ be a prime divisor of $a_1$.
Let $k$ be smallest index such that $p \nmid a_k$ (which must exist).
In particular, note that $a_1 \neq a_k$.

Consider the mean $x = \frac{a_1+a_k}{2}$; by assumption,
it equals some geometric mean, hence
\[ \sqrt[m]{a_{i_1} \dots a_{i_m}} = \frac{a_1 + a_k}{2} > a_k. \]
Since the arithmetic mean is an integer not divisible by $p$,
all the indices $i_1$, $i_2$, \dots, $i_m$
must be at least $k$.
But then the GM is at most $a_k$, contradiction.

\begin{remark*}
  A similar approach could be attempted by using
  the smallest numbers rather than the largest ones,
  but one must then handle the edge case $a_n = 1$
  separately since no prime divides $1$.
\end{remark*}

\begin{remark*}
  Since $\frac{27+9}{2} = 18 = \sqrt[3]{27 \cdot 27 \cdot 8}$,
  it is not true that in general the AM of two largest different cards
  is not the GM of other numbers in the sequence
  (say the cards are $27, 27, 9, 8, \dots$).
\end{remark*}
\pagebreak

\subsection{IMO 2020/6, proposed by Ting-Feng Lin, Hung-Hsun Hans Yu (TWN)}
\textsl{Available online at \url{https://aops.com/community/p17821732}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Consider an integer $n > 1$, and a set $\mathcal S$ of $n$ points
in the plane such that the distance between any two different points
in $\mathcal S$ is at least $1$.
Prove there is a line $\ell$ separating $\mathcal S$
such that the distance from any point of $\mathcal S$ to $\ell$
is at least $\Omega(n^{-1/3})$.

(A line $\ell$ separates a set of points $S$
if some segment joining two points in $\mathcal S$ crosses $\ell$.)
\end{mdframed}
We present the official solution given by the Problem Selection Committee.

Let's suppose that among all projections
of points in $\mathcal S$ onto some line $m$,
the maximum possible distance between two consecutive projections is $\delta$.
We will prove that $\delta \ge \Omega(n^{-1/3})$,
solving the problem.

We make the following the definitions:
\begin{itemize}
  \ii Define $A$ and $B$ as the two points farthest apart in $\mathcal S$.
  This means that all points lie in the intersections
  of the circles centered at $A$ and $B$ with radius $R = AB \ge 1$.
  \ii We pick chord $\ol{XY}$ of $\odot(B)$
  such that $\ol{XY} \perp \ol{AB}$ and the distance
  from $A$ to $\ol{XY}$ is exactly $\half$.
  \ii We denote by $\mathcal T$
  the smaller region bound by $\odot(B)$ and chord $\ol{XY}$.
\end{itemize}
The figure is shown below with $\mathcal T$ drawn in yellow,
and points of $\mathcal S$ drawn in blue.
\begin{center}
\begin{asy}
size(10cm);
pair A = (-2,0);
pair B = (5,0);

pen auxpen = brown+linetype("4 2");
pair X = (0, 24^0.5);
pair Y = (0, -24^0.5);

pair[] S = {
  (-1.3, 2.7),
  (-0.57, -2.61),
  (-0.21, 1.07),
  (0.33,-1.06),
  (0.83, 3.71),
  (1.57, -3.18),
  (2.14, 1.66),
  (2.72, 3.32),
  (3.37, -1.17),
  (3.97, 1.34),
  (4.37, -2.35),
};

fill(Y..A..X--cycle, paleyellow);
for (int i=0; i<S.length; ++i) {
  draw(S[i]--(S[i].x,0), grey);
  dot(S[i], blue);
}
draw(A--B, blue+1.3);
draw(arc(B,abs(B-A), 110, 250), auxpen);
draw(arc(A,abs(B-A), -70, 70), auxpen);
draw(B--X--Y--cycle, auxpen);

dot("$A$", A, dir(180), blue);
dot("$B$", B, dir(0), blue);
dot("$X$", X, dir(90), auxpen);
dot("$Y$", Y, dir(270), auxpen);

draw( (-1.9,-0.1)--(-1.9,-0.2)--(-0.1,-0.2)--(-0.1, -0.1) );
label("$\frac12$", (-1, -0.2), dir(-90));

draw( (2.14,-0.1)--(2.14,-0.2)--(2.72,-0.2)--(2.72,-0.1) );
label("$< \delta$", (2.43, -0.2), dir(-90), fontsize(9pt));

label("$\mathcal T$", (-0.7,3), fontsize(14pt));
\end{asy}
\end{center}

\begin{claim*}
  [Length of $AB$ + Pythagorean theorem]
  We have $XY < 2\sqrt{n\delta}$.
\end{claim*}
\begin{proof}
  First, note that we have $R = AB < (n-1) \cdot \delta$,
  since the $n$ projections of points onto $AB$
  are spaced at most $\delta$ apart.
  The Pythagorean theorem gives
  \[ XY = 2\sqrt{R^2 - \left(R-\half\right)^2}
    = 2\sqrt{R - \frac14} < 2\sqrt{n\delta}. \qedhere \]
\end{proof}
\begin{claim*}
  [$|\mathcal T|$ lower bound + narrowness]
  We have $XY > \frac{\sqrt3}{2} \left( \half \delta\inv - 1 \right)$.
\end{claim*}
\begin{proof}
  Because $\mathcal T$ is so narrow (has width $\half$ only),
  the projections of points in $\mathcal T$ onto line $XY$
  are spaced at least $\frac{\sqrt3}{2}$ apart (more than just $\delta$).
  This means
  \[ XY > \frac{\sqrt3}{2}
    \left( \left\lvert \mathcal T \right\rvert - 1 \right). \]
  But projections of points in $\mathcal T$
  onto the segment of length $\half$ are spaced at most $\delta$ apart,
  so apparently
  \[ \left\lvert \mathcal T \right\rvert > \half \cdot \delta\inv. \]
  This implies the result.
\end{proof}
Combining these two this implies $\delta \ge \Omega(n^{-1/3})$ as needed.

\begin{remark*}
  The constant $1/3$ in the problem is actually optimal
  and cannot be improved;
  the constructions give an example showing $\Theta(n^{-1/3} \log n)$.
\end{remark*}
\pagebreak


\end{document}
