AoPSWiki
Visit the AoPS Book Store.

2002 USAMO Problems/Problem 3

From AoPSWiki

Contents

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 \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.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2002_USAMO_Problems/Problem_3"
Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us