Find all positive integers $d$ with the following property: there exists a polynomial $P$ of degree $d$ with integer coefficients such that $|P(m)|=1$ for at least $d+1$ different integers $m$.

#
Note that $P(x)=c$ for a fixed constant has at most $d$ solutions, since the polynomial $P(x)-c$ of degree $d$ cancels at most $d$ times. This implies that there are integers $m$ satisfying $P(m)=1$, as well as integers $m$ such that $P(m)=-1$.

Next, we prove the following lemma.

Lemma. If $a$ and $b$ are integers such that $P(a)=-1$ and $P(b)=1$, then $|b-a| \leq 2$.

Proof Since $b-a \mid P(b)-P(a)$ by a well-known lemma (corollary of $a-b \mid a^{n}-b^{n}$ for every integer $n \geq 0)$, the conclusion follows.

Let us first consider the case that $d \geq 4$, and assume that there exists a polynomial $\mathrm{P}$ with at least $d+1 \geq 5$ solutions to $|P(m)|=1$. Let $a$ and $b$ be the smallest and largest solution respectively. Since $b-a \geq 4$, we need $P(a)=P(b)$ by the lemma. Without loss of generality (by switching $P$ with $-P$ if necessary) we can assume $P(a)=P(b)=1$. Take a value $m$ such that $P(m)=-1$. Due to the lemma, we need $b-m$ and $m-a$ to be both at most 2 . Since $b-a \geq 4$, there is only one possibility left in which case $b-a=4$ and thus $d=4$. By considering $P(x-m)$, we can assume $P( \pm 2)=P( \pm 1)=1$ and $P(0)=-1$. The unique fourth degree polynomial satisfying these equalities is $P(x)=-0.5\left(x^{2}-4\right)\left(x^{2}-1\right)+1$ which is not a polynomial with integer coefficients.

For $1 \leq d \leq 3$, there exist polynomials satisfying the conditions.

For $d=1$ we can take $P_{1}(X)=X$ as $P_{1}(-1)=-1$ and $P_{1}(1)=1$.

For $d=2, P_{2}(X)=2 X(X-2)+1$ satisfies $P_{2}(0)=1, P_{2}(1)=-1$ and $P_{2}(2)=1$.

For $d=3$, the polynomial ; $P_{3}(X)=(X+1) X(X-2)+1$ satisfies $P_{3}(-1)=1=P_{3}(0)=P_{3}(2)=1$ and $P_{3}(1)=-1$. So $\left|P_{3}(m)\right|=1$ for $m \in\{-1,0,1,2\}$.

Thus the integers with the required property are precisely $d=1,2,3$. This completes the proof.

## BxMO 2020: Problems and Solutions

#