% © 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{IMO 2009 Solution Notes}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2009 IMO.
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, k \ge 2$ be positive integers and let $a_1$, $a_2$, $a_3$, \dots, $a_k$
be distinct integers in the set $\left\{ 1,2,\dots,n \right\}$
such that $n$ divides $a_i(a_{i+1} - 1)$ for $i = 1,2,\dots,k-1$.
Prove that $n$ does not divide $a_k(a_1 - 1)$.

\item %% Problem 2
Let $ABC$ be a triangle with circumcenter $O$.
The points $P$ and $Q$ are interior points of the sides $CA$ and $AB$ respectively.
Let $K$, $L$, $M$ be the midpoints of $\ol{BP}$, $\ol{CQ}$, $\ol{PQ}$,
respectively, and let $\Gamma$ be the circumcircle of $\triangle KLM$.
Suppose that $\ol{PQ}$ is tangent to $\Gamma$. Prove that $OP = OQ$.

\item %% Problem 3
Suppose that $s_1,s_2,s_3, \dotsc$ is a strictly increasing sequence of
positive integers such that the sub-sequences
$s_{s_1}$, $s_{s_2}$, $s_{s_3}$, \dots
and $s_{s_1 + 1}$, $s_{s_2 + 1}$, $s_{s_3 + 1}$, \dots
are both arithmetic progressions.
Prove that the sequence $s_1$, $s_2$, $s_3$, \dots\ is itself an arithmetic progression.

\item %% Problem 4
Let $ABC$ be a triangle with $AB = AC$.
The angle bisectors of $\angle CAB$ and $\angle ABC$
meet the sides $BC$ and $CA$ at $D$ and $E$, respectively.
Let $K$ be the incenter of triangle $ADC$.
Suppose that $\angle BEK = 45^\circ$.
Find all possible values of $\angle CAB$.

\item %% Problem 5
Find all functions $f \colon \ZZ_{>0} \to \ZZ_{>0}$
such that for positive integers $a$ and $b$, the numbers
\[ a, \qquad f(b), \qquad f(b+f(a)-1) \]
are the sides of a non-degenerate triangle.

\item %% Problem 6
Let $a_1$, $a_2$, \dots, $a_n$ be distinct positive integers and
let $M$ be a set of $n-1$ positive integers not containing $s = a_1 + \dots + a_n$.
A grasshopper is to jump along the real axis, starting at the point $0$ and
making $n$ jumps to the right with lengths $a_1$, $a_2$, \dots, $a_n$ in some order.
Prove that the order can be chosen in such a way that
the grasshopper never lands on any point in $M$.

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{IMO 2009/1, proposed by Ross Atkins (AUS)}
\textsl{Available online at \url{https://aops.com/community/p1561571}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n, k \ge 2$ be positive integers and let $a_1$, $a_2$, $a_3$, \dots, $a_k$
be distinct integers in the set $\left\{ 1,2,\dots,n \right\}$
such that $n$ divides $a_i(a_{i+1} - 1)$ for $i = 1,2,\dots,k-1$.
Prove that $n$ does not divide $a_k(a_1 - 1)$.
\end{mdframed}
We proceed indirectly and assume that
\[ a_i (a_{i+1}-1) \equiv 0 \pmod n \]
for $i = 1, \dots, k$ (indices taken modulo $k$).
We claim that this implies all the $a_i$ are equal modulo $n$.

Let $q = p^e$ be any prime power dividing $n$.
Then, $a_1 (a_2 - 1) \equiv 0 \pmod q$, so $p$ divides either $a_1$ or $a_2$.
\begin{itemize}
  \ii If $p \mid a_1$, then $p \nmid a_1 - 1$. Then
  \[ a_k (a_1-1) \equiv 0 \pmod q \implies a_k \equiv 0 \pmod q. \]
  In particular, $p \mid a_k$.
  So repeating this argument,
  we get $a_{k-1} \equiv 0 \pmod q$, $a_{k-2} \equiv 0 \pmod q$, and so on.

  \ii Similarly, if $p \mid a_2 - 1$ then $p \nmid a_2$, and
  \[ a_2 (a_3-1) \equiv 0 \pmod q \implies a_3 \equiv 1 \pmod q.  \]
  In particular, $p \mid a_3 - 1$.
  So repeating this argument,
  we get $a_4 \equiv 0 \pmod q$, $a_5 \equiv 0 \pmod q$, and so on.
\end{itemize}
Either way, we find $a_i \pmod q$ is constant (and either $0$ or $1$).

Since $q$ was an arbitrary prime power dividing $n$,
by Chinese remainder theorem we conclude that $a_i \pmod n$ is constant as well.
But this contradicts the assumption of distinctness.
\pagebreak

\subsection{IMO 2009/2, proposed by Sergei Berlov (RUS)}
\textsl{Available online at \url{https://aops.com/community/p1561572}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a triangle with circumcenter $O$.
The points $P$ and $Q$ are interior points of the sides $CA$ and $AB$ respectively.
Let $K$, $L$, $M$ be the midpoints of $\ol{BP}$, $\ol{CQ}$, $\ol{PQ}$,
respectively, and let $\Gamma$ be the circumcircle of $\triangle KLM$.
Suppose that $\ol{PQ}$ is tangent to $\Gamma$. Prove that $OP = OQ$.
\end{mdframed}
By power of a point, we have $-AQ \cdot QB = OQ^2 - R^2$
and $-AP \cdot PC = OP^2 - R^2$.
Therefore, it suffices to show $AQ \cdot QB = AP \cdot PC$.

\begin{center}
\begin{asy}
pair A = dir(70);
pair B = dir(210);
pair C = dir(330);

pair P = 0.4*A+0.6*C;
pair Q = 0.25*B+0.75*A;

filldraw(A--B--C--cycle, opacity(0.2)+lightred, red);
pair M = midpoint(P--Q);
pair K = midpoint(P--B);
pair L = midpoint(Q--C);

filldraw(circumcircle(M, K, L), opacity(0.3)+lightcyan, blue);
draw(P--Q, heavygreen+1);
draw(B--P, heavygreen);
draw(C--Q, heavygreen);

filldraw(K--M--L--cycle, opacity(0.4)+cyan, heavycyan);

dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$P$", P, dir(P));
dot("$Q$", Q, dir(120));
dot("$M$", M, dir(M));
dot("$K$", K, dir(K));
dot("$L$", L, dir(20));

/* TSQ Source:

A = dir 70
B = dir 210
C = dir 330

P = 0.4*A+0.6*C
Q = 0.25*B+0.75*A R120

A--B--C--cycle 0.2 lightred / red
M = midpoint P--Q
K = midpoint P--B
L = midpoint Q--C R20

circumcircle M K L 0.3 lightcyan / blue
P--Q heavygreen+1
B--P heavygreen
C--Q heavygreen

K--M--L--cycle 0.4 cyan / heavycyan

*/
\end{asy}
\end{center}

As $\ol{ML} \parallel \ol{AC}$ and $\ol{MK} \parallel \ol{AB}$ we have that
\begin{align*}
  \dang APQ &= \dang LMP = \dang LKM \\
  \dang PQA &= \dang KMQ = \dang MLK
\end{align*}
and consequently we have the (opposite orientation) similarity
\[ \triangle APQ \overset{-}{\sim} \triangle MKL. \]
Therefore
\[ \frac{AQ}{AP} = \frac{ML}{MK} = \frac{2ML}{2MK} = \frac{PC}{QB} \]
id est $AQ \cdot QB = AP \cdot PC$, which is what we wanted to prove.
\pagebreak

\subsection{IMO 2009/3, proposed by Gabriel Carroll (USA)}
\textsl{Available online at \url{https://aops.com/community/p1561573}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Suppose that $s_1,s_2,s_3, \dotsc$ is a strictly increasing sequence of
positive integers such that the sub-sequences
$s_{s_1}$, $s_{s_2}$, $s_{s_3}$, \dots
and $s_{s_1 + 1}$, $s_{s_2 + 1}$, $s_{s_3 + 1}$, \dots
are both arithmetic progressions.
Prove that the sequence $s_1$, $s_2$, $s_3$, \dots\ is itself an arithmetic progression.
\end{mdframed}
We present two solutions.

\paragraph{First solution (Alex Zhai).}
Let $s(n) \coloneqq s_n$ and write
\begin{align*}
  s(s(n)) &= Dn + A \\
  s(s(n)+1) &= D'n + B.
\end{align*}
In light of the bounds $s(s(n)) \le s(s(n)+1) \le s(s(n+1))$
we right away recover $D = D'$ and $A \le B$.

Let $d_n = s(n+1)-s(n)$.
Note that $\sup d_n < \infty$ since $d_n$ is bounded above by $A$.

Then we let
\[ m \coloneqq \min d_n, \qquad M \coloneqq \max d_n. \]
Now suppose $a$ achieves the maximum, meaning $s(a+1)-s(a) = M$.
Then
\begin{align*}
  \underbrace{d_{s(s(a))} + \dots + d_{s(s(a+1))-1}}_{D \text{ terms}}
  &= \boxed{s(s(s(a+1))) - s(s(s(a)))} \\
  &= (D \cdot s(a+1) + A) - (D \cdot s(a) + A) = DM.
\end{align*}
Now $M$ was maximal hence $M = d_{s(s(a))} = \dots = d_{s(s(a+1))-1}$.
But $d_{s(s(a))} = B-A$ is a constant.
Hence $M = B-A$.
In the same way $m = B-A$ as desired.

\paragraph{Second solution.}
We retain the notation $D$, $A$, $B$ above,
as well as $m = \min_n s(n+1)-s(n) \ge B-A$.
We do the involution trick first as:
\[ D = \boxed{s(s(s(n)+1)) - s(s(s(n)))} = s(Dn+B) - s(Dn+A) \]
and hence we recover $D \ge m(B-A)$.

The edge case $D = B-A$ is easy since then $m=1$
and $D = s(Dn+B)-s(Dn+A)$ forces $s$ to be a constant shift.
So henceforth assume $D > B-A$.

The idea is that right now the $B$ terms are ``too big'',
so we want to use the involution trick in a way that makes as many
``$A$ minus $B$'' shape expressions as possible.
This motivates considering $s(s(s(n+1))) - s(s(s(n)+1)+1) > 0$,
since the first expression will have all $A$'s
and the second expression will have all $B$'s.
Calculation gives:
\begin{align*}
  s(D(n+1)+A) - s(Dn+B+1)
  &= \boxed{s(s(s(n+1))) - s(s(s(n)+1)+1)} \\
  &= (Ds(n+1) + A) - (D(s(n)+1) + B) \\
  &= D\left( s(n+1)-s(n) \right) + A-B-D.
\end{align*}
Then by picking $n$ achieving the minimum $m$,
\[ \underbrace{m(D+A-B-1)}_{>0} \le s(s(s(n+1))) - s(s(s(n)+1)+1) \le Dm + A-B-D \]
which becomes
\[ \left( D-m(B-A) \right) + \left( (B-A)-m \right) \le 0. \]
Since both of these quantities were supposed to be nonnegative,
we conclude $m = B-A$ and $D = m^2$.
Now the estimate $D = s(Dn+B) - s(Dn+A) \ge m(B-A)$ is actually sharp,
so it follows that $s(n)$ is arithmetic.
\pagebreak

\section{Solutions to Day 2}
\subsection{IMO 2009/4, proposed by Hojoo Lee, Peter Vandendriessche, Jan Vonk (BEL)}
\textsl{Available online at \url{https://aops.com/community/p1562847}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a triangle with $AB = AC$.
The angle bisectors of $\angle CAB$ and $\angle ABC$
meet the sides $BC$ and $CA$ at $D$ and $E$, respectively.
Let $K$ be the incenter of triangle $ADC$.
Suppose that $\angle BEK = 45^\circ$.
Find all possible values of $\angle CAB$.
\end{mdframed}
Here is the solution presented in my book \emph{EGMO}.

Let $I$ be the incenter of $ABC$,
and set $\angle DAC = 2x$ (so that $0\dg < x < 45\dg$).
From $\angle AIE = \angle DIC$, it is easy to compute
\[
  \angle KIE = 90\dg - 2x, \;
  \angle ECI = 45\dg -x, \;
  \angle IEK = 45\dg, \;
  \angle KEC = 3x. \]
Having chased all the angles we want, we need a relationship.
We can find it by considering the side ratio $\frac{IK}{KC}$.
Using the angle bisector theorem,
we can express this in terms of triangle $IDC$;
however we can also express it in terms of triangle $IEC$.


\begin{center}
  \begin{asy}
    size(7cm);
    pair A = Drawing("A", (0,7), dir(90));
    pair C = Drawing("C", (3,0), dir(-45));
    pair B = Drawing("B", -C, dir(225));
    draw(A--B--C--cycle);
    pair I = incenter(A,B,C);
    pair D = Drawing("D", origin, dir(-90));
    pair E = Drawing("E", extension(B,I,A,C), dir(45));
    pair K = Drawing("K", incenter(A,D,C), dir(-30));
    draw(A--D--K);
    draw(B--E--K);
    draw(incircle(A,D,C));
    markangle(9.0,B,E,K);
  \end{asy}
  \quad
  \begin{asy}
    pair A = Drawing("A", (0,5), dir(90));
    pair C = Drawing("C", (3,0), dir(-45));
    pair B = -C;
    pair D = Drawing("D", origin, dir(-90));
    pair I = Drawing("I", incenter(A,B,C), dir(180));
    pair E = Drawing("E", extension(B,I,A,C), dir(45));
    pair K = Drawing("K", incenter(A,D,C), 1.3*dir(-90));
    draw(A--D--C--cycle);
    draw(C--I--E--K);
    draw(D--K);
    MP("2x", A, dir(K-A)*8);
    MP(rotate(-35)*"45^{\circ}-x", C+dir(130)*1.2);
    MP(rotate(-10)*"45^{\circ}-x", C+dir(155));
    MP("45^{\circ}", E, dir(240)*6);
    MP("3x", E, dir(-80)*6);
    markangle(9.0,D,I,C);
    markangle(9.0,E,I,A);
  \end{asy}
\end{center}

By the law of sines, we obtain
\[ \frac{IK}{KC} = \frac%
  {\sin 45\dg \cdot \frac{EK}{\sin \left( 90\dg - 2x \right)}}%
  {\sin \left( 3x \right) \cdot \frac{EK}{\sin \left( 45\dg-x \right)}}
  = \frac{\sin 45\dg \sin \left( 45\dg - x \right)}%
  {\sin \left( 3x \right) \sin \left( 90\dg - 2x \right)}. \]
Also, by the angle bisector theorem on $\triangle IDC$,
we have
\[ \frac{IK}{KC} = \frac{ID}{DC}
  = \frac{\sin \left( 45\dg-x \right)}{\sin\left( 45\dg+x \right)}. \]
Equating these and cancelling $\sin \left( 45\dg-x \right) \neq 0$ gives
\[ \sin 45\dg \sin \left( 45\dg + x \right)
  = \sin 3x \sin \left( 90\dg - 2x \right). \]

Applying the product-sum formula
(again, we are just trying to break down things as much as possible),
this just becomes
\[ \cos\left( x \right) - \cos \left( 90\dg + x \right)
  = \cos \left( 5x-90\dg \right) - \cos \left( 90\dg+x \right) \]
or $\cos x = \cos \left( 5x-90\dg \right)$.

At this point we are basically done;
the rest is making sure we do not miss any solutions
and write up the completion nicely.
One nice way to do this is by using product-sum in reverse as
\[ 0 = \cos \left( 5x-90\dg \right) - \cos x
  = 2 \sin \left( 3x - 45\dg \right) \sin \left( 2x-45\dg \right). \]
This way we merely consider the two cases
\[ \sin \left( 3x-45\dg \right) = 0 \text{ and }
  \sin \left( 2x - 45\dg \right) = 0. \]
Notice that $\sin\theta = 0$ if and only $\theta$
is an integer multiple of $180\dg$.
Using the bound $0\dg < x < 45\dg$,
it is easy to see that that the permissible values of $x$
are $x = 15\dg$ and $x = \frac{45}{2}\dg$.
As $\angle A = 4x$, this corresponds to $\angle A = 60\dg$
and $\angle A = 90\dg$, which can be seen to work.
\pagebreak

\subsection{IMO 2009/5, proposed by Bruno Le Floch (FRA)}
\textsl{Available online at \url{https://aops.com/community/p1562848}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all functions $f \colon \ZZ_{>0} \to \ZZ_{>0}$
such that for positive integers $a$ and $b$, the numbers
\[ a, \qquad f(b), \qquad f(b+f(a)-1) \]
are the sides of a non-degenerate triangle.
\end{mdframed}
The only function is the identity function (which works).
We prove it is the only one.

Let $P(a,b)$ denote the given statement.

\begin{claim*}
  We have $f(1) = 1$, and $f(f(n)) = n$.
  (In particular $f$ is a bijection.)
\end{claim*}
\begin{proof}
  Note that \[ P(1,b) \implies f(b) = f(b+f(1)-1). \]
  Otherwise, the function $f$ is periodic modulo $N = f(1)-1 \ge 1$.
  This is impossible since we can fix $b$ and let $a$ be arbitrarily
  large in some residue class modulo $N$.

  Hence $f(1)=1$, so taking $P(n,1)$ gives $f(f(n)) = n$.
\end{proof}

\begin{claim*}
  Let $\delta = f(2)-1 > 0$.
  Then for every $n$,
  \[ f(n+1) = f(n) + \delta
    \quad\text{ or }\quad f(n-1) = f(n) + \delta \]
\end{claim*}
\begin{proof}
  Use
  \[ P(2, f(n)) \implies n-2 < f( f(n) + \delta ) < n+2. \]
  Let $y = f(f(n)+\delta)$, hence $n-2 < y < n+2$
  and $f(y) = f(n)+\delta$.
  But, remark that if $y = n$, we get $\delta = 0$, contradiction.
  So $y \in \{n+1, n-1\}$ and that is all.
\end{proof}

We now show $f$ is an arithmetic progression
with common difference $+\delta$.
Indeed we already know $f(1) = 1$ and $f(2) = 1+\delta$.
Now suppose $f(1)=1$, \dots, $f(n) = 1 + (n-1)\delta$.
Then by induction for any $n \ge 2$,
the second case can't hold,
so we have $f(n+1) = f(n)+\delta$, as desired.

Combined with $f(f(n)) = n$, we recover that $f$ is the identity.
\pagebreak

\subsection{IMO 2009/6, proposed by Dmitry Khramtsov (RUS)}
\textsl{Available online at \url{https://aops.com/community/p1562840}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $a_1$, $a_2$, \dots, $a_n$ be distinct positive integers and
let $M$ be a set of $n-1$ positive integers not containing $s = a_1 + \dots + a_n$.
A grasshopper is to jump along the real axis, starting at the point $0$ and
making $n$ jumps to the right with lengths $a_1$, $a_2$, \dots, $a_n$ in some order.
Prove that the order can be chosen in such a way that
the grasshopper never lands on any point in $M$.
\end{mdframed}
The proof is by induction on $n$.
Assume $a_1 < \dots < a_n$ and call each element of $M$ a \emph{mine}.
Let $x = s - a_n$.
We consider four cases, based on whether $x$ has a mine
and whether there is a mine past $x$.
\begin{itemize}
  \ii If $x$ has no mine, and there is a mine past $x$,
  then at most $n-2$ mines in $[0, x]$ and so we use induction to reach $x$,
  then leap from $x$ to $s$ and win.

  \ii If $x$ has no mine but there is also no mine to the right of $x$,
  then let $m$ be the maximal mine.
  By induction hypothesis on $M \setminus \{m\}$, there is a path to $x$
  using $\{a_1, \dots, a_{n-1}\}$ which avoids mines except possibly $m$.
  If the path hits the mine $m$ on the hop of length $a_k$,
  we then swap that hop with $a_n$, and finish.

  \ii If $x$ has a mine, but there are no mines to the right of $x$,
  we can repeat the previous case with $m = x$.

  \ii Now suppose $x$ has a mine, \emph{and} there is a mine past $x$.
  There should exist an integer $1 \le i \le n-1$
  such that $s-a_i$ and $y = s-a_i-a_n$ both have no mine.
  By induction hypothesis, we can then reach $y$ in $n-2$ steps
  (as there are two mines to the right of $y$); then $y \to s-a_i \to s$ finishes.
\end{itemize}

\begin{remark*}
  It seems much of the difficulty of the problem is
  realizing induction will actually work.
  Attempts at induction are, indeed, a total minefield (ha!),
  and given the position P6 of the problem,
  it is expected that many contestants will abandon
  induction after some cursory attempts fail.
\end{remark*}
\pagebreak


\end{document}
