IMO 1974 SL 3

Problem

I 3 (SWE 3)IMO6 Let P(x) be a polynomial with integer coefficients. If n(P) is the number of (distinct) integers k such that P 2(k) = 1, prove that n(P) −deg(P) \leq2, where deg(P) denotes the degree of the polynomial P.

Solution

For deg(P) \leq2 the statement is obvious, since n(P) \leqdeg(P 2) = 2 deg(P) \leqdeg(P) + 2. Suppose now that deg(P) \geq3 and n(P) > deg(P) + 2. Then there is at least one integer b for which P(b) = −1, and at least one x with P(x) = 1. We may assume w.l.o.g. that b = 0 (if necessary, we con- sider the polynomial P(x + b) instead). If k1, . . . , km are all integers for which P(ki) = 1, then P(x) = Q(x)(x −k1) \cdot \cdot \cdot (x −km) + 1 for some polynomial Q(x) with integer coefficients. Setting x = 0 we ob- tain (−1)mQ(0)k1 \cdot \cdot \cdot km = 1 −P(0) = 2. It follows that k1 \cdot \cdot \cdot km | 2, and hence m is at most 3. The same holds for the polynomial −P(x), and thus P(x) = −1 also has at most 3 integer solutions. This counts for 6 solutions of P 2(x) = 1 in total, implying the statement for deg(P) \geq4. It remains to verify the statement for n = 3. If deg(P) = 3 and n(P) = 6, then it follows from the above consideration that P(x) is either −(x2 − 1)(x −2) + 1 or (x2 −1)(x + 2) + 1. It is directly checked that n(P) equals only 4 in both cases.