% © 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 2014 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2014 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
Determine all real constants $t$ such that whenever $a$, $b$ and $c$ are the lengths of sides of a triangle, then so are $a^2+bct$, $b^2+cat$, $c^2+abt$.
\item %% Problem 2
Let $D$ and $E$ be points in the interiors of sides $AB$ and $AC$,
respectively, of a triangle $ABC$, such that $DB = BC = CE$.
Let the lines $CD$ and $BE$ meet at $F$.
Prove that the incenter $I$ of triangle $ABC$,
the orthocenter $H$ of triangle $DEF$ and
the midpoint $M$ of the arc $BAC$ of the circumcircle of triangle $ABC$
are collinear.
\item %% Problem 3
We denote the number of positive divisors of a positive integer $m$ by $d(m)$
and the number of distinct prime divisors of $m$ by $\omega(m)$.
Let $k$ be a positive integer.
Prove that there exist infinitely many positive integers $n$
such that $\omega(n) = k$ and
$d(n)$ does not divide $d(a^2+b^2)$
for any positive integers $a, b$ satisfying $a + b = n$.
\item %% Problem 4
Determine all positive integers $n\geq 2$ for which there exist integers
$x_1$, $x_2$, \dots, $x_{n-1}$ satisfying the condition that
if $0*0}^3$
(checking only one inequality is enough by symmetry).
Writing this is a quadratic in $x$, we want
\[ Q(x) \coloneqq (2-t)x^2 + (2+t)(y+z)x + ((y^2+yz+z^2)t - 2yz) > 0. \]
\begin{claim*}
Except when $t=2$,
the quadratic $Q$ always has two real roots.
\end{claim*}
\begin{proof}
The discriminant is
\begin{align*}
D &= [(2+t)(y+z)]^2 - 4(2-t)\left( (y^2+yz+z^2)t - 2yz \right) \\
&= \left( (2+t)^2 - 4(2-t)t \right)(y^2+z^2)
+ \left( 2(2+t)^2-4(2-t)(t-2) \right) yz \\
&= \left( 5t^2-4t+4 \right)(y^2+z^2) + \left( 6t^2-8t+24 \right) yz > 0
\end{align*}
which means $Q$ always has two real roots
(aside for the single exceptional case $t=2$,
in which $Q$ is not a quadratic).
\end{proof}
Now, we make a few closing observations.
\begin{itemize}
\ii It is clear we need $t \le 2$,
since a negative leading coefficient will
cause the inequality to fail for $x \gg y,z$.
\ii The case $t=2$ obviously has $Q > 0$ always.
\ii For $t < 2$, as $Q$ always has two real roots,
the assertion is true if and only if all coefficients
of $Q$ are nonnegative.
\ii When $t \ge \frac23$,
we have $(2+t)(y+z) > 0$ obviously, and from
\[ \frac{y^2+yz+z^2}{3} \ge yz \]
the constant coefficient is nonnegative as well.
Thus when $\boxed{\frac23 \le t \le 2}$
we indeed have $Q(x) > 0$ for $x,y,z > 0$.
\ii If $t < \frac23$,
then by letting $y=z$ fails the condition.
\end{itemize}
\pagebreak
\subsection{EGMO 2014/2, proposed by Ukraine}
\textsl{Available online at \url{https://aops.com/community/p3459750}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $D$ and $E$ be points in the interiors of sides $AB$ and $AC$,
respectively, of a triangle $ABC$, such that $DB = BC = CE$.
Let the lines $CD$ and $BE$ meet at $F$.
Prove that the incenter $I$ of triangle $ABC$,
the orthocenter $H$ of triangle $DEF$ and
the midpoint $M$ of the arc $BAC$ of the circumcircle of triangle $ABC$
are collinear.
\end{mdframed}
\paragraph{First solution (Cynthia Du).}
Let $BI$ and $CI$ meet the circumcircle again at $M_B$, $M_C$.
Observe that we have the spiral congruence
\[ \triangle MDB \sim \triangle MEC \]
from $\dang MBD = \dang MBA = \dang MCA = \dang MCE$
and $BD = EC$, $BM = CM$.
That is, $M$ is the Miquel point of $BDEC$.
\begin{center}
\begin{asy}
pair A = dir(110);
pair B = dir(240);
pair C = dir(300);
draw(A--B--C--cycle, heavycyan);
filldraw(unitcircle, opacity(0.1)+lightcyan, heavycyan);
pair I = incenter(A, B, C);
pair D = -C+2*foot(C, I, B);
pair E = -B+2*foot(B, I, C);
pair M_B = circumcenter(A, I, C);
pair M_C = circumcenter(A, I, B);
pair M = dir(90);
filldraw(M--D--B--cycle, opacity(0.1)+lightgreen, heavygreen);
filldraw(M--E--C--cycle, opacity(0.1)+lightgreen, heavygreen);
draw(B--M_B, heavycyan);
draw(C--M_C, heavycyan);
pair T = extension(M, E, B, I);
pair S = extension(M, D, C, I);
draw(circumcircle(D, I, E), lightred+dashed);
draw(D--S, heavygreen);
draw(E--T, heavygreen);
draw(D--I--E, lightred);
draw(C--D, lightgreen);
draw(B--E, lightgreen);
pair F = extension(C, D, B, E);
pair H = orthocenter(D, E, F);
draw(D--H--E, heavycyan);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$I$", I, dir(I));
dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$M_B$", M_B, dir(M_B));
dot("$M_C$", M_C, dir(M_C));
dot("$M$", M, dir(M));
dot("$T$", T, dir(T));
dot("$S$", S, dir(S));
dot("$F$", F, dir(F));
dot("$H$", H, dir(90));
/* TSQ Source:
A = dir 110
B = dir 240
C = dir 300
A--B--C--cycle heavycyan
unitcircle 0.1 lightcyan / heavycyan
I = incenter A B C
D = -C+2*foot C I B
E = -B+2*foot B I C
M_B = circumcenter A I C
M_C = circumcenter A I B
M = dir 90
M--D--B--cycle 0.1 lightgreen / heavygreen
M--E--C--cycle 0.1 lightgreen / heavygreen
B--M_B heavycyan
C--M_C heavycyan
T = extension M E B I
S = extension M D C I
circumcircle D I E lightred dashed
D--S heavygreen
E--T heavygreen
D--I--E lightred
C--D lightgreen
B--E lightgreen
F = extension C D B E
H = orthocenter D E F R90
D--H--E heavycyan
*/
\end{asy}
\end{center}
Let $T = \ol{ME} \cap \ol{BI}$ and $S = \ol{MD} \cap \ol{CI}$.
First, since $\ol{BI}$ is the perpendicular bisector of $\ol{CD}$
we have that
\[ \dang DIT = \dang CIT = \dang CIB = 90\dg - \half \angle A
= \dang MCB = \dang MED = \dang TED \]
and so $D$, $I$, $T$, $E$ is cyclic.
Similarly $S$ lies on this circle too.
But $\dang SDE = \dang EDM = \dang MED = \dang TED$
so in fact $\ol{ST} \parallel \ol{DE}$ (isosceles trapezoid).
Then $\triangle IST$ and $\triangle HDE$ are homothetic,
so $\ol{IH}$, $\ol{DS}$, and $\ol{ET}$ concur (at $M$).
\paragraph{Second solution (Evan Chen).}
Observe that we have the spiral congruence
\[ \triangle MDB \sim \triangle MEC \]
from $\dang MBD = \dang MBA = \dang MCA = \dang MCE$
and $BD = EC$, $BM = CM$.
That is, $M$ is the Miquel point of $BDEC$.
\begin{center}
\begin{asy}
pair A = dir(110);
pair B = dir(240);
pair C = dir(300);
draw(A--B--C--cycle, heavycyan);
filldraw(unitcircle, opacity(0.1)+lightcyan, heavycyan);
pair I = incenter(A, B, C);
pair D = -C+2*foot(C, I, B);
pair E = -B+2*foot(B, I, C);
pair M = dir(90);
pair F = extension(C, D, B, E);
pair X = midpoint(B--D);
pair Y = midpoint(C--E);
draw(X--M--Y, red+dotted);
pair H = orthocenter(D, E, F);
draw(C--D, lightgreen);
draw(B--E, lightgreen);
draw(I--M, red+dotted);
draw(CP(X, B), red+dashed);
draw(CP(Y, C), red+dashed);
filldraw(B--D--E--C--cycle, opacity(0.1)+yellow, lightgreen);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$I$", I, dir(I));
dot("$D$", D, dir(120));
dot("$E$", E, dir(75));
dot("$M$", M, dir(M));
dot("$F$", F, dir(F));
dot("$X$", X, dir(A+B));
dot("$Y$", Y, dir(A+C));
dot("$H$", H, dir(90));
/* TSQ Source:
A = dir 110
B = dir 240
C = dir 300
A--B--C--cycle heavycyan
unitcircle 0.1 lightcyan / heavycyan
I = incenter A B C
D = -C+2*foot C I B R120
E = -B+2*foot B I C R75
M = dir 90
F = extension C D B E
X = midpoint B--D RA+B
Y = midpoint C--E RA+C
X--M--Y red dotted
H = orthocenter D E F R90
C--D lightgreen
B--E lightgreen
I--M red dotted
CP X B red dashed
CP Y C red dashed
B--D--E--C--cycle 0.1 yellow / lightgreen
*/
\end{asy}
\end{center}
Let $X$ and $Y$ be the midpoints of $\ol{BD}$ and $\ol{CE}$.
Then $MX = MY$ by our congruence.
Consider now the circles with diameters $\ol{BD}$ and $\ol{CE}$.
We now claim that $H$, $I$, $M$ all lie on the radical axis
of these circles.
Note that $I$ is the orthocenter of $\triangle BFC$
and $H$ is the orthocenter of $\triangle DEF$,
so this follows from the so-called Steiner line of $BCDE$
(perpendicular to Gauss line $\ol{XY}$).
For $M$, we observe $MX^2 - XB^2 = MY^2 - YC^2$ thus completing the proof.
\paragraph{Third solution (homothety, official solution).}
Extend $DH$ and $EH$ to meet $BI$ and $CI$ at $D_1$ and $E_1$.
Note $DD_1 \perp BE$, $CI \perp BE$, so $DD_1 \parallel CI$.
Similarly $EE_1 \parallel BI$.
So $HE_1ID_1$.
\begin{center}
\begin{asy}
size(9cm);
pair A = dir(100);
pair B = dir(240);
pair C = dir(300);
pair I = incenter(A, B, C);
pair D = -C+2*foot(C, B, I);
pair E = -B+2*foot(B, C, I);
pair F = extension(B, E, C, D);
pair H = orthocenter(D, E, F);
draw(A--B--C--cycle);
draw(B--E);
draw(C--D);
pair D_1 = extension(D, H, B, I);
pair E_1 = extension(E, H, C, I);
pair D_2 = dir(20);
pair E_2 = dir(170);
draw(unitcircle);
pair M = D_2+E_2-I;
draw(circumcircle(B, C, D_1));
draw(B--D_2--M--E_2--C);
draw(E_1--E, dotted);
draw(M--I, dotted);
draw(D_1--D, dotted);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$I$", I, dir(I));
dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
dot("$H$", H, dir(90));
dot("$D_1$", D_1, dir(100));
dot("$E_1$", E_1, dir(80));
dot("$D_2$", D_2, dir(D_2));
dot("$E_2$", E_2, dir(E_2));
dot("$M$", M, dir(M));
/* Source generated by TSQ
A = dir 100
B = dir 240
C = dir 300
I = incenter A B C
D = -C+2*foot C B I
E = -B+2*foot B C I
F = extension B E C D
H = orthocenter D E F R90
A--B--C--cycle
B--E
C--D
D_1 = extension D H B I R100
E_1 = extension E H C I R80
D_2 = dir 20
E_2 = dir 170
unitcircle
M = D_2+E_2-I
circle B C D_1
B--D_2--M--E_2--C
E_1--E dotted
M--I dotted
D_1--D dotted
*/
\end{asy}
\end{center}
Angle chase to show that $B$, $E_1$, $F$, $C$ are cyclic --
$\angle DCE_1 = \angle DCI$ is computable in terms of $ABC$
and \[ \angle E_1BF = \angle E_1BE = \angle E_1EB = \angle HEF = \angle HDF = \angle HDC = \angle DCE_1 = \angle FCE_1. \]
Thus $B$, $D_1$, $F$, $C$ are also cyclic.
So $B$, $D_1$, $E_1$, $C$ are cyclic.
Extend $BI$ and $CI$ to meet the circumcircle again at $D_2$ and $E_2$.
Direct computation gives that $ME_2ID_2$ is also a parallelogram.
We also get $E_1D_1$ is parallel to $E_2D_2$
(both are antiparallel to $BC$ through $\angle BIC$).
So we have homothetic paralellograms and that finishes the problem.
\pagebreak
\subsection{EGMO 2014/3, proposed by Japan}
\textsl{Available online at \url{https://aops.com/community/p3459754}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
We denote the number of positive divisors of a positive integer $m$ by $d(m)$
and the number of distinct prime divisors of $m$ by $\omega(m)$.
Let $k$ be a positive integer.
Prove that there exist infinitely many positive integers $n$
such that $\omega(n) = k$ and
$d(n)$ does not divide $d(a^2+b^2)$
for any positive integers $a, b$ satisfying $a + b = n$.
\end{mdframed}
Let $n = 2^{p-1}t$, where $t \equiv 5 \pmod 6$, $\omega(t) = k-1$,
and $p \gg t$ is a sufficiently large prime.
Let $a+b=n$ and $a^2+b^2=c$.
We claim that $p \nmid d(c)$,
which solves the problem since $p \mid d(n)$.
First, note that $3 \nmid a^2+b^2$, since $3 \nmid n$.
Next, note that $c < 2n^2 < 5^{p-1}$ (since $p \gg t$)
so no exponent of an odd prime in $c$ exceeds $p-2$.
Moreover, $c < 2^{3p-1}$.
So, it remains to check that $\nu_2(c) \notin \{p-1, 2p-1\}$.
On the one hand, if $\nu_2(a) < \nu_2(b)$,
then $\nu_2(a) = p-1$ and $\nu_2(c) = 2\nu_2(a) = 2p-2$.
On the other hand, if $\nu_2(a) = \nu_2(b)$
then $\nu_2(a) \le p-2$, and $\nu_2(c) = 2\nu_2(a)+1$
is odd and less than $2p-1$.
\begin{remark*}
Personally, I find the condition to be artificial,
but the construction is kind of fun.
I also think the scores on this problem during the real contest
are low mostly because of the difficulty of problem 2.
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{EGMO 2014/4, proposed by Netherlands}
\textsl{Available online at \url{https://aops.com/community/p3460731}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Determine all positive integers $n\geq 2$ for which there exist integers
$x_1$, $x_2$, \dots, $x_{n-1}$ satisfying the condition that
if $0** \nu_p(3t_1) = \nu_p(3n/d)$ (since $d \ge 5$ is odd).
So indeed it's possible to construct a cycle.
\end{itemize}
Thus these are all the answers and the only answers.
\pagebreak
\subsection{EGMO 2014/5, proposed by Romania}
\textsl{Available online at \url{https://aops.com/community/p3460733}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n$ be a positive integer.
We have $n$ boxes where each box contains a non-negative number of pebbles.
In each move we are allowed to take two pebbles from a box we choose,
throw away one of the pebbles and put the other pebble in another box we choose.
An initial configuration of pebbles is called \emph{solvable} if it is possible
to reach a configuration with no empty box, in a finite (possibly zero) number of moves.
Determine all initial configurations of pebbles which are not solvable,
but become solvable when an additional pebble is added to a box,
no matter which box is chosen.
\end{mdframed}
The point of the problem is to characterize all the solvable configurations.
We claim that it is given by the following:
\begin{claim*}
A configuration $(a_1, \dots, a_n)$ is solvable
if and only if
\[ \sum_1^n \left\lceil \frac{a_i}{2} \right\rceil \ge n. \]
\end{claim*}
\begin{proof}
The proof is by induction on the number of stones.
If there are fewer than $n$ stones there is nothing to prove.
Now assume there are at least $n$ stones,
and let $S = \sum \left\lceil a_i/2 \right\rceil$.
Then:
\begin{itemize}
\ii If $S < n$, this remains true after any operation,
so by induction the configuration is not solvable.
\ii Suppose $S \ge n$, and also that there is an empty box
(else we are already done).
Then there must be some box with at least two stones.
In that case, using those two stones to fill the empty box
does not change the value of $S$,
but decreases the total number of stones by one, as desired.
\qedhere
\end{itemize}
\end{proof}
From here we may then extract the answer to the original problem:
we require all $a_i$ to be even and $\sum a_i = 2n-2$.
\begin{remark*}
It should be unsurprising that a criteria of this form exists,
since (1) intuitively, one loses nothing by filling
empty boxes as soon as possible,
and then ignoring boxes with one pebble in them,
(2) the set of configurations is a graded partially ordered set,
so one can inductively look at small cases.
\end{remark*}
\pagebreak
\subsection{EGMO 2014/6, proposed by Netherlands}
\textsl{Available online at \url{https://aops.com/community/p3460735}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Solve over $\RR$ the functional equation
\[ f(y^2+2xf(y)+f(x)^2) = (y+f(x)) (x+f(y)). \]
\end{mdframed}
A key motivation throughout the problem
is that the left-hand side is asymmetric
while the right-hand side is symmetric.
Thus any time we plug in two values for $x$ and $y$
we will also plug in the opposite pair.
Once $f$ is injective this will basically kill the problem.
First, we prove the following.
\begin{lemma*}
There is a unique $z \in \RR$ such that $f(z) = 0$.
\end{lemma*}
\begin{proof}
Clearly by putting $y=-f(x)$ such $z$ exists.
Now, suppose $f(u) = f(v) = 0$.
Then:
\begin{itemize}
\ii Plug $(x,y) = (u,v)$ gives $f(v^2) = uv$.
\ii Plug $(x,y) = (v,u)$ gives $f(u^2) = uv$.
\ii Plug $(x,y) = (u,u)$ gives $f(u^2) = u^2$.
\ii Plug $(x,y) = (v,v)$ gives $f(v^2) = v^2$.
\end{itemize}
Consequently $u^2 = uv = v^2$ which yields $u = v$.
\end{proof}
Next let $(x,y) = (z,0)$ and $(x,y) = (0,z)$ to get
\begin{align*}
& f\left( 2zf(0) \right)
= f\left( z^2 + f(0)^2 \right) = 0 \\
\implies & 2z f(0) = z^2 + f(0)^2 = z \\
\implies &\boxed{f(0) = z \in \left\{ 0, \half \right\}}.
\end{align*}
We now set to prove:
\begin{lemma*}
The function $f$ is injective.
\end{lemma*}
\begin{proof}
By putting $(x,y)=(x,z)$ and $(x,y)=(z,x)$ we get
\[ f\left( f(x)^2 + z^2 \right) = f\left( 2zf(x) + x^2 \right) = x(z+f(x)). \]
Now suppose $f(x_1) = f(x_2)$ but $x_1 \neq x_2$.
This can only happen if $f(x_1) = f(x_2) = -z$.
And now \[ f(x_i)^2 + z^2 = 2zf(x_i) + x_i^2 = z \qquad i = 1, 2. \]
Solving, we have $x_i = \pm 1$, $z = \half$,
(since $z = 0$ is not permissible).
Thus we have ``almost injectivity''.
Now plug in $(x,y) = (-1,0)$ and $(x,y) = (0,-1)$ in
the original and equate in order to obtain
$f(-\frac34) = f(\frac54)$, which contradicts the work above.
\end{proof}
Finally we may use the symmetry trick in full to obtain
\[ y^2 + 2xf(y) + f(x)^2 = x^2 + 2yf(x) + f(y)^2. \qquad(\heartsuit) \]
In particular, by setting $y=0$ we obtain
\[ f(x)^2 = \left( z - x \right)^2. \]
Two easy cases remain:
\begin{itemize}
\ii In the $z=0$ case simply note
that $(\heartsuit)$ gives
$2xf(y) = 2yf(x)$, so for $x \neq 0$
the value $f(x)/x$ is constant
and hence $f(x) \equiv \pm x$ follows.
\ii In the $z=\half$ case $(\heartsuit)$ becomes
$ \left( 2f(y)+1 \right)x = \left( 2f(x)+1 \right)y $
and hence we're done again by the same reasoning.
\end{itemize}
\pagebreak
\end{document}
*