South African Mathematical Olympiad Third Round

Note first that $x - y$ divides $P(x) - P(y)$. So if $d \neq 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) = ax^n + bx^{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$.