% © 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 2017 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2017 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 $ABCD$ be a convex quadrilateral
with $\angle DAB = \angle BCD = 90\dg$ and $\angle ABC > \angle CDA$.
Let $Q$ and $R$ be points on segments $BC$ and $CD$,
respectively, such that line $QR$ intersects lines $AB$ and $AD$
at points $P$ and $S$, respectively.
It is given that $PQ=RS$.
Let the midpoint of $BD$ be $M$ and the midpoint of $QR$ be $N$.
Prove that the points $M$, $N$, $A$ and $C$ lie on a circle.
\item %% Problem 2
Find the smallest positive integer $k$ for which
there exists a coloring of the positive integers
$\ZZ_{>0}$ with $k$ colors and a function $f \colon \ZZ_{>0} \to \ZZ_{>0}$
with the following two properties:
\begin{enumerate}[(i)]
\ii For all positive integers $m$, $n$ of the same color,
$f(m+n)=f(m)+f(n)$.
\ii There are positive integers $m$, $n$
such that $f(m+n) \neq f(m)+f(n)$.
\end{enumerate}
\item %% Problem 3
There are $2017$ lines in the plane such that
no three of them go through the same point.
Turbo the snail sits on a point on exactly one of the lines
and starts sliding along the lines in the following fashion:
she moves on a given line until she reaches an intersection of two lines.
At the intersection, she follows her journey
on the other line turning left or right,
alternating her choice at each intersection point she reaches.
She can only change direction at an intersection point.
Can there exist a line segment through which she passes
in both directions during her journey?
\item %% Problem 4
Let $n\geq1$ be an integer and let $t_1 \angle CDA$.
Let $Q$ and $R$ be points on segments $BC$ and $CD$,
respectively, such that line $QR$ intersects lines $AB$ and $AD$
at points $P$ and $S$, respectively.
It is given that $PQ=RS$.
Let the midpoint of $BD$ be $M$ and the midpoint of $QR$ be $N$.
Prove that the points $M$, $N$, $A$ and $C$ lie on a circle.
\end{mdframed}
The condition is equivalent to $N$ being the midpoint
of both $\ol{PS}$ and $\ol{QR}$ simultaneously.
(Thus triangles $BAD$ and $BCD$ play morally dual roles.)
\begin{center}
\begin{asy}
import graph; size(12cm);
pen zzttqq = rgb(0.6,0.2,0.); pen cqcqcq = rgb(0.75294,0.75294,0.75294);
draw((-1.83576,5.20298)--(-4.,1.5)--(-0.44779,-2.69232)--(4.5,1.5)--cycle, linewidth(0.6) + zzttqq);
draw(circle((0.25,1.5), 4.25), linewidth(0.6));
draw((-5.40339,-0.90118)--(6.45435,0.35776), linewidth(0.6));
draw((-1.83576,5.20298)--(-4.,1.5), linewidth(0.6) + zzttqq);
draw((-4.,1.5)--(-0.44779,-2.69232), linewidth(0.6) + zzttqq);
draw((-0.44779,-2.69232)--(4.5,1.5), linewidth(0.6) + zzttqq);
draw((4.5,1.5)--(-1.83576,5.20298), linewidth(0.6) + zzttqq);
draw((-4.,1.5)--(-5.40339,-0.90118), linewidth(0.6));
draw((4.5,1.5)--(6.45435,0.35776), linewidth(0.6));
dot("$D$", (4.5,1.5), dir(40));
dot("$B$", (-4.,1.5), dir(180));
dot("$M$", (0.25,1.5), dir(90));
dot("$A$", (-1.83576,5.20298), dir(130));
dot("$C$", (-0.44779,-2.69232), dir(270));
dot("$Q$", (-2.24919,-0.56630), dir(80));
dot("$R$", (2.67884,-0.04308), dir(135));
dot("$P$", (-5.40339,-0.90118), dir(270));
dot("$S$", (6.45435,0.35776), dir(270));
dot("$N$", (0.21482,-0.30469), dir(80));
\end{asy}
\end{center}
The rest is angle chasing.
We have
\begin{align*}
\dang ANC &= \dang ANP + \dang QNC \\
&= 2\dang ASP + 2\dang QRC \\
&= 2 \dang DSR + 2 \dang DRS = 2 \dang RDS \\
&= 2 \dang ADC = \dang AMC.
\end{align*}
\pagebreak
\subsection{EGMO 2017/2, proposed by Merlijn Staps (NLD)}
\textsl{Available online at \url{https://aops.com/community/p8024575}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find the smallest positive integer $k$ for which
there exists a coloring of the positive integers
$\ZZ_{>0}$ with $k$ colors and a function $f \colon \ZZ_{>0} \to \ZZ_{>0}$
with the following two properties:
\begin{enumerate}[(i)]
\ii For all positive integers $m$, $n$ of the same color,
$f(m+n)=f(m)+f(n)$.
\ii There are positive integers $m$, $n$
such that $f(m+n) \neq f(m)+f(n)$.
\end{enumerate}
\end{mdframed}
Answer: $k=3$.
Construction for $k=3$:
let
\[ f(n) =
\begin{cases} n/3 & n\equiv 0 \pmod 3 \\
n & \text{else} \end{cases} \]
and color the integers modulo $3$.
Now we prove that for $k=2$ a function $f$ obeying (i) must be linear,
even if $f \colon \ZZ_{>0} \to \RR_{>0}$.
Call the colors blue/red and WLOG $f(1) = 1$.
First, we obviously have:
\begin{claim*}
$f(2n) = 2f(n)$ for every $n$.
\end{claim*}
Now we proceed by induction in the following way.
Assume that $f(1) = 1$, $f(2) = 2$, \dots, $f(2n) = 2n$.
For brevity let $m = 2n+1$ be red
and assume for contradiction that $f(m) \neq m$.
The proof now proceeds in four steps.
First:
\begin{itemize}
\ii The number $m-2$ must be blue.
Indeed if $m-2$ was red we would have $f(2m-2) = f(m) + f(m-2)$
which is a contradiction as $f(2m-2) = 2f(m-1) = 2m-2$ and $f(m-2)=m-2$.
\ii The number $2$ must be red.
Indeed if it was blue then $f(m) = f(2) + f(m-2) = m$ contradiction.
\end{itemize}
Observe then that $f(m+2) = f(m)+2$ since $m$ and $2$ are both red.
Now we consider two cases:
\begin{itemize}
\ii If $m+2$ is red, then
$f(2m+2) = f(m+2) + f(m) = (f(m) + 2) + f(m)$.
But $f(2m+2) = f(4n+4) = 4f(n+1) = 2m+2$, contradiction.
\ii If $m+2$ is blue,
then $2f(m) = f(2m) = f(m+2) + f(m-2) = f(m) + 2 + (m-2)$.
So then $f(m) = m$ again a contradiction.
\end{itemize}
So $f(m) = m$, which completes the induction.
\pagebreak
\subsection{EGMO 2017/3, proposed by M\'{a}rk Di Giovanni (HUN)}
\textsl{Available online at \url{https://aops.com/community/p8024557}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
There are $2017$ lines in the plane such that
no three of them go through the same point.
Turbo the snail sits on a point on exactly one of the lines
and starts sliding along the lines in the following fashion:
she moves on a given line until she reaches an intersection of two lines.
At the intersection, she follows her journey
on the other line turning left or right,
alternating her choice at each intersection point she reaches.
She can only change direction at an intersection point.
Can there exist a line segment through which she passes
in both directions during her journey?
\end{mdframed}
\textbf{Color the regions} of the plane black and white in alternating colors.
Then:
\begin{claim*}
Turbo will always move in one orientation around black regions
and the other orientation around white regions.
\end{claim*}
This completes the proof, even if Turbo may pick
which of left/right she follows each time!
\begin{remark*}
An example of a cyclic path:
take a pentagon and extend its sides to form a star.
Then Turbo can trace around the exterior of the star.
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{EGMO 2017/4, proposed by Gerhard W\"{o}ginger (LUX)}
\textsl{Available online at \url{https://aops.com/community/p8029369}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n\geq1$ be an integer and let $t_1 2^{e-1}$.
Consequently we can take two adjacent edges $a+b = b+c$
with the same label; hence $a = c$.
Then delete $b$, $c$ and induct down.
For part (b), for odd integers $m$, let $f(m)$ denote $2^k - m$
where $2^k$ is the smallest power of two exceeding $m$.
Note $f(m) \le m$ with equality if and only if $m = 1$.
So repeatedly apply $f$ until we wrap around;
this gives twice a square of a power of two.
Example when $m = 13$:
\begin{center}
\begin{asy}
size(4cm);
int[] x = {13,3,1,1,3,13}; // repeat last guy
for (int i=0; i<5; ++i) {
dot( (string) x[i], dir(72*i), dir(72*i), darkcyan);
draw(dir(72*i)--dir(72*i+72), darkcyan);
label( (string) (x[i] + x[i+1]),
midpoint(dir(72*i)--dir(72*i+72)), dir(72*i+36), red);
}
\end{asy}
\end{center}
\begin{remark*}
By applying the process of (a) in reverse,
one essentially finds an inductive characterization
of all expensive $n$-tuples.
\end{remark*}
\pagebreak
\subsection{EGMO 2017/6, proposed by Charles Leytem (LUX)}
\textsl{Available online at \url{https://aops.com/community/p8029388}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be an acute-angled triangle in which no two sides
have the same length.
The reflections of the centroid $G$ and the circumcenter $O$ of $ABC$
in its sides $BC$, $CA$, $AB$
are denoted by $G_1$, $G_2$, $G_3$ and $O_1$, $O_2$, $O_3$, respectively.
Show that the circumcircles of triangles
$G_1G_2C$, $G_1G_3B$, $G_2G_3A$, $O_1O_2C$, $O_1O_3B$, $O_2O_3A$
and $ABC$ have a common point.
\end{mdframed}
Here is an approach with complex numbers.
Let $P$ be an arbitrary point.
Let $P_B$ and $P_C$ be the reflections of $P$ across $AB$ and $AC$
and let $Q_B$ and $Q_C$ be the second intersections of
lines $AP_B$ and $AP_C$ with the circumcircle.
Then we will compute the intersection of
$(A P_B P_C)$ and $(A Q_B Q_C) \equiv (ABC)$.
We have $p_B = a+c-ac\ol p$, $p_C = a+b-ab\ol p$.
To compute $q_B$ note that
\begin{align*}
a+q_B &= p_B + a q_B \ol{p_B} \\
&= a+c-ac\ol p + aq_B \left( 1/a + 1/c - p/ac \right) \\
\implies ac\ol p - c &= (a/c-p/c) q_B \\
\implies q_B &= c^2 \frac{a\ol p -1}{a-p}.
\end{align*}
Similarly $q_C = b^2 \frac{a \ol p - 1}{a-p}$.
Then, the desired intersection is
\begin{align*}
\frac{p_B q_C - p_C q_B}{p_B - p_C + q_C - q_B}
&= \frac{ \left( \frac{a \ol p -1}{a-p} \right)
\left( b^2(a+c-ac \ol p) - c^2 (a+b-ab\ol p) \right)}%
{(b-c)(a \ol p-1) + (b^2-c^2) \cdot \frac{a \ol p - 1}{a-p}} \\
&= \frac{b^2(a+c-ac \ol p) - c^2(a+b-ab\ol p)}%
{(b-c)(a-p) + (b^2-c^2)} \\
&= \frac{(b-c)(a(b+c)+bc) - (b-c) abc \ol p}{(a-p)+(b+c)} \\
&= \frac{ab+bc+ca - abc \ol p}{a+b+c-p}
\end{align*}
which is in any case symmetric in $a$, $b$, $c$.
Moreover taking $p = \frac13(a+b+c)$ and $p=0$
give the same numbers (and indeed any $p$ on the Euler line).
\pagebreak
\end{document}