Difference between revisions of "2002 USAMO Problems/Problem 3"

Revision as of 22:12, 23 March 2012

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.

Resources

@@ Line 7: / Line 7: @@
 === 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 ===
-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>
 <math>
@@ Line 28: / Line 28: @@
 <center>
 <math>
-\displaystyle P(x) = x^n - kG(x)
+P(x) = x^n - kG(x)
 </math>
 </center>
@@ Line 34: / Line 34: @@
 <center>
 <math>
-\displaystyle Q(x) = 2F(x) - x^n + kG(x)
+Q(x) = 2F(x) - x^n + kG(x)
 </math>.
 </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.

Page

Toolbox

Search