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

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2013 JMO.
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
Are there integers $a$ and $b$
such that $a^5b+3$ and $ab^5+3$
are both perfect cubes of integers?

\item %% Problem 2
Each cell of an $m\times n$ board is filled with some nonnegative integer.
Two numbers in the filling are said to be
\emph{adjacent} if their cells share a common side.
The filling is called a \emph{garden} if it
satisfies the following two conditions:
\begin{enumerate}
  \item[(i)] The difference between
    any two adjacent numbers is either $0$ or $1$.
  \item[(ii)] If a number is less than or equal to
    all of its adjacent numbers, then it is equal to $0$.
\end{enumerate}
Determine the number of distinct gardens in terms of $m$ and $n$.

\item %% Problem 3
In triangle $ABC$,
points $P$, $Q$, $R$ lie on sides $BC$, $CA$, $AB$, respectively.
Let $\omega_A$, $\omega_B$, $\omega_C$ denote the
circumcircles of triangles $AQR$, $BRP$, $CPQ$, respectively.
Given the fact that segment $AP$ intersects
$\omega_A$, $\omega_B$, $\omega_C$ again at $X$, $Y$, $Z$ respectively,
prove that $YX/XZ=BP/PC$.

\item %% Problem 4
Let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$,
where we keep track of the order of the summation.
For example, $f(4)=6$ because $4$ can be written
as $4$, $2+2$, $2+1+1$, $1+2+1$, $1+1+2$, and $1+1+1+1$.
Find the smallest $n$ greater than $2013$ for which $f(n)$ is odd.

\item %% Problem 5
Quadrilateral $XABY$ is inscribed in the semicircle $\omega$ with
diameter $\ol{XY}$.
Segments $AY$ and $BX$ meet at $P$.
Point $Z$ is the foot of the perpendicular from $P$ to line $\ol{XY}$.
Point $C$ lies on $\omega$ such that line $XC$ is perpendicular to line $AZ$.
Let $Q$ be the intersection of segments $AY$ and $XC$.
Prove that
\[\dfrac{BY}{XP}+\dfrac{CY}{XQ}=\dfrac{AY}{AX}.\]

\item %% Problem 6
Find all real numbers $x,y,z \ge 1$ satisfying
\[ \min \left( \sqrt{x+xyz}, \sqrt{y+xyz}, \sqrt{z+xyz} \right)
  = \sqrt{x-1} + \sqrt{y-1} + \sqrt{z-1}. \]

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{JMO 2013/1, proposed by Titu Andreescu}
\textsl{Available online at \url{https://aops.com/community/p3041819}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Are there integers $a$ and $b$
such that $a^5b+3$ and $ab^5+3$
are both perfect cubes of integers?
\end{mdframed}
No, there do not exist such $a$ and $b$.

We prove this in two cases.
\begin{itemize}
  \ii Assume $3 \mid ab$.
  WLOG we have $3 \mid a$,
  but then $a^5b+3 \equiv 3 \pmod 9$, contradiction.

  \ii Assume $3 \nmid ab$.
  Then $a^5b+3$ is a cube not divisible by $3$,
  so it is $\pm 1 \bmod 9$,
  and we conclude
  \[ a^5b \in \{5,7\} \pmod 9. \]
  Analogously \[ ab^5 \in \{5,7\} \pmod 9. \]
  We claim however these two equations cannot hold simultaneously.
  Indeed $(ab)^6 \equiv 1 \pmod 9$ by Euler's theorem,
  despite $5 \cdot 5 \equiv 7$, $5 \cdot 7 \equiv 8$,
  $7 \cdot 7 \equiv 4$ mod $9$.
\end{itemize}
\pagebreak

\subsection{JMO 2013/2, proposed by Sungyoon Kim}
\textsl{Available online at \url{https://aops.com/community/p3041818}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Each cell of an $m\times n$ board is filled with some nonnegative integer.
Two numbers in the filling are said to be
\emph{adjacent} if their cells share a common side.
The filling is called a \emph{garden} if it
satisfies the following two conditions:
\begin{enumerate}
  \item[(i)] The difference between
    any two adjacent numbers is either $0$ or $1$.
  \item[(ii)] If a number is less than or equal to
    all of its adjacent numbers, then it is equal to $0$.
\end{enumerate}
Determine the number of distinct gardens in terms of $m$ and $n$.
\end{mdframed}
The numerical answer is $2^{mn}-1$.
But we claim much more, by giving an explicit description of all gardens:
\begin{quote}
  Let $S$ be any nonempty subset of the $mn$ cells.
  Suppose we fill each cell $\theta$
  with the minimum (taxicab) distance
  from $\theta$ to some cell in $S$
  (in particular, we write $0$ if $\theta \in S$).
  Then
  \begin{itemize}
    \ii This gives a garden, and
    \ii All gardens are of this form.
  \end{itemize}
\end{quote}
Since there are $2^{mn}-1$ such nonempty subsets $S$,
this would finish the problem.
An example of a garden with $|S| = 3$ is shown below.
\[
  \begin{bmatrix}
    2 & 1 & 2 & 1 & \mathbf{\color{red}0} & 1 \\
    1 & \mathbf{\color{red}0} & 1 & 2 & 1 & 2 \\
    1 & 1 & 2 & 3 & 2 & 3 \\
    \mathbf{\color{red}0} & 1 & 2 & 3 & 3 & 4 \\
  \end{bmatrix}
\]

It is actually fairly easy to see that this
procedure always gives a garden;
so we focus our attention on showing that every
garden is of this form.

Given a garden, note first that it has at least
one cell with a zero in it --- by considering
the minimum number across the entire garden.
Now let $S$ be the (thus nonempty) set of
cells with a zero written in them.
We contend that this works, i.e.\ the following sentence holds:
\begin{claim*}
  If a cell $\theta$ is labeled $d$,
  then the minimum distance from that cell
  to a cell in $S$ is $d$.
\end{claim*}
\begin{proof}
  The proof is by induction on $d$, with $d = 0$ being by definition.
  Now, consider any cell $\theta$ labeled $d \ge 1$.
  Every neighbor of $\theta$ has label at least $d-1$,
  so any path will necessarily take $d-1$ steps after leaving $\theta$.
  Conversely, there is \emph{some} $d-1$ adjacent to $\theta$ by (ii).
  Stepping on this cell and using the minimal path
  (by induction hypothesis) gives us a path to
  a cell in $S$ with length \emph{exactly} $d$.
  So the shortest path does indeed have distance $d$, as desired.
\end{proof}
\pagebreak

\subsection{JMO 2013/3, proposed by Zuming Feng}
\textsl{Available online at \url{https://aops.com/community/p3041822}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
In triangle $ABC$,
points $P$, $Q$, $R$ lie on sides $BC$, $CA$, $AB$, respectively.
Let $\omega_A$, $\omega_B$, $\omega_C$ denote the
circumcircles of triangles $AQR$, $BRP$, $CPQ$, respectively.
Given the fact that segment $AP$ intersects
$\omega_A$, $\omega_B$, $\omega_C$ again at $X$, $Y$, $Z$ respectively,
prove that $YX/XZ=BP/PC$.
\end{mdframed}
Let $M$ be the concurrence point of
$\omega_A$, $\omega_B$, $\omega_C$
(by Miquel's theorem).


\begin{center}
  \begin{asy}
    size(8cm);
    defaultpen(fontsize(9pt));
    pair A = dir(110);
    pair B = dir(210);
    pair C = dir(330);
    pair P = 0.4*B+0.6*C;
    pair Q = 0.4*C+0.6*A;
    pair R = 0.7*A+0.3*B;
    draw(B--A--C);

    draw(circumcircle(A, Q, R), blue);
    draw(circumcircle(B, R, P), blue);
    draw(circumcircle(C, P, Q), blue);

    pair O_A = circumcenter(A, Q, R);
    pair O_B = circumcenter(B, R, P);
    pair O_C = circumcenter(C, P, Q);

    pair M = -P+2*foot(P, O_B, O_C);
    pair X = -A+2*foot(O_A, A, P);
    pair Y = -P+2*foot(O_B, A, P);
    pair Z = -P+2*foot(O_C, A, P);

    draw(X--M--P, dotted);
    draw(R--Q);
    draw(A--Y);
    draw(Z--P);

    draw(B--C, red);
    draw(Y--Z, red);

    dot("$A$", A, dir(A));
    dot("$B$", B, dir(B));
    dot("$C$", C, dir(C));
    dot("$P$", P, dir(P));
    dot("$Q$", Q, dir(Q));
    dot("$R$", R, dir(R));
    dot("$M$", M, dir(-90));
    dot("$X$", X, dir(225));
    dot("$Y$", Y, dir(45));
    dot("$Z$", Z, dir(180));

    /* Source generated by TSQ
    A = dir 110
    B = dir 210
    C = dir 330
    P = 0.4*B+0.6*C
    Q = 0.4*C+0.6*A
    R = 0.7*A+0.3*B
    B--A--C

    circumcircle A Q R blue
    circumcircle B R P blue
    circumcircle C P Q blue

    O_A := circumcenter A Q R
    O_B := circumcenter B R P
    O_C := circumcenter C P Q

    M = -P+2*foot P O_B O_C R-90
    X = -A+2*foot O_A A P R225
    Y = -P+2*foot O_B A P R45
    Z = -P+2*foot O_C A P R180

    X--M--P dotted
    R--Q
    A--Y
    Z--P

    B--C red
    Y--Z red
    */
  \end{asy}
\end{center}


Then $M$ is the center of a spiral similarity sending
$\ol{YZ}$ to $\ol{BC}$.
So it suffices to show that this spiral similarity
also sends $X$ to $P$, but
\[ \dang MXY = \dang MXA = \dang MRA = \dang MRB = \dang MPB \]
so this follows.
\pagebreak

\section{Solutions to Day 2}
\subsection{JMO 2013/4, proposed by Kiran Kedlaya}
\textsl{Available online at \url{https://aops.com/community/p3043748}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$,
where we keep track of the order of the summation.
For example, $f(4)=6$ because $4$ can be written
as $4$, $2+2$, $2+1+1$, $1+2+1$, $1+1+2$, and $1+1+1+1$.
Find the smallest $n$ greater than $2013$ for which $f(n)$ is odd.
\end{mdframed}
The answer is $2047$.

For convenience, we agree that $f(0) = 1$.
Then by considering cases on the first number in the representation,
we derive the recurrence
\[ f(n) = \sum_{k=0}^{\left\lfloor \log_2 n \right\rfloor} f(n-2^k).
  \qquad (\heartsuit) \]

We wish to understand the parity of $f$. The first few values are
\begin{align*}
  f(0) &= 1 \\
  f(1) &= 1 \\
  f(2) &= 2 \\
  f(3) &= 3 \\
  f(4) &= 6 \\
  f(5) &= 10 \\
  f(6) &= 18 \\
  f(7) &= 31.
\end{align*}

Inspired by the data we make the key claim that
\begin{claim*}
  $f(n)$ is odd if and only if $n+1$ is a power of $2$.
\end{claim*}
\begin{proof}
  We call a number \emph{repetitive} if it is zero or its binary representation
  consists entirely of $1$'s.
  So we want to prove that $f(n)$ is odd if and only if $n$ is repetitive.

  This only takes a few cases:
  \begin{itemize}
  \ii If $n = 2^k$, then $(\heartsuit)$
  has exactly two repetitive terms on the right-hand side, namely $0$ and $2^k-1$.

  \ii If $n = 2^k + 2^\ell - 1$, then $(\heartsuit)$
  has exactly two repetitive terms on the right-hand side,
  namely $2^{\ell+1}-1$ and $2^{\ell}-1$.

  \ii If $n = 2^k-1$, then $(\heartsuit)$
  has exactly one repetitive terms on the right-hand side, namely $2^{k-1}-1$.

  \ii For other $n$,
  there are no repetitive terms at all on the right-hand side of $(\heartsuit)$.
  \end{itemize}
  Thus the induction checks out.
\end{proof}

So the final answer to the problem is $2047$.
\pagebreak

\subsection{JMO 2013/5, proposed by Zuming Feng}
\textsl{Available online at \url{https://aops.com/community/p3043750}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Quadrilateral $XABY$ is inscribed in the semicircle $\omega$ with
diameter $\ol{XY}$.
Segments $AY$ and $BX$ meet at $P$.
Point $Z$ is the foot of the perpendicular from $P$ to line $\ol{XY}$.
Point $C$ lies on $\omega$ such that line $XC$ is perpendicular to line $AZ$.
Let $Q$ be the intersection of segments $AY$ and $XC$.
Prove that
\[\dfrac{BY}{XP}+\dfrac{CY}{XQ}=\dfrac{AY}{AX}.\]
\end{mdframed}
Let $\beta = \angle YXP$ and $\alpha = \angle PYX$ and set $XY = 1$.
We do not direct angles in the following solution.

\begin{center}
\begin{asy}
size(10cm);
pair X = Drawing("X", dir(180), dir(225));
pair Y = Drawing("Y", dir(0), dir(315));
pair A = Drawing("A", dir(130), dir(135));
pair B = Drawing("B", dir(94), dir(94));
pair P = Drawing("P", IP(X--B,A--Y), dir(90));
pair Z = Drawing("Z", foot(P,X,Y), dir(-90));
pair C = 2 * foot(origin, A+Y-Z, Y) - Y;
Drawing("C", C, C);
pair Q = Drawing("Q", IP(A--Y,X--C), dir(80));
draw(X--A--B--Y--cycle);
draw(A--Y--C--X--B);
draw(P--Z--A);
draw(arc(origin,1,0,180));
markangle("$\beta$", Y, X, P);
markangle("$\alpha$", A, Y, X);
\end{asy}
\end{center}

Observe that
\[ \angle AZX = \angle APX = \alpha + \beta \]
since $APZX$ is cyclic.
In particular, $\angle CXY = 90^\circ- (\alpha + \beta)$.
It is immediate that
\[ BY = \sin \beta, \quad CY = \cos \left( \alpha + \beta \right),
    \quad AY = \cos \alpha, \quad AX = \sin \alpha.  \]
The Law of Sines on $\triangle XPY$ gives $XP = XY \frac{\sin\alpha}{\sin(\alpha+\beta)}$,
and on $\triangle XQY$ gives $XQ = XY \frac{\sin\alpha}{\sin(90+\beta)} = \frac{\sin\alpha}{\cos\beta}$.
So, the given is equivalent to
\[ \frac{\sin\beta}{\frac{\sin\alpha}{\sin(\alpha+\beta)}}
  + \frac{\cos(\alpha+\beta)}{\frac{\sin\alpha}{\cos\beta}}
  = \frac{\cos\alpha}{\sin\alpha} \]
which is equivalent to $\cos\alpha = \cos\beta\cos(\alpha+\beta) + \sin\beta\sin(\alpha+\beta)$.
This is obvious, because the right-hand side is just $\cos\left( (\alpha+\beta)-\beta \right)$.
\pagebreak

\subsection{JMO 2013/6, proposed by Titu Andreescu}
\textsl{Available online at \url{https://aops.com/community/p3043752}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all real numbers $x,y,z \ge 1$ satisfying
\[ \min \left( \sqrt{x+xyz}, \sqrt{y+xyz}, \sqrt{z+xyz} \right)
  = \sqrt{x-1} + \sqrt{y-1} + \sqrt{z-1}. \]
\end{mdframed}
Set $x = 1+a$, $y = 1+b$, $z = 1+c$
which eliminates the $x,y,z \ge 1$ condition.
Assume without loss of generality that $a \leq b \leq c$.
Then the given equation rewrites as
\[ \sqrt{(1+a)\left( 1+(1+b)(1+c) \right)} = \sqrt a + \sqrt b + \sqrt c. \]

In fact, we are going to prove the left-hand side always exceeds the
right-hand side, and then determine the equality cases.
We have:
\begin{align*}
  (1+a)\left( 1 + (1+b)(1+c) \right)
  &= (a+1)\left( 1 + (b+1)(1+c) \right) \\
  &\le (a+1) \left( 1 + \left( \sqrt b + \sqrt c \right)^2 \right) \\
  &\le \left( \sqrt a + \left( \sqrt b + \sqrt c \right) \right)^2
\end{align*}
by two applications of Cauchy-Schwarz.

Equality holds if $bc = 1$ and $1/a = \sqrt b + \sqrt c$.
Letting $c = t^2$ for $t \ge 1$,
we recover $b = t^{-2} \le t^2$ and $a = \frac{1}{t+1/t} \le t^2$.

Hence the solution set is
\[ (x,y,z) = \left( 1 + \left( \frac{t}{t^2+1} \right)^2,
  1 + \frac{1}{t^2}, 1 + t^2 \right) \]
and permutations, for any $t > 0$.
\pagebreak


\end{document}
