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

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2019 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
Solve over $\ZZ$ the functional equation
$f(2a) + 2f(b) = f(f(a+b))$.

\item %% Problem 2
In triangle $ABC$ point $A_1$ lies on side $BC$
and point $B_1$ lies on side $AC$.
Let $P$ and $Q$ be points on segments $AA_1$ and $BB_1$,
respectively, such that $\ol{PQ} \parallel \ol{AB}$.
Point $P_1$ is chosen on ray $PB_1$ beyond $B_1$
such that $\angle PP_1C = \angle BAC$.
Point $Q_1$ is chosen on ray $QA_1$ beyond $A_1$
such that $\angle CQ_1Q = \angle CBA$.
Prove that points $P_1$, $Q_1$, $P$, $Q$ are cyclic.

\item %% Problem 3
A social network has $2019$ users,
some pairs of which are friends (friendship is symmetric).
If $A$, $B$, $C$ are three users such that
$AB$ are friends and $AC$ are friends but $BC$ is not,
then the administrator may perform the following operation:
change the friendships such that $BC$ are friends,
but $AB$ and $AC$ are no longer friends.

Initially, $1009$ users have $1010$ friends
and $1010$ users have $1009$ friends.
Prove that the administrator can make a sequence of operations
such that all users have at most $1$ friend.

\item %% Problem 4
Solve over positive integers the equation
\[ k! = \prod_{i=0}^{n-1} (2^n-2^i)
  = (2^n-1)(2^n-2)(2^n-4) \dots (2^n-2^{n-1}). \]

\item %% Problem 5
Let $n$ be a positive integer.
Harry has $n$ coins lined up on his desk, which can show either heads or tails.
He does the following operation: if there are $k$ coins which show heads and $k > 0$,
then he flips the $k$th coin over; otherwise he stops the process.
(For example, the process starting with $THT$ would be
$THT \to HHT \to HTT \to TTT$, which takes three steps.)

Prove the process will always terminate, and determine the average number of steps
this takes over all $2^n$ configurations.

\item %% Problem 6
Let $ABC$ be a triangle with incenter $I$ and incircle $\omega$.
Let $D$, $E$, $F$ denote the tangency points of $\omega$
with $\ol{BC}$, $\ol{CA}$, $\ol{AB}$.
The line through $D$ perpendicular to $\ol{EF}$
meets $\omega$ again at $R$ (other than $D$),
and line $AR$ meets $\omega$ again at $P$ (other than $R$).
Suppose the circumcircles of $\triangle PCE$ and $\triangle PBF$
meet again at $Q$ (other than $P$).
Prove that lines $DI$ and $PQ$ meet on the external $\angle A$-bisector.

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{IMO 2019/1, proposed by Liam Baker (SAF)}
\textsl{Available online at \url{https://aops.com/community/p12744859}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Solve over $\ZZ$ the functional equation
$f(2a) + 2f(b) = f(f(a+b))$.
\end{mdframed}
Notice that $f(x) \equiv 0$ or $f(x) \equiv 2x+k$ work
and are clearly the only linear solutions.
We now prove all solutions are linear.

Let $P(a,b)$ be the assertion.
\begin{claim*}
  For each $x \in \ZZ$ we have $f(2x) = 2f(x) - f(0)$.
\end{claim*}
\begin{proof}
  Compare $P(0,x)$ and $P(x,0)$.
\end{proof}
Now, $P(a,b)$ and $P(0,a+b)$ give
\begin{align*}
  f(f(a+b)) &= f(2a) + 2f(b) = f(0) + 2f(a+b) \\
  \implies [2f(a) - f(0)] + 2f(b) &= f(0) + 2f(a+b) \\
  \implies \left( f(a)-f(0) \right) + \left( f(b)-f(0) \right)
  &= \left( f(a+b)-f(0) \right).
\end{align*}
Thus the map $x \mapsto f(x) - f(0)$ is additive,
therefore linear.

\begin{remark*}
  The same proof works on the functional equation
  \[ f(2a) + 2f(b) = g(a+b) \]
  where $g$ is an arbitrary function (it implies that $f$ is linear).
\end{remark*}
\pagebreak

\subsection{IMO 2019/2, proposed by Anton Trygub (UKR)}
\textsl{Available online at \url{https://aops.com/community/p12744870}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
In triangle $ABC$ point $A_1$ lies on side $BC$
and point $B_1$ lies on side $AC$.
Let $P$ and $Q$ be points on segments $AA_1$ and $BB_1$,
respectively, such that $\ol{PQ} \parallel \ol{AB}$.
Point $P_1$ is chosen on ray $PB_1$ beyond $B_1$
such that $\angle PP_1C = \angle BAC$.
Point $Q_1$ is chosen on ray $QA_1$ beyond $A_1$
such that $\angle CQ_1Q = \angle CBA$.
Prove that points $P_1$, $Q_1$, $P$, $Q$ are cyclic.
\end{mdframed}
We present two solutions.

\paragraph{First solution by bary (Evan Chen).}
Let $PB_1$ and $QA_1$ meet line $AB$ at $X$ and $Y$.
Since $\ol{XY} \parallel \ol{PQ}$ it is equivalent
to show $P_1XYQ_1$ is cyclic (Reim's theorem).

Note the angle condition implies $P_1CXA$ and $Q_1CYB$ are cyclic.

Letting $T = \ol{PX} \cap \ol{QY}$ (possibly at infinity),
it suffices to show that the
radical axis of $\triangle CXA$ and $\triangle CYB$ passes through $T$,
because that would imply $P_1XYQ_1$ is cyclic
(by power of a point when $T$ is Euclidean,
and because it is an isosceles trapezoid if $T$ is at infinity).

\begin{center}
\begin{asy}
pair C = dir(110);
pair A = dir(210);
pair B = dir(330);

pair A_1 = 0.45*C+0.55*B;
pair P = 0.53*A+0.47*A_1;
pair B_1 = midpoint(A--C);
pair Q = extension(B, B_1, P, P+A-B);
pair T = extension(A_1, Q, B_1, P);
pair X = extension(A, B, P, T);
pair Y = extension(A, B, Q, T);

filldraw(A--B--C--cycle, opacity(0.1)+lightcyan, lightblue);
filldraw(circumcircle(A, C, X), opacity(0.05)+yellow, lightred);
filldraw(circumcircle(B, C, Y), opacity(0.05)+yellow, lightred);
draw(A--A_1, lightblue);
draw(B--B_1, lightblue);
draw(P--Q, blue);
draw(C--T, deepgreen);
pair P_1 = -X+2*foot(circumcenter(A, X, C), P, X);
pair Q_1 = -Y+2*foot(circumcenter(B, Y, C), Q, Y);
draw(P_1--T--Q_1, orange);

dot("$C$", C, dir(C));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$A_1$", A_1, dir(A_1));
dot("$P$", P, dir(160));
dot("$B_1$", B_1, dir(B_1));
dot("$Q$", Q, dir(20));
dot("$T$", T, dir(T));
dot("$X$", X, dir(X));
dot("$Y$", Y, dir(Y));
dot("$P_1$", P_1, dir(P_1));
dot("$Q_1$", Q_1, dir(Q_1));

/* TSQ Source:

C = dir 110
A = dir 210
B = dir 330

A_1 = 0.45*C+0.55*B
P = 0.53*A+0.47*A_1 R160
B_1 = midpoint A--C
Q = extension B B_1 P P+A-B R20
T = extension A_1 Q B_1 P
X = extension A B P T
Y = extension A B Q T

A--B--C--cycle 0.1 lightcyan / lightblue
circumcircle A C X 0.05 yellow / lightred
circumcircle B C Y 0.05 yellow / lightred
A--A_1 lightblue
B--B_1 lightblue
P--Q blue
C--T deepgreen
P_1 = -X+2*foot circumcenter A X C P X
Q_1 = -Y+2*foot circumcenter B Y C Q Y
P_1--T--Q_1 orange

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

To this end we use barycentric coordinates on $\triangle ABC$.
We begin by writing
\[ P = (u+t : s : r), \quad Q = (t : u+s : r) \]
from which it follows that
$A_1 = (0 : s : r)$ and $B_1 = (t : 0 : r)$.

Next, compute $X = \left(
  \det \left[ \begin{smallmatrix} u+t & r \\ t & r \end{smallmatrix} \right]
  : \det \left[ \begin{smallmatrix} s & r \\ 0 & r \end{smallmatrix} \right]
  : 0 \right) = (u : s : 0)$.
Similarly, $Y = (t : u : 0)$.
So we have computed all points.
\begin{claim*}
  Line $B_1X$ has equation
  $-rs \cdot x + ru \cdot y + st \cdot z = 0$,
  while line $C_1 Y$ has equation
  $ru \cdot x - rt \cdot y + st \cdot z = 0$.
\end{claim*}
\begin{proof}
  Line $B_1X$ is $0 = \det(B_1, X, -)
  = \det \left[ \begin{smallmatrix}
    t & 0 & r \\
    u & s & 0 \\
    x & y & z
\end{smallmatrix} \right]$.
  Line $C_1Y$ is analogous.
\end{proof}

\begin{claim*}
  The radical axis $(u+t) y - (u+s) x = 0$.
\end{claim*}
\begin{proof}
Circle $(AXC)$ is given by
$-a^2yz - b^2zx - c^2xy + (x+y+z) \cdot \frac{c^2 \cdot u}{u+s} y = 0$.
Similarly, circle $(BYC)$ has equation
$-a^2yz - b^2zx - c^2xy + (x+y+z) \cdot \frac{c^2 \cdot u}{u+t} x = 0$.
Subtracting gives the radical axis.
\end{proof}

Finally, to see these three lines are concurrent, we now compute
\begin{align*}
  \det \begin{bmatrix}
    -rs & ru & st \\
    ru & -rt & st \\
    -(u+s) & u+t & 0
  \end{bmatrix}
  &= rst \left[ [u(u+t)-t(u+s)] + [s(u+t)-u(u+s)] \right] \\
  &= rst \left[ (u^2-st) + (st-u^2) \right] = 0.
\end{align*}
This completes the proof.

\paragraph{Second official solution by tricky angle chasing.}
Let lines $AA_1$ and $BB_1$ meet at the circumcircle of $\triangle ABC$
again at points $A_2$ and $B_2$.
By Reim's theorem, $PQA_2B_2$ are cyclic.
\begin{center}
\begin{asy}
pair C = dir(110);
pair A = dir(210);
pair B = dir(330);

pair A_1 = 0.45*C+0.55*B;
pair P = 0.53*A+0.47*A_1;
pair B_1 = midpoint(A--C);
pair Q = extension(B, B_1, P, P+A-B);
pair T = extension(A_1, Q, B_1, P);
pair X = extension(A, B, P, T);
pair Y = extension(A, B, Q, T);

filldraw(A--B--C--cycle, opacity(0.1)+lightcyan, lightblue);
pair P_1 = -X+2*foot(circumcenter(A, X, C), P, X);
pair Q_1 = -Y+2*foot(circumcenter(B, Y, C), Q, Y);
pair A_2 = -A+2*foot(origin, A, P);
pair B_2 = -B+2*foot(origin, B, Q);
filldraw(unitcircle, opacity(0.1)+lightcyan, lightblue);

draw(A--A_2, lightblue);
draw(B--B_2, lightblue);

filldraw(circumcircle(C, B_1, B_2), opacity(0.05)+orange, red);
filldraw(circumcircle(C, A_1, A_2), opacity(0.05)+orange, red);
draw(P_1--P--Q--Q_1, blue);
filldraw(circumcircle(P, Q, Q_1), opacity(0.1)+yellow, deepgreen+dashed);

dot("$C$", C, dir(C));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$A_1$", A_1, dir(A_1));
dot("$P$", P, dir(270));
dot("$B_1$", B_1, dir(B_1));
dot("$Q$", Q, dir(270));
dot("$P_1$", P_1, dir(P_1));
dot("$Q_1$", Q_1, dir(Q_1));
dot("$A_2$", A_2, dir(A_2));
dot("$B_2$", B_2, dir(B_2));

/* TSQ Source:

C = dir 110
A = dir 210
B = dir 330

A_1 = 0.45*C+0.55*B
P = 0.53*A+0.47*A_1 R270
B_1 = midpoint A--C
Q = extension B B_1 P P+A-B R270
T := extension A_1 Q B_1 P
X := extension A B P T
Y := extension A B Q T

A--B--C--cycle 0.1 lightcyan / lightblue
P_1 = -X+2*foot circumcenter A X C P X
Q_1 = -Y+2*foot circumcenter B Y C Q Y
A_2 = -A+2*foot origin A P
B_2 = -B+2*foot origin B Q
unitcircle 0.1 lightcyan / lightblue

A--A_2 lightblue
B--B_2 lightblue

circumcircle C B_1 B_2 0.05 orange / red
circumcircle C A_1 A_2 0.05 orange / red
P_1--P--Q--Q_1 blue
circumcircle P Q Q_1 0.1 yellow / deepgreen dashed

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

\begin{claim*}
  The points $P$, $Q$, $A_2$, $Q_1$ are cyclic.
  Similarly the points $P$, $Q$, $B_2$, $P_1$ are cyclic.
\end{claim*}
\begin{proof}
  Note that $CA_1A_2Q_1$ is cyclic since
  $\dang CQ_1A_1 = \dang CQ_1Q = \dang CBA = \dang CA_2A = \dang CA_2A_1$.
  Then $\dang QQ_1A_2 = \dang A_1Q_1A_2 = \dang A_1 C A_2
  = \dang B C A_2 = \dang B A A_2 = \dang Q P A_2$.
\end{proof}

This claim obviously solves the problem.
\pagebreak

\subsection{IMO 2019/3, proposed by Adrian Beker (HRV)}
\textsl{Available online at \url{https://aops.com/community/p12744851}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A social network has $2019$ users,
some pairs of which are friends (friendship is symmetric).
If $A$, $B$, $C$ are three users such that
$AB$ are friends and $AC$ are friends but $BC$ is not,
then the administrator may perform the following operation:
change the friendships such that $BC$ are friends,
but $AB$ and $AC$ are no longer friends.

Initially, $1009$ users have $1010$ friends
and $1010$ users have $1009$ friends.
Prove that the administrator can make a sequence of operations
such that all users have at most $1$ friend.
\end{mdframed}
We take the obvious graph formulation
and call the move a \emph{toggle}.

\begin{claim*}
  Let $G$ be a connected graph.
  Then one can toggle $G$ without disconnecting the graph,
  unless $G$ is a clique, a cycle, or a tree.
\end{claim*}
\begin{proof}
  Assume $G$ is connected and not a tree, so it has a cycle.
  Take the smallest cycle $C$; by hypothesis $C \neq G$.

  If $C$ is not a triangle (equivalently, $G$ is triangle-free),
  then let $b \notin C$ be a vertex adjacent to $C$, say at $a$.
  Take a vertex $c$ of the cycle adjacent to $a$ (hence not to $b$).
  Then we can toggle $abc$.

  Now assume there exists a triangle; let $K$ be the maximal clique.
  By hypothesis, $K \neq G$.
  We take an edge $e = ab$ dangling off the clique,
  with $a \in K$ and $b \notin K$.
  Note some vertex $c$ of $K$ is not adjacent to $b$; now toggle $abc$.
\end{proof}

Back to the original problem;
let $G_{\text{imo}}$ be the given graph.
The point is that we can apply toggles (by the claim) repeatedly,
without disconnecting the graph, until we get a tree.
This is because
\begin{itemize}
  \ii $G_{\text{imo}}$ is connected,
  since any two vertices which are not adjacent
  have a common neighbor by pigeonhole
  ($1009 + 1009 + 2 > 2019$).
  \ii $G_{\text{imo}}$ cannot become a cycle,
  because it initially has an odd-degree vertex,
  and toggles preserve parity of degree!
  \ii $G_{\text{imo}}$ is obviously not a clique initially
  (and hence not afterwards).
\end{itemize}
So, we can eventually get $G_{\text{imo}}$ to be a tree.

Once $G_{\text{imo}}$ is a tree the problem follows by repeatedly applying
toggles arbitrarily until no more are possible;
the graph (although now disconnected) remains acyclic
(in particular having no triangles)
and therefore can only terminate in the desired situation.

\begin{remark*}
  The above proof in fact shows the following better result:
  \begin{quote}
  The task is possible if and only if
  $G_{\text{imo}}$ is a connected graph which is not a clique
  and has any vertex of odd degree.
  \end{quote}
  The ``only if'' follows from the observation
  that toggles preserve parity of degree.

  Thus the given condition about the degrees of vertices
  being $1009$ and $1010$ is largely a red herring;
  it's a somewhat strange way of masking the correct and more natural
  both-sufficient-and-necessary condition.
\end{remark*}
\pagebreak

\section{Solutions to Day 2}
\subsection{IMO 2019/4, proposed by Gabriel Chicas Reyes (SLV)}
\textsl{Available online at \url{https://aops.com/community/p12752761}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Solve over positive integers the equation
\[ k! = \prod_{i=0}^{n-1} (2^n-2^i)
  = (2^n-1)(2^n-2)(2^n-4) \dots (2^n-2^{n-1}). \]
\end{mdframed}
The answer is $(n,k) =(1,1)$ and $(n,k) = (2,3)$ which work.

Let $A = \prod_i (2^n-2^k)$, and assume $A = k!$ for some $k \ge 3$.
Recall by exponent lifting that
\[ \nu_3(2^t-1) = \begin{cases}
    0 & t \text{ odd} \\
    1 + \nu_3(t) & t \text{ even}.
  \end{cases} \]
Consequently, we can compute
\begin{align*}
  k > \nu_2(k!) &= \nu_2(A) = 1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2} \\
  \left\lfloor \frac k3 \right\rfloor
    \le \nu_3(k!) &= \nu_3(A) = \left\lfloor \frac n2 \right\rfloor
    + \left\lfloor \frac n6 \right\rfloor + \dots < \frac 34n.
\end{align*}
where the first inequality can be justified
by Legendre's formula $\nu_2(k!) = k - s_2(k)$.

In this way, we get
\[ \frac 94 n + 3 > k > \frac{n(n-1)}{2} \]
which means $n \le 6$; a manual check then shows the
solutions we claimed earlier are the only ones.

\begin{remark*}
  An amusing corollary of the problem pointed out in the shortlist
  is that the symmetric group $S_k$ cannot be isomorphic to the group $\GL_n(\FF_2)$
  unless $(n,k) = (1,1)$ or $(n,k) = (2,3)$, which indeed produce isomorphisms.
\end{remark*}
\pagebreak

\subsection{IMO 2019/5, proposed by David Altizio (USA)}
\textsl{Available online at \url{https://aops.com/community/p12752847}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n$ be a positive integer.
Harry has $n$ coins lined up on his desk, which can show either heads or tails.
He does the following operation: if there are $k$ coins which show heads and $k > 0$,
then he flips the $k$th coin over; otherwise he stops the process.
(For example, the process starting with $THT$ would be
$THT \to HHT \to HTT \to TTT$, which takes three steps.)

Prove the process will always terminate, and determine the average number of steps
this takes over all $2^n$ configurations.
\end{mdframed}
The answer is \[ E_n = \half (1 + \dots + n) = \frac14 n(n+1) \]
which is finite.

We'll represent the operation by a
directed graph $G_n$ on vertices $\{0,1\}^n$
(each string points to its successor)
with $1$ corresponding to heads and $0$ corresponding to tails.
For $b \in \{0,1\}$ we let $\ol b = 1-b$,
and denote binary strings as a sequence of $n$ symbols.

The main claim is that $G_n$
can be described explicitly in terms of $G_{n-1}$:
\begin{itemize}
  \ii We take two copies $X$ and $Y$ of $G_{n-1}$.

  \ii In $X$, we take each string of length $n-1$
  and just append a $0$ to it.  In symbols,
  we replace $s_1 \dots s_{n-1} \mapsto s_1 \dots s_{n-1} 0$.

  \ii In $Y$, we toggle every bit, then reverse the order,
  and then append a $1$ to it.
  In symbols, we replace
  $s_1 \dots s_{n-1} \mapsto \ol s_{n-1} \ol s_{n-2} \dots \ol s_{1} 1$.

  \ii Finally, we add one new edge from $Y$ to $X$ by
  $11 \dots 1 \to 11\dots110$.
\end{itemize}
An illustration of $G_4$ is given below.
\begin{center}
\begin{asy}
unitsize(0.8cm);

label("$0000$", (0, 0), red);
label("$1000$", (0, 1), red);
label("$1100$", (0, 2), red);
label("$1110$", (0, 3), red);
label("$0100$", (2, 2), red);
label("$1010$", (2, 3), red);
label("$0010$", (4, 3), red);
label("$0110$", (6, 3), red);

label("$1111$", (0, 4), blue);
label("$1101$", (0, 5), blue);
label("$1001$", (0, 6), blue);
label("$0001$", (0, 7), blue);
label("$1011$", (2, 6), blue);
label("$0101$", (2, 7), blue);
label("$0111$", (4, 7), blue);
label("$0011$", (6, 7), blue);

label(scale(1.5)*"$\downarrow$", (0, 0.5), red);
label(scale(1.5)*"$\downarrow$", (0, 1.5), red);
label(scale(1.5)*"$\downarrow$", (0, 2.5), red);
label(scale(1.2)*"$\leftarrow$", (1, 2), red);
label(scale(1.2)*"$\leftarrow$", (1, 3), red);
label(scale(1.2)*"$\leftarrow$", (3, 3), red);
label(scale(1.2)*"$\leftarrow$", (5, 3), red);

label(scale(1.5)*"$\downarrow$", (0, 4.5), blue);
label(scale(1.5)*"$\downarrow$", (0, 5.5), blue);
label(scale(1.5)*"$\downarrow$", (0, 6.5), blue);
label(scale(1.2)*"$\leftarrow$", (1, 6), blue);
label(scale(1.2)*"$\leftarrow$", (1, 7), blue);
label(scale(1.2)*"$\leftarrow$", (3, 7), blue);
label(scale(1.2)*"$\leftarrow$", (5, 7), blue);

label(scale(1.7)*"$\Downarrow$", (0, 3.5), deepgreen);
\end{asy}
\end{center}

To prove this claim, we need only show
the arrows of this directed graph remain valid.
The graph $X$ is correct as a subgraph of $G_n$,
since the extra $0$ makes no difference.
As for $Y$, note that if $s = s_1 \dots s_{n-1}$ had $k$ ones,
then the modified string has $(n-1-k)+1 = n-k$ ones, ergo
$\ol s_{n-1} \dots \ol s_1 1
\mapsto  \ol s_{n-1} \dots \ol s_{k+1} s_k \ol s_{k-1} \dots \ol s_1 1$
which is what we wanted.
Finally, the one edge from $Y$ to $X$ is obviously correct.

To finish, let $E_n$ denote the desired expected value.
Since $1 \dots 1$ takes $n$ steps to finish we have
\[ E_n = \half \left[ E_{n-1} + (E_{n-1}+n) \right] \]
based on cases on whether the chosen string is in $X$ or $Y$ or not.
By induction, we have $E_n = \half (1 + \dots + n) = \frac14 n(n+1)$,
as desired.

\begin{remark*}
  Actually, the following is true:
  if the indices of the $1$'s are $1 \le i_1 < \dots < i_\ell \le n$,
  then the number of operations required is
  \[ 2(i_1 + \dots + i_\ell) - \ell^2. \]
  This problem also has an interpretation as a Turing machine:
  the head starts at a position on the tape (the binary string).
  If it sees a $1$, it changes the cell to a $0$ and moves left;
  if it sees a $0$, it changes the cell to a $1$ and moves right.
\end{remark*}
\pagebreak

\subsection{IMO 2019/6, proposed by Anant Mudgal (IND)}
\textsl{Available online at \url{https://aops.com/community/p12752769}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a triangle with incenter $I$ and incircle $\omega$.
Let $D$, $E$, $F$ denote the tangency points of $\omega$
with $\ol{BC}$, $\ol{CA}$, $\ol{AB}$.
The line through $D$ perpendicular to $\ol{EF}$
meets $\omega$ again at $R$ (other than $D$),
and line $AR$ meets $\omega$ again at $P$ (other than $R$).
Suppose the circumcircles of $\triangle PCE$ and $\triangle PBF$
meet again at $Q$ (other than $P$).
Prove that lines $DI$ and $PQ$ meet on the external $\angle A$-bisector.
\end{mdframed}
We present three solutions.

\paragraph{First solution by complex numbers (Evan Chen, with Yang Liu).}
We use complex numbers with $D=x$, $E=y$, $F=z$.
\begin{center}
\begin{asy}
pair I = origin;
pair D = dir(110);
pair E = dir(210);
pair F = dir(330);
draw(D--E--F--cycle, blue);
filldraw(unitcircle, opacity(0.1)+lightcyan, blue);
pair A = 2*E*F/(E+F);
pair B = 2*F*D/(F+D);
pair C = 2*D*E/(D+E);
draw(A--B--C--cycle, blue);
pair R = -E*F/D;
pair P = -R+2*foot(I, A, R);
filldraw(circumcircle(P, C, E), opacity(0.1)+lightcyan, deepgreen);
filldraw(circumcircle(P, B, F), opacity(0.1)+lightcyan, deepgreen);
pair Q = -P+2*foot(P, circumcenter(C, P, E), circumcenter(B, P, F));
pair T = extension(P, Q, D, I);
draw(A--T, deepcyan);
draw(D--T--P, deepcyan);
draw(D--R, lightblue);
draw(A--P, lightblue);

dot("$I$", I, dir(45));
dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$R$", R, dir(R));
dot("$P$", P, dir(200));
dot("$Q$", Q, dir(70));
dot("$T$", T, dir(T));

/* TSQ Source:

I = origin R45
D = dir 110
E = dir 210
F = dir 330
D--E--F--cycle blue
unitcircle 0.1 lightcyan / blue
A = 2*E*F/(E+F)
B = 2*F*D/(F+D)
C = 2*D*E/(D+E)
A--B--C--cycle blue
R = -E*F/D
P = -R+2*foot I A R R200
circumcircle P C E 0.1 lightcyan / deepgreen
circumcircle P B F 0.1 lightcyan / deepgreen
Q = -P+2*foot P circumcenter C P E circumcenter B P F R70
T = extension P Q D I
A--T deepcyan
D--T--P deepcyan
D--R lightblue
A--P lightblue

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


Then $A = \frac{2yz}{y+z}$,
$R = \frac{-yz}{x}$ and so
\[ P = \frac{A-R}{1-R\ol{A}}
  = \frac{\frac{2yz}{y+z} + \frac{yz}{x}}
  {1 + \frac{yz}{x} \cdot \frac{2}{y+z}}
  = \frac{yz(2x+y+z)}{2yz+x(y+z)}. \]
We now compute
\begin{align*}
  O_B &= \det \begin{bmatrix}
    P & P \ol P & 1 \\
    F & F \ol F & 1 \\
    B & B \ol B & 1
  \end{bmatrix}
  \div \det \begin{bmatrix}
    P & \ol P & 1 \\
    F & \ol F & 1 \\
    B & \ol B & 1
  \end{bmatrix}
  = \det \begin{bmatrix}
    P & 1 & 1 \\
    z & 1 & 1 \\
    \frac{2xz}{x+z} & \frac{4xz}{(x+z)^2} & 1
  \end{bmatrix}
  \div \det \begin{bmatrix}
    P & 1/P & 1 \\
    z & 1/z & 1 \\
    \frac{2xz}{x+z} & \frac{2}{x+z} & 1
  \end{bmatrix} \\
  &= \frac{1}{x+z} \det \begin{bmatrix}
    P & 0 & 1 \\
    z & 0 & 1 \\
    2xz(x+z) & -(x-z)^2 & (x+z)^2
  \end{bmatrix}
  \div \det \begin{bmatrix}
    P & 1/P & 1 \\
    z & 1/z & 1 \\
    2xz & 2 & x+z
  \end{bmatrix} \\
  &= \frac{(x-z)^2}{x+z} \cdot \frac{P-z}{(x+z)(P/z-z/P)+2z-2x + \frac{2xz}{P}-2P} \\
  &= \frac{(x-z)^2}{x+z} \cdot \frac{P-z}{
    (\frac xz-1) P - 2(x-z) + (xz-z^2) \frac 1P  } \\
  &= \frac{x-z}{x+z} \cdot \frac{P-z}{P/z + z/P - 2}
  = \frac{x-z}{x+z} \cdot \frac{P-z}{\frac{(P-z)^2}{Pz}}
  = \frac{x-z}{x+z} \cdot \frac{1}{\frac 1z - \frac 1P} \\
  &= \frac{x-z}{x+z} \cdot \frac{y(2x+y+z)}{y(2x+y+z) - (2yz+xy+xz)}
  = \frac{x-z}{x+z} \cdot \frac{yz(2x+y+z)}{xy+y^2-yz-xz} \\
  &= \frac{x-z}{x+z} \cdot \frac{yz(2x+y+z)}{(y-z)(x+y)}.
\end{align*}
Similarly
\[ O_C = \frac{x-y}{x+y} \cdot \frac{yz(2x+y+z)}{(z-y)(x+z)}. \]
Therefore, subtraction gives
\[ O_B-O_C
  =
  \frac{yz(2x+y+z)}{(x+y)(x+z)(y-z)}
  \left[ (x-z) + (x-y) \right]
  = \frac{yz(2x+y+z)(2x-y-z)}{(x+y)(x+z)(z-y)}.
\]
It remains to compute $T$.
Since $T \in \ol{ID}$ we have $t/x \in \RR$
so $\ol t = t/x^2$.
Also,
\begin{align*}
  \frac{t - \frac{2yz}{y+z}}{y+z} \in i \RR
  \implies 0 &= \frac{t-\frac{2yz}{y+z}}{y+z}
  + \frac{\frac{t}{x^2}-\frac{2}{y+z}}{\frac1y+\frac1z} \\
  &= \frac{1+\frac{yz}{x^2}}{y+z} t - \frac{2yz}{(y+z)^2} - \frac{2yz}{(y+z)^2} \\
  \implies t &= \frac{x^2}{x^2+yz} \cdot \frac{4yz}{y+z}
\end{align*}
Thus
\begin{align*}
  P-T &= \frac{yz(2x+y+z)}{2yz+x(y+z)} - \frac{4x^2yz}{(x^2+yz)(y+z)} \\
  &= yz \cdot \frac{(2x+y+z)(x^2+yz)(y+z) - 4x^2(2yz+xy+xz)}
    {(y+z)(x^2+yz)(2yz+xy+xz)} \\
  &= -yz \cdot \frac{(2x-y-z)(x^2y+x^2z+4xyz+y^2z+yz^2)}
    {(y+z)(x^2+yz)(2yz+xy+xz)}.
\end{align*}
This gives $\ol{PT} \perp \ol{O_B O_C}$ as needed.

\paragraph{Second solution by tethered moving points, with optimization (Evan Chen).}
Fix $\triangle DEF$ and $\omega$, with $B = \ol{DD} \cap \ol{FF}$
and $C = \ol{DD} \cap \ol{EE}$.
We consider a variable point $M$ on $\omega$
and let $X$, $Y$ be on $\ol{EF}$ with
$\ol{CY} \cap \parallel \ol{ME}$, $\ol{BX} \cap \parallel \ol{MF}$.
We define $W = \ol{CY} \cap \ol{BX}$.
Also, let line $MW$ meet $\omega$ again at $V$.

\begin{center}
\begin{asy}
pair D = dir(105);
pair E = dir(200);
pair F = dir(340);
pair M = dir(275);
pair N = extension(D, M, E, F);
pair Rp = -D;
pair B = 2*D*F/(D+F);
pair C = 2*D*E/(D+E);
pair X = extension(E, F, B, B+M-F);
pair Y = extension(E, F, C, C+M-E);
pair W = extension(B, X, C, Y);
pair V = extension(N, Rp, M, W);

filldraw(unitcircle, opacity(0.1)+lightred, red);
draw(D--E--F--cycle, red);
draw(E--C--D--B--F, orange);
draw(V--M);
draw(X--B, deepgreen);
draw(C--Y, deepgreen);
draw(E--M--F, heavygreen);
draw(D--M, lightred);
draw(V--M, blue);
filldraw(circumcircle(C, W, V), opacity(0.1)+lightcyan, blue);
filldraw(circumcircle(B, W, V), opacity(0.1)+lightcyan, blue);
draw(V--Rp, grey+dotted);

dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
dot("$M$", M, dir(M));
dot("$N$", N, dir(N));
dot("$R'$", Rp, dir(Rp));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$X$", X, dir(270));
dot("$Y$", Y, dir(270));
dot("$W$", W, dir(W));
dot("$V$", V, dir(200));

/* TSQ Source:

D = dir 105
E = dir 200
F = dir 340
M = dir 275
N = extension D M E F
R' = -D
B = 2*D*F/(D+F)
C = 2*D*E/(D+E)
X = extension E F B B+M-F R270
Y = extension E F C C+M-E R270
W = extension B X C Y
V = extension N Rp M W R200

unitcircle 0.1 lightred / red
D--E--F--cycle red
E--C--D--B--F orange
V--M
X--B deepgreen
C--Y deepgreen
E--M--F heavygreen
D--M lightred
V--M blue
circumcircle C W V 0.1 lightcyan / blue
circumcircle B W V 0.1 lightcyan / blue
V--Rp grey dotted

*/
\end{asy}
\begin{asy}
pair D = dir(115);
pair E = dir(210);
pair F = dir(330);
pair N = midpoint(E--F);
pair M = -D+2*foot(origin, D, N);
pair Rp = -D;
pair B = 2*D*F/(D+F);
pair C = 2*D*E/(D+E);
pair X = extension(E, F, B, B+M-F);
pair Y = extension(E, F, C, C+M-E);
pair Q = extension(B, X, C, Y);
pair P = extension(N, Rp, M, Q);

pair R = E*F/Rp;
pair Mp = E*F/M;
pair A = 2*E*F/(E+F);
pair Z = extension(P, M, D, Rp);

filldraw(unitcircle, opacity(0.1)+lightred, red);
draw(D--E--F--cycle, red);
draw(E--A--F, orange);
draw(P--M);
draw(D--M, lightred);
// E--D--C orange
draw(P--Rp, deepgreen);

draw(A--Z, lightblue);
draw(P--Z--D, blue);
draw(P--A--D, deepcyan);

dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
dot("$N$", N, dir(N));
dot("$M$", M, dir(M));
dot("$R'$", Rp, dir(Rp));
dot("$Q$/$W$", Q, dir(Q));
dot("$P$/$V$", P, dir(200));
dot("$R$", R, dir(R));
dot("$M'$", Mp, dir(Mp));
dot("$A$", A, dir(A));

/* TSQ Source:

D = dir 115
E = dir 210
F = dir 330
N = midpoint E--F
M = -D+2*foot origin D N
R' = -D
B := 2*D*F/(D+F)
C := 2*D*E/(D+E)
X := extension E F B B+M-F R270
Y := extension E F C C+M-E R270
Q = extension B X C Y
P = extension N Rp M Q R200

R = E*F/Rp
M' = E*F/M
A = 2*E*F/(E+F)
Z := extension P M D Rp

unitcircle 0.1 lightred / red
D--E--F--cycle red
E--A--F orange
P--M
D--M lightred
// E--D--C orange
P--Rp deepgreen

A--Z lightblue
P--Z--D blue
P--A--D deepcyan

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

\begin{claim*}
  [Angle chasing]
  Pentagons $CVWXE$ and $BVWYF$ are cyclic.
\end{claim*}
\begin{proof}
  By $\dang EVW = \dang EVM = \dang EFM = \dang CEM = \dang ECW$
  and $\dang EXW = \dang EFM = \dang CEM = \dang ECW$.
\end{proof}

Let $N = \ol{DM} \cap \ol{EF}$ and $R'$ be the $D$-antipode on $\omega$.
\begin{claim*}
  [Black magic]
  The points $V$, $N$, $R'$ are collinear.
\end{claim*}
\begin{proof}
  We use tethered moving points with $\triangle DEF$ fixed.

  Obviously the map $\omega \mapsto \ol{EF} \mapsto \omega$
  by $M \mapsto N \mapsto \ol{R'N} \cap \omega$ is projective.
  Also, the map $\omega \mapsto \ol{EF} \mapsto \omega$
  by $M \mapsto X \mapsto V$ is also projective
  (the first by projection to the line at infinity at back;
  the second say by inversion at $E$).

  So it suffices to check for three points.
  When $M=E$ we get $N=E$ so $\ol{R'N} \cap \omega = E$,
  while $W=E$ and thus $V=E$.
  The case $M=F$ is similar.
  Finally, if $M = R'$, then $W$ is the center of $\omega$
  and so $V = \ol{R'N} \cap \ol{EF} = D$.
\end{proof}


We now address the original problem by specializing $M$:
choose it so that $N$ is the midpoint of $\ol{EF}$.
Let $M' = \ol{DA} \cap (DEF)$.
\begin{claim*}
  After this specialization, $V=P$ and $W=Q$.
\end{claim*}
\begin{proof}
  Thus $\ol{RR'}$ and $\ol{MM'}$ are parallel to $\ol{EF}$.
  From  $(EF;PR) = -1 = (EF;N\infty) \overset{R'}{=} (EF;NV)$,
  we derive that $P=V$ and $Q=R$, proving (i).
\end{proof}
Finally, the concurrence requested follows
by Pascal theorem on $M'MDR'PR$.

\paragraph{Third solution by power of a point linearity (Luke Robitaille).}

Let us define
\[ f(\bullet) = \opname{Pow}(\bullet, (CPE))
  - \opname{Pow}(\bullet, (BPF)) \]
which is a linear function from the plane to $\RR$.

Define $W = \ol{BA} \cap \ol{PE}$,
$V = \ol{AC} \cap \ol{PF}$.
Also, let $W_1 = \ol{ER} \cap \ol{AB}$,
$V_1 = \ol{FR} \cap \ol{AC}$.
Note that
\[ -1 = (PR;EF) \overset{E}{=} (WA; W_1F) \]
and similarly $(VA; V_1E) = -1$.

\begin{claim*}
  We have
  \begin{align*}
    f(F) &= \frac{|EF| \cdot (s-c) \sin C/2}{\sin B/2} \\
    f(E) &= -\frac{|EF| \cdot (s-b) \sin B/2}{\sin C/2}.
  \end{align*}
\end{claim*}
\begin{proof}
  We have
  \[ f(W) = WF^2 - WB \cdot WF = WF \cdot BF \]
  where lengths are directed.
  Next,
  \begin{align*}
    f(F) &= \frac{AF \cdot f(W) + FW \cdot f(A)}{AW} \\
    &= \frac{AF \cdot WF \cdot BF + FW \cdot
      \left( AE \cdot AC - AF \cdot AB \right)}{AW} \\
    &= \frac{WF(AF \cdot BF + AF \cdot AB) + FW \cdot AE \cdot AC}{AW} \\
    &= \frac{WF \cdot AF^2 - WF \cdot AE \cdot AC}{AW}
      = \frac{WF}{AW} \cdot (AE^2 - AE \cdot AC) \\
    &= \frac{WF}{AW} \cdot AE \cdot CE
      = -\frac{W_1F}{AW_1} \cdot AE \cdot CE.
  \end{align*}
  Since $\triangle DEF$ is acute,
  the point $R$ lies inside $\triangle AEF$.
  Thus $W_1$ lies inside segment $\ol{AF}$
  and the ratio $\frac{W_1F}{AW_1}$ is positive.
  We now determine its value: by the ratio lemma
  \begin{align*}
    \frac{|W_1F|}{|AW_1|}
    &= \frac{|EF| \sin \angle W_1 E F}{|AE| \sin \angle A E W_1} \\
    &= \frac{|EF| \sin \angle REF}{|AE| \sin \angle AER} \\
    &= \frac{|EF| \sin \angle RDF}{|AE| \sin \angle EDR} \\
    &= \frac{|EF| \sin C/2}{|AE| \sin B/2}.
  \end{align*}
  Also, we have $AE \cdot CE < 0$ since $E$ lies inside $\ol{AC}$.
  Hence
  \[ f(F) = -\frac{|EF| \sin C/2}{|AE| \sin B/2}.
    \cdot AE \cdot CE
    = |EF| \cdot \frac{|CE| \sin B/2}{\sin C/2}
    = |EF| \cdot \frac{(s-c) \sin B/2}{\sin C/2}. \]
  The calculation for $f(E)$ is similar,
  (noting the sign flips since $f$ is anti-symmetric
  in terms of $B$ and $C$).
\end{proof}

Let $Z \in \ol{DI}$ with $\angle ZAI = 90\dg$
be the point requested in the problem now.
Our goal is to show $f(Z) = 0$.
We assume WLOG that $AB < AC$, so $\frac{ZA}{EF} > 0$.
Then
\begin{align*}
  |ZA| &= |AI| \cdot \tan \angle AIZ \\
  &= |AI| \cdot \tan \angle(\ol{AI}, \ol{DI}) \\
  &= \frac{s-a}{\cos A/2} \cdot \tan (\ol{BC}, \ol{EF}) \\
  &= \frac{s-a}{\cos A/2} \tan (B/2-C/2).
\end{align*}

To this end we compute
\begin{align*}
  f(Z) &= f(A) + \left[ f(Z) - f(A) \right]
    = f(A) + \frac{ZA}{EF} \left[ f(E)-f(F) \right] \\
  &= f(A) - \frac{ZA}{EF}
  \left[ \frac{|EF| \cdot (s-b) \sin B/2}{\sin C/2}
    + \frac{|EF| \cdot (s-c) \sin C/2}{\sin B/2} \right] \\
  &= f(A) - |ZA| \left[ \frac{(s-b) \sin B/2}{\sin C/2}
    + \frac{(s-c) \sin C/2}{\sin B/2} \right] \\
  &= \left[ b(s-a) - c(s-a) \right]
    - |ZA| \left[ \frac{(s-b) \sin B/2}{\sin C/2}
    + \frac{(s-c) \sin C/2}{\sin B/2} \right] \\
  &= (b-c)(s-a) - \frac{s-a}{\cos A/2} \tan (B/2-C/2)
    \left[ \frac{(s-b) \sin B/2}{\sin C/2}
    + \frac{(s-c) \sin C/2}{\sin B/2} \right].
\end{align*}
Dividing out,
\begin{align*}
  \frac{f(Z)}{s-a}
  &= (b-c) - \frac{1}{\cos A/2} \tan (B/2-C/2)
    \left[ \frac{r \cos B/2}{\sin C/2}
      + \frac{r \cos C/2}{\sin B/2} \right] \\
  &= (b-c) - \frac{r \tan(B/2-C/2)}{\cos A/2}
    \cdot \frac{\cos B/2 \sin B/2 + \cos C/2 \sin C/2}%
    {\sin C/2 \sin B/2} \\
  &= (b-c) - \frac{r \tan(B/2-C/2)}{\cos A/2}
    \cdot \frac{\sin B + \sin C}%
    {2\sin C/2 \sin B/2} \\
  &= (b-c) - \frac{r \tan(B/2-C/2)}{\cos A/2}
    \cdot \frac{\sin(B/2+C/2)\cos(B/2-C/2)}
    {\sin C/2 \sin B/2} \\
  &= (b-c) - r \frac{\sin(B/2-C/2)}{\sin B/2 \sin C/2} \\
  &= (b-c) - r(\cot C/2 - \cot B/2)
    = (b-c) - \left( (s-c) - (s-b) \right) = 0.
\end{align*}
\paragraph{Fourth solution by incircle inversion (USA IMO live stream, led by Andrew Gu).}
Let $T$ be the intersection of line $DI$ and the external $\angle A$-bisector.
Also, let $G$ be the antipode of $D$ on $\omega$.

We perform inversion around $\omega$, using $\bullet^\ast$ for the inverse.
Then $\triangle A^\ast B^\ast C^\ast$
is the medial triangle of $\triangle DEF$,
and $T^\ast$ is the foot from $A^\ast$ on to $\ol{DI}$.
If we denote $Q^\ast$ as the second intersection
of $(PC^\ast E)$ and $(PB^\ast F)$,
then the goal it show that $Q^\ast$ lies on $(PIT^\ast)$.

\begin{center}
\begin{asy}
pair D = dir(115);
pair E = dir(210);
pair F = dir(330);
pair As = midpoint(E--F);
pair G = -D;
pair I = origin;
pair A = 2*E*F/(E+F);

pair R = -E*F/D;
pair P = -R+2*foot(I, R, A);

pair T = extension(D, I, A, E-F+A);

pair Bs = midpoint(D--F);
pair Cs = midpoint(D--E);
pair M = midpoint(As--D);
pair Qs = OP(circumcircle(Cs, P, E), circumcircle(Bs, P, F));

filldraw(unitcircle, opacity(0.1)+lightcyan, deepcyan);
draw(D--E--F--cycle, deepcyan);
draw(E--A--F, lightblue);
draw(P--G, deepgreen);
draw(D--T, lightblue);
draw(A--T, lightblue);
draw(A--P, lightblue);
pair Ts = foot(As, D, T);
draw(As--Ts, lightred);
draw(Qs--Bs, lightred+dashed);
draw(D--As, lightblue);

filldraw(circumcircle(P, Cs, E), opacity(0.05)+yellow, lightred);
filldraw(circumcircle(P, Bs, F), opacity(0.05)+yellow, lightred);

draw(CP(M, D), lightgreen);
draw(M--I, deepgreen);

clip(box((-1.8,-2.2), (2,2)));
filldraw(circumcircle(P, I, Ts), opacity(0.1)+orange, red+dashed);

dot("$D$", D, dir(D));
dot("$E$", E, dir(E));
dot("$F$", F, dir(F));
dot("$A^\ast$", As, dir(225));
dot("$G$", G, dir(245));
dot("$I$", I, dir(45));
dot("$A$", A, dir(A));
dot("$R$", R, dir(R));
dot("$P$", P, dir(P));
dot("$T$", T, dir(T));
dot("$B^\ast$", Bs, dir(Bs));
dot("$C^\ast$", Cs, dir(45));
dot("$M$", M, dir(225));
dot("$Q^\ast$", Qs, dir(Qs));
dot("$T^\ast$", Ts, dir(45));

/* TSQ Source:

D = dir 115
E = dir 210
F = dir 330
A* = midpoint E--F R225
G = -D R245
I = origin R45
A = 2*E*F/(E+F)

R = -E*F/D
P = -R+2*foot I R A

T = extension D I A E-F+A

B* = midpoint D--F
C* = midpoint D--E R45
M = midpoint As--D R225
Q* = OP circumcircle Cs P E circumcircle Bs P F

unitcircle 0.1 lightcyan / deepcyan
D--E--F--cycle deepcyan
E--A--F lightblue
P--G deepgreen
D--T lightblue
A--T lightblue
A--P lightblue
T* = foot As D T R45
As--Ts lightred
Qs--Bs lightred dashed
D--As lightblue

circumcircle P Cs E 0.05 yellow / lightred
circumcircle P Bs F 0.05 yellow / lightred

CP M D lightgreen
M--I deepgreen

!clip(box((-1.8,-2.2), (2,2)));
circumcircle P I Ts 0.1 orange / red dashed

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

\begin{claim*}
  Points $Q^\ast$, $B^\ast$, $C^\ast$ are collinear.
\end{claim*}
\begin{proof}
  $\dang PQ^\ast C^\ast = \dang PEC^\ast = \dang PED = \dang PFD
  = \dang PFB^\ast = \dang PQ^\ast B^\ast$.
\end{proof}

\begin{claim*}
  [cf Brazil 2011/5]
  Points $P$, $A^\ast$, $G$ are collinear.
\end{claim*}
\begin{proof}
  Project harmonic quadrilateral $PERF$ through $G$,
  noting $\ol{GR} \parallel \ol{EF}$.
\end{proof}

Denote by $M$ the center of parallelogram $DC^\ast A^\ast B^\ast$.
Note that it is the center of the circle with
diameter $\ol{DA^\ast}$, which passes through $P$ and $T^\ast$.
Also, $\ol{MI} \parallel \ol{PA^\ast G}$.

\begin{claim*}
  Points $P$, $M$, $I$, $T^\ast$ are cyclic.
\end{claim*}
\begin{proof}
  $\dang IT^\ast P = \dang D T^\ast P = \dang DA^\ast P
    = \dang M A^\ast P = \dang A^\ast P M  = \dang IMP$.
\end{proof}

\begin{claim*}
  Points $P$, $M$, $I$, $Q^\ast$ are cyclic.
\end{claim*}
\begin{proof}
  $\dang MQ^\ast P = \dang C^\ast Q^\ast P = \dang C^\ast E P
  = \dang D E P = \dang D G P = \dang GPI = \dang MIP$.
\end{proof}

\paragraph{Fifth solution by double inversion (Brandon Wang, Luke Robitaille, Michael Ren, Evan Chen).}
We outline one final approach.
After inverting about $\omega$ as in the previous approach,
we then apply another inversion around $P$.
Dropping the apostrophes/stars/etc now one can check
that the problem we arrive at becomes the following.
\begin{proposition*}
  [Doubly inverted problem]
  In $\triangle PEF$, the $P$-symmedian meets $\ol{EF}$
  and $(PEF)$ at $K$, $L$.
  Let $D \in \ol{EF}$ with $\angle DPK = 90\dg$,
  and let $T$ be the foot from $K$ to $\ol{DL}$.
  Denote by $I$ the reflection of $P$ about $\ol{EF}$.
  Finally, let $PDNE$ and $PDMF$ be cyclic harmonic quadrilaterals.
  Then lines $EN$, $MF$, $TI$, are concurrent.
\end{proposition*}

The proof proceeds in three steps.
Suppose the line through $L$ perpendicular to $\ol{EF}$
meets $\ol{EF}$ at $W$ and $(PEF)$ at $Z$.
\begin{center}
\begin{asy}
size(10cm);
pair P = dir(190);
pair E = dir(220);
pair F = dir(-40);
pair T = 2*E*F/(E+F);
pair K = extension(E, F, P, T);
pair L = -P+2*foot(origin, P, K);
pair W = foot(L, E, F);
pair Z = -L+2*foot(origin, W, L);
pair D = extension(E, F, P, P+dir(90)*(P-K));
pair T = foot(K, D, L);
pair I = -P+2*foot(P, E, F);
pair H = extension(P, Z, W, I);
pair N = -E+2*foot(circumcenter(P, D, E), H, E);
pair M = -F+2*foot(circumcenter(P, D, F), H, F);

filldraw(unitcircle, opacity(0.1)+lightcyan, blue);
draw(P--E--F--cycle, blue);
draw(D--E, blue);
draw(D--P--L--cycle, deepcyan);
draw(T--K, deepcyan);

draw(E--Z, orange);
draw(F--Z, orange);
draw(H--Z, orange);
draw(L--Z, orange);

filldraw(circumcircle(P, D, E), opacity(0.1)+lightgreen, deepgreen);
filldraw(circumcircle(P, D, F), opacity(0.1)+lightgreen, deepgreen);
draw(E--H, grey);
draw(W--H, grey);
draw(F--M, grey);

clip(box((-3,-2.3), (1.5,1.5)));

dot("$P$", P, dir(110));
dot("$E$", E, dir(135));
dot("$F$", F, dir(350));
dot("$K$", K, dir(70));
dot("$L$", L, dir(270));
dot("$W$", W, dir(45));
dot("$Z$", Z, dir(Z));
dot("$D$", D, dir(D));
dot("$T$", T, dir(270));
dot("$I$", I, dir(315));
dot(H);
dot("$N$", N, dir(100));
dot("$M$", M, dir(M));

/* TSQ Source:

P = dir 190 R110
E = dir 220 R135
F = dir -40 R350
T := 2*E*F/(E+F)
K = extension E F P T R70
L = -P+2*foot origin P K R270
W = foot L E F R45
Z = -L+2*foot origin W L
D = extension E F P P+dir(90)*(P-K)
T = foot K D L R270
I = -P+2*foot P E F R315
H .= extension P Z W I
N = -E+2*foot circumcenter P D E H E R100
M = -F+2*foot circumcenter P D F H F

unitcircle 0.1 lightcyan / blue
P--E--F--cycle blue
D--E blue
D--P--L--cycle deepcyan
T--K deepcyan

E--Z orange
F--Z orange
H--Z orange
L--Z orange

circumcircle P D E 0.1 lightgreen / deepgreen
circumcircle P D F 0.1 lightgreen / deepgreen
E--H grey
W--H grey
F--M grey

! clip(box((-3,-2.3), (1.5,1.5)));

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

\begin{enumerate}
  \ii Since $\dang ZEP = \dang WLP = \dang WDP$,
  it follows $\ol{ZE}$ is tangent to $(PDNE)$. \\
  Similarly, $\ol{ZF}$ is tangent to $(PDMF)$.
  \ii $\triangle WTP$ is the orthic triangle of $\triangle DKL$,
  so $\ol{WD}$ bisects $\angle PWT$ and $\ol{WTI}$ collinear.
  \ii $-1 = E(PN;DZ) = F(PM;DZ) = W(PI;DZ)$, so
  $\ol{EN}$, $\ol{FM}$, $\ol{WI}$ meet on $\ol{PZ}$.
\end{enumerate}
\pagebreak


\end{document}
