IMO 1977 LL USS50

Origin: USS

Problem

Determine all positive integers n for which there exists a poly- nomial Pn(x) of degree n with integer coefficients that is equal to n at n different integer points and that equals zero at zero.

Solution

Suppose that Pn(x) = n for x \in{x1, x2, . . . , xn}. Then Pn(x) = (x −x1)(x −x2) \cdot \cdot \cdot (x −xn) + n.

From Pn(0) = 0 we obtain n = |x1x2 \cdot \cdot \cdot xn| \geq2n−2 (because at least n −2 factors are different from \pm1) and therefore n \geq2n−2. It follows that n \leq4. For each positive integer n \leq4 there exists a polynomial Pn. Here is the list of such polynomials: n = 1 : \pmx, n = 2 : 2x2, x2 \pm x, −x2 \pm 3x, n = 3 : \pm(x3 −x) + 3x2, n = 4 : −x4 + 5x2.