% © 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 2013 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2013 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
The side $BC$ of the triangle $ABC$
is extended beyond $C$ to $D$ so that $CD = BC$.
The side $CA$ is extended beyond $A$ to $E$ so that $AE = 2CA$.
Prove that if $AD=BE$ then the triangle $ABC$ is right-angled.
\item %% Problem 2
Determine all integers $m$ for which the $m \times m$ square can be dissected
into five rectangles, the side lengths of which are
the integers $1$, $2$, \dots, $10$ in some order.
\item %% Problem 3
Let $n$ be a positive integer.
\begin{enumerate}
\ii[(a)]
Prove that there exists a set $S$ of $6n$ positive integers
such that the least common multiple of any two is at most $32n^2$.
\ii[(b)]
Show that every set $T$ of $6n$ positive integers
contains two elements with least common multiple
exceeding $9n^2$.
\end{enumerate}
\item %% Problem 4
Find all positive integers $a$ and $b$ for which there are three consecutive integers at which the polynomial $P(n) = \frac1b(n^5+a)$ takes integer values.
\item %% Problem 5
Let $\Omega$ be the circumcircle of the triangle $ABC$.
The circle $\omega$ is tangent to the sides $AC$ and $BC$,
and it is internally tangent to the circle $\Omega$ at the point $P$.
A line parallel to $AB$ intersecting the
interior of triangle $ABC$ is tangent to $\omega$ at $Q$.
Prove that $\angle ACP = \angle QCB$.
\item %% Problem 6
Snow White and the Seven Dwarves are living in their house in the forest.
On each of 16 consecutive days, some of the dwarves worked in the diamond mine
while the remaining dwarves collected berries in the forest.
No dwarf performed both types of work on the same day.
On any two different (not necessarily consecutive) days,
at least three dwarves each performed both types of work.
Further, on the first day, all seven dwarves worked in the diamond mine.
Prove that, on one of these 16 days, all seven dwarves were collecting berries.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{EGMO 2013/1, proposed by David Monk (UNK)}
\textsl{Available online at \url{https://aops.com/community/p3013167}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
The side $BC$ of the triangle $ABC$
is extended beyond $C$ to $D$ so that $CD = BC$.
The side $CA$ is extended beyond $A$ to $E$ so that $AE = 2CA$.
Prove that if $AD=BE$ then the triangle $ABC$ is right-angled.
\end{mdframed}
Let ray $DA$ meet $\ol{BE}$ at $M$.
Consider the triangle $EBD$.
Since the point lies on median $\ol{EC}$, and $EA = 2AC$,
it follows that $A$ is the centroid of $\triangle EBD$.
\begin{center}
\begin{asy}
pair A = dir(50);
pair B = dir(180);
pair C = dir(0);
draw(A--B--C--cycle, black+1.4);
pair D = 2*C-B;
pair E = 3*A-2*C;
draw(C--D);
draw(A--E);
draw(B--E, dotted);
draw(A--D, dotted);
pair M = extension(A, D, B, E);
draw(B--E--D--M);
dot("$A$", A, dir(A));
dot("$B$", B, dir(-90));
dot("$C$", C, dir(-90));
dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$M$", M, dir(M));
/* TSQ Source:
A = dir 50
B = dir 180 R-90
C = dir 0 R-90
A--B--C--cycle black+1.4
D = 2*C-B
E = 3*A-2*C
C--D
A--E
B--E dotted
A--D dotted
M = extension A D B E
B--E--D--M
*/
\end{asy}
\end{center}
So $M$ is the midpoint of $\ol{BE}$.
Moreover $MA = \frac 12 AD = \frac 12 BE$; so $MA = MB = ME$ and hence $\triangle ABE$ is inscribed in a circle with diameter $\ol{BE}$.
Thus $\angle BAE = 90\dg$, so $\angle BAC = 90\dg$.
\pagebreak
\subsection{EGMO 2013/2, proposed by Matti Lehtinen (FIN)}
\textsl{Available online at \url{https://aops.com/community/p3013170}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Determine all integers $m$ for which the $m \times m$ square can be dissected
into five rectangles, the side lengths of which are
the integers $1$, $2$, \dots, $10$ in some order.
\end{mdframed}
The answer is that this is possible if and only if $m = 11$ or $m = 13$.
\paragraph{Constructions for $m=11$ and $m=13$.}
See the figures below.
\begin{center}
\begin{asy}
size(12cm);
picture p11, p13;
pen b = black+2.5;
filldraw(p11, box((0,0), (11,11)), palegreen, b);
filldraw(p11, box((0,0), (8,5)), palecyan, b);
filldraw(p11, box((1,9), (11,11)), palecyan, b);
filldraw(p11, box((8,0), (11,9)), palered, b);
filldraw(p11, box((0,5), (6,11)), palered, b);
for (int i=0; i<11; ++i) {
for (int j=0; j<11; ++j) {
draw(p11, shift(i,j)*unitsquare, black);
}
}
add(p11);
filldraw(p13, box((0,0), (13,13)), palegreen, b);
filldraw(p13, box((0,0), (8,3)), palecyan, b);
filldraw(p13, box((6,4), (13,13)), palecyan, b);
filldraw(p13, box((8,0), (13,4)), palered, b);
filldraw(p13, box((0,3), (6,13)), palered, b);
for (int i=0; i<13; ++i) {
for (int j=0; j<13; ++j) {
draw(p13, shift(i,j)*unitsquare, black);
}
}
add(shift(13,-1)*p13);
\end{asy}
\end{center}
\paragraph{Proof the task is impossible unless $11 \le m \le 13$.}
The total area of the rectangles is of the form $A = a_1 b_1 + \dots + a_5 b_5$
for $(a_1, \dots, b_5)$ a permutation of $(1, \dots, 10)$.
By applying the rearrangement inequality repeatedly one can prove that
\[ A \le 1 \cdot 2 + 3 \cdot 4 + 5 \cdot 6 + 7 \cdot 8 + 9 \cdot 10 = 190. \]
Analogously, we can get a matching lower bound
\[ A \ge 1 \cdot 10 + 2 \cdot 9 + 3 \cdot 8 + 4 \cdot 7 + 5 \cdot 6 = 110. \]
Since $A = m^2$ for integer $m$, it follows $11 \le m \le 13$.
\paragraph{Proof the task is impossible for $m=12$.}
It remains to rule out such a tiling for a $12 \times 12$ square.
We start with the following structure claim:
\begin{claim*}
Any tiling for $m > 10$ must either be the spiral pattern below or a reflection of it.
\begin{center}
\begin{asy}
size(3cm);
draw(box((0,0),(7,7)), black+1.5);
draw((0,2)--(5,2), black+1);
draw((5,0)--(5,4), black+1);
draw((3,4)--(7,4), black+1);
draw((3,7)--(3,2), black+1);
\end{asy}
\end{center}
\end{claim*}
\begin{proof}
Label the square $ABCD$.
Because $m > 10$, each corner of the square must be part of a different rectangle.
Consider the rectangle covering $A$, and let the vertex opposite $A$ be $A'$.
Define $B'$, $C'$, $D'$ similarly.
We contend that no two of $A'$, $B'$, $C'$, $D'$ coincide.
Indeed, if $A' = C'$, then we get the figure on the left where the two
purple rectangles are part of the tiling.
The remaining two ``quadrants'' must be dissected into three rectangles,
but there is general a quadrant cannot be divided into either $2$ or $3$ rectangles
in aw way that doesn't create two equal lengths.
\begin{center}
\begin{asy}
size(7cm);
picture pl;
draw(pl, box((0,0),(7,7)), black+1.5);
label(pl, "$A$", (0,0), dir(225));
label(pl, "$B$", (7,0), dir(315));
label(pl, "$C$", (7,7), dir(45));
label(pl, "$D$", (0,7), dir(135));
dotfactor *= 2;
picture pr = rotate(0)*pl;
filldraw(pl, box((0,0), (5,3)), mediummagenta, black+1.5);
filldraw(pl, box((7,7), (5,3)), mediummagenta, black+1.5);
filldraw(pr, box((0,0), (5,3)), mediummagenta, black+1.5);
filldraw(pr, box((5,3), (7,0)), mediummagenta, black+1.5);
label(pl, "$A'=C'$", (5,3), dir(135));
label(pr, "$A'=B'$", (5,3), dir(90));
dot(pl, (5,3));
dot(pr, (5,3));
add(shift(0,0)*pl);
add(shift(11,0)*pr);
\end{asy}
\end{center}
Meanwhile, if $A' = B'$, the two purple rectangles
already obviously have a common dimension (right figure).
Hence $A'$, $B'$, $C'$, $D'$ are all different points.
They must each be part of some rectangle not using the corner.
Moreover, every rectangle in the dissection has at least one vertex
not on the boundary of the square.
So the fifth rectangle must be $A'B'C'D'$ exactly.
\end{proof}
Now on to the proof that $m = 12$ is impossible.
Assume for contradiction a construction exists and refer to the spiral figure above.
Note that because $12 > 1 + 10$,
the side length $1$ cannot belong to any edge of the outer $12 \times 12$ square.
This means that $1$ must be a side length of the center rectangle.
Moreover, because the outer square has perimeter $48$,
and we know $1+2+\dots+10 = 55$, the center rectangle has perimeter $7$.
In other words, the inner rectangle must be $1 \times 6$ exactly.
\begin{center}
\begin{asy}
size(5cm);
draw(box((0,0),(12,12)), black+1.5);
draw((0,2)--(5,2), black+1);
draw((5,0)--(5,8), black+1);
draw((4,8)--(12,8), black+1);
draw((4,12)--(4,2), black+1);
label("$6$", (5,4), dir(0));
label("$1$", (4.5,8), dir(90));
\end{asy}
\end{center}
Hence, we would need to partition the remaining numbers $\{2,3,4,5,7,8,9,10\}$
into eight pairs such that two pairs differ by $1$ and differ by $6$
(in the picture, the paired numbers are on opposite sides of the square).
Note that $7$ must be paired with $8$ (since $7 \pm 6$ and $7-1$ are not available)
and $5$ must be paired with $4$ (since $5 \pm 6$ and $5+1$ are not available).
But then the remaining pairs need to have difference $6$,
and there is no way to form even a single such pair in $\{2,3,9,10\}$.
This produces the desired contradiction.
\pagebreak
\subsection{EGMO 2013/3, proposed by Dan Schwarz (ROU)}
\textsl{Available online at \url{https://aops.com/community/p3013178}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n$ be a positive integer.
\begin{enumerate}
\ii[(a)]
Prove that there exists a set $S$ of $6n$ positive integers
such that the least common multiple of any two is at most $32n^2$.
\ii[(b)]
Show that every set $T$ of $6n$ positive integers
contains two elements with least common multiple
exceeding $9n^2$.
\end{enumerate}
\end{mdframed}
For part (a), let
\[ S = \{1, 2, \dots, 4n\} \cup \{4n+2, 4n+4, \dots, 8n\} \]
which works.
For (b),
the main idea is as follows.
Let $x_0 < x_1 < \dots < x_m$ be these integers.
Assume for contradiction the LCM's are less than $L$.
The main idea is the estimate
\[
L
\ge \frac{x_i x_{i+1}}{\gcd(x_i, x_{i+1})}
\ge \frac{x_i x_{i+1}}{x_{i+1} - x_i}
\]
whence
\[ \frac{1}{L} \le \frac{1}{x_i} - \frac{1}{x_{i+1}}. \]
so taking the sum starting from any $k$ gives
\[ \frac{m+1-k}{L} \le \frac{1}{x_k} - \frac{1}{x_m} < \frac 1{x_k}. \]
For $(k,m) = (3n,6n)$ and $L = 9n^2$ this is a contradiction
(since $x_k \ge 3n$).
\begin{remark*}
China TST 2007/6 follows the same idea.
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{EGMO 2013/4, proposed by Vesna Ir\v{s}i\v{c} (SLV)}
\textsl{Available online at \url{https://aops.com/community/p3014762}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all positive integers $a$ and $b$ for which there are three consecutive integers at which the polynomial $P(n) = \frac1b(n^5+a)$ takes integer values.
\end{mdframed}
The answer is
\begin{itemize}
\ii Either $b = 1$; or
\ii $a \equiv \pm 1 \pmod{11}$ and $b = 11$ (and $a > 0$).
\end{itemize}
We consider only the case $b>1$.
Suppose that $P$ is a prime power dividing $b$.
Evidently $P$ is not even.
Then there exists an $n$ for which
\[ n^5 \equiv (n+1)^5 \equiv (n-1)^5 \pmod{P}. \]
Therefore,
\[ 0 \equiv (n+1)^5 + (n-1)^5 - 2n^5 = 20n^3+10n \pmod{P}. \]
Since $n \not\equiv 0 \pmod{p}$ for obvious reasons, we obtain that
\[ n^2 \equiv -\tfrac{1}{2} \pmod{p}. \]
Then,
\begin{align*}
0 &\equiv 2((n+1)^5 - (n-1)^5) \pmod{P} \\
&= 20n^4+40n^2+4 \\
&\equiv 20 \cdot -\frac{1}{4} + 40 \cdot -\frac{1}{2} + 4 \pmod{P} \\
&= -11.
\end{align*}
This implies $P = 11$.
Since $P$ can be any prime power dividing $b$, this forces $b=11$.
In other words, $b \in \left\{ 1,11 \right\}$.
Finally, observe that
\[ 3^5 \equiv 4^5 \equiv 5^5 \equiv 1 \pmod{11} \]
and \[ (-3)^5 \equiv (-4)^5 \equiv (-5)^5 \equiv -1 \pmod{11} \]
are the only such triples modulo $11$.
Therefore the solution set is the one claimed above.
\pagebreak
\subsection{EGMO 2013/5, proposed by Waldemar Pompe (POL)}
\textsl{Available online at \url{https://aops.com/community/p3014767}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $\Omega$ be the circumcircle of the triangle $ABC$.
The circle $\omega$ is tangent to the sides $AC$ and $BC$,
and it is internally tangent to the circle $\Omega$ at the point $P$.
A line parallel to $AB$ intersecting the
interior of triangle $ABC$ is tangent to $\omega$ at $Q$.
Prove that $\angle ACP = \angle QCB$.
\end{mdframed}
First, let us extend $\ol{AQ}$ to meet $\ol{BC}$ at $Q_1$.
By homothety, we see that $Q_1$ is just the
contact point of the $A$-excircle with $\ol{BC}$.
\begin{center}
\begin{asy}
size(7cm);
pair A = Drawing("A", dir(100), dir(100));
pair B = Drawing("B", dir(210), dir(190));
pair C = Drawing("C", dir(330), dir(350));
pair I = incenter(A,B,C);
pair Ia = 2*dir(-90)-I;
pair Ib = 2*dir(35)-I;
pair Ic = 2*dir(155)-I;
draw(unitcircle);
pair E = dir(90);
pair T = Drawing("P", 2*foot(origin,I,E)-E, dir(I-E));
pair K = extension(A,B,T,midpoint(I--Ic));
pair L = extension(A,C,T,midpoint(I--Ib));
path w = Drawing(circumcircle(T,K,L));
Drawing("I_A", Ia, dir(-90));
pair Q1 = Drawing("Q_1", foot(Ia, B, C), dir(45));
pair Q = Drawing("Q", IP(A--Q1, w), dir(45));
draw(arc(Ia, abs(Ia-Q1), -20, 200));
draw(B--C);
draw(A--foot(Ia, A, B));
draw(A--foot(Ia, A, C));
draw(T--A--Q1);
draw( (Q-0.8)--(Q+0.8) );
\end{asy}
\end{center}
Now let us perform an inversion around $A$
with radius $\sqrt{AB \cdot AC}$ followed by
a reflection around the angle bisector;
call this map $\Psi$.
Note that $\Psi$ fixes $B$ and $C$.
Moreover it swaps $\ol{BC}$ and $(ABC)$.
Hence, this map swaps the $A$-excircle
with the $A$-mixtilinear incircle $\omega$.
Hence $\Psi$ swaps $P$ and $Q_1$.
It follows that $\ol{AP}$ and $\ol{AQ_1}$
are isogonal with respect to $\angle BAC$,
meaning $\angle BAP = \angle CAQ_1$.
Since $\angle CAQ = \angle CAQ_1$ we are done.
\pagebreak
\subsection{EGMO 2013/6, proposed by Emil Kolev (BGR)}
\textsl{Available online at \url{https://aops.com/community/p3014769}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Snow White and the Seven Dwarves are living in their house in the forest.
On each of 16 consecutive days, some of the dwarves worked in the diamond mine
while the remaining dwarves collected berries in the forest.
No dwarf performed both types of work on the same day.
On any two different (not necessarily consecutive) days,
at least three dwarves each performed both types of work.
Further, on the first day, all seven dwarves worked in the diamond mine.
Prove that, on one of these 16 days, all seven dwarves were collecting berries.
\end{mdframed}
Let $Q_n$ denote the vector space $\left\{ 0,1 \right\}^n$.
For a vector $v$, let $v[i]$ denote the $i$th component.
We may identify each day with a vector $v_k$,
where $v_k[i] = 0$ if dwarf $i$ worked in the diamond mine,
and $v_k[i] = 1$ otherwise.
Let $V = \left\{ v_1, v_2, \dots, v_{16} \right\}$
be the subset of $Q_7$ in the problem,
and assume $v_{16} = 0000000$.
We first prove the following:
\begin{lemma*}
Exactly two vectors start with each of $000$, $001$, \dots, $111$.
Similar statements hold for any choice of three indices.
\end{lemma*}
\begin{proof}
If three vectors start with $000$ (say)
then we run into problems.
\end{proof}
Now we know that $v_{16}$ is the all-null vector.
Ignoring that vector (and hence considering just the first $15$ vectors),
let $n_i$ be the number of $1$'s in $v_i$, where $i = 1, 2, \dots, 15$.
\begin{claim*}
We have
\begin{align*}
\sum_{i=1}^{15} \binom{n_i}{1} &= \frac{16}{2} \binom{7}{1} = 56 \\
\sum_{i=1}^{15} \binom{n_i}{2} &= \frac{16}{2^2} \binom{7}{2} = 84 \\
\sum_{i=1}^{15} \binom{n_i}{3} &= \frac{16}{2^3} \binom{7}{3} = 70.
\end{align*}
\end{claim*}
\begin{proof}
This follows using the lemma and double counting.
For example, the third equation is counting
the number of quadruples $(i, j_1, j_2, j_3)$
such that the $i$th string has a $1$
in the $j_1$th, $j_2$th, $j_3$th position, where $j_1 < j_2 < j_3$.
The left-hand side counts the number when summed by $i$;
the right-hand side counts the number according
to the $\binom73$ choices of $(j_1, j_2, j_3)$.
\end{proof}
We may then rewrite the lemma as
\begin{align*}
\sum_{i=1}^{15} n_i &= 56 \\
\sum_{i=1}^{15} n_i^2 &= 2 \cdot 84 + 56 = 224 \\
\sum_{i=1}^{15} n_i^3 &= 6 \cdot 70 + 3 \cdot 224 - 2 \cdot 56 = 980.
\end{align*}
Now remark that $(n_i-3)(n_i-4)(n_i-7) \le 0$ for each integer $1 \le n_i \le 7$.
We compute
\begin{align*}
0 &\ge \sum_{i=1}^{15} (n_i-3)(n_i-4)(n_i-7) \\
&= \sum_{i=1}^{15} n_i^3 - 14n_i^2 + 61n_i - 84 \\
&= 1 \cdot 980 - 14 \cdot 224 + 61 \cdot 56 - 15 \cdot 84 \\
&= 980 - 3136 + 3416 - 1260 \\
&= 0.
\end{align*}
This implies that $n_i \in \left\{ 3,4,7 \right\}$ for each $i$.
If $n_i \neq 7$ for any $i$ then we have
\[ 224 = \sum n_i^2 \equiv 15 \cdot 2 \not\equiv 0 \pmod{7} \]
which is impossible.
This means that $n_i = 7$ for some $i$, and therefore, $1111111 \in V$, as desired.
\begin{remark*}
Up to permutation there turns out to be a unique set of $16$ vectors.
Xinyang Chen gives the following compact description of the unique solution:
\begin{itemize}
\ii $0000000$ and $1111111$, of course
\ii $1101000$ and its six \emph{cyclic shifts}
$0110100$, $0011010$, $0001101$, $1000110$, $0100011$, $1010001$.
\ii The complements of the above seven strings
(i.e.\ $0010111$, $1001011$, etc.).
\end{itemize}
\end{remark*}
\pagebreak
\end{document}