% © 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 2007 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2007 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
Real numbers $a_1$, $a_2$, \dots, $a_n$ are fixed.
For each $1 \le i \le n$ we let
$d_i = \max\{a_j : 1 \le j \le i\} - \min\{a_j : i \le j \le n\}$
and let $d = \max \{d_i : 1 \le i \le n\}$.
\begin{enumerate}[(a)]
\ii Prove that for any real numbers $x_1 \le \dots \le x_n$ we have
\[
\max \left\{ \left\lvert x_i - a_i \right\rvert :
1 \le i \le n \right\}
\ge \half d.
\]
\ii Moreover, show that there exists some
choice of $x_1 \le \dots \le x_n$ which achieves equality.
\end{enumerate}
\item %% Problem 2
Consider five points $A$, $B$, $C$, $D$ and $E$
such that $ABCD$ is a parallelogram and $BCED$ is a cyclic quadrilateral.
Let $\ell$ be a line passing through $A$.
Suppose that $\ell$ intersects the interior of the segment $DC$ at $F$
and intersects line $BC$ at $G$.
Suppose also that $EF = EG = EC$.
Prove that $\ell$ is the bisector of angle $ DAB$.
\item %% Problem 3
In a mathematical competition some competitors are (mutual) friends.
Call a group of competitors a \emph{clique} if each two of them are friends.
Given that the largest size of a clique is even,
prove that the competitors can be arranged into two rooms
such that the largest size of a clique contained in one room
is the same as the largest size of a clique contained in the other room.
\item %% Problem 4
In triangle $ABC$ the bisector of $\angle BCA$
meets the circumcircle again at $R$,
the perpendicular bisector of $\ol{BC}$ at $P$,
and the perpendicular bisector of $\ol{AC}$ at $Q$.
The midpoint of $\ol{BC}$ is $K$ and the midpoint of $\ol{AC}$ is $L$.
Prove that the triangles $RPK$ and $RQL$ have the same area.
\item %% Problem 5
Let $a$ and $b$ be positive integers.
Show that if $4ab - 1$ divides $(4a^{2} - 1)^{2}$, then $a = b$.
\item %% Problem 6
Let $n$ be a positive integer.
Consider
\[ S = \left\{ (x,y,z) \mid
x,y,z \in \{ 0, 1, \dots, n\}, \;
x+y+z > 0 \right\} \]
as a set of $(n+1)^3-1$ points in the three-dimensional space.
Determine the smallest possible number of planes,
the union of which contains $S$ but does not include $(0,0,0)$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{IMO 2007/1, proposed by Michael Albert (NZL)}
\textsl{Available online at \url{https://aops.com/community/p893741}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Real numbers $a_1$, $a_2$, \dots, $a_n$ are fixed.
For each $1 \le i \le n$ we let
$d_i = \max\{a_j : 1 \le j \le i\} - \min\{a_j : i \le j \le n\}$
and let $d = \max \{d_i : 1 \le i \le n\}$.
\begin{enumerate}[(a)]
\ii Prove that for any real numbers $x_1 \le \dots \le x_n$ we have
\[
\max \left\{ \left\lvert x_i - a_i \right\rvert :
1 \le i \le n \right\}
\ge \half d.
\]
\ii Moreover, show that there exists some
choice of $x_1 \le \dots \le x_n$ which achieves equality.
\end{enumerate}
\end{mdframed}
Note that we can dispense of $d_i$ immediately
by realizing that the definition of $d$ just says
\[ d = \max_{1 \le i \le j \le n} \left( a_i - a_j \right). \]
If $a_1 \le \dots \le a_n$ are already nondecreasing
then $d = 0$ and there is nothing to prove
(for the equality case, just let $x_i = a_i$),
so we will no longer consider this case.
Otherwise, consider any indices $i < j$ with $a_i > a_j$.
We first prove (a) by applying the following claim
with $p = a_i$ and $q = a_j$:
\begin{claim*}
For any $p \le q$, we have
either $|p - a_i| \ge \half(a_i-a_j)$
or $|q - a_j| \ge \half(a_i-a_j)$.
\end{claim*}
\begin{proof}
Assume for contradiction both are false.
Then $p > a_i - \half(a_i-a_j)
= a_j + \half(a_i-a_j) > q$, contradiction.
\end{proof}
As for (b), we let $i < j$ be any indices for which
$a_i - a_j = d > 0$ achieves the maximal difference.
We then define $x_\bullet$ in three steps:
\begin{itemize}
\ii We set $x_k = \frac{a_i + a_j}{2}$ for $k = i, \dots, j$.
\ii We recursively set $x_{k} = \max(x_{k-1}, a_k)$
for $k = j+1, j+2, \dots$.
\ii We recursively set $x_{k} = \min(x_{k+1}, a_k)$
for $k = i-1, i-2, \dots$.
\end{itemize}
By definition, these $x_\bullet$ are weakly increasing.
To prove this satisfies (b) we only need to check that
\[ \left\lvert x_k - a_k \right\rvert \le \frac{a_i-a_j}{2} \qquad
(\star) \]
for any index $k$ (as equality holds for $k = i$ or $k = j$).
We note $(\star)$ holds for $i < k < j$ by construction.
For $k > j$, note that $x_k \in \{a_j, a_{j+1}, \dots, a_k\}$
by construction, so $(\star)$ follows from our choice of $i$ and $j$
giving the largest possible difference; the case $k < i$ is similar.
\pagebreak
\subsection{IMO 2007/2, proposed by Charles Leytem (LUX)}
\textsl{Available online at \url{https://aops.com/community/p893744}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Consider five points $A$, $B$, $C$, $D$ and $E$
such that $ABCD$ is a parallelogram and $BCED$ is a cyclic quadrilateral.
Let $\ell$ be a line passing through $A$.
Suppose that $\ell$ intersects the interior of the segment $DC$ at $F$
and intersects line $BC$ at $G$.
Suppose also that $EF = EG = EC$.
Prove that $\ell$ is the bisector of angle $ DAB$.
\end{mdframed}
Let $M$, $N$, $P$ denote the midpoints of $\ol{CF}$, $\ol{CG}$, $\ol{AC}$
(noting $P$ is also the midpoint of $\ol{BD}$).
By a homothety at $C$ with ratio $\half$,
we find $\ol{MNP}$ is the image of line $\ell \equiv \ol{AGF}$.
\begin{center}
\begin{asy}
pair C = dir(200);
pair D = dir(340);
pair E = dir(240);
pair K = E*E/C;
pair B = C*K/D;
pair A = B+D-C;
pair M = foot(E, C, D);
pair N = foot(E, C, B);
pair P = foot(E, B, D);
filldraw(unitcircle, opacity(0.1)+lightcyan, blue);
draw(B--C--D--cycle, blue);
filldraw(CP(E, C), opacity(0.1)+lightred, red+dotted);
pair F = 2*M-C;
pair G = 2*N-C;
draw(E--P, orange);
draw(E--M, orange);
draw(E--N, orange);
draw(C--G, blue);
draw(N--P, deepgreen);
draw(A--G, deepgreen);
draw(B--A--D, lightblue+dashed);
draw(A--C, lightblue+dashed);
dot("$C$", C, dir(180));
dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$B$", B, dir(B));
dot("$A$", A, dir(A));
dot("$M$", M, dir(135));
dot("$N$", N, dir(N));
dot("$P$", P, dir(P));
dot("$F$", F, dir(F));
dot("$G$", G, dir(G));
/* TSQ Source:
C = dir 200 R180
D = dir 340
E = dir 240
K := E*E/C
B = C*K/D
A = B+D-C
M = foot E C D R135
N = foot E C B
P = foot E B D
unitcircle 0.1 lightcyan / blue
B--C--D--cycle blue
CP E C 0.1 lightred / red dotted
F = 2*M-C
G = 2*N-C
E--P orange
E--M orange
E--N orange
C--G blue
N--P deepgreen
A--G deepgreen
B--A--D lightblue dashed
A--C lightblue dashed
*/
\end{asy}
\end{center}
However, since we also have $\ol{EM} \perp \ol{CF}$
and $\ol{EN} \perp \ol{CG}$ (from $EF=EG=EC$)
we conclude $\ol{PMN}$ is the Simson line of $E$ with respect to $\triangle BCD$,
which implies $\ol{EP} \perp \ol{BD}$.
In other words, $\ol{EP}$ is the perpendicular bisector of $\ol{BD}$,
so $E$ is the midpoint of arc $\widehat{BCD}$.
Finally,
\begin{align*}
\dang(\ol{AB}, \ell) &= \dang(\ol{CD}, \ol{MNP}) = \dang CMN = \dang CEN \\
&= 90\dg - \dang NCE = 90\dg + \dang ECB
\end{align*}
which means that $\ell$ is parallel to a bisector of $\angle BCD$,
and hence to one of $\angle BAD$.
(Moreover since $F$ lies on the interior of $\ol{CD}$,
it is actually the internal bisector.)
\pagebreak
\subsection{IMO 2007/3, proposed by Vasily Astakhov (RUS)}
\textsl{Available online at \url{https://aops.com/community/p893746}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
In a mathematical competition some competitors are (mutual) friends.
Call a group of competitors a \emph{clique} if each two of them are friends.
Given that the largest size of a clique is even,
prove that the competitors can be arranged into two rooms
such that the largest size of a clique contained in one room
is the same as the largest size of a clique contained in the other room.
\end{mdframed}
Take the obvious graph interpretation $G$.
We paint red any vertices in one of the maximal cliques $K$,
which we assume has $2r$ vertices,
and paint the remaining vertices green.
We let $\alpha(\bullet)$ denote the clique number.
Initially, let the two rooms $A = K$, $B = G-K$.
\begin{claim*}
We can move at most $r$ vertices of $A$ into $B$
to arrive at $\alpha(A) \le \alpha(B) \le \alpha(A)+1$.
\end{claim*}
\begin{proof}
This is actually obvious by discrete continuity.
We move one vertex at a time,
noting $\alpha(A)$ decreases by one at each step,
while $\alpha(B)$ increases by either zero or one at each step.
We stop once $\alpha(B) \ge \alpha(A)$,
which happens before we have moved $r$ vertices
(since then we have $\alpha(B) \ge r = \alpha(A)$).
The conclusion follows.
\end{proof}
So let's consider the situation
\[ \alpha(A) = k \ge r \qquad\text{and}\qquad \alpha(B) = k+1. \]
At this point $A$ is a set of $k$ red vertices,
while $B$ has the remaining $2r-k$ red vertices
(and all the green ones).
An example is shown below with $k=4$ and $2r = 6$.
\begin{center}
\begin{asy}
size(10cm);
pair K1 = 2*dir(45);
pair K2 = 2*dir(135);
pair K3 = 2*dir(225);
pair K4 = 2*dir(315);
label("$A$", (0,2), dir(90), red);
label("$\alpha(A) = k$", (0,-2.5), dir(90), red);
label("$k$ red vertices", (0,-2.5), dir(-90), red);
pair K5 = (6,1);
pair K6 = (6,-1);
draw(K1--K5, palered);
draw(K2--K5, palered);
draw(K3--K5, palered);
draw(K4--K5, palered);
draw(K1--K6, palered);
draw(K2--K6, palered);
draw(K3--K6, palered);
draw(K4--K6, palered);
pair B1 = (4.8,1.3);
pair B2 = (3.7,0);
pair B3 = (4.8,-1.3);
pair C1 = (7.2,1.3);
pair C2 = (8.3,0);
pair C3 = (7.2,-1.3);
draw(K5--B1--K6, paleblue);
draw(K5--B2--K6, paleblue);
draw(K5--B3--K6, paleblue);
draw(B1--B2--B3--cycle, paleblue);
draw(K5--C1--K6, paleblue);
draw(K5--C2--K6, paleblue);
draw(K5--C3--K6, paleblue);
draw(C1--C2--C3--cycle, paleblue);
draw(K1--K2--K3--K4--cycle, red+1);
draw(K1--K3, red+1);
draw(K2--K4, red+1);
draw(K5--K6, red+1);
dot(K1, red);
dot(K2, red);
dot(K3, red);
dot(K4, red);
dot(K5, red);
dot(K6, red);
dot(B1, deepgreen);
dot(B2, deepgreen);
dot(B3, blue);
dot(C1, deepgreen);
dot(C2, deepgreen);
dot(C3, blue);
draw(circle(B3, 0.15), blue);
draw(circle(C3, 0.15), blue);
label("$B$", (6,2), dir(90), deepgreen);
label("$\alpha(B) = k+1$", (6,-2.5), dir(90), deepgreen);
label("$2r-k$ red vertices", (6,-2.5), dir(-90), deepgreen);
draw((3,2.8)--(3,-2.8), black+1.5);
\end{asy}
\end{center}
Now, if we can move any red vertex from $B$ back to $A$
without changing the clique number of $B$, we do so, and win.
Otherwise, it must be the case that \emph{every}
$(k+1)$-clique in $B$ uses \emph{every} red vertex in $B$.
For each $(k+1)$-clique in $B$ (in arbitrary order), we do the following procedure.
\begin{itemize}
\ii If all $k+1$ vertices are still green, pick one and re-color it blue.
This is possible since $k+1 > 2r-k$.
\ii Otherwise, do nothing.
\end{itemize}
Then we move all the blue vertices from $B$ to $A$,
one at a time, in the same order we re-colored them.
This forcibly decreases the clique number of $B$ to $k$,
since the clique number is $k+1$ just before the last blue vertex is moved,
and strictly less than $k+1$ (hence equal to $k$) immediately after that.
\begin{claim*}
After this, $\alpha(A) = k$ still holds.
\end{claim*}
\begin{proof}
Assume not, and we have a $(k+1)$-clique
which uses $b$ blue vertices and $(k+1)-b$ red vertices in $A$.
Together with the $2r-k$ red vertices already in $B$
we then get a clique of size
\[ b + \left( (k+1-b) \right)
+ \left( 2r-k \right) = 2r + 1 \]
which is a contradiction.
\end{proof}
\begin{remark*}
Dragomir Grozev posted the
following motivation on
\href{https://dgrozev.wordpress.com/2019/12/05/splitting-the-cliques-of-a-graph-imo-2007-p3/}{his blog}:
\begin{quote}
I think, it’s a natural idea to
place all students in one room and begin
moving them one by one into the other one.
Then the max size of the cliques in the first and second room
increase (resp.\ decrease) at most with one.
So, there would be a moment both sizes are almost the same.
At that moment we may adjust something.
Trying the idea, I had some difficulties
keeping track of the maximal cliques in the both rooms.
It seemed easier all the students in one of the rooms
to comprise a clique.
It could be achieved by moving only the members
of the maximal clique.
Following this path the remaining obstacles
can be overcome naturally.
\end{quote}
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{IMO 2007/4, proposed by Marek Pechal (CZE)}
\textsl{Available online at \url{https://aops.com/community/p894655}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
In triangle $ABC$ the bisector of $\angle BCA$
meets the circumcircle again at $R$,
the perpendicular bisector of $\ol{BC}$ at $P$,
and the perpendicular bisector of $\ol{AC}$ at $Q$.
The midpoint of $\ol{BC}$ is $K$ and the midpoint of $\ol{AC}$ is $L$.
Prove that the triangles $RPK$ and $RQL$ have the same area.
\end{mdframed}
We first begin by proving the following claim.
\begin{claim*}
We have $CQ = PR$ (equivalently, $CP = QR$).
\end{claim*}
\begin{proof}
Let $O = \ol{LQ} \cap \ol{KP}$ be the circumcenter.
Then
\[ \dang OPQ = \dang KPC = 90\dg - \dang PCK
= 90\dg - \dang LCQ = \dang \dang CQL = \dang PQO. \]
Thus $OP = OQ$.
Since $OC = OR$ as well, we get the conclusion.
\end{proof}
Denote by $X$ and $Y$ the feet from $R$ to $\ol{CA}$
and $\ol{CB}$, so $\triangle CXR \cong \triangle CYR$.
Then, let $t = \frac{CQ}{CR} = 1 - \frac{CP}{CR}$.
\begin{center}
\begin{asy}
pair C = dir(90);
pair R = -C;
pair X = dir(205);
pair Y = -conj(X);
pair Q = 0.41*R+0.59*C;
pair P = R+C-Q;
pair L = foot(Q, C, X);
pair K = foot(P, C, Y);
pair A = 2*L-C;
pair B = 2*K-C;
pair O = extension(L, Q, P, K);
filldraw(L--Q--X--cycle, opacity(0.1)+orange, dotted+orange);
filldraw(P--K--Y--cycle, opacity(0.1)+orange, dotted+orange);
draw(C--A--B--cycle, lightblue);
draw(A--X, lightblue);
draw(circumcircle(C, A, B), lightblue+dashed);
draw(C--R, deepgreen);
draw(X--R--Y, deepgreen);
draw(L--O, blue);
draw(P--K, blue);
dot("$C$", C, dir(C));
dot("$R$", R, dir(R));
dot("$X$", X, dir(180));
dot("$Y$", Y, dir(0));
dot("$Q$", Q, dir(45));
dot("$P$", P, dir(215));
dot("$L$", L, dir(L));
dot("$K$", K, dir(K));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$O$", O, dir(315));
/* TSQ Source:
C = dir 90
R = -C
X = dir 205 R180
Y = -conj(X) R0
Q = 0.41*R+0.59*C R45
P = R+C-Q R215
L = foot Q C X
K = foot P C Y
A = 2*L-C
B = 2*K-C
O = extension L Q P K R315
L--Q--X--cycle 0.1 orange / dotted orange
P--K--Y--cycle 0.1 orange / dotted orange
C--A--B--cycle lightblue
A--X lightblue
circumcircle C A B lightblue dashed
C--R deepgreen
X--R--Y deepgreen
L--O blue
P--K blue
*/
\end{asy}
\end{center}
Then it follows that
\[ [RQL] = [XQL] = t(1-t) \cdot [XRC]
= t(1-t) \cdot [YCR] = [YKP] = [RKP] \]
as needed.
\begin{remark*}
Trigonometric approaches are very possible
(and easier to find) as well:
both areas work out to be $\frac 18 ab \tan \half C$.
\end{remark*}
\pagebreak
\subsection{IMO 2007/5, proposed by Kevin Buzzard, Edward Crane (UNK)}
\textsl{Available online at \url{https://aops.com/community/p894656}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $a$ and $b$ be positive integers.
Show that if $4ab - 1$ divides $(4a^{2} - 1)^{2}$, then $a = b$.
\end{mdframed}
As usual,
\[ 4ab-1 \mid (4a^2-1)^2 \iff 4ab-1 \mid (4ab \cdot a-b)^2
\iff 4ab-1 \mid (a-b)^2. \]
Then we use a typical Vieta jumping argument.
Define \[ k = \frac{(a-b)^2}{4ab-1}. \]
Note that $k = 0 \iff a = b$.
So we will prove that $k > 0$ leads to a contradiction.
Indeed, suppose $(a, b)$ is a minimal solution with $a > b$
(we have $a \neq b$ since $k \neq 0$).
By Vieta jumping, $(b, \frac{b^2+k}{a})$ is also such a solution.
But now
\begin{align*}
\frac{b^2+k}{a} \ge a &\implies k \ge a^2 - b^2 \\
&\implies \frac{(a-b)^2}{4ab-1} \ge a^2-b^2 \\
&\implies a-b \ge (4ab-1)(a+b)
\end{align*}
which is absurd for $a,b \in \ZZ_{>0}$.
(In the last step we divided by $a-b > 0$.)
\pagebreak
\subsection{IMO 2007/6, proposed by Gerhard Woeginger (NLD)}
\textsl{Available online at \url{https://aops.com/community/p894658}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n$ be a positive integer.
Consider
\[ S = \left\{ (x,y,z) \mid
x,y,z \in \{ 0, 1, \dots, n\}, \;
x+y+z > 0 \right\} \]
as a set of $(n+1)^3-1$ points in the three-dimensional space.
Determine the smallest possible number of planes,
the union of which contains $S$ but does not include $(0,0,0)$.
\end{mdframed}
The answer is $3n$.
Here are two examples of constructions with $3n$ planes:
\begin{itemize}
\ii $x+y+z=i$ for $i=1,\dots,3n$.
\ii $x=i$, $y=i$, $z=i$ for $i=1,\dots,n$.
\end{itemize}
Suppose for contradiction we have $N < 3n$ planes.
Let them be $a_i x + b_i y + c_i z + 1 = 0$, for $i = 1, \dots, N$.
Define the polynomials
\begin{align*}
A(x,y,z) &= \prod_{i=1}^n (x-i) \prod_{i=1}^n (y-i) \prod_{i=1}^n (z-i) \\
B(x,y,z) &= \prod_{i=1}^N \left( a_i x + b_i y + c_i z + 1 \right).
\end{align*}
Note that $A(0,0,0) = (-1)^n (n!)^3 \neq 0$
and $B(0,0,0) = 1 \neq 0$,
but $A(x,y,z) = B(x,y,z) = 0$ for any $(x,y,z) \in S$.
Also, the coefficient of $x^n y^n z^n$ in $A$ is $1$,
while the coefficient of $x^n y^n z^n$ in $B$ is $0$.
Now, define
\[ P(x,y,z) \coloneqq A(x,y,z) - \lambda B(x,y,z). \]
where $\lambda = \frac{A(0,0,0)}{B(0,0,0)} = (-1)^{n} (n!)^3$.
We now have that
\begin{itemize}
\ii $P(x,y,z) = 0$ for any $x,y,z \in \left\{ 0,1,\dots,n \right\}^3$.
\ii But the coefficient of $x^n y^n z^n$ is $1$.
\end{itemize}
This is a contradiction to Alon's combinatorial nullstellensatz.
\pagebreak
\end{document}