% © 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 2012 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2012 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 $ABC$ be a triangle with circumcenter $O$.
The points $D$, $E$, $F$ lie in the interiors
of the sides $BC$, $CA$, $AB$ respectively,
such that $\ol{DE} \perp \ol{CO}$ and $\ol{DF} \perp \ol{BO}$.
Let $K$ be the circumcenter of triangle $AFE$.
Prove that the lines $\ol{DK}$ and $\ol{BC}$ are perpendicular.
\item %% Problem 2
Let $n$ be a positive integer.
Find the greatest possible integer $m$, in terms of $n$,
with the following property: a table with $m$ rows and $n$ columns can be
filled with real numbers in such a manner that for any
two different rows $\left[ a_1, a_2, \dots, a_n \right]$
and $\left[ b_1, b_2, \dots, b_n \right]$ the following holds:
\[\max\left( {\left| {{a_1} - {b_1}} \right|,\left| {{a_2} - {b_2}} \right|,
\dots,\left| {{a_n} - {b_n}} \right|} \right) = 1. \]
\item %% Problem 3
Solve over $\RR$ the functional equation
\[ f\left( yf(x + y) + f(x) \right) = 4x + 2yf(x + y). \]
\item %% Problem 4
A set $A$ of integers is called \emph{sum-full} if $A \subseteq A + A$.
A set $A$ of integers is said to be \emph{zero-sum-free} if $0$
is the only integer that cannot be expressed as the
sum of the elements of a finite nonempty subset of $A$.
Does there exist a sum-full zero-sum-free set of integers?
\item %% Problem 5
The numbers $p$ and $q$ are prime and satisfy
\[ \frac{p}{p+1} + \frac{q+1}{q} = \frac{2n}{n+2} \]
for some positive integer $n$.
Find all possible values of $q-p$.
\item %% Problem 6
There are infinitely many people registered on the social network Mugbook.
Some pairs of (different) users are registered as friends, but each person has only finitely many friends.
Every user has at least one friend.
(Friendship is symmetric; that is, if $A$ is a friend of $B$, then $B$ is a friend of $A$.)
Each person is required to designate one of their friends as their best friend.
If $A$ designates $B$ as her best friend, then (unfortunately)
it does not follow that $B$ necessarily designates $A$ as her best friend.
Someone designated as a best friend is called a $1$-best friend.
More generally, if $n> 1$ is a positive integer,
then a user is an $n$-best friend provided that they have been designated
the best friend of someone who is an $(n-1)$-best friend.
Someone who is a $k$-best friend for every positive integer $k$ is called popular.
\begin{enumerate}
\ii[(a)] Prove that every popular person is the best friend of a popular person.
\ii[(b)] Show that if people can have infinitely many friends,
then it is possible that a popular person is not the best friend of a popular person.
\end{enumerate}
\item %% Problem 7
Let $ABC$ be an acute-angled triangle with circumcircle $\Gamma$ and orthocenter $H$. Let $K$ be a point of $\Gamma$ on the other side of $\ol{BC}$ from $A$. Let $L$ be the reflection of $K$ across $\ol{AB}$, and let $M$ be the reflection of $K$ across $\ol{BC}$. Let $E$ be the second point of intersection of $\Gamma$ with the circumcircle of triangle $BLM$. Show that the lines $KH$, $EM$ and $BC$ are concurrent.
\item %% Problem 8
A word is a finite sequence of letters from some alphabet.
A word is \emph{repetitive} if it is a concatenation of at least two identical subwords
(for example, $ababab$ and $abcabc$ are repetitive, but $ababa$ and $aabb$ are not).
Prove that if a word has the property that swapping any two adjacent letters
makes the word repetitive, then all its letters are identical.
(Note that one may swap two adjacent identical letters, leaving a word unchanged.)
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{EGMO 2012/1, proposed by Merljin Staps (NLD)}
\textsl{Available online at \url{https://aops.com/community/p2658992}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a triangle with circumcenter $O$.
The points $D$, $E$, $F$ lie in the interiors
of the sides $BC$, $CA$, $AB$ respectively,
such that $\ol{DE} \perp \ol{CO}$ and $\ol{DF} \perp \ol{BO}$.
Let $K$ be the circumcenter of triangle $AFE$.
Prove that the lines $\ol{DK}$ and $\ol{BC}$ are perpendicular.
\end{mdframed}
First, note
$\dang EDF = 180\dg - \dang BOC = 180\dg - 2A$,
so $\dang FDE = 2A$.
\begin{center}
\begin{asy}
pair A = Drawing("A", dir(110), dir(110));
pair B = Drawing("B", dir(210), dir(210));
pair C = Drawing("C", dir(330), dir(330));
draw(A--B--C--cycle);
pair O = Drawing("O", origin, dir(45));
pair D = Drawing("D", 0.4*B+0.6*C, dir(-90));
pair F = Drawing("F", extension(A,B,D,foot(D,O,B)), dir(-C));
pair E = Drawing("E", extension(A,C,D,foot(D,O,C)), dir(-B));
pair K = Drawing("K", circumcenter(A,E,F), dir(90));
draw(E--D--F--cycle);
draw(E--K--F, dashed);
draw(B--O--C);
draw(D--K);
draw(circumcircle(D,E,F), dotted);
\end{asy}
\end{center}
Observe that $\dang FKE = 2A$ as well; hence $KFDE$ is cyclic.
Hence
\begin{align*}
\dang KDB &= \dang KDF + \dang FDB \\
&= \dang KEF + \left( 90\dg - \dang DBO \right) \\
&= (90\dg-A) + (90\dg-(90\dg-A)) \\
&= 90\dg.
\end{align*}
and the proof ends here.
\pagebreak
\subsection{EGMO 2012/2}
\textsl{Available online at \url{https://aops.com/community/p2658981}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n$ be a positive integer.
Find the greatest possible integer $m$, in terms of $n$,
with the following property: a table with $m$ rows and $n$ columns can be
filled with real numbers in such a manner that for any
two different rows $\left[ a_1, a_2, \dots, a_n \right]$
and $\left[ b_1, b_2, \dots, b_n \right]$ the following holds:
\[\max\left( {\left| {{a_1} - {b_1}} \right|,\left| {{a_2} - {b_2}} \right|,
\dots,\left| {{a_n} - {b_n}} \right|} \right) = 1. \]
\end{mdframed}
\paragraph{Answer.} The largest $m$ is $m(n) = 2^n$.
\paragraph{Construction.} Choose the table with all $2^n$ binary vectors.
\paragraph{Bound.}
We will proceed by induction on $n$, with the base case $n=1$ being immediate.
Take the first column, and assume the entries lie in some interval $I = [r, r+1]$.
Then the rows with first entry equal to $r$
form an $(n-1)$-table, hence at most $m(n-1)$ of them.
The rows with first entry not equal to $r$
also form an $(n-1)$-table, hence at most $m(n-1)$ of them.
So
\[ m(n) \le \underbrace{m(n-1)}_{\text{first entry $r$}}
+ \underbrace{m(n-1)}_{\text{first entry not $r$}} = 2m(n-1) \]
and we're done by induction.
\pagebreak
\subsection{EGMO 2012/3}
\textsl{Available online at \url{https://aops.com/community/p2658967}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Solve over $\RR$ the functional equation
\[ f\left( yf(x + y) + f(x) \right) = 4x + 2yf(x + y). \]
\end{mdframed}
The only solution is $f(x) \equiv 2x$ which obviously works.
Let $P(x,y)$ be the given condition. Then:
\begin{itemize}
\ii Note $P(x,0) \implies f(f(x)) = 4x$; in particular $f$ is bijective.
\begin{itemize}
\ii \dots This also implies $f(4x) = f(f(f(x))) = 4f(x)$.
\ii Taking $x=0$ gives $f(0) = 4f(0) \implies f(0) = 0$.
\end{itemize}
\ii Now $P(0,2) \implies f(2f(2)) = 4f(2) = f(8) \implies f(2) = 4$.
\ii Then $P(0,1) \implies f(f(1)) = 2f(1) \implies 4 = 2f(1) \implies f(1)=2$.
\ii Finally, $P(x,1-x)$ gives
\[ f\left( 2(1-x) + f(x) \right) = 4x + 4(1-x) = 4. \]
Since $f$ is a bijection and $f(2) = 4$, this means $2(1-x)+f(x) = 2$,
so $f(x) = 2x$ as desired.
\end{itemize}
\pagebreak
\subsection{EGMO 2012/4}
\textsl{Available online at \url{https://aops.com/community/p2658986}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A set $A$ of integers is called \emph{sum-full} if $A \subseteq A + A$.
A set $A$ of integers is said to be \emph{zero-sum-free} if $0$
is the only integer that cannot be expressed as the
sum of the elements of a finite nonempty subset of $A$.
Does there exist a sum-full zero-sum-free set of integers?
\end{mdframed}
The answer is YES, such a set exists, and is given by
\[ A = \left\{ 1, -2, 3, -5, 8, -13, 21, -34, 55, \dots \right\}. \]
To prove every number can be expressed as a
(possibly empty) subset of $A$, we have the following stronger claim.
\begin{claim*}
Let $N$ be an integer (possibly zero or negative).
Let $F$ denote the smallest Fibonacci number
which is strictly greater than $|N|$.
Then there exists a representation of $N$ as the sum of
a (possibly empty) subset of $A$,
where no element used has absolute value greater than $N$.
\end{claim*}
\begin{proof}
By induction on $|N|$.
Omitted.
\end{proof}
On the other hand, the \emph{Zeckendorf representation theorem}
implies that it's not possible to express $0$
as a nonempty subset;
such a representation would amount to an identity of the form
\[ F_{i_1} + F_{i_2} + \dots = F_{j_1} + F_{j_2} + \dots \]
where no terms on either side are consecutive,
and both sides have no common terms; and this is impossible.
\pagebreak
\section{Solutions to Day 2}
\subsection{EGMO 2012/5}
\textsl{Available online at \url{https://aops.com/community/p2659385}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
The numbers $p$ and $q$ are prime and satisfy
\[ \frac{p}{p+1} + \frac{q+1}{q} = \frac{2n}{n+2} \]
for some positive integer $n$.
Find all possible values of $q-p$.
\end{mdframed}
We clean up the numerators as
\[ \left( 1-\frac{1}{p+1} \right) + \left( 1 + \frac{1}{q} \right) = 2 - \frac{4}{n+2} \]
which simplifies as
\[ \frac{4}{n+2} = \frac{1}{p+1} - \frac{1}{q} \]
which reduces as
\[ \frac{4}{n+2} = \frac{q-p-1}{q(p+1)} \]
At this point $n$ is a free parameter.
So, this motivates us to rewrite the equation as
\[ n+2 = \frac{4q(p+1)}{(q-p)-1}. \]
This implies that $q-p-1 \mid 4q(p+1)$.
Since $n$ is positive, we have $0 < q-p-1 < q$.
Because $q$ is prime, this implies $q-p-1 \mid 4(p+1)$.
But now $q-p-1 \mid 4(p+1) + 4(q-p-1) = 4q$.
Again, $q$ is prime, so $q-p-1 \mid 4$.
This implies $q-p \in \left\{ 2,3,5 \right\}$.
It is easy to construct working examples: say $(p,q)$ is $(3,5)$, $(2,5)$ and $(2,7)$.
\pagebreak
\subsection{EGMO 2012/6, proposed by Dan Schwarz (ROU)}
\textsl{Available online at \url{https://aops.com/community/p2659392}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
There are infinitely many people registered on the social network Mugbook.
Some pairs of (different) users are registered as friends, but each person has only finitely many friends.
Every user has at least one friend.
(Friendship is symmetric; that is, if $A$ is a friend of $B$, then $B$ is a friend of $A$.)
Each person is required to designate one of their friends as their best friend.
If $A$ designates $B$ as her best friend, then (unfortunately)
it does not follow that $B$ necessarily designates $A$ as her best friend.
Someone designated as a best friend is called a $1$-best friend.
More generally, if $n> 1$ is a positive integer,
then a user is an $n$-best friend provided that they have been designated
the best friend of someone who is an $(n-1)$-best friend.
Someone who is a $k$-best friend for every positive integer $k$ is called popular.
\begin{enumerate}
\ii[(a)] Prove that every popular person is the best friend of a popular person.
\ii[(b)] Show that if people can have infinitely many friends,
then it is possible that a popular person is not the best friend of a popular person.
\end{enumerate}
\end{mdframed}
First note the following statement is true by induction:
\begin{claim*}
Someone who is an $n$-best friend is also a $k$-best friend for all $1 \le k < n$.
\end{claim*}
\begin{proof}
Induction on $(k,n)$.
\end{proof}
For part (a), suppose Dan is a popular person.
Let the friends of Dan be $P_1$, $P_2$, \dots, $P_m$.
For each $n$, one of the $P_i$'s must be an $n$-best friend.
By pigeonhole, one of the $P_i$'s is an $n$-best friend for infinitely many $n \ge 1$.
Hence be the claim above they are popular too.
For part (b), consider a social graph defined by having Dan ($D$)
and the following chains of best friends:
\begin{align*}
D &\longleftarrow P_{11} \\
D &\longleftarrow P_{21} \longleftarrow P_{22} \\
D &\longleftarrow P_{31} \longleftarrow P_{32} \longleftarrow P_{33} \\
D &\longleftarrow P_{41} \longleftarrow P_{42} \longleftarrow P_{43} \longleftarrow P_{44} \\
&\vdotswithin{\longleftarrow}
\end{align*}
Then Dan is the only popular person in the entire network.
This gives the construction promised.
\pagebreak
\subsection{EGMO 2012/7, proposed by Pierre Haas (LUX)}
\textsl{Available online at \url{https://aops.com/community/p2659395}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be an acute-angled triangle with circumcircle $\Gamma$ and orthocenter $H$. Let $K$ be a point of $\Gamma$ on the other side of $\ol{BC}$ from $A$. Let $L$ be the reflection of $K$ across $\ol{AB}$, and let $M$ be the reflection of $K$ across $\ol{BC}$. Let $E$ be the second point of intersection of $\Gamma$ with the circumcircle of triangle $BLM$. Show that the lines $KH$, $EM$ and $BC$ are concurrent.
\end{mdframed}
\begin{center}
\begin{asy}
size(9cm);
pair A = dir(110);
pair B = dir(210);
pair C = dir(330);
draw(A--B--C--cycle);
pair Ap = -B*C/A;
pair Cp = -A*B/C;
draw(A--Ap);
draw(C--Cp);
draw(unitcircle);
pair K = dir(230);
pair M = reflect(B,C)*K;
pair blah = reflect(A,B)*K;
pair L = blah;
draw(M--K--L, dotted);
pair E = IP(unitcircle, circumcircle(B, L, M));
draw(circumcircle(B, L, M));
pair H = A+B+C;
draw(H--K, red);
draw(E--Ap, red);
draw(E--L, dotted);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$A'$", Ap, dir(Ap));
dot("$C'$", Cp, dir(Cp));
dot("$K$", K, dir(K));
dot("$M$", M, dir(M));
dot("$L$", L, dir(270));
dot("$E$", E, dir(100));
dot("$H$", H, dir(45));
/* Source generated by TSQ */
\end{asy}
\end{center}
The main idea is a ``floating orthocenter'' amidst a large number of reflections.
This motivates us to reflect $H$ over $\ol{BC}$ to $A'$
and $H$ over $\ol{AB}$ to $C'$.
Then the problem is equivalent to trying to prove that
the points $E$, $M$, $A'$ are collinear.
Let $E'$ be the second intersection of line $A'M$ with $\Gamma$.
First, we claim that $E'$, $C'$, $L$ are collinear.
Note that and \[ \angle LC'B = \angle KHB = \angle MA'B = \angle E'A'B \] (using the reflections).
From here we get $\angle LC'B + \angle BC'E' = 180^{\circ}$, and
hence the collinearity is proved.
On the other hand,
\[ \angle LBM =
2\left( \angle KBA - KBC \right)
= 2 \angle B \]
and
\[ \angle C'E'A' = 180 -2 \angle B. \]
So $L$, $B$, $M$, $E'$ are cyclic as desired.
\pagebreak
\subsection{EGMO 2012/8, proposed by Dan Schwarz (ROU)}
\textsl{Available online at \url{https://aops.com/community/p2659401}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A word is a finite sequence of letters from some alphabet.
A word is \emph{repetitive} if it is a concatenation of at least two identical subwords
(for example, $ababab$ and $abcabc$ are repetitive, but $ababa$ and $aabb$ are not).
Prove that if a word has the property that swapping any two adjacent letters
makes the word repetitive, then all its letters are identical.
(Note that one may swap two adjacent identical letters, leaving a word unchanged.)
\end{mdframed}
A word with the property that swapping any two adjacent letters
makes the word repetitive, but for which all letters the same,
will called a \emph{unicorn}.
The problem asks to show there are no unicorns.
So assume for contradiction there exists a unicorn.
We proceed in three steps.
\paragraph{Step 1. Reduction to binary alphabet.}
In the alphabet, choose one letter (that appears in the unicorn) to be $0$
and replace all the letters with $1$.
The resulting word is still a unicorn on the two symbols $\{0,1\}$.
In this way we only need to consider the problem for the alphabet $\Sigma = \{0,1\}$.
\paragraph{Step 2. Unicorns are repetitive themselves.}
So let $w \in \Sigma^n$ be a unicorn.
It's easy to see that $w = 010101\dotsm$ is not a unicorn;
if we swap the first two fits, the resulting word
$100101\dotsm$ has a doubled $00$ that appears only once, so it is not a unicorn.
Similarly, $w = 101010\dotsm$ is not a unicorn.
Hence, we may assume our unicorn $w$ has at least two adjacent bits equal.
This means that $w$ is itself repetitive.
\paragraph{Step 3. Main argument.}
From now on let $w[i]$ denote the $i$\ts{th} letter of $w$.
Fix an index $1 \le k < n/2$ for which $w[k] \neq w[k+1]$.
Let $w'$ be the word that results from swapping the unequal bits,
so $w'[k] = w[k+1]$ and $w'[k+1] = w[k]$.
Now $w$ is repetitive, and so is $w'$;
so there should exist integers $p \le n/2$ and $q \le n/2$ dividing $n$ (the \emph{periods})
such that the identities
\[
w[i] = w[i+p] \quad \forall 1 \le i \le n-p; \qquad
w'[i] = w'[i+q] \quad \forall 1 \le i \le n-q.
\]
We may assume $p$ and $q$ are different and don't divide each other.
We will now produce a contradiction in two cases.
\begin{itemize}
\ii Consider the case $\gcd(p,q) = 1$.
Then, the number of $1$'s in $w$ ought to be a multiple of $n/p$,
because $w$ consists of $n/p$ repetitions of some word.
Similarly, the number of $1$'s in $w'$ ought to be a multiple of $n/q$.
But these numbers are equal.
So the number of $1$'s is a multiple of both $n/p$ and $n/q$.
When $\gcd(p,q) = 1$, this can only occur if the numbers $1$'s is divisible by $n$,
i.e.\ $w = 0 \dots 0$ or $w = 1 \dots 1$.
Then $w$ is not in fact a unicorn.
\ii Otherwise, let $d = \gcd(p,q) > 1$.
Choose the index $i = k$ to start.
In a \emph{move} we update the index as follows:
\begin{itemize}
\ii If $i + p < n$, replace $i$ with $i + p$.
\ii Otherwise, replace $i$ with $i - q$.
\ii Repeat this until $i \equiv k \pmod q$ again for the first time.
\end{itemize}
This process is well defined since $p$ and $q$ are different and less than $n/2$.
This creates a sequence
\[ k = i_0, i_1, i_2, \dots, i_m \]
with the property that the values of $w$ and $w'$ at all indices
except the ends are equal.
(The assumption $d > 1$ means that all $i_\bullet$ are $k \pmod d$,
so this sequence never contains $k+1$.)
Following the chain then creates a contradiction,
because we started at $w[k]$ and ended at $w'[i_m] = w'[k] \neq w[k]$ following only equalities.
\end{itemize}
A cartoon is shown below for $p = 9$, $q = 6$, $n = 18$, $k = 2$.
\begin{center}
\begin{asy}
size(12cm);
for (int i=1; i<=18; ++i) {
dot("$" + ((string)(i)) + "$", (i,0), dir(-90));
}
void draw_arr(int x, int y, pen p) {
draw((x,0)..((x+y)/2, (y-x)/5)..(y,0), p, EndArrow(TeXHead), Margins);
}
draw_arr(2,11, deepgreen);
draw_arr(11,5, red);
draw_arr(5,14, deepgreen);
draw_arr(14,8, red);
draw_arr(8,2, red);
label("$w$", (0,-2), blue);
label("$w'$", (0,-3), blue);
draw(box((0.6,-1.6), (9.4,-2.4)), deepgreen);
draw(box((9.6,-1.6), (18.4,-2.4)), deepgreen);
draw(box((0.6,-2.6), (6.4,-3.4)), red);
draw(box((6.6,-2.6), (12.4,-3.4)), red);
draw(box((12.6,-2.6), (18.4,-3.4)), red);
label("$\mathbf{0}$", (2,-2), blue);
label("$\mathbf{1}$", (3,-2), blue);
label("$\mathbf{1}$", (2,-3), blue);
label("$\mathbf{0}$", (3,-3), blue);
label("$0$", (11,-2), blue);
label("$0$", (11,-3), blue);
label("$0$", (5,-2), blue);
label("$0$", (5,-3), blue);
label("$0$", (14,-2), blue);
label("$0$", (14,-3), blue);
label("$0$", (8,-2), blue);
label("$0$", (8,-3), blue);
\end{asy}
\end{center}
\begin{remark*}
[The smart solution]
An alternative clever way to do this last part is using roots of unity.
The idea is to show that in our binary language,
if $S$ is the subset of indices with $1$'s among $\{1, \dots, n\}$,
then every repetitive word satisfies
\[ \sum_{s \in S} \exp\left( \frac{2\pi n}{s} \right) = 0. \]
(The converse is not true.)
Hence a repetitive unicorn cannot exist;
swapping \emph{any} two adjacent indices with unequal bits makes the sum change.
(The proof earlier shows this too, since we only used one value of $k$.)
\end{remark*}
\pagebreak
\end{document}