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

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2004 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 $ABC$ be an acute-angled triangle with $AB\neq AC$.
The circle with diameter $BC$ intersects the sides $AB$ and $AC$
at $M$ and $N$ respectively.
Denote by $O$ the midpoint of the side $BC$.
The bisectors of the angles $\angle BAC$ and $\angle MON$ intersect at $R$.
Prove that the circumcircles of the triangles $BMR$ and $CNR$
have a common point lying on the side $BC$.

\item %% Problem 2
Find all polynomials $P$ with real coefficients such that
for all reals $a$, $b$, $c$ such that $ab+bc+ca = 0$, we have
\[ P(a-b) + P(b-c) + P(c-a) = 2P(a+b+c). \]

\item %% Problem 3
Define a ``hook'' to be a figure made up of six unit squares
as shown below in the picture,
or any of the figures obtained by applying rotations
and reflections to this figure.
\begin{center}
\begin{asy}
unitsize(0.5 cm);
draw(unitsquare);
draw(shift(0,1)*unitsquare);
draw(shift(0,2)*unitsquare);
draw(shift(1,2)*unitsquare);
draw(shift(2,1)*unitsquare);
draw(shift(2,2)*unitsquare);
\end{asy}
\end{center}
Which $m \times n$ rectangles can be tiled by hooks?

\item %% Problem 4
Let $n \ge 3$ be an integer
and $t_1$, $t_2$, \dots, $t_n$ positive real numbers such that
\[ n^2+1 > \left(t_1 + t_2 + \dots + t_n\right)
  \left( \frac{1}{t_1} + \frac{1}{t_2} + \dots + \frac{1}{t_n} \right). \]
Show that $t_i$, $t_j$, $t_k$ are the sides of a triangle
for all $i$, $j$, $k$ with $1 \le i < j < k \le n$.

\item %% Problem 5
In a convex quadrilateral $ABCD$,
the diagonal $BD$ bisects neither the angle $ABC$ nor the angle $CDA$.
The point $P$ lies inside $ABCD$ and satisfies
\[\angle PBC=\angle DBA \quad\text{and}\quad \angle PDC=\angle BDA. \]
Prove that $ABCD$ is a cyclic quadrilateral
if and only if $AP=CP$.

\item %% Problem 6
We call a positive integer \emph{alternating} if every two consecutive digits
in its decimal representation are of different parity.
Find all positive integers $n$ which have an alternating multiple.

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{IMO 2004/1, proposed by Dinu Serbanescu and Valentin Vornicu (ROU)}
\textsl{Available online at \url{https://aops.com/community/p99445}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be an acute-angled triangle with $AB\neq AC$.
The circle with diameter $BC$ intersects the sides $AB$ and $AC$
at $M$ and $N$ respectively.
Denote by $O$ the midpoint of the side $BC$.
The bisectors of the angles $\angle BAC$ and $\angle MON$ intersect at $R$.
Prove that the circumcircles of the triangles $BMR$ and $CNR$
have a common point lying on the side $BC$.
\end{mdframed}
By Miquel's theorem it's enough to show $AMRN$ is cyclic.
\begin{center}
\begin{asy}
pair A = dir(130);
pair B = dir(210);
pair C = dir(330);
pair H = A+B+C;
pair M = foot(C, A, B);
pair N = foot(B, A, C);
pair O = midpoint(B--C);
pair R = extension(A, incenter(A, B, C), O, midpoint(M--N));
pair T = extension(H, R, B, C);
filldraw(A--B--C--cycle, opacity(0.1)+lightblue, blue);
draw(B--N, blue);
draw(C--M, blue);
filldraw(circumcircle(A, M, N), opacity(0.1)+lightgreen, heavygreen);

dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$H$", H, dir(H));
dot("$M$", M, dir(M));
dot("$N$", N, dir(N));
dot("$O$", O, dir(O));
dot("$R$", R, dir(R));
// dot("$T$", T, dir(T));

/* TSQ Source:

A = dir 130
B = dir 210
C = dir 330
H = A+B+C
M = foot C A B
N = foot B A C
O = midpoint B--C
R = extension A incenter A B C O midpoint M--N
T = extension H R B C
A--B--C--cycle 0.1 lightblue / blue
B--N blue
C--M blue
circumcircle A M N 0.1 lightgreen / heavygreen
R--T--B blue

*/
\end{asy}
\end{center}
In fact, since the bisector of $\angle MON$
is just the perpendicular bisector of $\ol{MN}$,
the point $R$ is actually just the arc midpoint
of $\widehat{MN}$ of $(AMN)$ as desired.
\pagebreak

\subsection{IMO 2004/2, proposed by Hojoo Lee (KOR)}
\textsl{Available online at \url{https://aops.com/community/p99448}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all polynomials $P$ with real coefficients such that
for all reals $a$, $b$, $c$ such that $ab+bc+ca = 0$, we have
\[ P(a-b) + P(b-c) + P(c-a) = 2P(a+b+c). \]
\end{mdframed}
The answer is \[ P(x) = \alpha x^4 + \beta x^2 \]
which can be checked to work, for any real numbers $\alpha$ and $\beta$.

It is easy to obtain that $P$ is even and $P(0) = 0$.
The trick is now to choose $(a,b,c) = (6x,3x,-2x)$
and then compare the leading coefficients to get
\[ 3^n + 5^n + 8^n = 2 \cdot 7^n \]
for $n = \deg f$ (which is even).
As $n \ge 7 \implies (8/7)^n > 2$, this means that we must have $n \le 6$.
Moreover, taking modulo $7$ we have $3^n + 5^n \equiv 6 \pmod 7$
which gives $n \equiv 2, 4 \pmod 6$.

Thus $\deg P \le 4$, which (combined with $P$ even) resolves the problem.
\pagebreak

\subsection{IMO 2004/3, proposed by Jan Willemson (EST)}
\textsl{Available online at \url{https://aops.com/community/p99450}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Define a ``hook'' to be a figure made up of six unit squares
as shown below in the picture,
or any of the figures obtained by applying rotations
and reflections to this figure.
\begin{center}
\begin{asy}
unitsize(0.5 cm);
draw(unitsquare);
draw(shift(0,1)*unitsquare);
draw(shift(0,2)*unitsquare);
draw(shift(1,2)*unitsquare);
draw(shift(2,1)*unitsquare);
draw(shift(2,2)*unitsquare);
\end{asy}
\end{center}
Which $m \times n$ rectangles can be tiled by hooks?
\end{mdframed}
The answer is that one requires:
\begin{itemize}
  \ii $\{1,2,5\} \notin \{m,n\}$,
  \ii $3 \mid m$ or $3 \mid n$,
  \ii $4 \mid m$ or $4 \mid n$.
\end{itemize}

First, we check all of these work, in fact we claim:
\begin{claim*}
  Any rectangle satisfying these conditions
  can be tiled by $3 \times 4$ rectangles (and hence by hooks).
\end{claim*}
\begin{proof}
  If $3 \mid m$ and $4 \mid n$, this is clear.
  Else suppose $12 \mid m$ but $3 \nmid n$, $4 \nmid n$.
  Then $n \ge 7$, so it can be written in the form
  $3a+4b$ for nonnegative integers $a$ and $b$, which permits a tiling.
\end{proof}

We now prove these conditions are necessary.
It is not hard to see that $m,n \notin \{1,2,5\}$ is necessary.

We thus turn our attention to divisibility conditions.
Each hook has a \emph{hole}, and if we associate each hook with
the one that fills its hole, we get a bijective pairing of hooks.
Thus the number of cells is divisible by $12$,
and the cells come grouped into two possible shapes,
which we will call \textbf{tiles} shown below,
(rotations and reflections permitted).
\begin{center}
\begin{asy}
unitsize(0.5 cm);
filldraw(unitsquare, white, black);
filldraw(shift(0,1)*unitsquare, white, black);
filldraw(shift(0,2)*unitsquare, white, black);
filldraw(shift(1,2)*unitsquare, white, black);
filldraw(shift(2,1)*unitsquare, white, black);
filldraw(shift(2,2)*unitsquare, white, black);

filldraw(shift(1,0)*unitsquare, grey, black);
filldraw(shift(1,1)*unitsquare, grey, black);
filldraw(shift(2,0)*unitsquare, grey, black);
filldraw(shift(3,0)*unitsquare, grey, black);
filldraw(shift(3,1)*unitsquare, grey, black);
filldraw(shift(3,2)*unitsquare, grey, black);
\end{asy}
\qquad
\begin{asy}
unitsize(0.5 cm);
filldraw(unitsquare, white, black);
filldraw(shift(0,1)*unitsquare, white, black);
filldraw(shift(0,2)*unitsquare, white, black);
filldraw(shift(1,2)*unitsquare, white, black);
filldraw(shift(2,1)*unitsquare, white, black);
filldraw(shift(2,2)*unitsquare, white, black);

filldraw(shift(1,0)*unitsquare, grey, black);
filldraw(shift(1,1)*unitsquare, grey, black);
filldraw(shift(1,-1)*unitsquare, grey, black);
filldraw(shift(0,-1)*unitsquare, grey, black);
filldraw(shift(-1,-1)*unitsquare, grey, black);
filldraw(shift(-1,0)*unitsquare, grey, black);
\end{asy}
\end{center}

In particular, the total number of cells is divisible by $12$.
Thus the problem is reduced to proving that:
\begin{claim*}
  if a $6a \times 2b$ rectangle is tiled by tiles,
  then at least one of $a$ and $b$ is even.
\end{claim*}
\begin{proof}
  Note that the tiles can be further classified into two types:
  \begin{itemize}
    \ii \textbf{First type}: These tiles have exactly four columns,
    each with exactly three cells (an odd number).
    Moreover, all rows have an even number of cells (either $2$ or $4$).
    \ii \textbf{Second type}: vice-versa.
    These tiles have exactly four rows,
    each with exactly three cells (an odd number).
    Moreover, all rows have an odd number of cells.
  \end{itemize}
  We claim that any tiling uses an even number of each type, which is enough.

  By symmetry we prove an even number of first-type tiles.
  Color red every fourth column of the rectangle.
  The number of cells colored red is even.
  The tiles of the second type cover an even number of red cells,
  and the tiles of the first type cover an odd number of red cells.
  Hence the number of tiles of the first type must be even.
\end{proof}

\begin{remark*}
  This shows that a rectangle can be tiled by hooks
  if and only if it can be tiled by $3 \times 4$ rectangles.
  But there exist tilings which do not decompose into $3 \times 4$;
  see e.g.\ \url{https://aops.com/community/c6h14023p99881}.
\end{remark*}
\pagebreak

\section{Solutions to Day 2}
\subsection{IMO 2004/4, proposed by Hojoo Lee (KOR)}
\textsl{Available online at \url{https://aops.com/community/p99756}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n \ge 3$ be an integer
and $t_1$, $t_2$, \dots, $t_n$ positive real numbers such that
\[ n^2+1 > \left(t_1 + t_2 + \dots + t_n\right)
  \left( \frac{1}{t_1} + \frac{1}{t_2} + \dots + \frac{1}{t_n} \right). \]
Show that $t_i$, $t_j$, $t_k$ are the sides of a triangle
for all $i$, $j$, $k$ with $1 \le i < j < k \le n$.
\end{mdframed}
Let $a = t_1$, $b = t_2$, $c = t_3$.
Expand:
\begin{align*}
  n^2+1 &> \left(t_1 + t_2 + \dots + t_n\right)
    \left( \frac{1}{t_1} + \dots + \frac{1}{t_n} \right) \\
  &= n + \sum_{1 \le i < j \le n}
    \left( \frac{t_i}{t_j} + \frac{t_j}{t_i} \right) \\
  &= n + \sum_{1 \le i < j \le n}
    \left( \frac{t_i}{t_j} + \frac{t_j}{t_i} \right) \\
  &\ge n + \sum_{1 \le i < j \le 3}
    \left( \frac{t_i}{t_j} + \frac{t_j}{t_i} \right)
    + \sum_{\substack{1 \le i < j \le n \\ j > 3 }} 2 \\
  &= n + 2\left( \binom n2-3 \right)
    + \left( \frac ab + \frac ba \right)
    + \frac{a+b}{c} + \frac{c}{b} + \frac{c}{a} \\
  &\ge n + 2\left( \binom n2-3 \right) + 2
    + \frac{a+b}{c} + c \cdot \frac{4}{a+b}
\end{align*}
So, we conclude that
\[ \frac{a+b}{c} + \frac{4c}{a+b} < 5 \]
which rearranges to
\[ \left( 4c-(a+b) \right)\left( c-(a+b) \right) < 0. \]
This is enough to imply $c \le a+b$.

\begin{remark*}
  A variant of the same argument allows one to improve
  the left-hand side to $(n+\sqrt{10}-3)^2$.
  One does so by writing
  \[ \text{RHS} \ge \left( \sqrt{\left( a+b+c \right)
    \left( \frac1a+\frac1b+\frac1c \right)} + (n-3) \right)^2 \]
  and estimating the square root as in the previous approach.

  In addition, $(n+\sqrt{10}-3)^2$ is best possible,
  as seen by taking $(a,b,c) = (2,1,1)$ and $t_4 = t_5 = \dots = \frac25 \sqrt{10}$.
\end{remark*}
\pagebreak

\subsection{IMO 2004/5, proposed by Waldemar Pompe (POL)}
\textsl{Available online at \url{https://aops.com/community/p99759}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
In a convex quadrilateral $ABCD$,
the diagonal $BD$ bisects neither the angle $ABC$ nor the angle $CDA$.
The point $P$ lies inside $ABCD$ and satisfies
\[\angle PBC=\angle DBA \quad\text{and}\quad \angle PDC=\angle BDA. \]
Prove that $ABCD$ is a cyclic quadrilateral
if and only if $AP=CP$.
\end{mdframed}
Apply barycentric coordinates to $\triangle PBD$
with $P = (1,0,0)$, $B = (0,1,0)$ and $D = (0,0,1)$.
Define $a = BD$, $b = DP$ and $c = PB$.

Since $A$ and $C$ are isogonal conjugates with respect to $\triangle PBD$,
we set \[ A = (au : bv : cw) \qquad\text{and}\qquad
  C = \left( \frac au : \frac bv : \frac cw \right). \]
For brevity define $M = au + bv + cw$ and $N = avw + bwu + cuv$.

We now compute each condition.
\begin{claim*}
  Quadrilateral $ABCD$ is cyclic if and only if $N^2 = u^2 M^2$.
\end{claim*}
\begin{proof}
  W know a circle through $B$ and $D$
  is a locus of points
  with \[ \frac{a^2yz+b^2zx+c^2xy}{x(x+y+z)} \]
  is equal to some constant.
  Therefore quadrilateral $ABCD$ is cyclic if and only if
  $\frac{abc \cdot N}{au \cdot M}$
  is equal to $\frac{abc \cdot uvw \cdot M}{avw \cdot N}$
  which rearranges to $N^2 = u^2M^2$.
\end{proof}
\begin{claim*}
  We have $PA = PC$ if and only if $N^2 = u^2 M^2$.
\end{claim*}
\begin{proof}
  We have the displacement vector
  $\overrightarrow{PA}
  = \tfrac{1}{M} \left( bv+cw , -bv ,-cw \right)$.
  Therefore,
  \begin{align*}
    M^2 \cdot \left\lvert PA \right\rvert^2
    &= -a^2(bv)(cw) + b^2(cw)(bv+cw) + c^2(bv)(bv+cw) \\
    &= bc(-a^2vw + (bw+cv)(bv+cw)).
  \end{align*}
  In a similar way
  (by replacing $u$, $v$, $w$ with their inverses)
  we have
  \begin{align*}
    \left( \frac{N}{uvw} \right)^2 \cdot \left\lvert PC \right\rvert^2
    &= (vw)^{-2} \cdot bc(-a^2vw + (bv+cw)(bw+cv)) \\
    \iff N^2 \cdot \left\lvert PC \right\rvert^2
    & = u^2 bc(-a^2vw + (bw+cv)(bv+cw))
  \end{align*}
  These are equal if and only if $N^2 = u^2M^2$, as desired.
\end{proof}
\pagebreak

\subsection{IMO 2004/6, proposed by Mohsen Jamaali and Armin Morabbi (IRN)}
\textsl{Available online at \url{https://aops.com/community/p99760}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
We call a positive integer \emph{alternating} if every two consecutive digits
in its decimal representation are of different parity.
Find all positive integers $n$ which have an alternating multiple.
\end{mdframed}
If $20 \mid n$, then clearly $n$ has no alternating
multiple since the last two digits are both even.
We will show the other values of $n$ all work.

The construction is just rush-down do-it.
The meat of the solution is the two following steps.
\begin{claim*}
  [Tail construction]
  For every even integer $w \ge 2$,
  \begin{itemize}
    \ii there exists an even alternating multiple $g(w)$ of $2^{w+1}$
    with exactly $w$ digits, and
    \ii there exists an even alternating multiple $h(w)$ of $5^{w}$
    with exactly $w$ digits.
  \end{itemize}
\end{claim*}
(One might note this claim is implied by the problem, too.)
\begin{proof}
  We prove the first point by induction on $w$.
  If $w = 2$, take $g(2) = 32$.
  In general, we can construct $g(w+2)$ from $g(w)$
  by adding some element in
  \[ 10^w \cdot \{10, 12, 14, 16, 18, 30, \dots, 98\} \]
  to $g(w)$, corresponding to the digits
  we want to append to the start.
  This multiple is automatically divisible by $2^{w+1}$,
  and also can take any of the four possible values modulo $2^{w+3}$.

  The second point is a similar induction,
  with base case $h(2) = 50$.
  The same set above consists of numbers divisible by $5^w$,
  and covers all residues modulo $5^{w+2}$.
  Careful readers might recognize the second part
  as essentially USAMO 2003/1.
\end{proof}

\begin{claim*}
  [Head construction]
  If $\gcd(n,10) = 1$, then for any $b$,
  there exists an even alternating number $f(b \bmod n)$ which is
  $b \pmod n$.
\end{claim*}
\begin{proof}
  A standard argument shows that
  \[ 10 \cdot \frac{100^m-1}{99}
    = \underbrace{1010\dots10}_{m\ 10\text{'s}}
    \equiv 0 \pmod n \]
  for any $m$ divisible by $\varphi(99n)$.
  Take a very large such $m$,
  and then add on $b$ distinct numbers of the form $10^{\varphi(n)r}$
  for various even values of $r$; these all are $1 \pmod n$
  and change some of the $1$'s to $3$'s.
\end{proof}


Now, we can solve the problem.
Consider three cases:
\begin{itemize}
  \ii If $n = 2^k m$ where $\gcd(m,10) = 1$ and $k \ge 2$ is even,
  then the concatenated number
  \[ 10^k f\left( -\frac{g(k)}{10^k} \bmod m \right) + g(k) \]
  works fine.

  \ii If $n = 5^k m$ where $\gcd(m,10) = 1$ and $k \ge 2$ is even,
  then the concatenated number
  \[ 10^k f\left( -\frac{h(k)}{10^k} \bmod m \right) + h(k) \]
  works fine.

  \ii If $n = 50m$ where $\gcd(m,10) = 1$,
  then the concatenated number
  \[ 100 f\left( -\frac{1}{2} \bmod m \right) + 50 \]
  works fine.
\end{itemize}
Since every non-multiple of $20$ divides such a number, we are done.
\pagebreak


\end{document}
