% © 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 2015 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2015 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 $\triangle ABC$ be an acute-angled triangle,
and let $D$ be the foot of the altitude from $C$.
The angle bisector of $\angle ABC$ intersects $CD$ at $E$ and
meets the circumcircle $\omega$ of $\triangle ADE$ again at $F$.
If $\angle ADF = 45^{\circ}$, show that $CF$ is tangent to $\omega$.
\item %% Problem 2
A \emph{domino} is a $2 \times 1$ or $1 \times 2$ tile.
Determine in how many ways exactly $n^2$ dominoes can be placed
without overlapping on a $2n \times 2n$ chessboard
so that every $2 \times 2$ square contains at least
two uncovered unit squares which lie in the same row or column.
\item %% Problem 3
Let $n, m$ be integers greater than $1$,
and let $a_1, a_2, \dots, a_m$ be positive integers
not greater than $n^m$.
Prove that there exist integers $b_1, b_2, \dots, b_m$ not greater than $n$ such that
\[ \gcd(a_1 + b_1, a_2 + b_2, \dots, a_m + b_m) < n. \]
\item %% Problem 4
Determine whether or not there exists an infinite sequence
$a_1$, $a_2$, \dots\ of positive integers satisfying
\[ a_{n+2} = a_{n+1} + \sqrt{a_{n+1}+a_{n}} \]
for every positive integer $n$.
\item %% Problem 5
Let $m, n$ be positive integers with $m > 1$.
Anastasia partitions the integers $1, 2, \dots , 2m$ into $m$ pairs.
Boris then chooses one integer from each pair
and finds the sum of these chosen integers.
Prove that Anastasia can select the pairs
so that Boris cannot make his sum equal to $n$.
\item %% Problem 6
Let $H$ be the orthocenter and $G$ be the centroid of
acute-angled triangle $ABC$ with $AB \neq AC$.
The line $AG$ intersects the circumcircle
of $ABC$ at $A$ and $P$.
Let $P'$ be the reflection of $P$ in the line $BC$.
Prove that $\angle CAB = 60$ if and only if $HG = GP'$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{EGMO 2015/1, proposed by Luxembourg}
\textsl{Available online at \url{https://aops.com/community/p4725314}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $\triangle ABC$ be an acute-angled triangle,
and let $D$ be the foot of the altitude from $C$.
The angle bisector of $\angle ABC$ intersects $CD$ at $E$ and
meets the circumcircle $\omega$ of $\triangle ADE$ again at $F$.
If $\angle ADF = 45^{\circ}$, show that $CF$ is tangent to $\omega$.
\end{mdframed}
\begin{center}
\begin{asy}
pair A = dir(0);
pair B = dir(180);
pair F = dir(65);
pair D = extension(A, B, F, dir(205));
pair K = F*F;
pair C = extension(D, D+dir(90), B, K);
pair E = extension(B, F, C, D);
filldraw(unitcircle, palecyan+opacity(0.2), heavyblue);
filldraw(circumcircle(A, D, E), palered+opacity(0.2), red+dotted);
filldraw(CP(E,D), pink+opacity(0.2), magenta);
draw(arc(F,abs(E-F),170,310), orange+dashed);
draw(K--A--B--C--D, deepcyan);
draw(C--A, deepcyan+dashed);
draw(B--F--A, deepgreen);
draw(F--D, deepgreen);
draw(C--F, mediumred);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$F$", F, dir(F));
dot("$D$", D, dir(225));
dot("$K$", K, dir(K));
dot("$C$", C, dir(C));
dot("$E$", E, dir(165));
\end{asy}
\end{center}
Let $BC$ meet the circle with diameter $\ol{AB}$ at $K$.
By the conditions of the problem, we have $FK = FE = FA$.
Thus $E$ is the incenter of $\triangle KBA$.
By angle chasing, we can now show that
\[ \angle KFE = 90^{\circ} - \frac12 \angle KEF = \angle BCD, \]
so $KCFE$ is cyclic and thus
\[ \angle CKE = 135^{\circ} \implies \angle CFE = 45^{\circ} \]
as needed.
\begin{remark*}
One can also realize $CKEF$ is cyclic by noting
\[ BE \cdot BF = BD \cdot BA = BK \cdot BC. \]
\end{remark*}
\begin{remark*}
Another approach is to use barycentric coordinates on $\triangle ABK$.
Letting $a=BK$, $b=AK$, $c=AB$ we have $E = (a:b:c)$, $D = (s-b:s-a:0)$, and
\[ F = (a(a+c) : -b^2 : c(a+c))
= (a(a+c) : a^2-c^2 : c(a+c))
= (a : a-c : c). \]
\end{remark*}
\pagebreak
\subsection{EGMO 2015/2, proposed by Turkey}
\textsl{Available online at \url{https://aops.com/community/p4725316}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A \emph{domino} is a $2 \times 1$ or $1 \times 2$ tile.
Determine in how many ways exactly $n^2$ dominoes can be placed
without overlapping on a $2n \times 2n$ chessboard
so that every $2 \times 2$ square contains at least
two uncovered unit squares which lie in the same row or column.
\end{mdframed}
Generalizing the problem slightly,
the answer is $\binom{m+n}{n}^2$ for a $2m \times 2n$ rectangle,
The proof is the following nice bijection
between valid domino tilings and pairs of lattice paths joining
opposite corners of the grid, that travel along the borders of the
obvious $2 \times 2$ squares.
\begin{center}
\begin{asy}
size(10cm);
pen[] colors = {olive, deepmagenta, heavycyan, heavygreen};
fill((0,0)--(2,0)--(2,4)--(4,4)--(4,8)--(0,8)--cycle, cyan+opacity(0.2));
fill((2,0)--(6,0)--(6,2)--(4,2)--(4,4)--(2,4)--cycle, green+opacity(0.2));
fill(box((4,4),(6,8)), purple+opacity(0.2));
fill((4,2)--(6,2)--(6,0)--(8,0)--(8,8)--(6,8)--(6,4)--(4,4)--cycle, yellow+opacity(0.2));
for (int i=1; i<=4; ++i) {
draw((0,2*i-1)--(8,2*i-1), lightgrey+1);
draw((2*i-1,0)--(2*i-1,8), lightgrey+1);
}
for (int i=0; i<=4; ++i) {
draw((0,2*i)--(8,2*i), grey+1.5+linetype("3 2"));
draw((2*i,0)--(2*i,8), grey+1.5+linetype("3 2"));
}
path red_path = (0,0)--(2,0)--(2,4)--(6,4)--(6,8)--(8,8);
path blue_path = (0,8)--(4,8)--(4,2)--(6,2)--(6,0)--(8,0);
draw(red_path, lightred+7);
draw(red_path, heavyred+3);
draw(blue_path, lightcyan+7);
draw(blue_path, blue+3);
real eps = 0.22;
path dom = (eps,1-eps)--(1-eps,1-eps)--(1-eps,eps-1)--(eps,eps-1)--cycle;
void draw_domino(real x, real y, int n) {
filldraw(
shift(2*x-1,2*y-1)*rotate(90*n)*dom,
colors[n]+opacity(0.7),
black+1.3
);
}
draw_domino(4,4,0); draw_domino(4,3,0); draw_domino(4,2,0); draw_domino(4,1,0); draw_domino(3,2,0);
draw_domino(3,3,1); draw_domino(3,4,1);
draw_domino(1,1,2); draw_domino(1,2,2); draw_domino(1,3,2); draw_domino(1,4,2); draw_domino(2,3,2); draw_domino(2,4,2);
draw_domino(2,2,3); draw_domino(2,1,3); draw_domino(3,1,3);
\end{asy}
\end{center}
\begin{remark*}
The main reason I was able to make the correct guess
of the answer was because I generalized
the problem to rectangular boards rather than to square boards.
Three possible motivations:
\begin{itemize}
\ii The problem felt very recursive,
in that smaller instances of the problem would appear as sub-cases.
In particular, my computation for $(m,n)=(2,2)$ requires $(m,n)=(2,1)$ as a subcase anyways.
\ii The problem makes it otherwise too difficult to examine small cases.
\ii $(m,n)=(2,1)$ gives another perfect square $3^2=9$
so there is good reason to believe that something is going on here too.
\end{itemize}
Once you have the guess down, it becomes more clear that
any recursive solution is likely to fail (due to the square),
and one needs to find a ``combinatorial'' interpretation for the problem.
The two paths as shown is a natural one,
and with a little work one gets the bijection above.
\end{remark*}
\pagebreak
\subsection{EGMO 2015/3, proposed by United States of America}
\textsl{Available online at \url{https://aops.com/community/p4725324}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n, m$ be integers greater than $1$,
and let $a_1, a_2, \dots, a_m$ be positive integers
not greater than $n^m$.
Prove that there exist integers $b_1, b_2, \dots, b_m$ not greater than $n$ such that
\[ \gcd(a_1 + b_1, a_2 + b_2, \dots, a_m + b_m) < n. \]
\end{mdframed}
In fact, we will prove that it's possible to choose $b_i \in \{0,1\}$!
Assume not, and all GCD's are at least $n$.
Consider the choices:
\begin{itemize}
\ii $b_1 = \dots = b_m = 0$.
\ii $b_1 = b_2 = \dots = b_{k-1} = b_{k+1} = b_m = 0$ and $b_k = 1$,
for some $2 \le k \le m$.
\end{itemize}
This generates $m$ gcd's, say $g_1$, \dots, $g_m$.
Each divides $a_1$.
Moreover, they are pairwise coprime, s
\[ a_1 \ge \prod_i g_i = n(n+1) \dots + (n+m-1) > n^m \]
which is impossible.
\pagebreak
\section{Solutions to Day 2}
\subsection{EGMO 2015/4, proposed by Japan}
\textsl{Available online at \url{https://aops.com/community/p4728593}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Determine whether or not there exists an infinite sequence
$a_1$, $a_2$, \dots\ of positive integers satisfying
\[ a_{n+2} = a_{n+1} + \sqrt{a_{n+1}+a_{n}} \]
for every positive integer $n$.
\end{mdframed}
In fact, we will show the following stronger result:
the largest $N$ for which one can find $(a_1, \dots, a_N)$ satisfying
(for all $1 \le n \le N-2$) is actually $N = 5$.
This largest $N$ is obtained
for example by $(a_1,a_2,a_3,a_4,a_5) = (477,7,29,35,43)$.
\begin{remark*}
Basically, the idea is to choose $a_3$ first; then as long as the number
\[ s \coloneqq \sqrt{a_3 + a_4} = \sqrt{2a_3 + \sqrt{a_2 + a_3}} \]
is as integer, the rest of the sequence can be chosen to have integer values.
Unfortunately, $a_1$ may turn out to be negative in this situation.
But if one experiments with numbers, it should be possible to ensure $a_2 < a_3$,
and after this no further obstructions arise.
For example, if one makes the arbitrary starting choice $s = 10$,
then choosing $a_3 = 46$ gives the nice choice $a_2 = 18$, thus $a_1 = 766$.
(We picked this number so that $2a_3 + \sqrt{a_3}$ was just under $100$.)
Meanwhile, moving forward, $a_4 = 46 + \sqrt{46+18} = 54$
and $a_5 = 54 + \sqrt{46+54} = 64$.
Hence $(a_1,a_2,a_3,a_4,a_5) = (766, 18, 46, 54, 64)$ is another example.
\end{remark*}
Let
\[ x_n \coloneqq a_{n+1}-a_n = \sqrt{a_{n}+a_{n-1}}. \]
We will rewrite everything in terms of the $(x_n)$.
Since the $(a_n)$ are strictly increasing for $n \ge 2$
so are the $(x_n)$ when $n \ge 3$.
For $n \ge 2$ observe that
\[ x_{n+1}^2 - x_n^2 = a_{n+1} - a_{n-1}
= \left( a_{n+1}-a_{n} \right) + \left( a_{n}-a_{n-1} \right) = x_n + x_{n-1} \]
thus
\[ x_{n+1}-x_n = \frac{x_n+x_{n-1}}{x_{n+1}+x_n}. \]
But suppose $n \ge 4$.
Then since the $x_n$ are supposed to be strictly increasing, the right-hand side is $< 1$.
Yet $x_{n+1} - x_n \ge 1$ as well, which is a contradiction.
Thus it is impossible to have six terms in the sequence.
\pagebreak
\subsection{EGMO 2015/5, proposed by Netherlands}
\textsl{Available online at \url{https://aops.com/community/p4728599}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $m, n$ be positive integers with $m > 1$.
Anastasia partitions the integers $1, 2, \dots , 2m$ into $m$ pairs.
Boris then chooses one integer from each pair
and finds the sum of these chosen integers.
Prove that Anastasia can select the pairs
so that Boris cannot make his sum equal to $n$.
\end{mdframed}
Overall the idea is to try find a few constructions which eliminate most of the cases,
then clean out the last few ones leftover.
% (It's like using reavers on zerglings:
% knock out 90\% of the lings with a couple scarabs
% and then have the zealots finish the rest.)
\begin{itemize}
\ii If $n \notin [m^2, m^2+m]$, then use the construction
\[
\begin{array}{ccccc}
1 & 3 & \dots & 2m-3 & 2m-1 \\
2 & 4 & \dots & 2m-2 & 2m
\end{array}
\]
\ii If $n \not\equiv 1 + 2 + \dots + m = \half m(m+1) \pmod m$, use the construction
\[
\begin{array}{ccccc}
1 & 2 & \dots & m-1 & m \\
m+1 & m+2 & \dots & 2m-1 & 2m
\end{array}
\]
\end{itemize}
Henceforth, assume $m \ge 4$ (smaller cases can be dispensed with by hand).
\begin{itemize}
\ii Assume $m$ is odd, and either $n = m^2$ and $n = m^2 + m$.
Use the construction
\[
\begin{array}{ccccc}
1 & 2 & \dots & m-1 & m \\
m+2 & m+3 & \dots & 2m & m+1
\end{array}.
\]
The possible values of this modulo $m+1$ are
\[ \tfrac 12 m(m+1) + \{0,1\} \equiv \tfrac12(m+1) + \{0,1\} \pmod{m+1} \]
since $m$ is odd.
But $m^2$ and $m^2+m$ leave residues $1$ and $2$ modulo $m$, done.
\ii Assume $m$ is even (so $m+1$ is odd), and $n = m^2 + \half m \equiv \half \pmod{m+1}$.
The same pairing as before has possible residues
\[ \tfrac 12m (m+1) + \{0,1\} \equiv \{0,1\} \pmod{m+1}. \]
This completes the proof.
\end{itemize}
\pagebreak
\subsection{EGMO 2015/6, proposed by Ukraine}
\textsl{Available online at \url{https://aops.com/community/p4728597}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $H$ be the orthocenter and $G$ be the centroid of
acute-angled triangle $ABC$ with $AB \neq AC$.
The line $AG$ intersects the circumcircle
of $ABC$ at $A$ and $P$.
Let $P'$ be the reflection of $P$ in the line $BC$.
Prove that $\angle CAB = 60$ if and only if $HG = GP'$.
\end{mdframed}
The following complex numbers solution was given by Stefan Tudose.
First
\[ \frac{pa(b+c)-bc(p+a)}{pa-bc}
= \frac{b+c}{2} \implies p
= -\frac{2bc-ab-ac}{bc(2a-b-c)}. \]
Then
\[ p' = b+c-bc\ol p = \frac{ab+ac-b^2-c^2}{2a-b-c}. \]
Now let $D$ be the midpoint of $\ol{HP'}$.
Then
\begin{align*}
d = \frac{h+p'}{2} & = \frac{a^2-b^2-c^2+ab+ac-bc}{2a-b-c} \\
h-p' &= \frac{2(a^2-bc)}{2a-b-c} \\
g-d &= \frac{2b^2+2c^2-a^2+bc-2ab-2ac}{3(2a-b-c)}
\end{align*}
Then $HG = GP' \iff \ol{GD} \perp \ol{HP'}$ and we have
\[
\frac{g-d}{h-p'}
= \frac{2b^2+2c^2-a^2+bc-2ab-2ac}{6(a^2-bc)}
\]
which we would like to be pure imaginary.
However the negative conjugate equals
\[
\ol{\left( \frac{g-d}{h-p'} \right)}
= -\frac{2a^2c^2+2a^2b^2-b^2c^2+a^2bc-2abc^2-2ab^2c}{6bc(bc-a^2)}.
\]
Expanding, the condition we have becomes
\[ b^3c+bc^3+b^2c^2=a^2bc+a^2c^2+a^2b^2
\iff (b^2+bc+c^2)(a^2-bc) = 0. \]
Now $b^2+bc+c^2=0 \iff \angle A = 60\dg$ as desired.
\begin{remark*}
One can also proceed by $|g-h| = |g-p'|$
which is longer but ultimately the same calculation.
\end{remark*}
\begin{remark*}
The condition $AB \neq AC$ is not cosmetic;
it cannot be dropped from the problem condition.
This is reflected in the presence of $a^2-bc$ factor.
\end{remark*}
\pagebreak
\end{document}