Only 12 polynomials exist with given properties 
Prove that there are only 12 polynomials that have

*

*all real roots, and

*whose coefficients are all $-1$ or $1$.

(zero coefficients are not allowed, and constant polynomials do not count.)

Two of them are obviously $x-1$ and $x+1$.
I tried applying Viete's theorems, but could not get anything useful.
 A: I will assume that the reader is capable of finding that there are exactly 12 such polynomials in degree $3$ or less, by brute force if necessary.
Assume the degree of such a polynomial $f(x)$ is at least 4 for the sake of contradiction.  Let the leading coefficients be $f(x) = x^n - Ax^{n-1} + Bx^{n-2} - C x^{n-3} + Dx^{n-4} + \ldots$.  This convention is adopted so that the values $A,B,C,D\in \{\pm 1\}$ are the first four elementary symmetric polynomials in the roots.  That is, if $\alpha_1, \alpha_n$ are the $n$ real roots of $f(x)$, we have


*

*$A = \sum_{i=1}^n \alpha_i =\alpha_1 + \alpha_2 + \ldots + \alpha_n$

*$B = \sum_{1 \le i<j\le n} \alpha_i\alpha_j = \alpha_1\alpha_2 + \alpha_1\alpha_3 + \ldots + \alpha_{n-1}\alpha_n$

*$C = \sum_{1 \le i<j<k\le n}\alpha_i\alpha_j\alpha_k$

*$D = \sum_{1 \le i<j<k<l\le n}\alpha_i\alpha_j\alpha_k\alpha_l$


Remember that $\alpha_i^2 > 0 $ holds for all $i$ (nonzero constant term) and all of $A,B,C,D$ square to $1$.  We will now use Newton's identities to compute some values that must be positive.
$$\begin{align*}
0 < \sum_{i=1}^n \alpha_i^2 & = A^2-2B = 1-2B\\
0 < \sum_{i=1}^n \alpha_i^4 & = A^4-4A^2B + 2B^2 + 4AC - 4D\\
& = 3 - 4B + 4AC - 4D
\end{align*}
$$
In particular, from $0 < 1-2B$ we conclude $B = -1$ and the first sum must be 3.
The second sum is thus simplified to $7+4AC-4D$.
Next we note the identity
$$
9 = \left( \sum_{i=1}^n \alpha_i^2 \right)^2
= \sum_{i=1}^n \alpha_i^4 + 2\sum_{1 \le i<j\le n} \alpha_i^2\alpha_j^2
$$
then implies
$$
0 <\sum_{1 \le i<j\le n} \alpha_i^2\alpha_j^2
= \frac{1}{2}\left(9 - \sum_{i=1}^n \alpha_i^4 \right)
= \frac{1}{2}\left(9 - (7+4AC-4D)\right)
= 1 -2AC + 2D
$$
Now, we note that $AC-D \in \{-2, 0, 2\}$, but $0 < 7+4AC-4D$ tells us it cannot be $-2$, and $0< 1 - 2AC+2D$ tells us it cannot be $2$.  Thus, it must be $0$, and in particular the above sum simplifies to $1-2AC+2D = 1$.  We now perform one final calculation and rearrangement
$$
\begin{align*}
3 = 3\cdot 1 & = \left( \sum_{i=1}^n \alpha_i^2 \right)
\left(\sum_{1 \le i<j\le n} \alpha_i^2\alpha_j^2\right)
= \sum_{1 \le i<j\le n} \alpha_i^4\alpha_j^2
+ 3 \sum_{1 \le i<j<k\le n} \alpha_i^2\alpha_j^2\alpha_k^2\\
0 < \sum_{1 \le i<j\le n} \alpha_i^4\alpha_j^2
& = 3 \left( 1 - \sum_{1 \le i<j<k\le n} \alpha_i^2\alpha_j^2\alpha_k^2\right) 
\end{align*}
$$
This last line is a contradiction, because $\sum_{1 \le i<j<k\le n} \alpha_i^2\alpha_j^2\alpha_k^2$ is (by the fundamental theorem of symmetric polynomials) a polynomial in the coefficients of $f$, and is therefore at least $1$.
A: I already accepted @Rolf Hoyer s excellent answer, this is just its simplification, too large for comment, but using the same notation, for the sake of clarity.


*

*$A = \sum_{i=1}^n \alpha_i =\alpha_1 + \alpha_2 + \ldots + \alpha_n$

*$B = \sum_{1 \le i<j\le n} \alpha_i\alpha_j = \alpha_1\alpha_2 + \alpha_1\alpha_3 + \ldots + \alpha_{n-1}\alpha_n$

*$Z = \prod_{i=1}^n \alpha_i =\alpha_1\alpha_2\ldots\alpha_n$


Since polynomials have coefficients are $-1$ or $1$, than $A$, $B$, and $Z$ must be $-1$ or $1$.
The idea is to express $\sum_{i=1}^n \alpha_i^2$ in terms of $A$ and $B$:
$$\sum_{i=1}^n \alpha_i^2 =\alpha_1^2 + \alpha_2^2 + \ldots + \alpha_n^2 = (\sum_{i=1}^n \alpha_i)^2 - 2*\sum_{1 \le i<j\le n} \alpha_i\alpha_j$$
$$= A^2 - 2B = 1 - 2B = 3$$
Last two steps are based on $A^2 = 1$, and $B$ must be $-1$ since otherwise $\sum_{i=1}^n \alpha_i^2 =1 - 2B$ is negative.
Now, let us apply AM-GM inequality on $\alpha_1^2, \alpha_2^2, \ldots, \alpha_n^2$:
$$3=\sum_{i=1}^n \alpha_i^2 =\alpha_1^2 + \alpha_2^2 + \ldots + \alpha_n^2 \ge  n \sqrt[n]{\prod_{i=1}^n \alpha_i^2} = n \sqrt[n] {Z^2} = n \sqrt[n] 1 = n$$
This means $n \le 3$, in other words, polynomials must be of degree 1, 2, or 3, and those were 12 already found by others in the comments to the original question above. They are:
$$x+1$$
$$x-1$$
$$x^2+x-1$$
$$x^2-x-1$$
$$x^3-x^2-x+1$$
$$x^3+x^2-x-1$$
$$-(x+1)$$
$$-(x-1)$$
$$-(x^2+x-1)$$
$$-(x^2-x-1)$$
$$-(x^3-x^2-x+1)$$
$$-(x^3+x^2-x-1)$$
