% © 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 2023 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2023 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
Determine all composite integers $n>1$ that satisfy the following property:
if $d_1 < d_2 < \dots < d_k$ are all the positive divisors of $n$ with
then $d_i$ divides $d_{i+1} + d_{i+2}$ for every $1 \leq i \leq k - 2$.
\item %% Problem 2
Let $ABC$ be an acute-angled triangle with $AB < AC$.
Let $\Omega$ be the circumcircle of $ABC$.
Let $S$ be the midpoint of the arc $CB$ of $\Omega$ containing $A$.
The perpendicular from $A$ to $BC$ meets $BS$ at $D$ and meets $\Omega$ again at $E \neq A$.
The line through $D$ parallel to $BC$ meets line $BE$ at $L$.
Denote the circumcircle of triangle $BDL$ by $\omega$.
Let $\omega$ meet $\Omega$ again at $P \neq B$.
Prove that the line tangent to $\omega$ at $P$ meets line $BS$
on the internal angle bisector of $\angle BAC$.
\item %% Problem 3
For each integer $k\geq 2$, determine all infinite sequences of positive integers
$a_1$, $a_2$, \dots\ for which there exists a polynomial $P$ of the form
\[ P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0, \]
where $c_0$, $c_1$, \dots, $c_{k-1}$ are non-negative integers, such that
\[ P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k} \]
for every integer $n\geq 1$.
\item %% Problem 4
Let $x_1$, $x_2$, \dots, $x_{2023}$ be pairwise different positive real numbers such that
\[ a_n = \sqrt{(x_1+x_2+\dots+x_n)
\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}\right)} \]
is an integer for every $n=1,2,\dots,2023$. Prove that $a_{2023} \geq 3034$.
\item %% Problem 5
Let $n$ be a positive integer.
A \emph{Japanese triangle} consists of $1 + 2 + \dots + n$ circles arranged in an
equilateral triangular shape such that for each $1 \le i \le n$,
the $i$\ts{th} row contains exactly $i$ circles, exactly one of which is colored red.
A \emph{ninja path} in a Japanese triangle is a sequence of $n$ circles
obtained by starting in the top row, then repeatedly going from a circle to
one of the two circles immediately below it and finishing in the bottom row.
Here is an example of a Japanese triangle with $n = 6$,
along with a ninja path in that triangle containing two red circles.
\begin{center}
\begin{asy}
size(4cm);
pair X = dir(240); pair Y = dir(0);
path c = scale(0.5)*unitcircle;
int[] t = {0,0,2,2,3,0};
for (int i=0; i<=5; ++i) {
for (int j=0; j<=i; ++j) {
filldraw(shift(i*X+j*Y)*c, (t[i]==j) ? lightred : white);
draw(shift(i*X+j*Y)*c);
}
}
draw((0,0)--(X+Y)--(2*X+Y)--(3*X+2*Y)--(4*X+2*Y)--(5*X+2*Y),linewidth(1.5));
path q = (3,-3sqrt(3))--(-3,-3sqrt(3));
draw(q,Arrows(TeXHead, 1));
label("$n = 6$", q, S);
\end{asy}
\end{center}
In terms of $n$, find the greatest $k$ such that in each Japanese triangle
there is a ninja path containing at least $k$ red circles.
\item %% Problem 6
Let $ABC$ be an equilateral triangle.
Let $A_1$, $B_1$, $C_1$ be interior points of $ABC$
such that $BA_1=A_1C$, $CB_1=B_1A$, $AC_1=C_1B$, and
\[ \angle BA_1C + \angle CB_1A + \angle AC_1B = 480\dg. \]
Let $A_2 = \ol{BC_1} \cap \ol{CB_1}$, $B_2 = \ol{CA_1} \cap \ol{AC_1}$,
$C_2 = \ol{AB_1} \cap \ol{BA_1}$.
Prove that if triangle $A_1B_1C_1$ is scalene,
then the circumcircles of triangles $AA_1A_2$, $BB_1B_2$, and $CC_1C_2$
all pass through two common points.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{IMO 2023/1, proposed by Santiago Rodriguez (COL)}
\textsl{Available online at \url{https://aops.com/community/p28097575}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Determine all composite integers $n>1$ that satisfy the following property:
if $d_1 < d_2 < \dots < d_k$ are all the positive divisors of $n$ with
then $d_i$ divides $d_{i+1} + d_{i+2}$ for every $1 \leq i \leq k - 2$.
\end{mdframed}
The answer is prime powers.
\paragraph{Verification that these work}
When $n = p^e$, we get $d_i = p^{i-1}$.
The $i$\ts{th} relationship reads \[ p^{i-1} \mid p^i + p^{i+1} \]
which is obviously true.
\paragraph{Proof that these are the only answers}
Conversely, suppose $n$ has at least two distinct prime divisors.
Let $p < q$ denote the two smallest ones,
and let $p^e$ be the largest power of $p$ which both divides $n$
and is less than $q$, hence $e \ge 1$.
Then the smallest factors of $n$ are $1$, $p$, \dots, $p^e$, $q$.
So we are supposed to have
\[ \frac{n}{q} \mid \frac{n}{p^e} + \frac{n}{p^{e-1}}
= \frac{(p+1)n}{p^e} \]
which means that the ratio
\[ \frac{q(p+1)}{p^e} \]
needs to be an integer, which is obviously not possible.
\pagebreak
\subsection{IMO 2023/2, proposed by Tiago Mourão and Nuno Arala (POR)}
\textsl{Available online at \url{https://aops.com/community/p28097552}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be an acute-angled triangle with $AB < AC$.
Let $\Omega$ be the circumcircle of $ABC$.
Let $S$ be the midpoint of the arc $CB$ of $\Omega$ containing $A$.
The perpendicular from $A$ to $BC$ meets $BS$ at $D$ and meets $\Omega$ again at $E \neq A$.
The line through $D$ parallel to $BC$ meets line $BE$ at $L$.
Denote the circumcircle of triangle $BDL$ by $\omega$.
Let $\omega$ meet $\Omega$ again at $P \neq B$.
Prove that the line tangent to $\omega$ at $P$ meets line $BS$
on the internal angle bisector of $\angle BAC$.
\end{mdframed}
\begin{claim*}
We have $LPS$ collinear.
\end{claim*}
\begin{proof}
Because $\dang LPB = \dang LDB = \dang CBD = \dang CBS = \dang SCB = \dang SPB$.
\end{proof}
Let $F$ be the antipode of $A$, so $AMFS$ is a rectangle.
\begin{claim*}
We have $PDF$ collinear. (This lets us erase $L$.)
\end{claim*}
\begin{proof}
Because $\dang SPD = \dang LPD = \dang LBD = \dang SBE = \dang FCS = \dang FPS$.
\end{proof}
Let us define $X = \ol{AM} \cap \ol{BS}$ and complete chord $\ol{PXQ}$.
We aim to show that $\ol{PXQ}$ is tangent to $(PDLB)$.
\begin{center}
\begin{asy}
/*
Converted from GeoGebra by User:Azjps using Evan's magic cleaner
https://github.com/vEnhance/dotfiles/blob/main/py-scripts/export-ggb-clean-asy.py
*/
pair C = (0.5,0.);
pair B = (-4.5,0.);
pair A = (-3.54989,4.84867);
pair M = (-2.,-1.19129);
pair S = (-2.,5.24638);
pair X = (-3.07373,2.99308);
pair E = (-3.54989,-0.79358);
pair D = (-3.54989,1.99384);
pair L = (-6.88710,1.99384);
pair P = (-4.96929,3.27021);
pair Q = (1.20076,2.36814);
pair F = (-0.45010,-0.79358);
size(9cm);
pen qqffff = rgb(0.,1.,1.);
pen yqqqqq = rgb(0.50196,0.,0.);
pen zzttqq = rgb(0.6,0.2,0.);
pen ffxfqq = rgb(1.,0.49803,0.);
pen qqwuqq = rgb(0.,0.39215,0.);
draw(A--B--C--cycle, linewidth(0.6) + zzttqq);
draw(A--M, linewidth(0.6) + qqffff);
draw(B--S, linewidth(0.6) + qqffff);
draw(circle((-2.,2.02754), 3.21884), linewidth(0.6) + yqqqqq);
draw(A--B, linewidth(0.6) + zzttqq);
draw(B--C, linewidth(0.6) + zzttqq);
draw(C--A, linewidth(0.6) + zzttqq);
draw(circle((-5.21849,1.56567), 1.72266), linewidth(0.6) + ffxfqq);
draw(A--E, linewidth(0.6) + yqqqqq);
draw(D--L, linewidth(0.6) + qqwuqq);
draw(P--Q, linewidth(0.6) + ffxfqq);
draw(L--E, linewidth(0.6) + ffxfqq);
draw(E--Q, linewidth(0.6) + qqwuqq);
draw(E--F, linewidth(0.6) + yqqqqq);
draw(S--M, linewidth(0.6) + yqqqqq);
draw(A--F, linewidth(0.6));
draw(P--F, dashed);
draw(S--L, dashed);
dot("$C$", C, dir((2.343, -22.443)));
dot("$B$", B, dir((-19.721, -25.483)));
dot("$A$", A, dir((-11.383, 10.955)));
dot("$M$", M, dir((-8.308, -21.862)));
dot("$S$", S, dir((3.090, 6.140)));
dot("$X$", X, dir((3.315, 5.773)));
dot("$E$", E, dir((-12.903, -21.357)));
dot("$D$", D, dir(20));
dot("$L$", L, dir((-24.946, -1.451)));
dot("$P$", P, dir((-12.308, 13.017)));
dot("$Q$", Q, dir(20));
dot("$F$", F, dir((1.604, -19.837)));
\end{asy}
\end{center}
\begin{claim*}
[Main projective claim]
We have $XP = XA$.
\end{claim*}
\begin{proof}
Introduce $Y = \ol{PDF} \cap \ol{AM}$.
Note that
\[ -1 = (SM;EF) \overset{A}{=} (S,X;D,\ol{AF} \cap \ol{ES}) \overset{F}{=} (\infty X;YA) \]
where $\infty = \ol{AM} \cap \ol{SF}$ is at infinity (because $AMSF$ is a rectangle).
Thus, $XY = XA$.
\begin{center}
\begin{asy}
/*
Converted from GeoGebra by User:Azjps using Evan's magic cleaner
https://github.com/vEnhance/dotfiles/blob/main/py-scripts/export-ggb-clean-asy.py
*/
pair C = (0.5,0.);
pair B = (-4.5,0.);
pair A = (-3.54989,4.84867);
pair M = (-2.,-1.19129);
pair S = (-2.,5.24638);
pair X = (-3.07373,2.99308);
pair E = (-3.54989,-0.79358);
pair D = (-3.54989,1.99384);
pair P = (-4.96929,3.27021);
pair Q = (1.20076,2.36814);
pair K = (10.67519,1.99384);
pair F = (-0.45010,-0.79358);
pair Y = (-2.59758,1.13749);
import graph;
size(9cm);
pen qqffff = rgb(0.,1.,1.);
pen yqqqqq = rgb(0.50196,0.,0.);
pen zzttqq = rgb(0.6,0.2,0.);
pen ffxfqq = rgb(1.,0.49803,0.);
pen qqwuqq = rgb(0.,0.39215,0.);
pen ffqqff = rgb(1.,0.,1.);
draw(circle((-2.,2.02754), 3.21884), linewidth(0.6) + yqqqqq);
draw(A--E, linewidth(0.6) + yqqqqq);
draw(E--F, linewidth(0.6) + yqqqqq);
draw(S--M, linewidth(0.6) + yqqqqq);
draw(A--F, linewidth(0.6));
draw(A--M, blue);
draw(S--D, blue);
draw(D--F, red);
draw(D--P, grey+dotted);
draw(P--Q, grey+dotted);
/*
draw(A--M, linewidth(0.6) + qqffff);
draw(B--S, linewidth(0.6) + qqffff);
draw(P--F, linewidth(0.6) + ffqqff);
draw(P--Q, linewidth(0.6) + ffxfqq);
*/
dot("$A$", A, dir((-10.485, 9.780)));
dot("$M$", M, dir((-7.272, -19.720)));
dot("$S$", S, dir((3.090, 5.242)));
dot("$X$", X, dir(310));
dot("$E$", E, dir((-11.866, -19.423)));
dot("$D$", D, dir(20));
dot("$P$", P, dir((-16.384, -0.247)));
dot("$F$", F, dir((1.466, -18.041)));
dot("$Y$", Y, dir((2.746, 5.774)));
dot(extension(A,F,B,S));
\end{asy}
\end{center}
Since $\triangle APY$ is also right, we get $XP = XA$.
\end{proof}
\begin{proof}[Alternative proof of claim without harmonic bundles,
from Solution 9 of the marking scheme]
With $Y = \ol{PDF} \cap \ol{AM}$ defined as before, note that
$\ol{AE} \parallel \ol{SM}$ and $\ol{AM} \parallel \ol{SF}$ (as $AMFS$ is a rectangle)
gives respectively the similar triangles
\[ \triangle AXD \sim \triangle MXS, \qquad \triangle XDY \sim \triangle SDF. \]
From this we conclude
\[ \frac{AX}{XD} = \frac{AX+XM}{XD+SX} = \frac{AM}{SD} = \frac{SF}{SD} = \frac{XY}{XD}. \]
So $AX = XY$ and as before we conclude $XP = XA$.
\end{proof}
From $XP = XA$, we conclude that $\arc{PM}$ and $\arc{AQ}$ have the same measure.
Since $\arc{AS}$ and $\arc{EM}$ have the same measure,
it follows $\arc{PE}$ and $\arc{SQ}$ have the same measure.
The desired tangency then follows from
\[ \dang QPL = \dang QPS = \dang PQE = \dang PFE = \dang PDL. \]
\begin{remark*}
[Logical ordering]
This solution is split into two phases:
the ``synthetic phase'' where we do a bunch of angle chasing, and the
``projective phase'' where we use cross-ratios because I like projective.
For logical readability (so we write in only one logical direction),
the projective phase is squeezed in two halves of the synthetic phase,
but during an actual solve it's expected to complete
the whole synthetic phase first (i.e.\ to reduce the problem to show $XP=XA$).
\end{remark*}
\begin{remark*}
There are quite a multitude of approaches for this problem;
the marking scheme for this problem at the actual IMO had 13 different solutions.
\end{remark*}
\pagebreak
\subsection{IMO 2023/3, proposed by Ivan Chan (MAS)}
\textsl{Available online at \url{https://aops.com/community/p28097600}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
For each integer $k\geq 2$, determine all infinite sequences of positive integers
$a_1$, $a_2$, \dots\ for which there exists a polynomial $P$ of the form
\[ P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0, \]
where $c_0$, $c_1$, \dots, $c_{k-1}$ are non-negative integers, such that
\[ P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k} \]
for every integer $n\geq 1$.
\end{mdframed}
The answer is $a_n$ being an arithmetic progression.
Indeed, if $a_n = d(n-1) + a_1$ for $d \ge 0$ and $n \ge 1$, then
\[ a_{n+1} a_{n+2} \dots a_{n+k} = (a_n+d)(a_n+2d)\dots(a_n+kd) \]
so we can just take $P(x) = (x+d)(x+2d) \dots (x+kd)$.
The converse direction takes a few parts.
\begin{claim*}
Either $a_1 < a_2 < \cdots$ or the sequence is constant.
\end{claim*}
\begin{proof}
Note that
\begin{align*}
P(a_{n-1}) &= a_{n}a_{n+1}\cdots a_{n+k-1} \\
P(a_n) &= a_{n+1}a_{n+2}\cdots a_{n+k} \\
\implies a_{n+k} &= \frac{P(a_n)}{P(a_{n-1})} \cdot a_n.
\end{align*}
Now the polynomial $P$ is strictly increasing over $\NN$.
So assume for contradiction there's an index $n$ such that $a_n < a_{n-1}$.
Then in fact the above equation shows $a_{n+k} < a_n < a_{n-1}$.
Then there's an index $\ell \in [n+1,n+k]$ such that
$a_\ell < a_{\ell-1}$, and also $a_\ell < a_n$.
Continuing in this way, we can an infinite descending subsequence of $(a_n)$,
but that's impossible because we assumed integers.
Hence we have $a_1 \le a_2 \le \cdots$.
Now similarly, if $a_n = a_{n-1}$ for any index $n$, then $a_{n+k} = a_n$,
ergo $a_{n-1} = a_n = a_{n+1} = \dots = a_{n+k}$.
So the sequence is eventually constant, and then by downwards induction,
it is fully constant.
\end{proof}
\begin{claim*}
There exists a constant $C$ (depending only $P$, $k$)
such that we have $a_{n+1} \leq a_n + C$.
\end{claim*}
\begin{proof}
Let $C$ be a constant such that $P(x) < x^k + Cx^{k-1}$ for all $x \in \NN$
(for example $C = c_0 + c_1 + \dots + c_{k-1} + 1$ works).
We have
\begin{align*}
a_{n+k} &= \frac{P(a_n)}{a_{n+1} a_{n+2} \dots a_{n+k-1}} \\
&< \frac{P(a_n)}{(a_n+1)(a_n+2)\dots(a_n+k-1)} \\
&< \frac{a_n^k + C \cdot a_n^{k-1}}{(a_n+1)(a_n+2)\dots(a_n+k-1)} \\
&< a_n + C + 1. \qedhere
\end{align*}
\end{proof}
Assume henceforth $a_n$ is nonconstant, and hence unbounded.
For each index $n$ and term $a_n$ in the sequence,
consider the associated differences
$d_1 = a_{n+1} - a_n$, $d_2 = a_{n+2} - a_{n+1}$, \dots, $d_k = a_{n+k}-a_{n+k-1}$,
which we denote by
\[ \Delta(n) \coloneqq (d_1, \dots, d_k).\]
This $\Delta$ can only take up to $C^k$ different values.
So in particular, some tuple $(d_1, \dots, d_n)$
must appear infinitely often as $\Delta(n)$; for that tuple, we obtain
\[ P(a_N) = (a_N+d_1)(a_N+d_1+d_2) \dots (a_N+d_1+\dots+d_k) \]
for infinitely many $N$.
But because of that, we actually must have
\[ P(X) = (X+d_1)(X+d_1+d_2) \dots (X+d_1+\dots+d_k). \]
However, this \emph{also} means that \emph{exactly} one output to $\Delta$
occurs infinitely often (because that output is determined by $P$).
Consequently, it follows that $\Delta$ is eventually constant.
For this to happen, $a_n$ must eventually coincide with an arithmetic
progression of some common difference $d$,
and $P(X) = (X+d)(X+2d) \dots (X+kd)$.
Finally, this implies by downwards induction that $a_n$ is
an arithmetic progression on all inputs.
\pagebreak
\section{Solutions to Day 2}
\subsection{IMO 2023/4, proposed by Merlijn Staps (NLD)}
\textsl{Available online at \url{https://aops.com/community/p28104298}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $x_1$, $x_2$, \dots, $x_{2023}$ be pairwise different positive real numbers such that
\[ a_n = \sqrt{(x_1+x_2+\dots+x_n)
\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}\right)} \]
is an integer for every $n=1,2,\dots,2023$. Prove that $a_{2023} \geq 3034$.
\end{mdframed}
Note that $a_{n+1} > \sqrt{\sum_1^n x_i \sum_1^n \frac{1}{x_i}} = a_n$ for all $n$,
so that $a_{n+1} \geq a_n + 1$.
Observe $a_1 = 1$.
We are going to prove that \[ a_{2m+1} \geq 3m+1 \qquad \text{for all } m \geq 0 \]
by induction on $m$, with the base case being clear.
We now present two variations of the induction.
The first shorter solution compares $a_{n+2}$ directly to $a_n$,
showing it increases by at least $3$.
Then we give a longer approach that compares $a_{n+1}$ to $a_n$,
and shows it cannot increase by $1$ twice in a row.
\paragraph{Induct-by-two solution}
Let $u = \sqrt{\frac{x_{n+1}}{x_{n+2}}} \neq 1$.
Note that by using Cauchy-Schwarz with three terms:
\begin{align*}
a_{n+2}^2 &= \Bigg[ (x_1+\dots+x_n)+x_{n+1}+x_{n+2} \Bigg]
\Bigg[ \left(\frac{1}{x_1}+\dots+\frac{1}{x_n}\right)
+\frac{1}{x_{n+2}} + \frac{1}{x_{n+1}} \Bigg] \\
&\geq \left( \sqrt{ (x_1+\dots+x_n)\left(\frac{1}{x_1}+\dots+\frac{1}{x_n}\right)}
+ \sqrt{\frac{x_{n+1}}{x_{n+2}}} + \sqrt{\frac{x_{n+2}}{x_{n+1}}} \right)^2 \\
&= \left( a_n + u + \frac 1u \right)^2. \\
\implies a_{n+2} &\ge a_n + u + \frac 1u > a_n + 2
\end{align*}
where the last equality $u + \frac 1u > 2$ is by AM-GM, strict as $u \neq 1$.
It follows that $a_{n+2} \geq a_n + 3$, completing the proof.
\paragraph{Induct-by-one solution}
The main claim is:
\begin{claim*}
It's impossible to have
$a_n = c$, $a_{n+1} = c+1$, $a_{n+2} = c+2$ for any $c$ and $n$.
\end{claim*}
\begin{proof}
Let $p = x_{n+1}$ and $q = x_{n+2}$ for brevity.
Let $s = \sum_1^n x_i$ and $t = \sum_1^n \frac{1}{x_n}$, so $c^2 = a_n^2 = st$.
From $a_n = c$ and $a_{n+1} = c$ we have
\begin{align*}
(c+1)^2 &= a_{n+1}^2 = (p+s)\left( \frac 1p+t \right) \\
&= st + pt + \frac1ps + 1 = c^2 + pt + \frac1ps + 1 \\
&\overset{\text{AM-GM}}{\geq} c^2 + 2\sqrt{st} + 1 = c^2 + 2\sqrt{c^2} + 1 = (c+1)^2.
\end{align*}
Hence, equality must hold in the AM-GM we must have exactly
\[ p t = \frac 1p s = c. \]
If we repeat the argument again on $a_{n+1}=c+1$ and $a_{n+2}=c_{n+2}$, then
\[ p \left( \frac 1q + t \right) = \frac 1p \left( q + s \right) = c + 1. \]
However this forces $\frac pq = \frac qp = 1$ which is impossible.
\end{proof}
\pagebreak
\subsection{IMO 2023/5, proposed by Merlijn Staps and Daniël Kroes (NLD)}
\textsl{Available online at \url{https://aops.com/community/p28104367}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n$ be a positive integer.
A \emph{Japanese triangle} consists of $1 + 2 + \dots + n$ circles arranged in an
equilateral triangular shape such that for each $1 \le i \le n$,
the $i$\ts{th} row contains exactly $i$ circles, exactly one of which is colored red.
A \emph{ninja path} in a Japanese triangle is a sequence of $n$ circles
obtained by starting in the top row, then repeatedly going from a circle to
one of the two circles immediately below it and finishing in the bottom row.
Here is an example of a Japanese triangle with $n = 6$,
along with a ninja path in that triangle containing two red circles.
\begin{center}
\begin{asy}
size(4cm);
pair X = dir(240); pair Y = dir(0);
path c = scale(0.5)*unitcircle;
int[] t = {0,0,2,2,3,0};
for (int i=0; i<=5; ++i) {
for (int j=0; j<=i; ++j) {
filldraw(shift(i*X+j*Y)*c, (t[i]==j) ? lightred : white);
draw(shift(i*X+j*Y)*c);
}
}
draw((0,0)--(X+Y)--(2*X+Y)--(3*X+2*Y)--(4*X+2*Y)--(5*X+2*Y),linewidth(1.5));
path q = (3,-3sqrt(3))--(-3,-3sqrt(3));
draw(q,Arrows(TeXHead, 1));
label("$n = 6$", q, S);
\end{asy}
\end{center}
In terms of $n$, find the greatest $k$ such that in each Japanese triangle
there is a ninja path containing at least $k$ red circles.
\end{mdframed}
The answer is
\[ k = \left\lfloor \log_2(n) \right\rfloor + 1. \]
\paragraph{Construction}
It suffices to find a Japanese triangle for $n = 2^e-1$
with the property that at most $e$ red circles in any ninja path.
The construction shown below for $e=4$ obviously generalizes,
and works because in each of the sets $\{1\}$, $\{2,3\}$, $\{4,5,6,7\}$,
\dots, $\{2^{e-1},\dots,2^e-1\}$, at most one red circle can be taken.
(These sets are colored in different shades of red for visual clarity).
\begin{center}
\begin{asy}
size(8cm);
pair X = dir(240); pair Y = dir(0);
path c = scale(0.5)*unitcircle;
fill(shift(0*X+0*Y)*c, heavyred);
fill(shift(1*X+0*Y)*c, red);
fill(shift(2*X+2*Y)*c, red);
fill(shift(3*X+0*Y)*c, magenta);
fill(shift(4*X+2*Y)*c, magenta);
fill(shift(5*X+4*Y)*c, magenta);
fill(shift(6*X+6*Y)*c, magenta);
fill(shift(7*X+0*Y)*c, lightred);
fill(shift(8*X+2*Y)*c, lightred);
fill(shift(9*X+4*Y)*c, lightred);
fill(shift(10*X+6*Y)*c, lightred);
fill(shift(11*X+8*Y)*c, lightred);
fill(shift(12*X+10*Y)*c, lightred);
fill(shift(13*X+12*Y)*c, lightred);
fill(shift(14*X+14*Y)*c, lightred);
for (int i=0; i<15; ++i) {
for (int j=0; j<=i; ++j) {
draw(shift(i*X+j*Y)*c);
}
}
\end{asy}
\end{center}
\paragraph{Bound}
Conversely, we show that in any Japanese triangle,
one can find a ninja path containing at least
\[ k = \left\lfloor \log_2(n) \right\rfloor + 1. \]
The following short solution was posted at \url{https://aops.com/community/p28134004},
apparently first found by the team leader for Iran.
We construct a rooted binary tree on the set of all circles as follows.
For each row other than the bottom row:
the white circles to the left to their left desce
\begin{itemize}
\ii Connect the red circle to both circles under it,
\ii White circles to the left of the red circle are connected to the left.
\ii White circles to the right of the red circle are connected to the right.
\end{itemize}
The circles in the bottom row are all leaves of this tree.
For example, the $n=6$ construction in the beginning gives the following tree:
\begin{center}
\begin{asy}
size(7cm);
pair X = dir(240); pair Y = dir(0);
path c = scale(0.3)*unitcircle;
int[] t = {0,0,2,2,3,0};
for (int i=0; i<5; ++i) {
for (int j=0; j<=i; ++j) {
if (j <= t[i]) {
draw( (i*X+j*Y)--((i+1)*X+j*Y), blue+1.4);
}
if (j >= t[i]) {
draw( (i*X+j*Y)--((i+1)*X+(j+1)*Y), blue+1.4);
}
}
}
for (int i=0; i<=5; ++i) {
for (int j=0; j<=i; ++j) {
filldraw(shift(i*X+j*Y)*c, (t[i]==j) ? lightred : white);
draw(shift(i*X+j*Y)*c);
}
}
\end{asy}
\end{center}
Now focus on only the red circles.
Each red circle has at most $2$ red circles below it by construction.
Hence some path must have at least more than $\log_2(n)$ red circles in it.
\pagebreak
\subsection{IMO 2023/6, proposed by Ankan Bhattacharya, Luke Robitaille (USA)}
\textsl{Available online at \url{https://aops.com/community/p28104331}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be an equilateral triangle.
Let $A_1$, $B_1$, $C_1$ be interior points of $ABC$
such that $BA_1=A_1C$, $CB_1=B_1A$, $AC_1=C_1B$, and
\[ \angle BA_1C + \angle CB_1A + \angle AC_1B = 480\dg. \]
Let $A_2 = \ol{BC_1} \cap \ol{CB_1}$, $B_2 = \ol{CA_1} \cap \ol{AC_1}$,
$C_2 = \ol{AB_1} \cap \ol{BA_1}$.
Prove that if triangle $A_1B_1C_1$ is scalene,
then the circumcircles of triangles $AA_1A_2$, $BB_1B_2$, and $CC_1C_2$
all pass through two common points.
\end{mdframed}
This is the second official solution from the marking scheme,
also communicated to me by Michael Ren.
Define $O$ as the center of $ABC$ and set the angles
\begin{align*}
\alpha &\coloneqq \angle A_1CB = \angle CBA_1 \\
\beta &\coloneqq \angle ACB_1 = \angle B_1AC \\
\gamma &\coloneqq \angle C_1AB = \angle C_1BA
\end{align*}
so that
\[ \alpha + \beta + \gamma = 30\dg. \]
In particular, $\max(\alpha,\beta,\gamma) < 30\dg$,
so it follows that $A_1$ lies inside $\triangle OBC$, and similarly for the others.
This means for example that $C_1$ lies between $B$ and $A_2$, and so on.
Therefore the polygon $A_2C_1B_2A_1C_2B_1$ is convex.
\begin{center}
\begin{asy}
size(14cm);
pair A = dir(90);
pair B = dir(210);
pair C = dir(330);
real s = abs(B-C)/2;
pair A_1 = midpoint(B--C) + dir(A) * s*Tan(11);
pair B_1 = midpoint(C--A) + dir(B) * s*Tan(13);
pair C_1 = midpoint(A--B) + dir(C) * s*Tan(6);
pair A_1 = A_1;
pair B_1 = B_1;
pair C_1 = C_1;
pair O = origin;
filldraw(A--B--C--cycle, opacity(0.1)+lightcyan, blue);
draw(A--A_1, blue);
draw(B--B_1, blue);
draw(C--C_1, blue);
pair A_2 = extension(B, C_1, B_1, C);
pair B_2 = extension(C, A_1, C_1, A);
pair C_2 = extension(A, B_1, B, A_1);
draw(B--A_2--C, lightred);
draw(C--B_2--A, lightred);
draw(A--C_2--B, lightred);
markangle("$\alpha$", n=1, radius=32.0, C, B, A_1, deepgreen);
markangle("$\alpha$", n=1, radius=32.0, A_1, C, B, deepgreen);
markangle("$\beta$", n=2, radius=56.0, A, C, B_1, deepgreen);
markangle("$\beta$", n=2, radius=56.0, B_1, A, C, deepgreen);
markangle("$\gamma$", n=3, radius=64.0, B, A, C_1, deepgreen);
markangle("$\gamma$", n=3, radius=64.0, C_1, B, A, deepgreen);
draw(circumcircle(B_1, C_1, B_2), grey);
draw(circumcircle(C_1, A_1, C_2), grey);
draw(circumcircle(A_1, B_1, A_2), grey);
pair Z = A_1;
pair X = -Z+2*foot(circumcenter(A_1, A_2, B_1), A, O);
pair Y = -Z+2*foot(circumcenter(A_1, A_2, C_1), A, O);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$A_1$", A_1, dir(A_1));
dot("$B_1$", B_1, dir(B_1));
dot("$C_1$", C_1, dir(C_1));
dot("$O$", O, 1.4*dir(240));
dot("$A_2$", A_2, dir(A_2));
dot("$B_2$", B_2, dir(B_2));
dot("$C_2$", C_2, dir(320));
dot("$X$", X, 1.7*dir(295));
dot("$Y$", Y, dir(55));
/* -----------------------------------------------------------------+
| TSQX: by CJ Quines and Evan Chen |
| https://github.com/vEnhance/dotfiles/blob/main/py-scripts/tsqx.py |
+-------------------------------------------------------------------+
!size(14cm);
A = dir 90
B = dir 210
C = dir 330
!real s = abs(B-C)/2;
!pair A_1 = midpoint(B--C) + dir(A) * s*Tan(11);
!pair B_1 = midpoint(C--A) + dir(B) * s*Tan(13);
!pair C_1 = midpoint(A--B) + dir(C) * s*Tan(6);
A_1 = A_1
B_1 = B_1
C_1 = C_1
O 1.4R240 = origin
A--B--C--cycle / 0.1 lightcyan / blue
A--A_1 / blue
B--B_1 / blue
C--C_1 / blue
A_2 = extension B C_1 B_1 C
B_2 = extension C A_1 C_1 A
C_2 320 = extension A B_1 B A_1
B--A_2--C / lightred
C--B_2--A / lightred
A--C_2--B / lightred
!markangle("$\alpha$", n=1, radius=32.0, C, B, A_1, deepgreen);
!markangle("$\alpha$", n=1, radius=32.0, A_1, C, B, deepgreen);
!markangle("$\beta$", n=2, radius=56.0, A, C, B_1, deepgreen);
!markangle("$\beta$", n=2, radius=56.0, B_1, A, C, deepgreen);
!markangle("$\gamma$", n=3, radius=64.0, B, A, C_1, deepgreen);
!markangle("$\gamma$", n=3, radius=64.0, C_1, B, A, deepgreen);
circumcircle B_1 C_1 B_2 / grey
circumcircle C_1 A_1 C_2 / grey
circumcircle A_1 B_1 A_2 / grey
Z := A_1
X 1.7R295 = -Z+2*foot (circumcenter A_1 A_2 B_1) A O
Y 55 = -Z+2*foot (circumcenter A_1 A_2 C_1) A O
*/
\end{asy}
\end{center}
We start by providing the ``interpretation'' for the $480\dg$ angle in the statement:
\begin{claim*}
Point $A_1$ is the circumcenter of $\triangle A_2BC$, and similarly for the others.
\end{claim*}
\begin{proof}
We have $\angle BA_1C = 180\dg - 2\alpha$, and
\begin{align*}
\angle BA_2C &= 180\dg - \angle C_1BA - \angle B_1CB \\
&= 180\dg - \left( 60\dg - \gamma \right) - \left( 60\dg - \beta \right) \\
&= 60\dg + \beta + \gamma = 90\dg-\alpha = \half \angle BA_1 C.
\end{align*}
Since $A_1$ lies inside $\triangle BA_2C$,
it follows $A_1$ is exactly the circumcenter.
\end{proof}
\begin{claim*}
Quadrilateral $B_2C_1B_1C$ can be inscribed in a circle, say $\gamma_a$.
Circles $\gamma_b$ and $\gamma_c$ can be defined similarly.
Finally, these three circles are pairwise distinct.
\end{claim*}
\begin{proof}
Using directed angles now, we have
\[ \dang B_2B_1C_2 = 180\dg-\dang AB_1B_2
= 180\dg - 2 \dang ACB = 180\dg-2(60\dg-\alpha) = 60\dg+2\alpha. \]
By the same token, $\dang B_2C_1C_2 = 60\dg+2\alpha$.
This establishes the existence of $\gamma_a$.
The proof for $\gamma_b$ and $\gamma_c$ is the same.
Finally, to show the three circles are distinct, it would be enough to
verify that the convex hexagon $A_2C_1B_2A_1C_2B_1$ is not cyclic.
Assume for contradiction it was cyclic. Then
\[ 360\dg = \angle C_2A_1B_1 + \angle B_2C_1A_2 + \angle A_2B_1C_2
= \angle BA_1C + \angle CB_1A + \angle AC_1B = 480\dg \]
which is absurd.
This contradiction eliminates the degenerate case, so the three circles are distinct.
\end{proof}
For the remainder of the solution, let $\opname{Pow}(P, \omega)$
denote the power of a point $P$ with respect to a circle $\omega$.
Let line $AA_1$ meet $\gamma_b$ and $\gamma_c$ again at $X$ and $Y$,
and set $k_a \coloneqq \frac{AX}{AY}$.
Consider the locus of all points $P$ such that
\[ \mathcal C_a \coloneqq \Big\{ \text{points } P \text{ in the plane satisfying }
\opname{Pow}(P, \gamma_b) = k_a \opname{Pow}(P, \gamma_c) \Big\}. \]
We recall the \emph{coaxiality lemma}\footnote{We quickly outline a proof of this lemma:
in the Cartesian coordinate system, the expression $\opname{Pow}((x,y), \omega)$
is an expression of the form $x^2 + y^2 + {\bullet} x + {\bullet} y + {\bullet}$
for some constants ${\bullet}$ whose value does not matter.
Substituting this into the equation
$\frac{k_a \opname{Pow}(P, \gamma_c) - \opname{Pow}(P, \gamma_b)}{k_a-1} = 0$
gives the equation of a circle provided $k_a \neq 1$,
and when $k_a = 1$, one instead recovers the radical axis.},
which states that (given $\gamma_b$ and $\gamma_c$ are not concentric)
the locus $\mathcal C_a$ must be either a circle (if $k_a \neq 1$) or a line (if $k_a=1$).
On the other hand, $A_1$, $A_2$, and $A$ all obviously lie on $\mathcal C_a$.
(For $A_1$ and $A_2$, the powers are both zero, and for the point $A$,
we have $\opname{Pow}(P, \gamma_b) = AX \cdot AA_1$
and $\opname{Pow}(P, \gamma_c) = AY \cdot AA_1$.)
So $\mathcal C_a$ must be exactly the circumcircle of $\triangle AA_1A_2$
from the problem statement.
We turn to evaluating $k_a$ more carefully.
First, note that
\[ \angle A_1XB_1 = \angle A_1B_2B_1 = \angle CB_2B_1
= 90\dg - \angle B_2AC = 90\dg - (60\dg-\gamma) = 30\dg + \gamma. \]
Now using the law of sines, we derive
\begin{align*}
\frac{AX}{AB_1} &= \frac{\sin \angle XAB_1}{\sin \angle AB_1X}
= \frac{\sin \angle XAB_1}{\sin(\angle A_1XB_1 - \angle XAB_1)} \\
&= \frac{\sin \angle XAB_1}{\sin(\angle A_1XB_1 - \angle XAB_1)}
= \frac{\sin (60\dg-\beta)}{\sin\left( (90\dg-\beta)-(30\dg+\gamma) \right)}
= \frac{\sin (60\dg-\beta)}{\sin(30\dg-\alpha)}.
\end{align*}
Similarly, $AY = AC_1 \cdot \frac{\sin(60\dg-\gamma)}{\sin(30\dg-\alpha)}$, so
\[ k_a = \frac{AX}{AY}
= \frac{AB_1}{AC_1} \cdot \frac{\sin(60\dg-\beta)}{\sin(60\dg-\gamma)}. \]
Now define analogous constants $k_b$ and $k_c$
and circles $\mathcal C_b$ and $\mathcal C_c$.
Owing to the symmetry of the expressions, we have the key relation
\[ k_a k_b k_c = 1. \]
In summary, the three circles in the problem statement may be described as
\begin{align*}
\mathcal C_a &= (AA_1A_2)
= \left\{ \text{points $P$ such that } \opname{Pow}(P, \gamma_b) = k_a \opname{Pow}(P, \gamma_c) \right\} \\
\mathcal C_b &= (BB_1B_2)
= \left\{ \text{points $P$ such that } \opname{Pow}(P, \gamma_c) = k_b \opname{Pow}(P, \gamma_a) \right\} \\
\mathcal C_c &= (CC_1C_2)
= \left\{ \text{points $P$ such that } \opname{Pow}(P, \gamma_a) = k_c \opname{Pow}(P, \gamma_b) \right\}.
\end{align*}
Since $k_a$, $k_b$, $k_c$ have product $1$,
it follows that any point on at least two of the circles
must lie on the third circle as well.
The convexity of hexagon $A_2C_1B_2A_1C_2B_1$ mentioned earlier ensures these
any two of these circles do intersect at two different points, completing the solution.
\pagebreak
\end{document}