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

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 polymomial (a polynomial with leading coefficient 1) of degree <math> \displaystyle n </math> with real coefficients is the average of two monic polynomials of degree <math> \displaystyle n </math> with <math> \displaystyle n </math> real roots.
+
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> \displaystyle x_i \neq x_j </math> for all <math> \displaystyle i \neq j </math>, there exists a unique monic real polynomial  <math> \displaystyle P(x) </math> of degree <math> \displaystyle n </math> such that <math> \displaystyle P(x_i) = y_i </math> for all integers <math> i \in [1,n] </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> \displaystyle Q(x) </math> of degree less than <math> \displaystyle n </math> such that <math> \displaystyle Q(x_i) = y_i - x_i^n </math>.  Then it is necessary and sufficient that <math> \displaystyle P(x) = x^n + Q(x) </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> \displaystyle Q(x) </math> of degree less than <math> \displaystyle n </math> such that <math> \displaystyle 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>.
+
''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> \displaystyle F(x) </math> be the monic polynomial of degree <math> \displaystyle 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> \displaystyle i </math>, <math> \displaystyle y_i > \max (0, 2F(x_i))</math>, but for even <math> \displaystyle i </math>, <math> \displaystyle y_i < \min (0, 2F(x_i))</math>.  Let <math> \displaystyle P(x) </math> be the unique monic polynomial such that <math> \displaystyle P(x_i) = y_i </math>.  We shall prove that <math> \displaystyle P(x) </math> and <math> \displaystyle Q(x) = 2F(x) - P(x) </math> satisfy the problem's conditions.
+
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> \displaystyle i < n </math>, <math> \displaystyle P(x_i) </math> and <math> \displaystyle P(x_{i+1}) </math> have different signs, so <math> \displaystyle P(x) </math> has a real root between <math> \displaystyle x_i </math> and <math> \displaystyle x_{i+1} </math>.  It follows that <math> \displaystyle P(x) </math> has at least <math> \displaystyle n-1 </math> real roots.  But a polynomial with real coefficients must have an even number of non-real roots, so <math> \displaystyle P(x) </math> must have <math> \displaystyle n </math> real roots.  Similarly, <math> \displaystyle Q(x) </math> must have <math> \displaystyle n </math> real roots.  Q.E.D.
+
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> \displaystyle F(x) </math> be our polynomial.  If <math> \displaystyle n = 1 </math>, then we may let <math> \displaystyle F = x + a </math>, which is the average of the polynomials <math> \displaystyle x </math> and <math> \displaystyle x + 2a </math>, each of which has a real root.  Otherwise, let
+
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>
−
\displaystyle P(x) = x^n - kG(x)
+
P(x) = x^n - kG(x)
 
</math>
 
</math>
 
</center>
 
</center>
Line 34: Line 34:
 
<center>
 
<center>
 
<math>
 
<math>
−
\displaystyle Q(x) = 2F(x) - x^n + kG(x)
+
Q(x) = 2F(x) - x^n + kG(x)
 
</math>.
 
</math>.
 
</center>
 
</center>
  
−
We will prove that for sufficiently large <math> \displaystyle k </math>, <math> \displaystyle P(x) </math> and <math> \displaystyle Q(x) </math> satisfy the problem's conditions.
+
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> \displaystyle x </math>, <math> \displaystyle 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> \displaystyle c </math> such that for all <math> x \in [1, 2n-1] </math>, <math> \displaystyle |x^n| < c </math> and <math> \displaystyle |F(n) - x^n | < c </math>.  Let <math> \displaystyle k </math> be greater than <math> \displaystyle c </math>.  Then both <math> \displaystyle P(x) </math> and <math> \displaystyle Q(x) </math> alternate in sign for <math> x = 1, 3, \ldots, 2n-1 </math>.  It follows that each has at least <math> \displaystyle 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> \displaystyle P </math> and <math> \displaystyle Q </math> must have <math> \displaystyle n </math> roots.  Q.E.D.
+
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}}
  
−
== Resources ==
+
== See also ==
−
* [[2002 USAMO Problems]]
+
{{USAMO newbox|year=2002|num-b=2|num-a=4}}
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=337849#p337849 Discussion on AoPS/MathLinks]
 
  
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 +
{{MAA Notice}}

Latest revision as of 12:38, 4 July 2013

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"