Putnam Problem

• Sep 3rd 2010, 11:16 AM
arsenicbear
Putnam Problem
Hi guys,

I am currently stuck on this Putnam problem and was wondering if anyone had some tips/strategies to attack it?

Determine all polynomials that have only real roots and all coefficients are +/-1?
• Sep 3rd 2010, 12:22 PM
TheEmptySet
Since $\pm 1$ is rational the rational roots theorem should be of some help

Rational root theorem - Wikipedia, the free encyclopedia
• Sep 3rd 2010, 06:25 PM
Soroban
Hello, arsenicbear!

Quote:

Determine all polynomials that have only real roots and all coefficients are $\pm1$.

I started scribbling and came up a surprising answer.
. . (Or am I totally wrong?)

There are two linear polynomials: . $\begin{array}{ccc}x + 1 \\ x - 1 \end{array}$

There are two cubic polynomials: . $\begin{array}{ccc}x^3-x^2 - x + 1 \\ x^3 + x^2 - x - 1 \end{array}$

I did not include $x^2-1$

It has a zero-coefficient: . $x^2 + {\bf 0}x - 1$

Did I miss any?

• Sep 5th 2010, 12:37 PM
Opalg
Quote:

Originally Posted by Soroban
Did I miss any?

There are two quadratic polynomials $x^2+x-1$ and $x^2-x-1$. I can't find any of degree 4 or higher, but then again I have no idea how to prove that there aren't any.
• Sep 7th 2010, 07:42 AM
ebaines
Here are two more quadratics: $-x^2 \pm x +1$
• Sep 8th 2010, 11:01 AM
Opalg
This problem has been bugging me. Since I could make no progress on it, I eventually resorted to a Google search for a solution, which I found here.

We may assume that the leading coefficient is +1. The sum of the squares of the roots of $x^n + a_1 x^{n-1} + \ldots + a_n$ is $a_1^2 - 2a_2$ . The product of the squares of the roots is $a_n^2$. Using the AGM inequality we have $\frac{a_1^2 - 2a_2}n \geqslant \sqrt[n]{a_n^2}.$

Since the coefficients are ±1 that inequality is (1 ± 2)/n ≥ 1, hence n ≤ 3.

Clever, huh? No wonder I couldn't do it.

So there are two of these polynomials in each of degree 1, 2, 3, together with their negatives, and no others, giving a total of 12 such polynomials.