2002 USAMO Problems/Problem 3

Problem

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

Solutions

Solution 1

Lemma. For any set of ordered pairs of reals $\{ (x_i , y_i ) \}_{i=1}^{n}$ with $\displaystyle x_i \neq x_j$ for all $\displaystyle i \neq j$ , there exists a unique monic real polynomial $\displaystyle P(x)$ of degree $\displaystyle n$ such that $\displaystyle 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 $\displaystyle Q(x)$ of degree less than $\displaystyle n$ such that $\displaystyle Q(x_i) = y_i - x_i^n$ . Then it is necessary and sufficient that $\displaystyle P(x) = x^n + Q(x)$ .

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

Let $\displaystyle F(x)$ be the monic polynomial of degree $\displaystyle 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 $\displaystyle i$ , $\displaystyle y_i > \max (0, 2F(x_i))$ , but for even $\displaystyle i$ , $\displaystyle y_i < \min (0, 2F(x_i))$ . Let $\displaystyle P(x)$ be the unique monic polynomial such that $\displaystyle P(x_i) = y_i$ . We shall prove that $\displaystyle P(x)$ and $\displaystyle Q(x) = 2F(x) - P(x)$ satisfy the problem's conditions.

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

Solution 2

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

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

and let

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

and

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

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

We note that for the values $1, 3, \ldots, 2n-1$ of $\displaystyle x$ , $\displaystyle 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 $\displaystyle c$ such that for all $x \in [1, 2n-1]$ , $\displaystyle |x^n| < c$ and $\displaystyle |F(n) - x^n | < c$ . Let $\displaystyle k$ be greater than $\displaystyle c$ . Then both $\displaystyle P(x)$ and $\displaystyle Q(x)$ alternate in sign for $x = 1, 3, \ldots, 2n-1$ . It follows that each has at least $\displaystyle n-1$ real roots. But since a polynomial with real coefficients can only have an even number of complex roots, this means that both $\displaystyle P$ and $\displaystyle Q$ must have $\displaystyle n$ roots. Q.E.D.