75th NMO Selection Tests

The required polynomials are $P=0$, $P=1$, $P=(X-1{)}^2$, $P=X(X-1)\cdots (X-k)$ and $P=X(X-1)\cdots (X-k)(X-k-2{)}^2$ for some non-negative integer $k$. The verification is routine and is hence omitted.

We first deal with the case $P(0)=1$. The polynomials $P_1=1$ and $P_2=(X-1{)}^2$ both satisfy the condition in the statement and $P_1(0)=P_2(0)=1$.

We will prove that either $P=P_1$ or $P=P_2$. Consider an index $i$ such that $P(1)=P_i(1)$ and let $\tilde{P}=P-P_i$. Induct on $n$ to show that $\tilde{P}(n)=0$ for all non-negative integers $n$. The base cases $n=0$ and $n=1$ are clear. For the inductive step, assume $\tilde{P}(m)=0$ for all non-negative integers $m<n$. Then $X(X-1)\cdots (X-(n-1))$ divides $\tilde{P}$, so $n!$ divides $\tilde{P}(n)$. As $0<P_i(n)<n!$, it follows that $|\tilde{P}(n)|=|P(n)-P_i(n)|<n!$, so $\tilde{P}(n)=0$. Consequently, $\tilde{P}$ has infinitely many roots, so it vanishes identically; that is, $P=P_i$, as desired.

Finally, we deal with the case $P(0)=0$. Assume $P$ is non-zero. Let $P(X)=XQ(X-1)$, where $Q$ has integer coefficients. Then $0\le Q(n)\le n!$ for all non-negative integers $n$. If $Q(0)=0$, repeat the argument for $Q$ and so on and so forth, all the way down to some polynomial with a non-zero constant term — this is clearly the case, as $P$ is non-zero and degrees strictly decrease in the process. By the preceding, such a polynomial is either $1$ or $(X-1{)}^2$. An obvious induction then shows that $P$ has one of the last two forms mentioned in the beginning.