% © 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 2016 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2016 IMO.
Some of the solutions are my own work,
but many are from the official solutions provided by the organizers
(for which they hold any copyrights),
and others were found by users on the Art of Problem Solving forums.
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
In convex pentagon $ABCDE$ with $\angle B > 90\dg$,
let $F$ be a point on $\ol{AC}$ such that $\angle FBC = 90\dg$.
It is given that $FA=FB$, $DA=DC$, $EA=ED$,
and rays $\ol{AC}$ and $\ol{AD}$ trisect $\angle BAE$.
Let $M$ be the midpoint of $\ol{CF}$.
Let $X$ be the point such that $AMXE$ is a parallelogram.
Show that $\ol{FX}$, $\ol{EM}$, $\ol{BD}$ are concurrent.
\item %% Problem 2
Find all integers $n$ for which each cell of $n \times n$ table
can be filled with one of the letters $I$, $M$ and $O$ in such a way that:
\begin{itemize}
\item In each row and column, one third of the entries are $I$,
one third are $M$ and one third are $O$; and
\item in any diagonal, if the number of entries on the diagonal is a multiple of three,
then one third of the entries are $I$, one third are $M$ and one third are $O$.
\end{itemize}
Note that an $n \times n$ table has $4n-2$ diagonals.
\item %% Problem 3
Let $P=A_1A_2\cdots A_k$ be a convex polygon in the plane.
The vertices $A_1, A_2, \ldots, A_k$ have integral coordinates
and lie on a circle.
Let $S$ be the area of $P$.
An odd positive integer $n$ is given such that
the squares of the side lengths of $P$ are integers divisible by $n$.
Prove that $2S$ is an integer divisible by $n$.
\item %% Problem 4
A set of positive integers is called \emph{fragrant}
if it contains at least two elements and each of its elements
has a prime factor in common with at least one of the other elements.
Let $P(n)=n^2+n+1$.
What is the smallest possible positive integer value of $b$ such that
there exists a non-negative integer $a$ for which the set
\[ \{P(a+1),P(a+2),\ldots,P(a+b)\} \]
is fragrant?
\item %% Problem 5
The equation
\[ (x-1)(x-2)\cdots(x-2016)=(x-1)(x-2)\cdots (x-2016) \]
is written on the board, with $2016$ linear factors on each side.
What is the least possible value of $k$ for which it is possible to
erase exactly $k$ of these $4032$ linear factors so that at least
one factor remains on each side and the resulting equation
has no real solutions?
\item %% Problem 6
There are $n\ge 2$ line segments in the plane such that
every two segments cross and no three segments meet at a point.
Geoff has to choose an endpoint of each segment and place a frog
on it facing the other endpoint. Then he will clap his hands $n-1$ times.
Every time he claps, each frog will immediately jump forward
to the next intersection point on its segment.
Frogs never change the direction of their jumps.
Geoff wishes to place the frogs in such a way that no two of them
will ever occupy the same intersection point at the same time.
\begin{enumerate}[(a)]
\ii Prove that Geoff can always fulfill his wish if $n$ is odd.
\ii Prove that Geoff can never fulfill his wish if $n$ is even.
\end{enumerate}
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{IMO 2016/1, proposed by Art Waeterschoot (BEL)}
\textsl{Available online at \url{https://aops.com/community/p6637656}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
In convex pentagon $ABCDE$ with $\angle B > 90\dg$,
let $F$ be a point on $\ol{AC}$ such that $\angle FBC = 90\dg$.
It is given that $FA=FB$, $DA=DC$, $EA=ED$,
and rays $\ol{AC}$ and $\ol{AD}$ trisect $\angle BAE$.
Let $M$ be the midpoint of $\ol{CF}$.
Let $X$ be the point such that $AMXE$ is a parallelogram.
Show that $\ol{FX}$, $\ol{EM}$, $\ol{BD}$ are concurrent.
\end{mdframed}
Here is a ``long'' solution which I think
shows where the ``power'' in the configuration comes from
(it should be possible to come up with shorter solutions
by cutting more directly to the desired conclusion).
Throughout the proof, we let
\[ \theta = \angle FAB = \angle FBA = \angle DAC = \angle DCA
= \angle EAD = \angle EDA. \]
We begin by focusing just on $ABCD$ with point $F$,
ignoring for now the points $E$ and $X$
(and to some extent even point $M$).
It turns out this is a very familiar configuration.
\begin{lemma*}
[Central lemma]
The points $F$ and $C$
are the incenter and $A$-excenter of $\triangle DAB$.
Moreover, $\triangle DAB$ is isosceles with $DA = DB$.
\end{lemma*}
\begin{proof}
The proof uses three observations:
\begin{itemize}
\ii We already know that $\ol{FAC}$ is the angle bisector of $\angle ABD$.
\ii We were given $\angle FBC = 90\dg$.
\ii Next, note that $\triangle AFB \sim \triangle ADC$
(they are similar isosceles triangles).
From this it follows that $AF \cdot AC = AB \cdot AD$.
\end{itemize}
These three facts, together with $F$ lying inside $\triangle ABD$,
are enough to imply the result.
\end{proof}
\begin{center}
\begin{asy}
pair F = dir(157);
pair C = -F;
pair B = conj(F);
pair M = origin;
pair A = dir(F-C)*abs(F-B)+F;
pair t(pair X) { return A + (X-A) * (F-A) / (B-A); }
pair D = t(C);
filldraw(A--F--B--cycle, opacity(0.1)+red, grey);
filldraw(A--C--D--cycle, opacity(0.1)+orange, grey);
filldraw(F--B--C--cycle, opacity(0.1)+lightcyan, grey);
draw(circumcircle(A, B, D), orange+dashed);
draw(circumcircle(B, C, F), orange+dashed);
draw(B--D, grey);
draw(F--D, grey);
draw(A--B--D--cycle, black+0.8);
dot("$F$", F, dir(115));
dot("$C$", C, dir(C));
dot("$B$", B, dir(B));
dot("$M$", M, dir(280));
dot("$A$", A, dir(A));
dot("$D$", D, dir(60));
/* TSQ Source:
F = dir 157 R115
C = -F
B = conj(F)
M = origin R280
A = dir(F-C)*abs(F-B)+F
!pair t(pair X) { return A + (X-A) * (F-A) / (B-A); }
D = t(C) R60
A--F--B--cycle 0.1 red / grey
A--C--D--cycle 0.1 orange / grey
F--B--C--cycle 0.1 lightcyan / grey
circumcircle A B D orange dashed
circumcircle B C F orange dashed
B--D grey
F--D grey
A--B--D--cycle black+0.8
*/
\end{asy}
\end{center}
\begin{corollary*}
The point $M$ is the midpoint of arc $\widehat{BD}$ of $(DAB)$,
and the center of cyclic quadrilateral $FDCB$.
\end{corollary*}
\begin{proof}
Fact 5.
\end{proof}
Using these observations as the anchor
for everything that follows,
we now prove several claims about $X$ and $E$ in succession.
\begin{center}
\begin{asy}
pair F = dir(157);
pair C = -F;
pair B = conj(F);
pair M = origin;
pair A = dir(F-C)*abs(F-B)+F;
pair t(pair X) { return A + (X-A) * (F-A) / (B-A); }
pair D = t(C);
pair E = t(D);
pair X = E+M-A;
draw(E--F, lightgreen);
draw(D--M, lightgreen);
draw(B--D, lightblue);
draw(F--X, lightblue);
draw(M--E, lightblue);
filldraw(A--F--B--cycle, opacity(0.1)+red, grey);
filldraw(A--C--D--cycle, opacity(0.1)+orange, grey);
filldraw(A--E--D--cycle, opacity(0.1)+yellow, grey);
filldraw(F--B--C--cycle, opacity(0.1)+lightcyan, grey);
draw(A--E--X--M--cycle, heavygreen);
draw(circumcircle(E, F, X), lightgreen+dashed);
draw(circumcircle(A, B, D), orange);
draw(circumcircle(B, C, F), orange);
dot("$F$", F, dir(45));
dot("$C$", C, dir(C));
dot("$B$", B, dir(B));
dot("$M$", M, dir(260));
dot("$A$", A, dir(A));
dot("$D$", D, dir(60));
dot("$E$", E, dir(E));
dot("$X$", X, dir(X));
/* TSQ Source:
F = dir 157 R45
C = -F
B = conj(F)
M = origin R260
A = dir(F-C)*abs(F-B)+F
!pair t(pair X) { return A + (X-A) * (F-A) / (B-A); }
D = t(C) R60
E = t(D)
X = E+M-A
E--F lightgreen
D--M lightgreen
B--D lightblue
F--X lightblue
M--E lightblue
A--F--B--cycle 0.1 red / grey
A--C--D--cycle 0.1 orange / grey
A--E--D--cycle 0.1 yellow / grey
F--B--C--cycle 0.1 lightcyan / grey
A--E--X--M--cycle heavygreen
circumcircle E F X lightgreen dashed
circumcircle A B D orange
circumcircle B C F orange
*/
\end{asy}
\end{center}
\begin{claim*}
Point $E$ is the midpoint of arc $\widehat{AD}$
in $(ABMD)$, and hence lies on ray $BF$.
\end{claim*}
\begin{proof}
This follows from
$\angle EDA = \theta = \angle EBA$.
\end{proof}
\begin{claim*}
Points $X$ is the second intersection of ray $\ol{ED}$
with $(BFDC)$.
\end{claim*}
\begin{proof}
First, $\ol{ED} \parallel \ol{AC}$ already since
$\angle AED = 180\dg - 2\theta$
and $\angle CAE = 2\theta$.
Now since $DB = DA$, we get $MB = MD = ED = EA$.
Thus, $MX = AE = MB$,
so $X$ also lies on the circle $(BFDC)$ centered at $M$.
\end{proof}
\begin{claim*}
The quadrilateral $EXMF$ is an isosceles trapezoid.
\end{claim*}
\begin{proof}
We already know $\ol{EX} \parallel \ol{FM}$.
Since $\angle EFA = 180\dg - \angle AFB = 2\theta = \angle FAE$,
we have $EF = EA$ as well (and $F \neq A$).
As $EXMA$ was a parallelogram,
it follows $EXMF$ is an isosceles trapezoid.
\end{proof}
The problem then follows by radical axis theorem
on the three circles $(AEDMB)$, $(BFDXC)$ and $(EXMF)$.
\pagebreak
\subsection{IMO 2016/2, proposed by Trevor Tau (AUS)}
\textsl{Available online at \url{https://aops.com/community/p6637677}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all integers $n$ for which each cell of $n \times n$ table
can be filled with one of the letters $I$, $M$ and $O$ in such a way that:
\begin{itemize}
\item In each row and column, one third of the entries are $I$,
one third are $M$ and one third are $O$; and
\item in any diagonal, if the number of entries on the diagonal is a multiple of three,
then one third of the entries are $I$, one third are $M$ and one third are $O$.
\end{itemize}
Note that an $n \times n$ table has $4n-2$ diagonals.
\end{mdframed}
The answer is $n$ divisible by $9$.
First we construct $n=9$ and by extension every multiple of $9$.
\[
\begin{array}{|ccc|ccc|ccc|} \hline
I & I & I & M & M & M & O & O & O \\
M & M & M & O & O & O & I & I & I \\
O & O & O & I & I & I & M & M & M \\\hline
I & I & I & M & M & M & O & O & O \\
M & M & M & O & O & O & I & I & I \\
O & O & O & I & I & I & M & M & M \\\hline
I & I & I & M & M & M & O & O & O \\
M & M & M & O & O & O & I & I & I \\
O & O & O & I & I & I & M & M & M \\\hline
\end{array}
\]
We now prove $9 \mid n$ is necessary.
Let $n = 3k$, which divides the given grid into $k^2$ sub-boxes
(of size $3 \times 3$ each).
We say a multiset of squares $S$ is \emph{clean} if
the letters distribute equally among them;
note that unions of clean multisets are clean.
Consider the following clean sets (given to us by problem statement):
\begin{itemize}
\ii All columns indexed $2 \pmod 3$,
\ii All rows indexed $2 \pmod 3$, and
\ii All $4k-2$ diagonals mentioned in the problem.
\end{itemize}
Take their union.
This covers the center of each box four times,
and every other cell exactly once.
We conclude the set of $k^2$ center squares
are clean, hence $3 \mid k^2$ and so $9 \mid n$,
as desired.
Shown below is the sums over all diagonals only,
and of the entire union.
\[
\begin{array}{|ccc|ccc|ccc|} \hline
1 & & 1 & 1 & & 1 & 1 & & 1 \\
& 2 & & & 2 & & & 2 & \\
1 & & 1 & 1 & & 1 & 1 & & 1 \\\hline
1 & & 1 & 1 & & 1 & 1 & & 1 \\
& 2 & & & 2 & & & 2 & \\
1 & & 1 & 1 & & 1 & 1 & & 1 \\\hline
1 & & 1 & 1 & & 1 & 1 & & 1 \\
& 2 & & & 2 & & & 2 & \\
1 & & 1 & 1 & & 1 & 1 & & 1 \\\hline
\end{array}
\qquad
\begin{array}{|ccc|ccc|ccc|} \hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 4 & 1 & 1 & 4 & 1 & 1 & 4 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 4 & 1 & 1 & 4 & 1 & 1 & 4 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 4 & 1 & 1 & 4 & 1 & 1 & 4 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
\end{array}
\]
\pagebreak
\subsection{IMO 2016/3, proposed by Russia}
\textsl{Available online at \url{https://aops.com/community/p6637660}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $P=A_1A_2\cdots A_k$ be a convex polygon in the plane.
The vertices $A_1, A_2, \ldots, A_k$ have integral coordinates
and lie on a circle.
Let $S$ be the area of $P$.
An odd positive integer $n$ is given such that
the squares of the side lengths of $P$ are integers divisible by $n$.
Prove that $2S$ is an integer divisible by $n$.
\end{mdframed}
Solution by Jeck Lim:
We will prove the result just for $n = p^e$
where $p$ is an odd prime and $e \ge 1$.
The case $k=3$ is resolved by Heron's formula directly:
we have $S = \frac14\sqrt{2(a^2b^2 + b^2c^2 + c^2a^2) - a^4-b^4-c^4}$,
so if $p^e \mid \gcd(a^2,b^2,c^2)$ then $p^{2e} \mid S^2$.
Now we show we can pick a diagonal and induct down on $k$
by using inversion.
Let the polygon be $A_1 A_2 \dots A_{k+1}$
and suppose for contradiction that all sides are divisible by $p^e$
but no diagonals are.
Let $O = A_{k+1}$ for notational convenience.
By applying inversion around $O$ with radius $1$,
we get the ``generalized Ptolemy theorem''
\[
\frac{A_1A_2}{OA_1 \cdot OA_2}
+ \frac{A_2A_3}{OA_2 \cdot OA_3}
+ \dots
+ \frac{A_{k-1} A_k}{OA_{k-1} \cdot OA_k}
= \frac{A_1 A_k}{OA_1 \cdot OA_k}
\]
or, making use of square roots,
\[
\sqrt{\frac{A_1A_2^2}{OA_1^2 \cdot OA_2^2}}
+ \sqrt{\frac{A_2A_3^2}{OA_2^2 \cdot OA_3^2}}
+ \dots
+ \sqrt{\frac{A_{k-1} A_k^2}{OA_{k-1}^2 \cdot OA_k^2}}
= \sqrt{\frac{A_1 A_k^2}{OA_1^2 \cdot OA_k^2}}
\]
Suppose $\nu_p$ of all diagonals is strictly less than $e$.
Then the relation becomes
\[ \sqrt{q_1} + \dots + \sqrt{q_{k-1}} = \sqrt q \]
where $q_i$ are positive rational numbers.
Since there are no nontrivial relations between square roots
(see \href{https://qchu.wordpress.com/2009/07/02/square-roots-have-no-unexpected-linear-relationships/}{this link})
there is a positive rational number $b$
such that $r_i = \sqrt{q_i/b}$ and $r = \sqrt{q/b}$
are all rational numbers.
Then
\[ \sum r_i = r. \]
However, the condition implies that $\nu_p(q_i^2) > \nu_p(q^2)$ for all $i$
(check this for $i=1$, $i=k-1$ and $2 \le i \le k-2$),
and hence $\nu_p(r_i) > \nu_p(r)$.
This is absurd.
\begin{remark*}
I think you basically have to use some Ptolemy-like geometric property,
and also all correct solutions I know of $n = p^e$
depend on finding a diagonal and inducting down.
(Actually, the case $k=4$ is pretty motivating;
Ptolemy implies one can cut in two.)
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{IMO 2016/4, proposed by Luxembourg}
\textsl{Available online at \url{https://aops.com/community/p6642559}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A set of positive integers is called \emph{fragrant}
if it contains at least two elements and each of its elements
has a prime factor in common with at least one of the other elements.
Let $P(n)=n^2+n+1$.
What is the smallest possible positive integer value of $b$ such that
there exists a non-negative integer $a$ for which the set
\[ \{P(a+1),P(a+2),\ldots,P(a+b)\} \]
is fragrant?
\end{mdframed}
The answer is $b = 6$.
First, we prove $b \ge 6$ must hold.
It is not hard to prove the following divisibilities by Euclid:
\begin{align*}
\gcd(P(n), P(n+1)) &\mid 1 \\
\gcd(P(n), P(n+2)) &\mid 7 \\
\gcd(P(n), P(n+3)) &\mid 3 \\
\gcd(P(n), P(n+4)) &\mid 19.
\end{align*}
Now assume for contradiction $b \le 5$.
Then any GCD's among $P(a+1)$, \dots, $P(a+b)$ must be among $\{3, 7, 19\}$.
Consider a multi-graph on $\{a+1, \dots, a+b\}$ where we join two elements with nontrivial GCD
and label the edge with the corresponding prime.
Then we readily see there is at most one edge each of $\{3, 7, 19\}$:
id est at most one edge of gap $2$, $3$, $4$ (and no edges of gap $1$).
(By the gap of an edge $e = \{u,v\}$ we mean $|u - v|$.)
But one can see that it's now impossible for every vertex to have nonzero degree, contradiction.
To construct $b = 6$ we use the Chinese remainder theorem: select $a$ with
\begin{align*}
a+1 & \equiv 7 \pmod{19} \\
a+5 & \equiv 11 \pmod{19} \\
a+2 & \equiv 2 \pmod{7} \\
a+4 & \equiv 4 \pmod{7} \\
a+3 & \equiv 1 \pmod{3} \\
a+6 & \equiv 1 \pmod{3}
\end{align*}
which does the trick.
\pagebreak
\subsection{IMO 2016/5, proposed by Russia}
\textsl{Available online at \url{https://aops.com/community/p6642565}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
The equation
\[ (x-1)(x-2)\cdots(x-2016)=(x-1)(x-2)\cdots (x-2016) \]
is written on the board, with $2016$ linear factors on each side.
What is the least possible value of $k$ for which it is possible to
erase exactly $k$ of these $4032$ linear factors so that at least
one factor remains on each side and the resulting equation
has no real solutions?
\end{mdframed}
The answer is $2016$.
Obviously this is necessary in order to delete duplicated factors.
We now prove it suffices to deleted $2 \pmod 4$ and $3 \pmod 4$
guys from the left-hand side, and $0 \pmod 4$,
$1 \pmod 4$ from the right-hand side.
Consider the $1008$ inequalities
\begin{align*}
(x-1)(x-4) &< (x-2)(x-3) \\
(x-5)(x-8) &< (x-6)(x-7) \\
(x-9)(x-12) &< (x-10)(x-11) \\
&\vdots \\
(x-2013)(x-2016) &< (x-2014)(x-2015).
\end{align*}
Notice that in all these inequalities, at most one of them
has non-positive numbers in it, and we never have both zero.
If there is exactly one negative term among the $1008 \cdot 2 = 2016$ sides,
it is on the left and we can multiply all together.
Thus the only case that remains is if $x \in (4m-2, 4m-1)$ for some $m$,
say the $m$th inequality.
In that case, the two sides of that inequality differ by a factor of at least $9$.
\begin{claim*}
We have \[ \prod_{k \ge 0} \frac{(4k+2)(4k+3)}{(4k+1)(4k+4)} < e. \]
\end{claim*}
\begin{proof}
[Proof of claim using logarithms]
To see this, note that it's equivalent to prove
\[ \sum_{k \ge 0} \log \left( 1 + \frac{2}{(4k+1)(4k+4)} \right) < 1. \]
To this end, we use the deep fact that $\log(1+t) \le t$,
and thus it follows from
$\sum_{k \ge 0} \frac{1}{(4k+1)(4k+4)} < \half$,
which one can obtain for example by noticing
it's less than $\frac14\frac{\pi^2}{6}$.
\end{proof}
\begin{proof}
[Elementary proof of claim, given by Espen Slettnes]
For each $N \ge 0$, the partial product is bounded by
\begin{align*}
\prod_{k=0}^N \frac{(4k+2)(4k+3)}{(4k+1)(4k+4)}
&=
\frac 21 \cdot \left( \frac 34 \cdot \frac 65 \right)
\cdot \left( \frac 78 \cdot \frac{10}{9} \right) \cdot \dots
\cdot \frac{4N+3}{4N+4} \\
&< 2 \cdot 1 \cdot 1 \cdot \dots \cdot \frac{4N+3}{4N+4}
< 2 < e. \qedhere
\end{align*}
\end{proof}
This solves the problem,
because then the factors being multiplied
on by the positive inequalities before the
$m$th one are both less than $e$, and $e^2 < 9$.
In symbols, for $4m-2 < x < 4m-1$ we should have
\[
\frac{(x-(4m-6))(x-(4m-5))}{(x-(4m-7))(x-(4m-4))}
% \times \frac{(x-(4m-10))(x-(4m-9))}{(x-(4m-11))(x-(4m-8))}
\times
\dots
\times
\frac{(x-2)(x-3)}{(x-1)(x-4)}
< e \]
and
\[
\frac{(x-(4m+2))(x-(4m+3))}{(x-(4m+1))(x-(4m+4))}
% \times \frac{(x-(4m+6))(x-(4m+7))}{(x-(4m+1))(x-(4m+4))}
\times
\dots
\times
\frac{(x-2014)(x-2015)}{(x-2013)(x-2016)}
< e
\]
because the $(k+1)$st term of each left-hand side
is at most $\frac{(4k+2)(4k+3)}{(4k+1)(4k+4)}$, for $k \ge 0$.
As $e^2 < 9$, we're okay.
\pagebreak
\subsection{IMO 2016/6, proposed by Josef Tkadlec (CZE)}
\textsl{Available online at \url{https://aops.com/community/p6642576}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
There are $n\ge 2$ line segments in the plane such that
every two segments cross and no three segments meet at a point.
Geoff has to choose an endpoint of each segment and place a frog
on it facing the other endpoint. Then he will clap his hands $n-1$ times.
Every time he claps, each frog will immediately jump forward
to the next intersection point on its segment.
Frogs never change the direction of their jumps.
Geoff wishes to place the frogs in such a way that no two of them
will ever occupy the same intersection point at the same time.
\begin{enumerate}[(a)]
\ii Prove that Geoff can always fulfill his wish if $n$ is odd.
\ii Prove that Geoff can never fulfill his wish if $n$ is even.
\end{enumerate}
\end{mdframed}
The following solution was communicated to me by Yang Liu.
Imagine taking a larger circle $\omega$ encasing
all $\binom{n}{2}$ intersection points.
Denote by $P_1$, $P_2$, \dots, $P_{2n}$ the order of the points on $\omega$
in clockwise order; we imagine placing the frogs on $P_i$ instead.
Observe that, in order for every pair of segments to meet,
each line segment must be of the form $P_i P_{i+n}$.
\begin{center}
\begin{asy}
draw(unitcircle);
pair P_1 = dir(100);
pair P_2 = dir(150);
pair P_3 = dir(190);
pair P_4 = dir(210);
pair P_5 = dir(280);
pair P_6 = dir(340);
pair P_7 = dir(2);
pair P_8 = dir(55);
dot("$1$", P_1, dir(P_1));
dot("$2$", P_2, dir(P_2));
dot("$3$", P_3, dir(P_3));
dot("$4$", P_4, dir(P_4));
dot("$5$", P_5, dir(P_5));
dot("$6$", P_6, dir(P_6));
dot("$7$", P_7, dir(P_7));
dot("$8$", P_8, dir(P_8));
draw(P_1--P_5);
draw(P_2--P_6);
draw(P_3--P_7);
draw(P_4--P_8);
dot(extension(P_1, P_5, P_2, P_6), red);
dot(extension(P_1, P_5, P_3, P_7), red);
dot(extension(P_1, P_5, P_4, P_8), red);
dot(extension(P_2, P_6, P_3, P_7), red);
dot(extension(P_2, P_6, P_4, P_8), red);
dot(extension(P_3, P_7, P_4, P_8), red);
\end{asy}
\end{center}
Then:
\begin{enumerate}[(a)]
\ii Place the frogs on $P_1$, $P_3$, \dots, $P_{2n-1}$.
A simple parity arguments shows this works.
\ii Observe that we cannot place frogs on consecutive $P_i$,
so the $n$ frogs must be placed on alternating points.
But since we also are supposed to not place frogs on
diametrically opposite points,
for even $n$ we immediately get a contradiction.
\end{enumerate}
\begin{remark*}
Yang says: this is easy to guess if you just do a
few small cases and notice that the pairs of
``violating points'' just forms a large cycle around.
\end{remark*}
\pagebreak
\end{document}