Find all finite polynomials whose coefficients are all ±1 and whose roots are all real.
Answer: ±(x + 1), ±(x - 1), ±(x2 + x - 1), ±(x2 - x - 1), ±(x3 + x2 - x - 1), ±(x3 - x2 - x + 1).
The linear and quadratic polynomials are easy to find (and it is easy to show that they are the only ones).
Suppose the polynomial has degree n ≥ 3. Let the roots be ki. Then ∑ ki2 = (∑ ki)2 - 2 ∑ kikj = a2 ± 2b, where a is the coefficient of xn-1 and b is the coefficient of xn-2. Hence the arithmetic mean of the squares of the roots is (a2 ± 2b)/n. But it is at least as big as the geometric mean which is 1 (because it is an even power of c, the constant term). So we cannot have n > 3. For n = 3, we must have b the opposite sign to the coefficient of xn and it is then easy to check that the only possibilities are those given above.
29th Putnam 1968
© John Scholes
14 Jan 2002