% © 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 2018 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2018 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
Let $ABC$ be a triangle with $CA=CB$ and $\angle{ACB}=120^{\circ}$,
and let $M$ be the midpoint of $AB$.
Let $P$ be a variable point of the circumcircle of $ABC$,
and let $Q$ be the point on the segment $CP$ such that $QP = 2QC$.
It is given that the line through $P$ and perpendicular to $AB$
intersects the line $MQ$ at a unique point $N$.
Prove that there exists a fixed circle such that $N$
lies on this circle for all possible positions of $P$.
\item %% Problem 2
Consider the set
\[ A = \left\{ 1 + \frac 1k : k = 1, 2, 3, \dots \right\}. \]
For every integer $x \ge 2$, let $f(x)$ denote
the minimum integer such that $x$ can be written as the product
of $f(x)$ elements of $A$ (not necessarily distinct).
Prove that there are infinitely many pairs of integers $x \ge 2$
and $y \ge 2$ for which \[ f(xy) < f(x) + f(y). \]
\item %% Problem 3
The $n$ contestants of EGMO are named $C_1$, $C_2$, \dots, $C_n$.
After the competition,
they queue in front of the restaurant according to the following rules.
\begin{itemize}
\ii The Jury chooses the initial order of the contestants in the queue.
\ii Every minute, the Jury chooses an integer $i$ with $1 \leq i \leq n$.
\begin{itemize}
\ii If contestant $C_i$ has at least $i$ other contestants in front of her,
she pays one euro to the Jury and moves forward in the queue by exactly $i$ positions.
\ii If contestant $C_i$ has fewer than $i$ other contestants in front of her,
the restaurant opens and the process ends.
\end{itemize}
\end{itemize}
For every $n$, prove that this process must terminate
and determine the maximum number of euros
that the Jury can collect by cunningly choosing
the initial order and the sequence of moves.
\item %% Problem 4
Let $n \ge 3$ be an integer.
Several non-overlapping dominoes are placed on an $n \times n$ board.
The \emph{value} of a row or column is the number of dominoes
that cover at least one cell of that row or column.
A domino configuration is called \emph{balanced} if there exists
some $k \ge 1$ such that every row and column has value $k$.
Prove that a balanced configuration exists for every $n \ge 3$
and find the minimum number of dominoes needed
in such a configuration.
\item %% Problem 5
Let $\Gamma $ be the circumcircle of triangle $ABC$.
A circle $\Omega$ is tangent to the line segment $AB$
and is tangent to $\Gamma$ at a point
lying on the same side of the line $AB$ as $C$.
The angle bisector of $\angle BCA$ intersects $\Omega$
at two different points $P$ and $Q$. Prove that $\angle ABP = \angle QBC$.
\item %% Problem 6
Fix a real number $0 < t < \half$.
\begin{enumerate}
\ii [(a)]
Prove that there exists a positive integer $n$
such that for every set $S$ of $n$ positive integers,
the following holds:
there exist distinct $x, y \in S$ and \emph{nonnegative} integer $m \ge 0$
such that $|x-my| \le ty$.
\ii [(b)]
Determine whether there exists an infinite set $S$
of positive integers such that the following holds:
for any distinct $x, y \in S$ and \emph{positive} integer $m > 0$,
we have $|x-my| > ty$.
\end{enumerate}
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{EGMO 2018/1, proposed by Velina Ivanova (BGR)}
\textsl{Available online at \url{https://aops.com/community/p10185390}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a triangle with $CA=CB$ and $\angle{ACB}=120^{\circ}$,
and let $M$ be the midpoint of $AB$.
Let $P$ be a variable point of the circumcircle of $ABC$,
and let $Q$ be the point on the segment $CP$ such that $QP = 2QC$.
It is given that the line through $P$ and perpendicular to $AB$
intersects the line $MQ$ at a unique point $N$.
Prove that there exists a fixed circle such that $N$
lies on this circle for all possible positions of $P$.
\end{mdframed}
Since $\vec N = 3\vec Q - 2\vec M$,
it suffices to show $Q$ moves on a fixed circle.
That fixed circle is the image of $(CAB)$ under a homothety at $C$ with ratio $1/3$,
so we are done.
\begin{center}
\begin{asy}
pair C = dir(90);
pair A = dir(150);
pair B = dir(30);
pair M = midpoint(A--B);
pair P = dir(-40);
pair Q = (2*C+P)/3;
pair N = extension(M, Q, P, P+C);
draw(unitcircle);
draw(A--B--C--cycle, dotted);
draw(C--P--N--M--cycle);
dot("$C$", C, dir(C));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$M$", M, dir(270));
dot("$P$", P, dir(P));
dot("$Q$", Q, dir(225));
dot("$N$", N, dir(N));
/* TSQ Source:
C = dir 90
A = dir 150
B = dir 30
M = midpoint A--B R270
P = dir -40
Q = (2*C+P)/3 R225
N = extension M Q P P+C
unitcircle
A--B--C--cycle dotted
C--P--N--M--cycle
*/
\end{asy}
\end{center}
\begin{remark*}
Note that points $A$ and $B$ are superfluous,
and the choice of constant $2$ or the definition of $M$
is also arbitrary (only the fact that $\ol{CM} \parallel \ol{PN}$ matters).
Moreover, the condition $\angle ACB = 120^{\circ}$ is never used either.
As a result, I did not find this problem very inspiring.
\end{remark*}
\pagebreak
\subsection{EGMO 2018/2, proposed by Mihail Baluna (ROM)}
\textsl{Available online at \url{https://aops.com/community/p10185417}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Consider the set
\[ A = \left\{ 1 + \frac 1k : k = 1, 2, 3, \dots \right\}. \]
For every integer $x \ge 2$, let $f(x)$ denote
the minimum integer such that $x$ can be written as the product
of $f(x)$ elements of $A$ (not necessarily distinct).
Prove that there are infinitely many pairs of integers $x \ge 2$
and $y \ge 2$ for which \[ f(xy) < f(x) + f(y). \]
\end{mdframed}
One of many constructions: let $n = 2^e+1$
for $e \equiv 5 \pmod{10}$
and let $x = 11$, $y = n/11$ be our two integers.
We prove two lemmas:
\begin{claim*}
For any $m \ge 2$ we have
$f(m) \ge \left\lceil \log_2 m \right\rceil$.
\end{claim*}
\begin{proof}
This is obvious.
\end{proof}
It follows that $f(n) = e+1$, since $n = \frac{n}{n-1} \cdot 2^e$.
\begin{claim*}
$f(11) = 5$.
\end{claim*}
\begin{proof}
We have $11 = \frac{33}{32} \cdot \frac 43 \cdot 2^3$.
So it suffices to prove $f(11) > 4$.
Note that a decomposition of $11$ must
contain a fraction at most $\frac{11}{10} = 1.1$.
But $2^3 \cdot 1.1 = 8.8 < 11$, contradiction.
\end{proof}
To finish, note that
\[ f(11) + f(n/11) \ge 5 + \log_2(n/11) = 1 + \log_2(16n/11) > 1 + e = 1 + f(n). \]
\begin{remark*}
Most solutions seem to involve picking $n$ such that
$f(n)$ is easy to compute.
Indeed, it's hard to get nontrivial lower bounds other than the log,
and even harder to actually come up with complicated constructions.
It might be said the key to this problem
is doing as little number theory as possible.
\end{remark*}
\pagebreak
\subsection{EGMO 2018/3, proposed by Hungary}
\textsl{Available online at \url{https://aops.com/community/p10185368}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
The $n$ contestants of EGMO are named $C_1$, $C_2$, \dots, $C_n$.
After the competition,
they queue in front of the restaurant according to the following rules.
\begin{itemize}
\ii The Jury chooses the initial order of the contestants in the queue.
\ii Every minute, the Jury chooses an integer $i$ with $1 \leq i \leq n$.
\begin{itemize}
\ii If contestant $C_i$ has at least $i$ other contestants in front of her,
she pays one euro to the Jury and moves forward in the queue by exactly $i$ positions.
\ii If contestant $C_i$ has fewer than $i$ other contestants in front of her,
the restaurant opens and the process ends.
\end{itemize}
\end{itemize}
For every $n$, prove that this process must terminate
and determine the maximum number of euros
that the Jury can collect by cunningly choosing
the initial order and the sequence of moves.
\end{mdframed}
The maximum money is
$1 + 3 + 7 + \dots + (2^{n-1}-1) = 2^n-n-1$,
which is finite.
Call the 1-euro process a jump,
and let $x_i$ denote the number of times that $C_i$ jumps.
Note that:
\begin{itemize}
\ii Whenever $C_i$ jumps it must jump over some $C_j$ with $j > i$.
\ii Contestant $C_i$ can jump over a $C_j$ with $j > i$ at most $1 + x_j$ times.
\end{itemize}
Now, we have $x_n = 0$ and in general,
\begin{align*}
x_{n-1} &\le 1 + x_n \le 1 \\
x_{n-2} &\le (1 + x_{n-1}) + (1 + x_{n-2}) \le 3 \\
x_{n-3} &\le (1 + x_{n-1}) + (1 + x_{n-2}) + (1 + x_{n-3}) \le 7
\end{align*}
and so on, which gives the bound.
The construction is inductive; here is the example for $n = 3$,
with the food towards the right:
\[
\begin{array}{ccc}
C_1 & C_2 & C_3 \\
C_2 & C_1 & C_3 \\
C_2 & C_3 & C_1 \\
C_3 & C_1 & C_2 \\
C_3 & C_2 & C_1
\end{array}
\]
In general, we can start the contestants in reverse order,
apply inductive hypothesis to $C_1$ through $C_{n-1}$ to flip their order,
then have $C_1$, $C_2$, $\dots$, $C_{n-1}$ jump over $C_n$,
then repeat.
This gives a construction with value $a_1 = 0$
and $a_n = 2a_{n-1} + (n-1)$ which is the same as the bound.
\pagebreak
\section{Solutions to Day 2}
\subsection{EGMO 2018/4, proposed by Merlijn Staps (NLD)}
\textsl{Available online at \url{https://aops.com/community/p10191585}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n \ge 3$ be an integer.
Several non-overlapping dominoes are placed on an $n \times n$ board.
The \emph{value} of a row or column is the number of dominoes
that cover at least one cell of that row or column.
A domino configuration is called \emph{balanced} if there exists
some $k \ge 1$ such that every row and column has value $k$.
Prove that a balanced configuration exists for every $n \ge 3$
and find the minimum number of dominoes needed
in such a configuration.
\end{mdframed}
The answer is $2n/3$ when $n \equiv 0 \pmod 3$, and $2n$ otherwise.
\paragraph{Proof this is best possible.}
To prove these are best possible, assume there are $d$ dominoes.
\begin{claim*}
In any balanced configuration, we always have $k \cdot 2n = 3d$.
\end{claim*}
\begin{proof}
Consider counting the number of ordered pairs
\[ (\text{row or column},
\text{domino touching at least one cell in that row or column}). \]
On the one hand, this is equal to $k \cdot 2n$,
because there are $2n$ choices for the row and column,
and by the balanced hypothesis, there are $k$ dominoes for that row or column.
On the other hand, it must be equal to $3d$,
because for each domino there are either one column and two rows it touches,
or two columns and one row.
Hence the result.
\end{proof}
Written another way, we have
\[ d = 2n \cdot \frac{k}{3}. \]
Since $k \ge 1$, the first few possible values of $d$ are $2n/3$, $4n/3$, $2n$, \dots.
So we get a lower bound by taking the first integer in this sequence.
\paragraph{Constructions.}
When $n \equiv 0 \pmod 3$, one takes block-diagonal
copies of the following $3 \times 3$ square with $k = 1$.
\[
\begin{bmatrix}
A & A & \\
& & B \\
& & B
\end{bmatrix}.
\]
On the other hand, we give below construction for $4 \le n \le 7$
which have $k = 3$ and $2n$ dominoes.
By taking block-diagonal copies of these, we obtain a $k = 3$ construction
using $2n$ dominoes for any value of $n \ge 4$.
\[
\begin{bmatrix}
A & A & B & C \\
D & D & B & C \\
W & X & Y & Y \\
W & X & Z & Z
\end{bmatrix}
\qquad
\begin{bmatrix}
A & A & B & B & C \\
H & X & & & C \\
H & X & & & D \\
G & & Y & Y & D \\
G & F & F & E & E
\end{bmatrix}
\]
\[
\begin{bmatrix}
A & A & B & C & & \\
D & D & B & C & & \\
& & W & W & Y & Z \\
& & X & X & Y & Z \\
P & Q & & & R & R \\
P & Q & & & S & S \\
\end{bmatrix}
\qquad
\begin{bmatrix}
A & A & B & B & & & C \\
& W & W & & & X & C \\
& & P & & & X & D \\
H & & P & & & & D \\
H & Z & & Q & Q & & \\
G & Z & & & Y & Y & \\
G & & & F & F & E & E
\end{bmatrix}
\]
\begin{remark*}
Most of the difficulty of the problem is the construction for $n \in \{5,7\}$.
\end{remark*}
\pagebreak
\subsection{EGMO 2018/5, proposed by Dominika Regiec (POL)}
\textsl{Available online at \url{https://aops.com/community/p10191590}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $\Gamma $ be the circumcircle of triangle $ABC$.
A circle $\Omega$ is tangent to the line segment $AB$
and is tangent to $\Gamma$ at a point
lying on the same side of the line $AB$ as $C$.
The angle bisector of $\angle BCA$ intersects $\Omega$
at two different points $P$ and $Q$. Prove that $\angle ABP = \angle QBC$.
\end{mdframed}
If we let $M$ denote the midpoint of arc $\widehat{AB}$
then the inversion at $M$ with radius $MA = MB$ fixes $\Omega$,
so it swaps $P$ and $Q$, thus
\[ \dang MPB = \dang QBM. \]
\begin{center}
\begin{asy}
pair A = dir(210);
pair B = dir(330);
pair C = dir(110);
pair T = dir(20);
pair M = dir(270);
pair S = extension(T, M, A, B);
pair O = extension(origin, T, S, S+M);
pair P = IP(CP(O, T), C--M);
pair Q = OP(CP(O, T), C--M);
filldraw(unitcircle, opacity(0.1)+lightcyan, deepcyan);
draw(C--M, deepcyan);
draw(A--B--C--cycle, deepcyan);
filldraw(CP(O, T), opacity(0.1)+lightgreen, deepgreen);
draw(A--P--B--Q--cycle, lightred);
draw(M--T, blue+dotted);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$T$", T, dir(T));
dot("$M$", M, dir(M));
dot("$S$", S, dir(S));
dot("$P$", P, dir(140));
dot("$Q$", Q, dir(Q));
/* TSQ Source:
A = dir 210
B = dir 330
C = dir 110
T = dir 20
M = dir 270
S = extension T M A B
O := extension origin T S S+M
P = IP CP O T C--M R140
Q = OP CP O T C--M
unitcircle 0.1 lightcyan / deepcyan
C--M deepcyan
A--B--C--cycle deepcyan
CP O T 0.1 lightgreen / deepgreen
A--P--B--Q--cycle lightred
M--T blue dotted
*/
\end{asy}
\end{center}
But
\begin{align*}
\dang MPB &= \dang MCB + \dang CBP \\
\dang QBM &= \dang ABM + \dang QBA
\end{align*}
implying the desired isogonality,
since $\dang ABM = \dang ACM = \dang MCB$.
\pagebreak
\subsection{EGMO 2018/6, proposed by Merlijn Staps (NLD)}
\textsl{Available online at \url{https://aops.com/community/p10191603}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Fix a real number $0 < t < \half$.
\begin{enumerate}
\ii [(a)]
Prove that there exists a positive integer $n$
such that for every set $S$ of $n$ positive integers,
the following holds:
there exist distinct $x, y \in S$ and \emph{nonnegative} integer $m \ge 0$
such that $|x-my| \le ty$.
\ii [(b)]
Determine whether there exists an infinite set $S$
of positive integers such that the following holds:
for any distinct $x, y \in S$ and \emph{positive} integer $m > 0$,
we have $|x-my| > ty$.
\end{enumerate}
\end{mdframed}
\paragraph{Solution to (a).}
Assume not. Let $S = \left\{ s_1 < \dots < s_n \right\}$.
Consider
\[ 1 > \frac{s_1}{s_2} > \frac{s_1}{s_3} > \dots > \frac{s_1}{s_n} > t. \]
Note that two of the fractions above are within a factor of
$t^{1/(n-1)}$ of each other; taking $n$ large enough so that
$t^{1/(n-1)} \ge 1-t$ gives the conclusion.
\paragraph{Solution to (b).}
Yes, such a set $S$ exists.
To construct it, we employ a greedy algorithm.
Let $N$ be a large integer such that $t < 1/2-1/N$.
We define $S = \left\{ s_1 < s_2 < \dots \right\}$ inductively as follows.
\begin{itemize}
\ii First, let $s_1$ be any prime number exceeding $N$.
\ii Then, given $s_1$, \dots, $s_k$,
we let $s_{k+1}$ equal a prime number which is greater than $2s_k$,
and is congruent to $\tfrac{s_i-1}{2} \pmod{s_i}$ for $i = 1, \dots, k$.
This is possible by Chinese remainder theorem and Dirichlet theorem.
\end{itemize}
By construction, this works: if $i < j$ then $s_i / s_j < 1/2$
while $s_j / s_i$ has fractional part within $s_i^{-1}$ of $1/2$.
\pagebreak
\end{document}