% © 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 2016 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2016 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 $n$ be an odd positive integer,
and let $x_1$, $x_2$, \dots, $x_n$ be nonnegative real numbers.
Show that
\[ \min(x_i^2+x_{i+1}^2) \le \max(2x_jx_{j+1}) \]
where $1\le i,j\le n$ and $x_{n+1}=x_1$.
\item %% Problem 2
Let $ABCD$ be a cyclic quadrilateral,
and let diagonals $AC$ and $BD$ intersect at $X$.
Let $C_1,D_1$ and $M$ be the midpoints of segments $CX$,
$DX$ and $CD$, respectively.
Lines $AD_1$ and $BC_1$ intersect at $Y$,
and line $MY$ intersects diagonals $AC$ and $BD$
at different points $E$ and $F$, respectively.
Prove that line $XY$ is tangent to the circle through $E$, $F$ and $X$.
\item %% Problem 3
Let $m$ be a positive integer. Consider a $4m \times 4m$ array of square unit cells.
Two different cells are \emph{related} to each other
if they are in either the same row or in the same column.
No cell is related to itself.
Some cells are colored blue, such that every cell is
related to at least two blue cells.
Determine the minimum number of blue cells.
\item %% Problem 4
Two circles $\omega_1$ and $\omega_2$, of equal radius
intersect at different points $X_1$ and $X_2$.
Consider a circle $\omega$ externally tangent to $\omega_1$ at $T_1$
and internally tangent to $\omega_2$ at point $T_2$.
Prove that lines $X_1T_1$ and $X_2T_2$ intersect at a point lying on $\omega$.
\item %% Problem 5
Let $k$ and $n$ be integers such that $k\ge 2$ and $k \le n \le 2k-1$.
Place rectangular tiles, each of size $1 \times k$ or $k \times 1$
on a $n \times n$ chessboard so that each tile covers
exactly $k$ cells and no two tiles overlap.
Do this until no further tile can be placed in this way.
For each such $k$ and $n$, determine the minimum number of tiles
that such an arrangement may contain.
\item %% Problem 6
Let $S$ be the set of all positive integers $n$ such that $n^4$ has a divisor
in the range $n^2 + 1$, $n^2+2$, \dots, $n^2 + 2n$.
Prove that there are infinitely many elements of $S$ of
each of the forms $7m$, $7m+1$, $7m+2$, $7m+5$, $7m+6$
and no elements of $S$ of the form $7m+3$ and $7m+4$,
where $m$ is an integer.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{EGMO 2016/1, proposed by Netherlands}
\textsl{Available online at \url{https://aops.com/community/p6171538}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n$ be an odd positive integer,
and let $x_1$, $x_2$, \dots, $x_n$ be nonnegative real numbers.
Show that
\[ \min(x_i^2+x_{i+1}^2) \le \max(2x_jx_{j+1}) \]
where $1\le i,j\le n$ and $x_{n+1}=x_1$.
\end{mdframed}
It suffices to exhibit a single pair $(i,j)$ where
\[ x_i^2 + x_{i+1}^2 \le 2 x_j x_{j+1}. \]
Since $n$ is odd we can find three adjacent $x_k$'s,
call them $a$, $b$, and $c$ (with $b$ in middle) such that $a \ge b \ge c$.
Then indeed
\[ 2ab \ge b^2+c^2 \]
so we're done.
\begin{remark*}
When $n$ is even, counterexamples to the problem statement alternate up and down,
such as $(1,100,1,100,1,100,\dots)$.
This provides a reason why one should consider $a \ge b \ge c$ to exploit
the parity of $n$.
\end{remark*}
\pagebreak
\subsection{EGMO 2016/2, proposed by Belarus}
\textsl{Available online at \url{https://aops.com/community/p6171514}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABCD$ be a cyclic quadrilateral,
and let diagonals $AC$ and $BD$ intersect at $X$.
Let $C_1,D_1$ and $M$ be the midpoints of segments $CX$,
$DX$ and $CD$, respectively.
Lines $AD_1$ and $BC_1$ intersect at $Y$,
and line $MY$ intersects diagonals $AC$ and $BD$
at different points $E$ and $F$, respectively.
Prove that line $XY$ is tangent to the circle through $E$, $F$ and $X$.
\end{mdframed}
We present two approaches.
\paragraph{First approach through isogonality lemma.}
Note $ABC_1D_1$ is cyclic.
By the ``isogonality lemma'' applied to $\triangle YC_1D_1$,
it follows that $YX$ and $YM$ are isogonal
with respect to $\triangle YC_1D_1$.
Then
\[ \angle EXY = \angle XC_1Y + \angle C_1YX
= \angle AD_1X + \angle MYA = \angle YFX \]
and we're done (angles are directed).
\begin{remark*}
Note that the points $C$ and $D$ can be more or less deleted immediately.
The ``isogonality lemma'' people has mentioned has appeared in other places too.
In addition to the Taiwan TST 2014 round 2 problem 6, it also shows itself in
ELMO 2012/5, % http://aops.com/community/c6h486936p2728469
BrMO2 2013/2, % http://www.aops.com/community/c6h518987
SL 2009 G4, SL 2012 G2.
\end{remark*}
\paragraph{Solution with complex numbers, by Sanjana Das.}
Quadrilateral $ABC_1D_1$ is also cyclic ($\dang AC_1D_1 = \dang ACD = \dang ABD_1$).
We want $\dang YXE = \dang XFE$,
or \[\dang(XY, AC) = \dang(BD, MY).\]
Now use complex numbers with unit circle $(ABC_1D_1)$
(using $c$ and $d$ to refer to $C_1$ and $D_1$ for berevity).
We want to check that $\frac{(x - y)(m - y)}{(a - c)(b - d)}$ is real.
First, if $Z = AB \cap C_1D_1$,
then $XY \perp OZ$ where $O$ is the
circumcenter of $(ABC_1D_1)$ by Brokard's Theorem,
so we want to show
\[ \frac{(ab(c + d) - cd(a + b))\cdot (y - m)}
{(a - c)(b - d)(ab - cd)} \in i\RR.\]
Now we have $m = c + d - x$, which means
\begin{align*}
y - m &= x + y - c - d \\
&= \frac{ac(b +d) - bd(a +c)}{ac - bd} + \frac{ad(b + c) - bc(a+ d)}{ad - bc} - c - d \\
&= \frac{ab(2acd + 2bcd + c^3 + d^3 - ac^2 - ad^2 - bc^2 - bd^2 - c^2d - cd^2)}{(ac - bd)(ad - bc)} \\
&= -\frac{ab(a + b - c - d)(c - d)^2}{(ac - bd)(ad - bc)}.
\end{align*}
This means our final expression is
\[-\frac{ab(ab(c + d) - cd(a + b))(a + b - c - d)(c - d)^2}{(ac - bd)(ad - bc)(a - c)(b - d)(ab - cd)},\]
which is visibly the negative of its conjugate and is therefore imaginary.
\pagebreak
\subsection{EGMO 2016/3, proposed by Mexico}
\textsl{Available online at \url{https://aops.com/community/p6171553}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $m$ be a positive integer. Consider a $4m \times 4m$ array of square unit cells.
Two different cells are \emph{related} to each other
if they are in either the same row or in the same column.
No cell is related to itself.
Some cells are colored blue, such that every cell is
related to at least two blue cells.
Determine the minimum number of blue cells.
\end{mdframed}
We'll prove that the answer is at least $6m$.
The construction is to take
diagonal copies of the matrix
\[ \begin{bmatrix}
& 1 & 1 & 1 \\
1 &&& \\
1 &&& \\
1 &&&
\end{bmatrix}. \]
We present two proofs this is optimal.
\paragraph{Bipartite graph (Kevin Sun).}
Consider the bipartite subgraph
\[ H \subseteq K_{4m,4m} \]
with vertices being rows/columns,
and edges corresponding blue squares.
Assume for contradiction the are fewer than $6m$ edges.
Then there are at least $|V(H)|-|E(H)|=8m-6m=2m$
connected components in $H$,
so some connected component has at most three vertices.
We consider two cases:
\begin{itemize}
\ii Note that if there are any isolated vertices $v$
(connected components with no edges),
then it follows $H$ needs at least $8m$ edges,
because every vertex on the opposite shore from $v$ has
blue-degree at least $2$.
\ii Thus assume no isolated vertices exist.
On the other hand, every blue edge
is incident to at least two more blue edges,
so no connected component can have fewer than three edges.
As the connected components are bipartite,
it follows each connected component has at least four vertices,
which is impossible.
\end{itemize}
\paragraph{Brute force (mine).}
%I'll admit that unlike P1 and P2 (which I solved in about five minutes each),
%there is \emph{no way} I would have gotten this problem under time pressure:
%I had to stay up all night (despite a sore throat) to solve it.
%Also, this solution (linear programming after optimization)
%seems too silly to be true.
We prove that for a general $n \times n$ board,
a good configuration has at least $\frac32n$ blue squares.
Consider any minimal good configuration
with $k$ squares, and assume $k \le \frac 32 n$
(and we will prove $k \ge \frac32n$).
We observe that no column and row can be empty in a good
configuration with $k \le 2n$ squares.
Now, assume there are $x_i$ columns with exactly $i$ blue squares,
and $a_i$ rows with exactly $i$ blue squares (for $i = 1,\dots,n$.)
Permute the board to arrive at the following:
\[
\begin{array}{r|c|c|c|}
\multicolumn{1}{c}{\ }
& \multicolumn{1}{c}{x_1\text{ cols}}
& \multicolumn{1}{c}{x_2\text{ cols}}
& \multicolumn{1}{c}{x_3+x_4+\dots+x_n\text{ cols}} \\\cline{2-4}
a_1 \text{ rows} & 0 & 0 & a_1 \\ \cline{2-4}
a_2 \text{ rows} & 0 & P & Q \\ \cline{2-4}
&&& \\[1em]
a_3+\dots+a_n & x_1 & R & S \\
\text{rows} &&& \\[1em]\cline{2-4}
\end{array}
\]
In each subgrid, the letter denotes the number of blue squares in that region.
Consequently, we have $P+Q=2a_2$, $P+R=2x_2$,
and $a_1+Q+S = 3x_3+4x_4+\dots+nx_n$.
We also know that $n = \sum a_i = \sum x_i$ and $k = \sum ia_i = \sum ix_i$.
Without loss of generality we assume that $a_1 \le x_1$.
Then, it would suffice to prove that
\[ \sum ia_i \ge \frac32 \sum a_i \iff a_1 \le a_2 + 3a_3 + 5a_4 + \dots. \]
We observe that
\begin{align*}
0 &\le S = 3x_3 + \dots + nx_n - a_1 - Q \\
&= \left( a_1+2a_2+\dots+na_n \right) - (x_1+2x_2) - (a_1-Q) \\
\implies x_1 &\le (3a_3+4a_4+\dots+na_n) - (Q - 2a_2 + 2x_2) \\
&= (3a_3+4a_4+\dots+na_n) - R \\
&\le 3a_3 + 4a_4 + \dots + na_n \\
&\le a_2 + 3a_3 + 5a_4 + \dots + (2n-3)a_n.
\end{align*}
Since we assumed $a_1 \le x_1$, we are done.
% http://aops.com/community/c6t30365f6h1226675_related_blue_squares_in_4m_by_4m_board
\pagebreak
\section{Solutions to Day 2}
\subsection{EGMO 2016/4, proposed by Charles Leytem (LUX)}
\textsl{Available online at \url{https://aops.com/community/p6177803}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Two circles $\omega_1$ and $\omega_2$, of equal radius
intersect at different points $X_1$ and $X_2$.
Consider a circle $\omega$ externally tangent to $\omega_1$ at $T_1$
and internally tangent to $\omega_2$ at point $T_2$.
Prove that lines $X_1T_1$ and $X_2T_2$ intersect at a point lying on $\omega$.
\end{mdframed}
We present two solutions,
one by homothety and another by inversion.
\paragraph{First solution (homothety).}
Consider the composition of homotheties
\[ \omega_1 \xrightarrow{T_1} \omega \xrightarrow{T_2} \omega_2. \]
This is a negative homothety,
and since $\omega_1$ and $\omega_2$ have equal radius,
it follows that the composition is just reflection
about the midpoint of $\ol{X_1X_2}$.
In particular, it sends $X_1$ to $X_2$,
and thus $\ol{X_1T_1} \cap \ol{X_2T_2}$
is just the image of $X_1$ under the first homothety.
\paragraph{Second solution (inversion).}
Invert around $X_1$.
Then we have the following:
\begin{itemize}
\ii $\omega_1^\ast$ and $\omega_2^\ast$ are lines intersecting at $X_2^\ast$,
and $X_1$ is a point on the external angle bisector of the two lines.
\ii The circle $\omega^\ast$ becomes tangent to the two lines
(in a region adjacent to $X_1$).
\ii Let $P = \ol{T_1^\ast X_1} \cap \omega^\ast$.
Then one wishes to show $X_1 X_2^\ast P T_2^\ast$ are concyclic.
\end{itemize}
To show this, notice that
\[ \dang T_2^\ast X_2^\ast X_1 = \dang T_1^\ast T_2^\ast X_2^\ast
= \dang T_2^\ast P T_1^\ast = \dang T_2^\ast P X_1. \]
% http://aops.com/community/c6t30365f6h1227238_geometry_tangent_circles
\pagebreak
\subsection{EGMO 2016/5, proposed by Netherlands}
\textsl{Available online at \url{https://aops.com/community/p6177809}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $k$ and $n$ be integers such that $k\ge 2$ and $k \le n \le 2k-1$.
Place rectangular tiles, each of size $1 \times k$ or $k \times 1$
on a $n \times n$ chessboard so that each tile covers
exactly $k$ cells and no two tiles overlap.
Do this until no further tile can be placed in this way.
For each such $k$ and $n$, determine the minimum number of tiles
that such an arrangement may contain.
\end{mdframed}
The answer is
\[
\begin{cases}
n & n=k \text{ or } n = 2k-1 \\
2(n-k+1) & k < n < 2k-1.
\end{cases}
\]
Here are constructions.
\begin{itemize}
\ii For $n = k$ it's trivial.
\ii For $k < n < 2k-1$, observe that one can construct
it when $n = k+1$ by simply filling in the perimeter
of the $(k+1) \times (k+1)$ square with four dominoes,
then one can inductively obtain the next values
$n = k+2, k+3, \dots$ by adding a new domino to each row and column,
hence increasing the count by $2$.
An example with $(k,n) = (5,8)$ is shown below.
\[
\begin{bmatrix}
w & w & w & w & w & x & a & b \\
y & & & & & x & a & b \\
y & & & & & x & a & b \\
y & & & & & x & a & b \\
y & & & & & x & a & b \\
y & z & z & z & z & z & & \\
c & c & c & c & c & & & \\
d & d & d & d & d & & & \\
\end{bmatrix}
\]
\ii For $n = 2k-1$ one places a domino in each column,
alternating between upper-most possible and lower-most possible.
An example with $(k,n) = (3,5)$ is shown below.
\[
\begin{bmatrix}
a & & c & & e \\
a & & c & & e \\
a & b & c & d & e \\
& b & & d & \\
& b & & d & \\
\end{bmatrix}
\]
\end{itemize}
Now we now prove this is optimal.
Call a row (resp column) \emph{bare}
if it contains no horizontal (resp vertical) domino
contained completely inside it.
The main observation is that:
\begin{claim*}
The bare columns are consecutive, as are the bare rows.
\end{claim*}
\begin{proof}
Consider a vertical domino $D$ (say) in some column $C$,
and assume it is in the left half of the board.
Then the column to the left of $C$ must also contain a domino,
otherwise we could add the domino exactly to the left of $D$
since there is not enough space to fit a horizontal domino
to $D$'s left.
Inductively, then, every column left of $C$ is not bare.
Similarly, if $C$ had been on the right half of the board,
then all columns to the right of $C$ are not bare.
\end{proof}
To finish, we consider two cases.
\begin{itemize}
\ii If there are no bare columns,
then we need at least $n$ dominoes,
since each column contains a domino.
Similarly, if there are no bare rows, we also need at least $n$ dominoes.
\ii In the case there exist at least one bare row or bare column,
note that given $k$ (consecutive) bare columns,
then intersecting them with a bare row
gives a place where we can add an additional domino, contradiction.
So there are at most $k$ bare columns,
and hence at least $n-(k-1) = n-k+1$ vertical dominoes
(one per non-bare column).
Similarly, there are at least $n-k+1$ horizontal dominoes.
So there are at least $2(n-k+1)$ dominoes total.
\end{itemize}
This shows one always needs at least
$\min(n, 2(n-k+1))$ dominoes.
This resolves every case except $k = n$,
(in which case the bound is true but not achievable).
However, the case $k = n$ is trivial --- just note that
all the dominoes must have the same orientation when $k = n$,
so we are necessarily in the first case.
\pagebreak
\subsection{EGMO 2016/6, proposed by Netherlands}
\textsl{Available online at \url{https://aops.com/community/p6177824}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $S$ be the set of all positive integers $n$ such that $n^4$ has a divisor
in the range $n^2 + 1$, $n^2+2$, \dots, $n^2 + 2n$.
Prove that there are infinitely many elements of $S$ of
each of the forms $7m$, $7m+1$, $7m+2$, $7m+5$, $7m+6$
and no elements of $S$ of the form $7m+3$ and $7m+4$,
where $m$ is an integer.
\end{mdframed}
Start from the implication
\[ n^2 + k \mid n^4 \iff n^2 + k \mid k^2. \]
Since $1 \le k \le 2n$, in fact the quotient $\frac{k^2}{n^2+k}$
can only take values from $1$ to $3$.
In other words, $S$ is the set of integers $n$ for which at least one equation
\begin{align*}
n^2 + k &= k^2 \\
2(n^2 + k) &= k^2 \\
3(n^2 + k) &= k^2
\end{align*}
has at least one solution $1 \le k \le 2n$.
The first equation has no solutions with $k \ge 1$
since we can put $(k-1)^2 < n^2 < k^2$.
The other two are Pell equations,
and one can check that $n^2 \equiv 2 \pmod 7$ has no solutions at all
for $k \pmod 7$ in either case.
The assertion about infinitely many solutions then follows by
using the Pell recursion, and taking modulo $7$.
\pagebreak
\end{document}