2002 USAMO Problems/Problem 3

Problem

Prove that any monic polynomial (a polynomial with leading coefficient 1) of degree $n$ with real coefficients is the average of two monic polynomials of degree $n$ with $n$ real roots.

Solutions

Solution 1

Lemma. For any set of ordered pairs of reals $\{ (x_i , y_i ) \}_{i=1}^{n}$ with $x_i \neq x_j$ for all $i \neq j$ , there exists a unique monic real polynomial $P(x)$ of degree $n$ such that $P(x_i) = y_i$ for all integers $i \in [1,n]$ .

Proof 1. By the Lagrange Interpolation Formula, there exists a unique real polynomial $Q(x)$ of degree less than $n$ such that $Q(x_i) = y_i - x_i^n$ . Then it is necessary and sufficient that $P(x) = x^n + Q(x)$ .

Proof 2. Again by the Lagrange Interpolation Formula, there exists a unique real polynomial $Q(x)$ of degree less than $n$ such that $Q(x_i) = y_i$ . Then it is necessary and sufficient that $P(x) = Q(x) + \prod_{i=1}^{n}(x-x_i)$ .

Let $F(x)$ be the monic polynomial of degree $n$ given in the problem. Let $x_1, \ldots, x_n$ be a sequence of strictly increasing reals, and choose $y_1, \ldots, y_n$ such that for odd $i$ , $y_i > \max (0, 2F(x_i))$ , but for even $i$ , $y_i < \min (0, 2F(x_i))$ . Let $P(x)$ be the unique monic polynomial such that $P(x_i) = y_i$ . We shall prove that $P(x)$ and $Q(x) = 2F(x) - P(x)$ satisfy the problem's conditions.

Note that for $i < n$ , $P(x_i)$ and $P(x_{i+1})$ have different signs, so $P(x)$ has a real root between $x_i$ and $x_{i+1}$ . It follows that $P(x)$ has at least $n-1$ real roots. But a polynomial with real coefficients must have an even number of non-real roots, so $P(x)$ must have $n$ real roots. Similarly, $Q(x)$ must have $n$ real roots. Q.E.D.

Solution 2

Let $F(x)$ be our polynomial. If $n = 1$ , then we may let $F = x + a$ , which is the average of the polynomials $x$ and $x + 2a$ , each of which has a real root. Otherwise, let

$G(x) = \prod_{i=1}^{n-1}(x-2i)$ ,

and let

$P(x) = x^n - kG(x)$

and

$Q(x) = 2F(x) - x^n + kG(x)$ .

We will prove that for sufficiently large $k$ , $P(x)$ and $Q(x)$ satisfy the problem's conditions.

We note that for the values $1, 3, \ldots, 2n-1$ of $x$ , $G(x)$ alternates in sign, and always has magnitude at least 1 (since it is the product of several factors of magnitude at least one. On the other hand, there exists some $c$ such that for all $x \in [1, 2n-1]$ , $|x^n| < c$ and $|F(n) - x^n | < c$ . Let $k$ be greater than $c$ . Then both $P(x)$ and $Q(x)$ alternate in sign for $x = 1, 3, \ldots, 2n-1$ . It follows that each has at least $n-1$ real roots. But since a polynomial with real coefficients can only have an even number of complex roots, this means that both $P$ and $Q$ must have $n$ roots. Q.E.D.