The South African Mathematical Olympiad Third Round

Note first that $x-y$ divides $P(x)-P(y)$. So if $d\ne 0$, there are only finitely many possibilities for $x-y$. For one of these possible values, let us denote it by $a$, there must be

infinitely many pairs $(x,y)$ such that $x-y=a$ and $P(x)-P(y)=d$. Note that $$P(x)-P(x-a)-d$$ is still a polynomial. The only way it can have infinitely many zeros is that it is identically zero. But then $P(x)=dx/a+b$ for some number $b$. This gives us the first set of solutions, consisting of an arbitrary integer $d$ and a polynomial $P(x)=dx/a+b$, where $a$ is a (positive or negative) divisor of $d$ and $b$ an arbitrary integer. This includes the solution where $d=0$ and the polynomial $P(x)$ is constant. For the rest of this solution, we can assume that $d=0$. If the degree of the polynomial is odd, then there exist integers $A$ and $B$ such that $P(x)$ is either increasing for $x\ge A$ and for $x\le B$, or decreasing for $x\ge A$ and $x\le B$. If $P(x)$ is increasing for $x\ge A$, then $P(A)$, $P(A+1)$, $P(A+2)$, ... are a strictly increasing sequence of integers, thus distinct. Moreover, from some point on these numbers are all greater than the maximum of $P(x)$ for $x\le A$. Likewise, $P(B)$, $P(B-1)$, $P(B-2)$, ... are a strictly decreasing sequence of integers, and from some point on they are all less than the minimum of $P(x)$ for $x\ge B$. This means that there cannot be infinitely many pairs $x,y$ with $x\ne y$ such that $P(x)-P(y)=0$. The same argument applies if $P(x)$ is decreasing for $x\ge A$ and $x\le B$. Thus $P(x)$ must be a polynomial of even degree. Now there exist integers $A$ and $B$ such that $P(x)$ is increasing for $x\ge A$ and decreasing for $x\le B$, or vice versa. Thus there can only be infinitely many pairs $x,y$ with $x\ne y$ such that $P(x)-P(y)=0$ if one of the two $(x,y)$ is $\ge A$ while the other is $\le B$. We show that $x+y$ has to be constant for these solutions. Let the first terms of the polynomial be as follows: $$P(x)=a{x}^n+b{x}^{n-1}+\dots$$ Assume that $a$ is positive, for otherwise one can replace $P(x)$ by $-P(x)$. If $an(x+y)\ge -2b+1$, then we have $$P(x)-P\left(\frac{-2b+1}{an}-x\right)=x^{n-1}+\dots ,$$ where the dots stand for terms involving lower powers of $x$. For large enough $x$, this will be strictly positive, so $P(x)-P(y)\ne 0$. Likewise, if $an(x+y)\le -2b-1$, then we have $$P(x)-P\left(\frac{-2b-1}{an}-x\right)=-x^{n-1}+\dots ,$$ which is negative for large enough $x$. Hence $P(x)-P(y)\ne 0$ in this case as well. Thus there must be infinitely many solutions of $P(x)-P(y)=0$ with $an(x+y)=-2b$. In this case, $$P(x)-P\left(\frac{-2b}{an}-x\right)$$ is a polynomial with infinitely many zeros, hence it is constant. Thus $$P(x)=P\left(\frac{-2b}{an}-x\right)$$ for all $x$, which gives $$Q(x)=P\left(\frac{-b}{an}+x\right)=P\left(\frac{-b}{an}-x\right)=Q(-x)$$ for all $x$. It follows that the polynomial $Q(x)$ can only contain even powers of $x$, i.e. $Q(x)=R(x^2)$. This gives us the second set of solutions, consisting of a polynomial of the form $P(x)=R((x-c{)}^2)$, where $2c$ is an integer, and $d=0$.