4. Determine all polynomials of the form $a_{n} x^{n}+a_{n-1} x^{n-1}+\ldots+a_{1} x+a_{0}$, where $a_{j} \in\{-1,1\}, j=0,1,2, \ldots, n$, which have only real roots.
Solution. Let's find the polynomials with the given property for which $a_{n}=1$. The remaining polynomials are obtained by multiplying the found ones by -1.

For $n=1$, such polynomials are $x-1$ and $x+1$.

Let's assume that $n \geq 2$ and $x_{i}, i=1,2, \ldots, n$ are the real roots of the desired polynomial. From Vieta's formulas, it follows that

$$
\left(x_{1} x_{2} \ldots x_{n}\right)^{2}=a_{0}^{2}=1
$$

and

$$
0 \leq \sum_{i=1}^{n} x_{i}^{2}=\left(\sum_{i=1}^{n} x_{i}\right)^{2}-2 \sum_{i \neq k} x_{i} x_{k}=a_{n-1}^{2}-2 a_{n-2}=1-2 a_{n-2}
$$

However, $a_{n-2} \in\{1,-1\}$, so $a_{n-2}=-1$ and $\sum_{i=1}^{n} x_{i}^{2}=3$. From the inequality between the arithmetic and geometric means, it follows that

$$
\frac{3}{n}=\frac{1}{n} \sum_{i=1}^{n} x_{i}^{2} \geq\left(x_{1}^{2} x_{2}^{2} \ldots x_{n}^{2}\right)^{1 / n}=1
$$

so $n \leq 3$. It is easily obtained that for $n=2$ the desired polynomials are

$$
\pm\left(x^{2}+x-1\right) \text { and } \pm\left(x^{2}-x-1\right)
$$

For $n=3$, only the polynomials

$$
\pm\left(x^{3}+x^{2}-x-1\right) \text { and } \pm\left(x^{3}-x^{2}-x+1\right)
$$

have real roots, while the other polynomials of the desired form have complex roots.

Finally, the desired polynomials are:

$$
\begin{gathered}
\pm(x-1), \pm(x+1), \pm\left(x^{2}+x-1\right), \pm\left(x^{2}-x-1\right) \\
\pm\left(x^{3}+x^{2}-x-1\right) \text { and } \pm\left(x^{3}-x^{2}-x+1\right) .
\end{gathered}
$$

## 4th year