Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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.


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

See also

2002 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_USAMO_Problems/Problem_3&oldid=54768"