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

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2018 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 $\Gamma$ be the circumcircle of acute triangle $ABC$.
Points $D$ and $E$ lie on segments $AB$ and $AC$,
respectively, such that $AD = AE$.
The perpendicular bisectors of $\ol{BD}$ and $\ol{CE}$
intersect the minor arcs $AB$ and $AC$ of $\Gamma$
at points $F$ and $G$, respectively.
Prove that the lines $DE$ and $FG$ are parallel.

\item %% Problem 2
Find all integers $n \geq 3$ for which
there exist real numbers $a_1, a_2, \dots, a_n$ satisfying
\[ a_i a_{i+1} +1 = a_{i+2} \]
for $i=1,2, \dots, n$, where indices are taken modulo $n$.

\item %% Problem 3
An \emph{anti-Pascal triangle} is an equilateral triangular array
of numbers such that, except for the numbers in the bottom row,
each number is the absolute value of the difference
of the two numbers immediately below it.
For example, the following array is an anti-Pascal triangle
with four rows which contains every integer from $1$ to $10$.
\begin{center}
\begin{tikzpicture}[scale = 0.8]
\node at (1.5,2.58) {$4$};
\node at (1,1.72) {$2$};
\node at (2,1.72) {$6$};
\node at (0.5,0.86) {$5$};
\node at (1.5,0.86) {$7$};
\node at (2.5,0.86) {$1$};
\node at (0,0) {$8$};
\node at (1,0) {$3$};
\node at (2,0) {$10$};
\node at (3,0) {$9$};
\end{tikzpicture}
\end{center}
Does there exist an anti-Pascal triangle with $2018$ rows
which contains every integer from $1$ to $1+2+\dots +2018$?

\item %% Problem 4
A \emph{site} is any point $(x,y)$ in the plane
for which $x,y \in \{1, \dots, 20\}$.
Initially, each of the $400$ sites is unoccupied.
Amy and Ben take turns placing stones on unoccupied sites,
with Amy going first;
Amy has the additional restriction that no two of her stones
may be at a distance equal to $\sqrt5$.
They stop once either player cannot move.
Find the greatest $K$ such that Amy can ensure that
she places at least $K$ stones.

\item %% Problem 5
Let $a_1$, $a_2$, \dots\ be an infinite sequence of positive integers,
and $N$ a positive integer.
Suppose that for all integers $n \ge N$, the expression
\[ \frac{a_1}{a_2} + \frac{a_2}{a_3} + \dots
  + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1} \]
is an integer.
Prove that $(a_n)$ is eventually constant.

\item %% Problem 6
A convex quadrilateral $ABCD$ satisfies $AB \cdot CD = BC \cdot DA$.
Point $X$ lies inside $ABCD$ so that
\[ \angle XAB=\angle XCD \quad \text{ and } \quad \angle XBC=\angle XDA. \]
Prove that $\angle BXA + \angle DXC=180\dg$.

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{IMO 2018/1, proposed by Silouanos Brazitikos, Vangelis Psyxas, Michael Sarantis (HEL)}
\textsl{Available online at \url{https://aops.com/community/p10626500}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $\Gamma$ be the circumcircle of acute triangle $ABC$.
Points $D$ and $E$ lie on segments $AB$ and $AC$,
respectively, such that $AD = AE$.
The perpendicular bisectors of $\ol{BD}$ and $\ol{CE}$
intersect the minor arcs $AB$ and $AC$ of $\Gamma$
at points $F$ and $G$, respectively.
Prove that the lines $DE$ and $FG$ are parallel.
\end{mdframed}
We present a synthetic solution from the IMO shortlist
as well as a complex numbers approach.
We also outline a trig solution (the one I found at IMO),
and a fourth solution from Derek Liu.


\paragraph{Synthetic solution (from Shortlist).}
Construct parallelograms $AXFD$ and $AEGY$,
noting that $X$ and $Y$ lie on $\Gamma$.
As $\ol{XF} \parallel \ol{AB}$ we can let $M$
denote the midpoint of minor arcs $\widehat{XF}$ and $\widehat{AB}$
(which coincide). Define $N$ similarly.

\begin{center}
\begin{asy}
pair A = dir(110);
pair B = dir(210);
pair C = dir(330);
pair F = dir(190);
pair M = dir(160);
pair N = dir(40);
pair G = M*N/F;
pair K = foot(F, A, B);
pair L = foot(G, A, C);
pair D = -B+2*K;
pair E = -C+2*L;
pair X = M*M/F;
pair Y = N*N/G;
filldraw(unitcircle, opacity(0.1)+lightcyan, lightblue);
draw(D--B--C--E--cycle, lightblue);

draw(X--A, red);
draw(A--Y, pink);
draw(F--X, heavygreen);
draw(Y--G, heavygreen);
draw(F--G, dotted+blue);
draw(M--N, dotted+blue);
filldraw(A--X--F--D--cycle, opacity(0.1)+lightgreen, heavygreen);
filldraw(A--E--G--Y--cycle, opacity(0.1)+lightgreen, heavygreen);
draw(B--F, heavygreen);
draw(C--G, heavygreen);

draw(X--F, heavycyan+1);
draw(D--A--E, heavycyan+1);
draw(Y--G, heavycyan+1);

dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$F$", F, dir(F));
dot("$M$", M, dir(M));
dot("$N$", N, dir(N));
dot("$G$", G, dir(G));
dot("$D$", D, dir(160));
dot("$E$", E, dir(80));
dot("$X$", X, dir(X));
dot("$Y$", Y, dir(Y));

/* TSQ Source:

A = dir 110
B = dir 210
C = dir 330
F = dir 190
M = dir 160
N = dir 40
G = M*N/F
K := foot F A B
L := foot G A C
D = -B+2*K R160
E = -C+2*L R80
X = M*M/F
Y = N*N/G
unitcircle 0.1 lightcyan / lightblue
D--B--C--E--cycle lightblue

X--A red
A--Y pink
F--X heavygreen
Y--G heavygreen
F--G dotted blue
M--N dotted blue
A--X--F--D--cycle 0.1 lightgreen / heavygreen
A--E--G--Y--cycle 0.1 lightgreen / heavygreen
B--F heavygreen
C--G heavygreen

X--F heavycyan+1
D--A--E heavycyan+1
Y--G heavycyan+1

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

Observe that $XF = AD = AE = YG$,
so arcs $\widehat{XF}$ and $\widehat{YG}$ have equal measure;
hence arcs $\widehat{MF}$ and $\widehat{NG}$ have equal measure;
therefore $\ol{MN} \parallel \ol{FG}$.

Since $\ol{MN}$ and $\ol{DE}$ are both perpendicular
to the $\angle A$ bisector, so we're done.

\paragraph{Complex numbers solution.}
Let $b$, $c$, $f$, $g$, $a$ be as usual.
Note that
\begin{align*}
  d-a &= \left( 2 \cdot \frac{f+a+b-ab\ol f}{2} -b \right)-a
    = f - \frac{ab}{f} \\
  e-a &= g - \frac{ac}{g}
\end{align*}
We are given $AD = AE$ from which one deduces
\begin{align*}
  \left( \frac{e-a}{d-a} \right)^2 &= \frac cb
  \implies \frac{(g^2-ac)^2}{(f^2-ab)^2} = \frac{g^2 c}{f^2 b} \\
  \implies bc(bg^2-cf^2)a^2 &= g^2f^4c - f^2g^4b = f^2g^2(f^2c-g^2b) \\
  \implies bc \cdot a^2 &= (fg)^2 \implies \left( -\frac{fg}{a} \right)^2 = bc.
\end{align*}
Since $\frac{-fg}{a}$ is the point $X$ on the circle
with $\ol{AX} \perp \ol{FG}$,
we conclude $\ol{FG}$ is either parallel or perpendicular
to the $\angle A$-bisector; it must the latter
since the $\angle A$-bisector separates the two minor arcs.

\paragraph{Trig solution (outline).}
Let $\ell$ denote the $\angle A$ bisector.
Fix $D$ and $F$.
We define the phantom point $G'$ such that $\ol{FG'} \perp \ell$
and $E'$ on side $\ol{AC}$ such that $GE'=GC$.
\begin{claim*}
  [Converse of the IMO problem]
  We have $AD = AE'$, so that $E = E'$.
\end{claim*}
\begin{proof}
  Since $\ol{FG'} \perp \ell$,
  one can deduce $\angle FBD = \half C + x$
  and $\angle GCA = \half B + x$ for some $x$.
  (One fast way to see this is to note that $\ol{FG} \parallel \ol{MN}$
  where $M$ and $N$ are in the first solution.)
  Then $\angle FAB = \half C -x$ and $\angle GAC = \half B - x$.

  Let $R$ be the circumradius.
  Now, by the law of sines,
  \[ BF = 2R \sin\left( \half C - x \right). \]
  From there we get
  \begin{align*}
  BD &= 2 \cdot BF \cos\left(\half C + x\right)
    = 4R \cos\left(\half C+x\right) \sin \left(\half C-x\right) \\
  DA &= AB - BD = 2R\sin C
    - 4R\cos\left(\half C+x\right) \sin\left(\half C -x\right) \\
  &= 2R\left[ \sin C - 2\cos\left( \half C + x \right) \sin \left( \half C -x \right) \right] \\
  &= 2R\left[ \sin C - \left( \sin C - \sin 2x  \right) \right]
  = 2R \sin 2x.
  \end{align*}
  A similar calculation gives $AE' = 2R \sin 2x$ as needed.
\end{proof}
Thus, $\ol{FG'} \parallel \ol{DE}$, so $G = G'$ as well.
This concludes the proof.

\paragraph{Synthetic solution from Derek Liu.}
Let lines $FD$ and $GE$ intersect $\Gamma$ again at $J$ and $K$, respectively.
\begin{center}
\begin{asy}
unitsize(0.5cm);
import graph;
pair A=(-2.5,6), B=(-5.2,-3.9), C=(5.2,-3.9), D=(-4,0.5), E=(1,1.5), F=(-6.39,-1.21), G=(6.36,1.33), J=(3.19,5.66), K=(-6.27,1.72);
draw(Circle((0,0),6.5)); draw(A--B--C--A); draw(B--F--J--A--K--G--C); draw(Circle(A,5.7),dashed);
dot(A); dot(B); dot(C); dot(D); dot(E); dot(F); dot(G); dot(J); dot(K);
label("$A$",A,N);
label("$B$",B,SW);
label("$C$",C,SE);
label("$D$",D,SSE);
label("$E$",E,S);
label("$F$",F,W);
label("$G$",G,E);
label("$J$",J,ENE);
label("$K$",K,WSW);
\end{asy}
\end{center}
Notice that $\triangle BFD\sim\triangle JAD$; as $FB=FD$, it follows that $AJ=AD$.
Likewise, $\triangle CGE\sim\triangle KAE$ and $GC=GE$, so $AK=AE$.
Hence,
\[ AK=AE=AD=AJ, \]
so $DEJK$ is cyclic with center $A$.

It follows that
\[ \dang KED=\dang KJD=\dang KJF=\dang KGF, \]
so we're done.
\begin{remark*}
Note that $K$ and $J$ must be distinct for this solution to work.
Since $G$ and $K$ lie on opposite sides of $AC$, $K$ is on major arc $ABC$.
As $AK=AD=AE\le \min(AB,AC)$, $K$ lies on minor arc $AB$.
Similarly, $J$ lies on minor arc $AC$, so $K\neq J.$
\end{remark*}
\pagebreak

\subsection{IMO 2018/2, proposed by Patrik Bak (SVK)}
\textsl{Available online at \url{https://aops.com/community/p10626524}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all integers $n \geq 3$ for which
there exist real numbers $a_1, a_2, \dots, a_n$ satisfying
\[ a_i a_{i+1} +1 = a_{i+2} \]
for $i=1,2, \dots, n$, where indices are taken modulo $n$.
\end{mdframed}
The answer is $3 \mid n$,
achieved by $(-1,-1,2,-1,-1,2,\dots)$.
We present two solutions.

\paragraph{First solution by inequalities.}
We compute $a_i a_{i+1} a_{i+2}$ in two ways:
\begin{align*}
  a_i a_{i+1} a_{i+2} &= [a_{i+2}-1]a_{i+2} = a_{i+2}^2 - a_{i+2} \\
  &= a_i [a_{i+3}-1] = a_i a_{i+3} - a_i.
\end{align*}
Cyclically summing $a_{i+2}^2 - a_{i+2} = a_i a_{i+3} - a_i$ then gives
\[ \sum_i a_{i+2}^2 = \sum_i a_i a_{i+3}
  \iff \sum_{\text{cyc}} \left( a_i - a_{i+3} \right)^2 = 0.  \]
This means for inequality reasons the sequence is $3$-periodic.
Since the sequence is clearly not $1$-periodic,
as $x^2 + 1 = x$ has no real solutions.
Thus $3 \mid n$.

\paragraph{Second solution by sign counting.}
Extend $a_n$ to be a periodic sequence.
The idea is to look at the signs, and show the sequence
of the signs must be $--+$ repeated.
This takes several steps:
\begin{itemize}
  \ii The pattern $---$ is impossible. Obvious, since the third term should be $ > 1$.
  \ii The pattern $++$ is impossible. Then the sequence becomes strictly increasing,
  hence may not be periodic.
  \ii Zeros are impossible. If $a_1 = 0$, then $a_2 = 0$, $a_3 > 0$, $a_4 > 0$,
  which gives the impossible $++$.
  \ii The pattern $--+-+$ is impossible.
  Compute the terms:
  \begin{align*}
    a_1 &= -x < 0 \\
    a_2 &= -y < 0 \\
    a_3 &= 1 + xy > 1 \\
    a_4 &= 1 - y(1+xy) < 0 \\
    a_5 &= 1 + (1+xy)(1-y(1+xy)) < 1.
  \end{align*}
  But now
  \[ a_6 - a_5 = (1 + a_5 a_4) - (1 + a_3 a_4)
    = a_4 (a_5 - a_3) > 0 \]
  since $a_5 > 1 > a_3$.
  This means we have the impossible $++$ pattern.
  \ii The infinite alternating pattern $-+-+-+-+\dots$ is impossible.
  Note that
  \[ a_1 a_2 + 1 = a_3 < 0 < a_4 = 1 + a_2 a_3 \implies a_1 < a_3 \]
  since $a_2 > 0$;
  extending this we get $a_1 < a_3 < a_5 < \dots$
  which contradicts the periodicity.
\end{itemize}
We finally collate the logic of sign patterns.
Since the pattern is not alternating, there must be $--$ somewhere.
Afterwards must be $+$, and then after that must be two minus signs
(since one minus sign is impossible by impossibility of $--+-+$
and $---$ is also forbidden);
thus we get the periodic $--+$ as desired.
\pagebreak

\subsection{IMO 2018/3, proposed by Morteza Saghafian (IRN)}
\textsl{Available online at \url{https://aops.com/community/p10626557}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
An \emph{anti-Pascal triangle} is an equilateral triangular array
of numbers such that, except for the numbers in the bottom row,
each number is the absolute value of the difference
of the two numbers immediately below it.
For example, the following array is an anti-Pascal triangle
with four rows which contains every integer from $1$ to $10$.
\begin{center}
\begin{tikzpicture}[scale = 0.8]
\node at (1.5,2.58) {$4$};
\node at (1,1.72) {$2$};
\node at (2,1.72) {$6$};
\node at (0.5,0.86) {$5$};
\node at (1.5,0.86) {$7$};
\node at (2.5,0.86) {$1$};
\node at (0,0) {$8$};
\node at (1,0) {$3$};
\node at (2,0) {$10$};
\node at (3,0) {$9$};
\end{tikzpicture}
\end{center}
Does there exist an anti-Pascal triangle with $2018$ rows
which contains every integer from $1$ to $1+2+\dots +2018$?
\end{mdframed}
The answer is no, there is no anti-Pascal triangle
with the required properties.

Let $n = 2018$ and $N = 1+2+\dots+n$.
For every number $d$ not in the bottom row,
draw an arrow from $d$ to the larger of the two numbers below it
(i.e.\ if $d=a-b$, draw $d \to a$).
This creates an \emph{oriented forest} (which looks like lightning strikes).

Consider the directed path starting from the top vertex $A$.
Starting from the first number, it increments by at least $1+2+\dots+n$,
since the increments at each step in the path are distinct;
therefore equality must hold
and thus the path from the top ends at $N = 1+2+\dots+n$
with all the numbers $\{1,2,\dots,n\}$ being close by.
Let $B$ be that position.

\begin{center}
\begin{asy}
  size(8cm);
  pair P(int x, int y) {
    return x*dir(60)+y*dir(0);
  }
  pair A = P(12,0);
  draw(A--P(0,0)--P(0,12)--cycle, grey+0.4);
  draw(A--P(11,1)--P(9,1)--P(8,2)--P(5,5)--P(3,7)--P(1,7)--P(0,8),
    orange+1.1, EndArrow(TeXHead));
  draw(P(0,7)--P(7,0), blue);
  draw(P(0,9)--P(3,9), blue);
  draw(P(7,0)--P(6,0)--P(5,1)--P(3,1)--P(2,2)--P(0,2),
    orange+1.1, EndArrow(TeXHead));

  dot("$A$", A, dir(90));
  dot("$B$", P(0,8), dir(-90));
  dot("$C$", P(7,0), dir(150));
  dot("$D$", P(0,2), dir(-90));
  dot("$X$", P(0,7), dir(-90));
  dot("$Y$", P(0,9), dir(-90));
  dot(P(3,9));
\end{asy}
\end{center}
Consider the two left/right neighbors $X$ and $Y$ of the endpoint $B$.
Assume that $B$ is to the right of the midpoint of the bottom side,
and complete the equilateral triangle as shown to an apex $C$.
Consider the lightning strike from $C$ hitting the bottom at $D$.
It travels at least $\left\lfloor n/2-1 \right\rfloor$ steps, by construction.
But the increases must be at least $n+1$, $n+2$, \dots since $1,2,\dots,n$
are close to the $A \to B$ lightning path.
Then the number at $D$ is at least
\[ (n+1) + (n+2) + \dots +
  \left( n+\left( \left\lfloor n/2-1 \right\rfloor \right) \right)
  > 1 + 2 + \dots + n \]
for $n \ge 2018$, contradiction.
\pagebreak

\section{Solutions to Day 2}
\subsection{IMO 2018/4, proposed by Gurgen Asatryan (ARM)}
\textsl{Available online at \url{https://aops.com/community/p10632348}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A \emph{site} is any point $(x,y)$ in the plane
for which $x,y \in \{1, \dots, 20\}$.
Initially, each of the $400$ sites is unoccupied.
Amy and Ben take turns placing stones on unoccupied sites,
with Amy going first;
Amy has the additional restriction that no two of her stones
may be at a distance equal to $\sqrt5$.
They stop once either player cannot move.
Find the greatest $K$ such that Amy can ensure that
she places at least $K$ stones.
\end{mdframed}
The answer is $K = 100$.

First, we show Amy can always place at least $100$ stones.
Indeed, treat the problem as a grid with checkerboard coloring.
Then Amy can choose to always play on one of the $200$ black squares.
In this way, she can guarantee half the black squares,
i.e.\ she can get $\half \cdot 200 = 100$ stones.

Second, we show Ben can prevent Amy from placing more than $100$ stones.
Divide into several $4 \times 4$ squares and then further partition
each $4 \times 4$ squares as shown in the grid below.
\[
  \left[
  \begin{array}{cccc}
    1 & 2 & 3 & 4 \\
    3 & 4 & 1 & 2 \\
    2 & 1 & 4 & 3 \\
    4 & 3 & 2 & 1
  \end{array}
  \right]
\]
The squares with each label form $4$-cycles by knight jumps.
For each such cycle, whenever Amy plays in the cycle,
Ben plays in the opposite point of the cycle,
preventing Amy from playing any more stones in that original cycle.
Hence Amy can play at most in $1/4$ of the stones, as desired.
\pagebreak

\subsection{IMO 2018/5, proposed by Bayarmagnai Gombodorj (MNG)}
\textsl{Available online at \url{https://aops.com/community/p10632353}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $a_1$, $a_2$, \dots\ be an infinite sequence of positive integers,
and $N$ a positive integer.
Suppose that for all integers $n \ge N$, the expression
\[ \frac{a_1}{a_2} + \frac{a_2}{a_3} + \dots
  + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1} \]
is an integer.
Prove that $(a_n)$ is eventually constant.
\end{mdframed}
The condition implies that the difference
\[ S(n) = \frac{a_{n+1} - a_n}{a_1} + \frac{a_n}{a_{n+1}} \]
is an integer for all $n > N$.
We proceed by $p$-adic valuation only henceforth;
fix a prime $p$.
Then analyzing the $\nu_p$, we immediately get that for $n > N$:
\begin{itemize}
\ii If $\nu_p(a_n) < \nu_p(a_{n+1})$, then $\nu_p(a_{n+1}) = \nu_p(a_1)$.
\ii If $\nu_p(a_n) = \nu_p(a_{n+1})$, no conclusion.
\ii If $\nu_p(a_n) > \nu_p(a_{n+1})$,
then $\nu_p(a_{n+1}) \ge \nu_p(a_1)$.
\end{itemize}
In other words:
\begin{claim*}
Let $p$ be a prime.  Consider the sequence
$\nu_p(a_{N+1})$, $\nu_p(a_{N+2})$, \dots.
Then either:
\begin{itemize}
  \ii We have $\nu_p(a_{N+1}) \ge \nu_p(a_{N+2}) \ge \dots$
  and so on, i.e.\ the sequence is weakly decreasing immediately; or
  \ii For some index $K > N$ we have
  $\nu_p(a_K) < \nu_p(a_{K+1}) = \nu_p(a_{K+2}) = \dots = \nu_p(a_1)$,
  i.e.\ the sequence ``jumps'' to $\nu_p(a_1)$
  at some point and then stays there forever after.
  Note this requires $\nu_p(a_1) > 0$.
\end{itemize}
\end{claim*}

A cartoon of the situation is drawn below.
\begin{center}
  \begin{asy}
    label("$\nu_p(a_1)$", (0,3), dir(180), deepcyan);
    draw( (0,3)--(11,3), blue+dotted );
    draw( (0,9)--(0,-1)--(12,-1), black, Arrows );
    dot( (1,6), red );
    dot( (2,5), red );
    dot( (3,5), red );
    dot( (4,5), red );
    dot( (5,4), red );
    dot( (6,4), red );
    dot( (7,4), red );
    dot( (8,3), red );
    dot( (1,9), darkred );
    dot( (2,7), darkred );
    dot( (3,6), darkred );
    dot( (4,6), darkred );
    dot( (5,6), darkred );
    dot( (6,6), darkred );
    dot( (7,6), darkred );
    dot( (8,6), darkred );
    dot( (9,6), darkred );
    draw( (1,6)--(2,5)--(4,5)--(5,4)--(7,4)--(8,3), red );
    draw( (1,9)--(2,7)--(3,6)--(4,6)--(9,6), darkred );
    dot( (1,1), brown );
    dot( (2,1), brown );
    dot( (3,1), brown );
    dot( (4,1), brown );
    dot( (5,1), brown );
    dot( (6,3), brown );
    dot( (6,3), brown );
    draw( (1,1)--(5,1)--(6,3), brown );
    dot( (1,0), orange );
    dot( (2,0), orange );
    dot( (3,0), orange );
    dot( (4,0), orange );
    dot( (5,0), orange );
    dot( (6,0), orange );
    dot( (7,0), orange );
    dot( (8,0), orange );
    dot( (9,0), orange );
    draw( (1,0)--(9,0), orange );
    draw( (1,-0.8)--(1,-1.2) );
    draw("$n > N$", (1,-1.2), dir(-90) );
  \end{asy}
\end{center}

As only finitely many primes $p$ divide $a_1$,
after some time $\nu_p(a_n)$ is fixed for all such $p \mid a_1$.
Afterwards, the sequence satisfies $a_{n+1} \mid a_n$ for each $n$,
and thus must be eventually constant.

\begin{remark*}
  This solution is almost completely $p$-adic,
  in the sense that I think a similar result
  holds if one replaces $a_n \in \ZZ$
  by $a_n \in \ZZ_p$ for any particular prime $p$.
  In other words, the primes almost do not talk to each other.

  There is one caveat: if $x_n$ is an integer sequence
  such that $\nu_p(x_n)$ is eventually constant for each prime
  then $x_n$ may not be constant.
  For example, take $x_n$ to be the $n$th prime!
  That's why in the first claim (applied to co-finitely many of the primes),
  we need the stronger non-decreasing condition,
  rather than just eventually constant.
\end{remark*}

\begin{remark*}
  An alternative approach is to show that, when the fractions $a_n / a_1$
  is written in simplest form for $n = N+1, N+2, \dots$,
  the numerator and denominator are both weakly decreasing.
  Hence it must eventually be constant; in which case it equals $\frac11$.
\end{remark*}
\pagebreak

\subsection{IMO 2018/6, proposed by Tomasz Ciesla (POL)}
\textsl{Available online at \url{https://aops.com/community/p10632360}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A convex quadrilateral $ABCD$ satisfies $AB \cdot CD = BC \cdot DA$.
Point $X$ lies inside $ABCD$ so that
\[ \angle XAB=\angle XCD \quad \text{ and } \quad \angle XBC=\angle XDA. \]
Prove that $\angle BXA + \angle DXC=180\dg$.
\end{mdframed}
We present two solutions by inversion.
The first is the official one.
The second is a solution via inversion,
completed by USA5 Michael Ren.

\paragraph{Official solution by inversion.}
In what follows a convex quadrilateral is called
\emph{quasi-harmonic} if $AB \cdot CD = BC \cdot DA$.

\begin{claim*}
  A quasi-harmonic quadrilateral is determined
  up to similarity by its angles.
\end{claim*}
(This could be expected by degrees of freedom;
a quadrilateral has four degrees of freedom up to similarity;
the pseudo-harmonic condition is one
while the angles provide three conditions.)
\begin{proof}
  Do some inequalities.
\end{proof}

Performing an inversion at $X$, one obtains a
second quasi-harmonic quadrilateral
$A^\ast B^\ast C^\ast D^\ast$ which has the same angles
as the original one, $\angle D^\ast = \angle A$,
$\angle A^\ast = \angle B$, and so on.
Thus by the claim we obtain similarity
\[ D^\ast A^\ast B^\ast C^\ast \sim ABCD. \]
If one then maps $D^\ast A^\ast B^\ast C^\ast$,
onto $ABCD$, the image of $X^\ast$
becomes a point isogonally conjugate to $X$.
In other words, $X$ has an isogonal conjugate in $ABCD$.

It is well-known that this is equivalent to
$\angle BXA + \angle DXC = 180\dg$,
for example by inscribing an ellipse with foci $X$ and $X^\ast$.

\paragraph{Second solution: ``rhombus inversion'', by Michael Ren.}
Since
\[ \frac{AB}{AD} = \frac{CB}{CD} \]
and
\[ \frac{BA}{BC} = \frac{DA}{DC} \]
it follows that $B$ and $D$ lie on an Apollonian circle $\omega_{AC}$
through $A$ and $C$,
while $A$ and $C$ lie on an Apollonian circle $\omega_{BD}$
through $B$ and $D$.
We let these two circles intersect at a point $P$ inside $ABCD$.

The main idea is then to
perform an inversion about $P$ with radius $1$.
We obtain:
%\paragraph{Rhombus construction.}
\begin{lemma*}
  The image of $ABCD$ is a rhombus.
\end{lemma*}
\begin{proof}
  By the inversion distance formula, we have
  \[ \frac{1}{A'B'} = \frac{PA}{AB} \cdot PB = \frac{PC}{BC} \cdot PB = \frac{1}{B'C'} \]
  and so $A'B' = B'C'$.
  In a similar way, we derive $B'C' = C'D' = D'A'$,
  so the image is a rhombus as claimed.
\end{proof}

Let us now translate the angle conditions.
We were given that $\dang XAB = \dang XCD$, but
\begin{align*}
  \dang XAB &= \dang XAP + \dang PAB = \dang PX'A' + \dang A'B'P \\
  \dang XCD &= \dang XCP + \dang PCD = \dang PX'C' + \dang C'D'P
  \intertext{so subtracting these gives}
  \dang A'X'C' &= \dang A'B'P + \dang PD'C' = \dang (A'B', B'P) + \dang (PD', C'D') \\
  &= \dang (A'B', B'P) + \dang (PD', A'B') = \dang D' P B'. \tag{1}
\end{align*}
since $\ol{A'B'} \parallel \ol{C'D'}$.
Similarly, we obtain
\[ \dang B'X'D' = \dang A'PC' \tag{2}. \]
We now translate the desired condition.
Since
\begin{align*}
  \dang AXB &= \dang AXP + \dang PXB = \dang PA'X' + \dang X'B'P \\
  \dang CXD &= \dang CXP + \dang PXD = \dang PC'X' + \dang X'DP'
\end{align*}
we compute
\begin{align*}
  \dang AXB + \dang CXD &= (\dang PA'X' + \dang X'B'P) + (\dang PC'X' + \dang X'D'P) \\
  &= -\left[ \left( \dang A'X'P + \dang X'PA' \right)
    + \left( \dang PX'B' + \dang B'PX' \right) \right] \\
  &\quad- \left[ \left( \dang C'X'P + \dang X'PC' \right)
    + \left( \dang PX'D' + \dang D'PX'  \right) \right] \\
  &= \left[ \dang PX'A' + \dang BX'P + \dang PX'C' + \dang D'X'P  \right] \\
  &\quad+ \left[ \dang A'PX' + \dang X'PB' + \dang C'PX' + \dang X'PD' \right] \\
  &= \dang A'PB' + \dang C'PD' + \dang B'X'C + \dang D'X'A
\end{align*}
and we wish to show this is equal to zero, i.e.\
the desired becomes
\[ \dang A'PB' + \dang C'PD' + \dang B'X'C + \dang D'X'A = 0. \tag{3} \]
In other words, the problem is to show (1) and (2) implies (3).

Henceforth drop apostrophes.
Here is the inverted diagram (with apostrophes dropped).
\begin{center}
\begin{asy}
size(12cm);
pair A = (0,3);
pair B = (-8,0);
pair C = (0,-3);
pair D = (8,0);

pair X = (-5.6,7.8);
pair Y = reflect(circumcenter(A,C,X), circumcenter(D,B,X))*X;
pair Q = IP(circumcircle(A, Y, D), circumcircle(B, Y, C));
pair P = conj(Q);

filldraw(A--B--C--D--cycle, opacity(0.1)+lightred, red);
draw(A--C, red);
draw(B--D, red);

draw(B--X--D, lightgreen);
draw(A--P--C, lightgreen);
draw(C--X--A, lightblue);
draw(B--P--D, lightblue);

draw(circumcircle(A, X, C), heavycyan);
draw(circumcircle(B, X, D), heavycyan);
draw(circumcircle(B, Q, C), lightcyan);
draw(circumcircle(A, Q, D), lightcyan);
draw(Q--P, red);

dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$D$", D, dir(D));
dot("$X$", X, dir(X));
dot("$Y$", Y, dir(Y));
dot("$Q$", Q, dir(Q));
dot("$P$", P, dir(P));

/* TSQ Source:

A = (0,3)
B = (-8,0)
C = (0,-3)
D = (8,0)

X = (-5.6,7.8)
Y = OP circumcircle A X C circumcircle B X D
Q = IP circumcircle A Y D circumcircle B Y C
P = conj(Q)

A--B--C--D--cycle 0.1 lightred / red
A--C red
B--D red

B--X--D lightgreen
A--P--C lightgreen
C--X--A lightblue
B--P--D lightblue

circumcircle A X C heavycyan
circumcircle B X D heavycyan
circumcircle B Q C lightcyan
circumcircle A Q D lightcyan
Q--P red

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

Let $Q$ denote the reflection of $P$
and let $Y$ denote the second intersection of $(BQC)$ and $(AQD)$.
Then
\begin{align*}
  -\dang AXC &= -\dang DPB = \dang BQD = \dang BQY + \dang YQD = \dang BCY + \dang YAD \\
  &= \dang(BC,CY) + \dang(YA,AD) = \dang YCA = -\dang AYC.
\end{align*}
% again using $\ol{AB} \parallel \ol{CD}$.
Hence $XACY$ is concyclic; similarly $XBDY$ is concyclic.

\begin{claim*}
  $X \neq Y$.
\end{claim*}
\begin{proof}
  To see this: Work pre-inversion assuming $AB < AC$.
  Then $Q$ was the center of $\omega_{BD}$.
  If $T$ was the second intersection of $BA$ with $(QBC)$,
  then $QB = QD = QT = \sqrt{QA \cdot QC}$, by shooting lemma.
  Since $\angle BAD < 180\dg$,
  it follows $(QBCY)$ encloses $ABCD$ (pre-inversion).
  (This part is where the hypothesis that
  $ABCD$ is convex with $X$ inside is used.)
\end{proof}

Finally, we do an angle chase to finish:
\begin{align*}
  \dang DXA &= \dang DXY + \dang YXA = \dang DBY + \dang YCA \\
  &= \dang (DB, YB) + \dang (CY, CA) = \dang CYB + 90\dg \\
  &= \dang CQB + 90\dg = -\dang APB + 90\dg \tag{4}.
\end{align*}
Similarly,
\[ \dang BXC = \dang DPC + 90\dg. \tag{5} \]
%% \dang AXB = \dang DYC + 90\dg, \quad
%% \dang CXD = \dang BYC + 90\dg.
Summing (4) and (5) gives (3).
% $\dang BXC + \dang DXA = (\dang BPA + 90\dg) + (\dang DPC + 90\dg) = -(\dang APB + \dang CPD)$.


\begin{remark*}
  A difficult part of the problem in many solutions
  is that the conclusion is false in the directed sense,
  if the point $X$ is allowed to lie outside the quadrilateral.
  We are saved in the first solution because the equivalence
  of the isogonal conjugation requires $X$ inside the quadrilateral.
  On the other hand, in the second solution,
  the issue appears in the presence of the second point $Y$.
\end{remark*}
\pagebreak


\end{document}
