2023 IMO Problems/Problem 3

Problem

For each integer $k \geqslant 2$ , determine all infinite sequences of positive integers $a_1, a_2, \ldots$ for which there exists a polynomial $P$ of the form $P(x)=x^k+c_{k-1} x^{k-1}+\cdots+c_1 x+c_0$ , where $c_0, c_1, \ldots, c_{k-1}$ are non-negative integers, such that $P\left(a_n\right)=a_{n+1} a_{n+2} \cdots a_{n+k}$ for every integer $n \geqslant 1$ .

Solution

https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems]

https://www.youtube.com/watch?v=CmJn5FKxpPY [Video contains another solution to problem 3]

Let $f(n)$ and $g(j)$ be functions of positive integers $n$ and $j$ respectively.

Let $a_{n}=a_{1}+f(n)$ , then $a_{n+1}=a_{1}+f(n+1)$ , and $a_{n+k}=a_{1}+f(n+k)$

Let $P=\prod_{j=1}^{k}\left ( a_{n+j} \right ) = \prod_{j=1}^{k}\left ( a_{n}+g(j)) \right )$

If we want the coefficients of $P(a_{n})$ to be positive, then $g(j)\geq 0$ for all $j$ which will give the following value for $P$ :

$P=a_{n}^{k}+C_{k-1}a_{n}^{k-1}+...+C_{1}a_{n}+\prod_{j=1}^{k} g(j) = P(a_{n})$

Thus for every $j$ and $n$ we need the following:

$a_{n}+g(j)=a_{n+j}=a_{1}+f(n+j)$

Solving for $g(j)$ we get:

$g(j)=a_{1}+f(n+j)-a_{n}=a_{1}+f(n+j)-a_{1}-f(n)$

$g(j)=f(n+j)-f(n)\geq 0$ for all $n$ and $j$ because $g(j)$ needs to be greater than or equal to zero for all coefficients to be non-negative.

This means that $f(n)$ needs to be increasing with $n$ , or staying constant, and also with $f(1)=0$ because $a_{1}=a_{1}+f(1)$ .

In addition, since we need all coefficients to be integer, then all $f(n)$ and $g(j)$ must also be integers. We also need $g(j)$ to not be dependent of $n$ , so in the expression $f(n+j)-f(n)$ , the $n$ needs to cancel. This mean that the rate of change for $f(n)$ with respect to $n$ needs to be constant. This can only be achieved with $f(n)$ be the equation of a line with slope being either zero or positive integer.

So, we set $f(n)$ to be the equation of a line as $f(n)=mn+b$ with $m$ being the slope with a non-negative value and with $b$ the intercept at $n=0$ . We know that $f(1)=0$ so $f(1)=m+b=0$ which means that $b=-m$ and our function becomes $f(n)=mn-m=(n-1)m$ . Since $f(n)$ needs to be non-negative integer then $m\geq 0 \mid m \in \mathbb{Z}$ then $f(n)$ is increasing or constant, with $f(1)=0$