\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Malaysia SST 2023/7}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 131}
\maketitle
\section*{Problem}
Find all polynomials with integer coefficients $P$
such that for all positive integers $n$, the sequence
\[ 0, P(0), P(P(0)), P(P(P(0))), \dots \]
is eventually constant modulo $n$.
\section*{Video}
\href{https://www.youtube.com/watch?v=oNISgD_vjkM&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/oNISgD\_vjkM}}
\section*{External Link}
\url{https://aops.com/community/p28524876}
\newpage
\section*{Solution}
The answer is:
\begin{itemize}
\ii Any polynomial of the form $P(x) = Q(x)x(x-c)+c$,
where $Q \in \ZZ[x]$ and $c \in \ZZ$.
\ii Any polynomial of the form $P(x) = Q(x)(x+c)(x-c)-c$,
where $Q \in \ZZ[x]$ has $Q(0) = -\frac{2}{c}$ and $c \in \{\pm1,\pm2\}$.
\end{itemize}
The main claim of the problem is that the sequence can be described as follows.
\begin{claim*}
The sequence is either
\begin{align*}
0,\; & c,\; c,\; c,\; \dots \\
0,\; & c,\; -c,\; -c,\; \dots
\end{align*}
for some integer $c$.
\end{claim*}
\begin{proof}
If $P(0)=0$ we're done, so assume $c \coloneqq P(0) \neq 0$.
Then every term must in the sequence is a multiple of $c$, by working modulo $|c|$.
On the other hand, I contend every term in the sequence is $\pm c$ now.
Indeed, if some term $M$ in the sequence is a different multiple of $c$,
then take modulo $|M|$ to find the sequence is not eventually constant modulo $M$.
(In the case $M = 0$, take modulo any number larger than $c$.)
The claim then follows from this.
\end{proof}
The answer then follows from the two cases of the claim.
In the first case where the sequence is eventually constant,
the only constraint is that we have $P(0)=P(c)=c$ for some $c$,
which is equivalent to the bullet above.
In the second case, we first read the constraint $P(c)=P(-c)=-c$ to get
$P(x) = Q(x)(x+c)(x-c)-c$, and then plug in $x=0$ to conclude.
\end{document}