Difference between revisions of "2002 USAMO Problems/Problem 3"
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Prove that any monic | + | Prove that any monic polynomial (a polynomial with leading coefficient 1) of degree <math>n </math> with real coefficients is the average of two monic polynomials of degree <math>n </math> with <math>n </math> real roots. |
== Solutions == | == Solutions == | ||
Line 7: | Line 7: | ||
=== Solution 1 === | === Solution 1 === | ||
− | '''Lemma.''' For any set of ordered pairs of reals <math> \{ (x_i , y_i ) \}_{i=1}^{n} </math> with <math> | + | '''Lemma.''' For any set of ordered pairs of reals <math> \{ (x_i , y_i ) \}_{i=1}^{n} </math> with <math>x_i \neq x_j </math> for all <math>i \neq j </math>, there exists a unique monic real polynomial <math>P(x) </math> of degree <math>n </math> such that <math>P(x_i) = y_i </math> for all integers <math> i \in [1,n] </math>. |
− | ''Proof 1.'' By the [[Lagrange Interpolation Formula]], there exists a unique real polynomial <math> | + | ''Proof 1.'' By the [[Lagrange Interpolation Formula]], there exists a unique real polynomial <math>Q(x) </math> of degree less than <math>n </math> such that <math>Q(x_i) = y_i - x_i^n </math>. Then it is necessary and sufficient that <math>P(x) = x^n + Q(x) </math>. |
− | ''Proof 2.'' Again by the Lagrange Interpolation Formula, there exists a unique real polynomial <math> | + | ''Proof 2.'' Again by the Lagrange Interpolation Formula, there exists a unique real polynomial <math>Q(x) </math> of degree less than <math>n </math> such that <math>Q(x_i) = y_i </math>. Then it is necessary and sufficient that <math> P(x) = Q(x) + \prod_{i=1}^{n}(x-x_i) </math>. |
− | Let <math> | + | Let <math>F(x) </math> be the monic polynomial of degree <math>n </math> given in the problem. Let <math> x_1, \ldots, x_n </math> be a sequence of strictly increasing reals, and choose <math> y_1, \ldots, y_n </math> such that for odd <math>i </math>, <math>y_i > \max (0, 2F(x_i))</math>, but for even <math>i </math>, <math>y_i < \min (0, 2F(x_i))</math>. Let <math>P(x) </math> be the unique monic polynomial such that <math>P(x_i) = y_i </math>. We shall prove that <math>P(x) </math> and <math>Q(x) = 2F(x) - P(x) </math> satisfy the problem's conditions. |
− | Note that for <math> | + | Note that for <math>i < n </math>, <math>P(x_i) </math> and <math>P(x_{i+1}) </math> have different signs, so <math>P(x) </math> has a real root between <math>x_i </math> and <math>x_{i+1} </math>. It follows that <math>P(x) </math> has at least <math>n-1 </math> real roots. But a polynomial with real coefficients must have an even number of non-real roots, so <math>P(x) </math> must have <math>n </math> real roots. Similarly, <math>Q(x) </math> must have <math>n </math> real roots. Q.E.D. |
=== Solution 2 === | === Solution 2 === | ||
− | Let <math> | + | Let <math>F(x) </math> be our polynomial. If <math>n = 1 </math>, then we may let <math>F = x + a </math>, which is the average of the polynomials <math>x </math> and <math>x + 2a </math>, each of which has a real root. Otherwise, let |
<center> | <center> | ||
<math> | <math> | ||
Line 28: | Line 28: | ||
<center> | <center> | ||
<math> | <math> | ||
− | + | P(x) = x^n - kG(x) | |
</math> | </math> | ||
</center> | </center> | ||
Line 34: | Line 34: | ||
<center> | <center> | ||
<math> | <math> | ||
− | + | Q(x) = 2F(x) - x^n + kG(x) | |
</math>. | </math>. | ||
</center> | </center> | ||
− | We will prove that for sufficiently large <math> | + | We will prove that for sufficiently large <math>k </math>, <math>P(x) </math> and <math>Q(x) </math> satisfy the problem's conditions. |
− | We note that for the values <math> 1, 3, \ldots, 2n-1 </math> of <math> | + | We note that for the values <math> 1, 3, \ldots, 2n-1 </math> of <math>x </math>, <math>G(x) </math> 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 <math>c </math> such that for all <math> x \in [1, 2n-1] </math>, <math>|x^n| < c </math> and <math>|F(n) - x^n | < c </math>. Let <math>k </math> be greater than <math>c </math>. Then both <math>P(x) </math> and <math>Q(x) </math> alternate in sign for <math> x = 1, 3, \ldots, 2n-1 </math>. It follows that each has at least <math>n-1 </math> real roots. But since a polynomial with real coefficients can only have an even number of complex roots, this means that both <math>P </math> and <math>Q </math> must have <math>n </math> roots. Q.E.D. |
{{alternate solutions}} | {{alternate solutions}} | ||
− | == | + | == See also == |
− | + | {{USAMO newbox|year=2002|num-b=2|num-a=4}} | |
− | |||
[[Category:Olympiad Algebra Problems]] | [[Category:Olympiad Algebra Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 13:38, 4 July 2013
Problem
Prove that any monic polynomial (a polynomial with leading coefficient 1) of degree with real coefficients is the average of two monic polynomials of degree
with
real roots.
Solutions
Solution 1
Lemma. For any set of ordered pairs of reals with
for all
, there exists a unique monic real polynomial
of degree
such that
for all integers
.
Proof 1. By the Lagrange Interpolation Formula, there exists a unique real polynomial of degree less than
such that
. Then it is necessary and sufficient that
.
Proof 2. Again by the Lagrange Interpolation Formula, there exists a unique real polynomial of degree less than
such that
. Then it is necessary and sufficient that
.
Let be the monic polynomial of degree
given in the problem. Let
be a sequence of strictly increasing reals, and choose
such that for odd
,
, but for even
,
. Let
be the unique monic polynomial such that
. We shall prove that
and
satisfy the problem's conditions.
Note that for ,
and
have different signs, so
has a real root between
and
. It follows that
has at least
real roots. But a polynomial with real coefficients must have an even number of non-real roots, so
must have
real roots. Similarly,
must have
real roots. Q.E.D.
Solution 2
Let be our polynomial. If
, then we may let
, which is the average of the polynomials
and
, each of which has a real root. Otherwise, let
,
and let
and
.
We will prove that for sufficiently large ,
and
satisfy the problem's conditions.
We note that for the values of
,
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
such that for all
,
and
. Let
be greater than
. Then both
and
alternate in sign for
. It follows that each has at least
real roots. But since a polynomial with real coefficients can only have an even number of complex roots, this means that both
and
must have
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.