\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{SIME 2020/14}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 23}
\maketitle
\section*{Problem}
Let $P(x) = x^3 - 3x^2 + 3$.
For how many positive integers $n < 1000$
does there not exist a pair $(a, b)$ of positive integers
such that the equation
\[ \underbrace{P(P(\dots P}_{a \text{ times}}(x)\dots))
= \underbrace{P(P(\dots P}_{b \text{ times}}(x)\dots)) \]
has exactly $n$ distinct real solutions?
\section*{Video}
\href{https://www.youtube.com/watch?v=6RJbk6tTUi0&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/6RJbk6tTUi0}}
\section*{External Link}
\url{https://aops.com/community/p16682015}
\newpage
\section*{Solution}
The idea is to replace $x$ with the variable $y=2x+1$.
To formally, express this consider the substitution $T(y) = 2y+1$,
which is a bijective function.
Then
\[ P(T(y)) = T\left( 4y^3 - 3y \right) \]
Thus, if we define $Q(y) = 4y^3-3y$,
the problem is actually equivalent to saying that
\[ Q(Q(\dots Q(y))) = Q(Q(\dots Q(y))) \]
where $Q$ appears $a$ times on the left and $b$ times on the right.
We now substitute $y = \cos\theta$ for $\theta \in \CC$,
recognizing $Q$ as the triple-angle formula:
$Q(\cos\theta) = \cos3\theta$.
Thus the condition then becomes equivalent to
\[ \cos(3^a\theta) = \cos(3^b\theta). \]
\begin{claim*}
Assume $a < b$.
There are $n = 3^b - 3^a + 1$ solutions to the above equation
in terms of $y$, as a function of $a$ and $b$.
\end{claim*}
\begin{proof}
It is simplest to re-parametrize by $z \in \CC$ on the unit circle;
the relevant condition is
\[ z^{3^a} + z^{-3^a} = z^{3^b} + z^{-3^b}. \]
which simplifies to
\[ \left( z^{3^b+3^a} - 1 \right)
\left( z^{3^b-3^a} - 1 \right) = 0. \]
Note there are $\gcd(3^b+3^a, 3^b-3^a) = 2 \cdot 3^a$ repeated roots.
So in total there are $2 \cdot (3^b - 3^a)$
To avoid double counting we only take those $z$ with $\Im z \ge 0$.
There are two roots $z = \pm 1$ on the real axis;
so this gives the final count $n = 3^b - 3^a + 1$.
\end{proof}
A calculations gives an answer of $999-(1+2+3+4+5) = 984$ now.
\end{document}