% © 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{EGMO 2020 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2020 EGMO.
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
The positive integers $a_0$, $a_1$, $a_2$, \dots, $a_{3030}$ satisfy
\[ 2a_{n + 2} = a_{n + 1} + 4a_n \text{ for } n = 0, 1, 2, \dots, 3028. \]
Prove that at least one of the numbers
$a_0$, $a_1$, $a_2$, \dots, $a_{3030}$ is divisible by $2^{2020}$.
\item %% Problem 2
Find all lists $(x_1, x_2, \dots, x_{2020})$ of non-negative real numbers
such that the following three conditions are all satisfied:
\begin{itemize}
\ii $x_1 \le x_2 \le \dots \le x_{2020}$;
\ii $x_{2020} \le x_1 + 1$;
\ii there is a permutation $(y_1, y_2, \dots, y_{2020})$
of $(x_1, x_2, \dots, x_{2020})$ such that
\[ \sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 = 8 \sum_{i = 1}^{2020} x_i^3. \]
\end{itemize}
\item %% Problem 3
Let $ABCDEF$ be a convex hexagon such that $\angle A = \angle C = \angle E$ and $\angle B = \angle D = \angle F$
and the (interior) angle bisectors of $\angle A$, $\angle C$, and $\angle E$ are concurrent.
Prove that the (interior) angle bisectors of $\angle B$, $\angle D$, and $\angle F$ must also be concurrent.
\item %% Problem 4
A permutation of the integers $1, 2, \dots, m$ is called \emph{fresh} if there exists
no positive integer $k < m$ such that the first $k$ numbers
in the permutation are $1, 2, \dots, k$ in some order.
Let $f_m$ be the number of fresh permutations of the integers $1, 2, \dots, m$.
Prove that $f_n \ge n \cdot f_{n - 1}$ for all $n \ge 3$.
\item %% Problem 5
Triangle $ABC$ has circumcircle $\Gamma$ and obeys $\angle BCA > 90^{\circ}$.
There is a point $P$ in the interior of the line segment $AB$
such that $PB = PC$ and the length of $PA$ equals the radius of $\Gamma$.
The perpendicular bisector of $\ol{PB}$ intersects $\Gamma$ at the points $D$ and $E$.
Prove $P$ is the incenter of triangle $CDE$.
\item %% Problem 6
Find all integers $m > 1$ for which the sequence $(a_n)_{n\ge1}$
defined recursively by
\[ a_{n+2} = m(a_{n+1} + a_n) - a_{n-1} \]
with initial conditions $a_1 = a_2 = 1$ and $a_3 = 4$
contains only perfect squares.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{EGMO 2020/1, proposed by Dzmitry Badziahin (AUS)}
\textsl{Available online at \url{https://aops.com/community/p14780286}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
The positive integers $a_0$, $a_1$, $a_2$, \dots, $a_{3030}$ satisfy
\[ 2a_{n + 2} = a_{n + 1} + 4a_n \text{ for } n = 0, 1, 2, \dots, 3028. \]
Prove that at least one of the numbers
$a_0$, $a_1$, $a_2$, \dots, $a_{3030}$ is divisible by $2^{2020}$.
\end{mdframed}
The idea is this:
\begin{itemize}
\ii All terms $a_0$, \dots, $a_{3030}$ are integers
(divisible by $2^0=1$);
\ii Hence all terms $a_1$, \dots, $a_{3029}$ are divisible by $2$,
\ii Hence all terms $a_1$, \dots, $a_{3028}$ are divisible by $4$,
\ii Hence all terms $a_2$, \dots, $a_{3027}$ are divisible by $8$,
\ii \dots and so on.
\end{itemize}
The $2021$st item in this list reads as $2^{2020} \mid a_{1010}$.
One can also phrase this with induction.
Replace $1010$ by $N$ in the obvious way and proceed by induction on $N \ge 0$
with the base case $N = 0$ being vacuous.
Notice that for any index $k \neq 0, 3N-1, 3N$ we have
\[ a_k = 2a_{k+1} - 4a_{k-1} = 2(2a_{k+2}-4a_k)-4a_{k-1}
= 4(a_{k+2}-2a_k-a_{k-1}) \]
so it follows that $(a_1, a_2, \dots, a_{3N-2})$
are all divisible by $4$ and satisfy the same relations.
But then $(a_1/4, a_2/4, \dots, a_{3N-2}/4)$ has length $3(N-1)+1$
and so one of them is divisible by $4^{N-1}$;
hence some term of our original sequence is divisible by $4^N$.
\pagebreak
\subsection{EGMO 2020/2, proposed by Patrik Bak (SVK)}
\textsl{Available online at \url{https://aops.com/community/p14780288}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all lists $(x_1, x_2, \dots, x_{2020})$ of non-negative real numbers
such that the following three conditions are all satisfied:
\begin{itemize}
\ii $x_1 \le x_2 \le \dots \le x_{2020}$;
\ii $x_{2020} \le x_1 + 1$;
\ii there is a permutation $(y_1, y_2, \dots, y_{2020})$
of $(x_1, x_2, \dots, x_{2020})$ such that
\[ \sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 = 8 \sum_{i = 1}^{2020} x_i^3. \]
\end{itemize}
\end{mdframed}
The main point of the problem is to prove an inequality.
\begin{claim*}
If $a$ and $b$ are real numbers with $|a-b| \le 1$,
then \[ (a+1)^2(b+1)^2 \geq 4(a^3+b^3). \]
Moreover, equality holds only when $\{a,b\}=\{1,0\}$ or $\{a,b\}=\{2,1\}$.
\end{claim*}
\begin{proof}
Write
\begin{align*}
a^3+b^3 &= (a+b)(a^2-ab+b^2) = (a+b)[(a-b)^2 + ab] \\
&\le (a+b)(1+ab) \\
&\le \left( \frac{(a+b)+(1+ab)}{2} \right)^2 = \frac{(a+1)^2(b+1)^2}{4}. \qedhere
\end{align*}
\end{proof}
From this it follows that $(x_n)_n$
should be either $(1,\dots,1,2,\dots,2)$ or $(0,\dots,0,1,\dots,1)$.
\begin{remark*}
There is a sense in which the problem \emph{must} be an inequality,
because given a \emph{fixed} permutation of the indices
of $y_i$ by $x_i$, one gets an equation which \emph{a priori}
ought to cut out a codimension $1$ surface in $\RR^{2020}$.
So the fact that the answer set appears finite
is an indication that some inequality at play here.
\end{remark*}
\pagebreak
\subsection{EGMO 2020/3, proposed by Anton Trygub (UKR)}
\textsl{Available online at \url{https://aops.com/community/p14780291}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABCDEF$ be a convex hexagon such that $\angle A = \angle C = \angle E$ and $\angle B = \angle D = \angle F$
and the (interior) angle bisectors of $\angle A$, $\angle C$, and $\angle E$ are concurrent.
Prove that the (interior) angle bisectors of $\angle B$, $\angle D$, and $\angle F$ must also be concurrent.
\end{mdframed}
In general, if hexagon $ABCDEF$ has $\angle A = \angle C = \angle E$ and $\angle B = \angle D = \angle F$,
then its sides can be extended to form two
equilateral triangles $PQR$ and $XYZ$, as shown.
\begin{center}
\begin{asy}
size(5cm);
pair P = dir(90);
pair Q = dir(210);
pair R = dir(330);
pair O = (0.1,0.2);
pair z = dir(-40);
pair Y = O+z*(P-O);
pair X = O+z*(R-O);
pair Z = O+z*(Q-O);
filldraw(P--Q--R--cycle, opacity(0.1)+lightblue, blue);
filldraw(X--Y--Z--cycle, opacity(0.1)+lightcyan, deepcyan);
pair A = extension(Q, P, Y, Z);
pair B = extension(P, R, Y, Z);
pair C = extension(P, R, X, Y);
pair D = extension(R, Q, X, Y);
pair E = extension(R, Q, X, Z);
pair F = extension(Q, P, X, Z);
dot("$P$", P, dir(P));
dot("$Q$", Q, dir(Q));
dot("$R$", R, dir(R));
dot("$Y$", Y, dir(Y));
dot("$X$", X, dir(X));
dot("$Z$", Z, dir(Z));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
\end{asy}
\end{center}
The problem is solved upon proving the following claim.
\begin{claim*}
The angle bisectors of $\angle A$, $\angle C$, $\angle E$ are concurrent if and only if
the unique spiral similarity sending $PQR$ to $YZX$ is a rotation;
equivalently, the two triangles are congruent.
\end{claim*}
\begin{center}
\begin{asy}
pair P = dir(90);
pair Q = dir(210);
pair R = dir(330);
pair O = (0.1,0.2);
pair z = dir(-40);
pair Y = O+z*(P-O);
pair X = O+z*(R-O);
pair Z = O+z*(Q-O);
filldraw(P--Q--R--cycle, opacity(0.1)+lightblue, blue);
filldraw(X--Y--Z--cycle, opacity(0.1)+lightcyan, deepcyan);
pair A = extension(Q, P, Y, Z);
pair B = extension(P, R, Y, Z);
pair C = extension(P, R, X, Y);
pair D = extension(R, Q, X, Y);
pair E = extension(R, Q, X, Z);
pair F = extension(Q, P, X, Z);
draw(circumcircle(O, A, C), deepgreen);
draw(circumcircle(O, C, E), deepgreen);
draw(circumcircle(O, E, A), deepgreen);
draw(A--O, red);
draw(C--O, red);
draw(E--O, red);
label("$2\theta$", A, 5*dir(40), orange);
label("$2\theta$", C, 5*dir(280), orange);
label("$2\theta$", E, 5*dir(160), orange);
dot("$P$", P, dir(P));
dot("$Q$", Q, dir(Q));
dot("$R$", R, dir(R));
dot("$O$", O, dir(O));
dot("$Y$", Y, dir(Y));
dot("$X$", X, dir(X));
dot("$Z$", Z, dir(Z));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
/* TSQ Source:
P = dir 90
Q = dir 210
R = dir 330
O = (0.1,0.2)
z := dir -40
Y = O+z*(P-O)
X = O+z*(R-O)
Z = O+z*(Q-O)
P--Q--R--cycle 0.1 lightblue / blue
X--Y--Z--cycle 0.1 lightcyan / deepcyan
A = extension Q P Y Z
B = extension P R Y Z
C = extension P R X Y
D = extension R Q X Y
E = extension R Q X Z
F = extension Q P X Z
circumcircle O A C deepgreen
circumcircle O C E deepgreen
circumcircle O E A deepgreen
A--O red
C--O red
E--O red
!label("$2\theta$", A, 5*dir(40), orange);
!label("$2\theta$", C, 5*dir(280), orange);
!label("$2\theta$", E, 5*dir(160), orange);
*/
\end{asy}
\end{center}
\begin{proof}[Proof of ``if'' direction]
Let $O$ be the center of the rotation.
Then $O$ is equidistant form $\ol{YZ}$ and $\ol{PQ}$ by rotation;
similarly for the other pairs of sides.
So the bisectors meet at $O$.
\end{proof}
\begin{proof}[Proof of ``only if'' direction]
Let $O$ be the concurrency point.
Let $\angle PAB = \angle RCD = \angle QEF = 2\theta$
Since $\angle APC = \angle AYC = 60\dg$ the quadrilateral $PACY$ is cyclic.
But $\angle PAO + \angle PCO = (90\dg+\theta) + (90\dg-\theta) = 180\dg$, so $PAOCY$ is cyclic.
Now $\angle PAO = \angle YCO \implies OP = OY$, and $\angle POY = 2\theta$.
So $O$ is the center of rotation from $\triangle PQR$ to $\triangle YXZ$ with angle $2\theta$.
\end{proof}
\pagebreak
\section{Solutions to Day 2}
\subsection{EGMO 2020/4, proposed by Patrik Bak (SVK)}
\textsl{Available online at \url{https://aops.com/community/p14780296}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A permutation of the integers $1, 2, \dots, m$ is called \emph{fresh} if there exists
no positive integer $k < m$ such that the first $k$ numbers
in the permutation are $1, 2, \dots, k$ in some order.
Let $f_m$ be the number of fresh permutations of the integers $1, 2, \dots, m$.
Prove that $f_n \ge n \cdot f_{n - 1}$ for all $n \ge 3$.
\end{mdframed}
For every fresh permutation on $(1, 2, \dots, n-1)$
we generate $n$ fresh permutations on $(1, 2, \dots, n)$ in the following way:
\begin{itemize}
\ii Insert $n$ in the $k$th position for $k=1, 2, \dots, n-1$;
\ii Replace $n-1$ with $n$ and append $n-1$ to the end.
\end{itemize}
For example, $3142$ would generate $53142$, $35142$, $31542$, $31452$ and $31524$.
All permutations generated this way are distinct.
Indeed, the only thing to note is that the second type of permutation
yields a non-fresh permutation when $n$ is deleted
(because $n-1$ is at the end, and $n \ge 3$).
This implies the result.
\pagebreak
\subsection{EGMO 2020/5, proposed by Agnijo Banerjee (UNK)}
\textsl{Available online at \url{https://aops.com/community/p14780281}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Triangle $ABC$ has circumcircle $\Gamma$ and obeys $\angle BCA > 90^{\circ}$.
There is a point $P$ in the interior of the line segment $AB$
such that $PB = PC$ and the length of $PA$ equals the radius of $\Gamma$.
The perpendicular bisector of $\ol{PB}$ intersects $\Gamma$ at the points $D$ and $E$.
Prove $P$ is the incenter of triangle $CDE$.
\end{mdframed}
Let $O$ be the center of $\Gamma$ and $M$
the arc midpoint of $\ol{DE}$.
\begin{claim*}
Quadrilateral $APMO$ is a rhombus.
\end{claim*}
\begin{proof}
Since $PA = MO$ and both are perpendicular to $\ol{DE}$,
it follows $APMO$ is a parallelogram.
In fact though, because $AO = MO$, we get the rhombus.
\end{proof}
\begin{center}
\begin{asy}
size(6cm);
pair B = dir(0);
pair C = dir(180);
pair D = dir(37);
pair A = D*D;
pair E = dir(60)*A;
pair F = dir(-60)*A;
pair O = origin;
pair J = A+O-D;
filldraw(unitcircle, opacity(0.1)+lightcyan, heavycyan);
filldraw(A--B--C--cycle, opacity(0.1)+lightcyan, heavycyan);
draw(A--D, red);
draw(O--J, red);
filldraw(C--E--F--cycle, opacity(0.1)+green, heavygreen);
filldraw(A--E--O--F--cycle, opacity(0.1)+lightblue, blue);
draw(E--F, blue);
draw(A--O, blue);
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(D));
dot("$A$", A, dir(A));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
dot("$O$", O, dir(-90));
dot("$J$", J, dir(J));
label("IMO 2002/2", dir(-90), dir(-90));
\end{asy}
\qquad
\begin{asy}
size(6cm);
pair C = dir(180);
pair K = dir(37);
pair M = K*K;
pair D = dir(60)*M;
pair E = dir(-60)*M;
pair O = origin;
pair P = M+O-K;
filldraw(unitcircle, opacity(0.1)+lightcyan, heavycyan);
filldraw(C--D--E--cycle, opacity(0.1)+green, heavygreen);
filldraw(M--D--O--E--cycle, opacity(0.1)+lightblue, blue);
draw(D--E, blue);
draw(M--O, blue);
draw(C--P, deepcyan);
draw(P--M, blue+dotted);
pair A = P+O-M;
pair B = -A+2*foot(O, P, A);
draw(A--B--O, orange);
dot("$C$", C, dir(C));
dot("$M$", M, dir(M));
dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$O$", O, dir(-90));
dot("$P$", P, dir(P));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
label("EGMO 2020/5", dir(-90), dir(-90));
/* TSQ Source:
C = dir 180
K := dir 37
M = K*K
D = dir(60)*M
E = dir(-60)*M
O = origin R-90
P = M+O-K
unitcircle 0.1 lightcyan / heavycyan
C--D--E--cycle 0.1 green / heavygreen
M--D--O--E--cycle 0.1 lightblue / blue
D--E blue
M--O blue
C--P deepcyan
P--M blue dotted
A = P+O-M
B = -A+2*foot O P A
A--B--O orange
*/
\end{asy}
\end{center}
Since $PC = PB$, and $PA = PM$,
it follows that $C$, $P$, $M$ are collinear now.
\begin{claim*}
We have $MP = MD = ME$ equal to the radius of $\Gamma$.
\end{claim*}
\begin{proof}
Note $PBMO$ is an isosceles trapezoid.
Since $\ol{DE}$ is the perpendicular bisector of $\ol{PB}$,
it is the perpendicular bisector of $\ol{OM}$ too.
Hence $MDOE$ is a rhombus (with $60\dg$ internal angles), the end.
\end{proof}
Since $MP = MD = ME$ we are done by Fact 5.
\begin{remark*}
The same figure appears in IMO 2002/2,
drawn on the left for contrast.
\end{remark*}
\pagebreak
\subsection{EGMO 2020/6, proposed by Mads Bjerge Christensen (DEN)}
\textsl{Available online at \url{https://aops.com/community/p14780304}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all integers $m > 1$ for which the sequence $(a_n)_{n\ge1}$
defined recursively by
\[ a_{n+2} = m(a_{n+1} + a_n) - a_{n-1} \]
with initial conditions $a_1 = a_2 = 1$ and $a_3 = 4$
contains only perfect squares.
\end{mdframed}
The answer is $m=2$ and $m=10$.
The verification they work is left as an exercise.
Now compute the first several terms:
\begin{align*}
a_1 &= 1 \\
a_2 &= 1 \\
a_3 &= 4 \\
a_4 &= 5m-1 \\
a_5 &= 5m^2+3m-1 \\
a_6 &= 5m^3+8m^2-2m-4.
\end{align*}
We will now prove:
\begin{claim*}
If $a_4 \cdot a_6$ is a square then $m \in \{2,10\}$.
\end{claim*}
\begin{proof}
A computation gives
\begin{align*}
16 a_4 a_6
&= 400 m^4 + 560 m^3 - 288 m^2 - 288 m + 64 \\
&= \left(20m^2+14m-\frac{121}{10} \right)^2
+ \frac{508}{10}m - \frac{8241}{100}.
\end{align*}
Let $A = 200m^2+140m-121 \equiv -1 \pmod{20}$.
Then $42A+441 > 5080m-8241$ for all $m$ and hence
\[ A^2 < \underbrace{A^2+5080m-8241}_{=1600a_3a_5} < (A+21)^2. \]
But the inner term is the square of a multiple of $20$
so it must equal $(A+1)^2$.
Thus, we have
\[ 2(\underbrace{200m^2+140m-121}_{=A})+1 = 5080m-8241 \implies m \in \{2,10\} \]
as desired.
\end{proof}
\begin{remark*}
In general, if $f(x) \in \ZZ[x]$ has even degree
and the leading coefficient is a square,
then $f(x)$ should be a square finitely often
(unless $f$ is itself the square of a polynomial).
The proof proceeds along the same lines,
by bounding $f$ between two squares.
See China TST 2001 for example
which asked students to determine all $x$ for which
\[ f(x) = x^6 + 15x^5 + 85x^4 + 225x^3 + 274x^2 + 120x + 1 \]
was equal to a perfect square.
\end{remark*}
\pagebreak
\end{document}