\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{IMO 2023/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 130}
\maketitle
\section*{Problem}
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}\dotsm a_{n+k} \]
for every integer $n\geq 1$.
\section*{Video}
\href{https://www.youtube.com/watch?v=yGZUjUYTbzc&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/yGZUjUYTbzc}}
\section*{External Link}
\url{https://aops.com/community/p28097600}
\newpage
\section*{Solution}
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 < \dotsb$ or the sequence is constant.
\end{claim*}
\begin{proof}
Note that
\begin{align*}
P(a_{n-1}) &= a_{n}a_{n+1}\dotsm a_{n+k-1} \\
P(a_n) &= a_{n+1}a_{n+2}\dotsm 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 \dotsb$.
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.
\end{document}