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 "1992 USAMO Problems/Problem 5"

m (→‎Resources)
m (→‎Solution)
 
Line 5: Line 5:
 
== Solution ==
 
== Solution ==
  
−
Since the zeros <math>z_{1}, z_{2}, \ldots, z_{1992}</math> of the polynomial <math>P(z)</math> are distinct, the polynomial <math>P(z)</math> divides the polynomial <math>Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}</math> if and only if <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;1992\right\}</math>. So it is enough to show that for any <math>1992</math> complex numbers <math>z_{1}, z_{2}, \;dpts, z_{1992}</math>, there exist <math>1992</math> complex numbers <math>a_{1}, a_{2}, \ldots, a_{1992}</math>, such that the polynomial <math>Q\left(z\right) = \left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}</math> satisfies <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;1992\right\}</math>. This can be generalized:
+
Since the zeros <math>z_{1}, z_{2}, \ldots, z_{1992}</math> of the polynomial <math>P(z)</math> are distinct, the polynomial <math>P(z)</math> divides the polynomial  
 +
<cmath>Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}</cmath>
 +
if and only if <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;1992\right\}</math>. So it is enough to show that for any <math>1992</math> complex numbers <math>z_{1}, z_{2}, \dots, z_{1992}</math>, there exist <math>1992</math> complex numbers <math>a_{1}, a_{2}, \ldots, a_{1992}</math>, such that the polynomial  
 +
<cmath>Q\left(z\right) = \left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}</cmath>
 +
satisfies <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;1992\right\}</math>. This is a special case of the following lemma.
  
 
<br/>
 
<br/>
−
<b>Lemma</b>) Let <math>n</math> be a positive integer, and <math>z_{1}, z_{2}, \ldots, z_{n}</math> be <math>n</math> complex numbers. Then, there exist <math>n</math> complex numbers <math>a_{1}, a_{2},\ldots, a_{n}</math> such that the polynomial <math>Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{n-1}\right)^{2}-a_{n}</math> satisfies <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;n\right\}</math>.
+
<b>Lemma:</b> Let <math>n</math> be a positive integer, and <math>z_{1}, z_{2}, \ldots, z_{n}</math> be <math>n</math> complex numbers. Then, there exist <math>n</math> complex numbers <math>a_{1}, a_{2},\ldots, a_{n}</math> such that the polynomial <math>Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{n-1}\right)^{2}-a_{n}</math> satisfies <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;n\right\}</math>.
  
 
<br/>
 
<br/>
−
Proof: We use induction over <math>n</math>.
+
<b>Proof:</b> We use induction over <math>n</math>.
  
 
For <math>n = 1</math>, the lemma is trivial, since <math>Q\left(z\right)=z-a_{1}</math>, so we can take <math>a_{1}=z_{1}</math>, and then the polynomial <math>Q\left(z\right)=z-z_{1}</math> clearly satisfies <math>Q\left(z_{1}\right)=0</math>.
 
For <math>n = 1</math>, the lemma is trivial, since <math>Q\left(z\right)=z-a_{1}</math>, so we can take <math>a_{1}=z_{1}</math>, and then the polynomial <math>Q\left(z\right)=z-z_{1}</math> clearly satisfies <math>Q\left(z_{1}\right)=0</math>.
  
 
<br/>
 
<br/>
−
Let <math>k</math> be a positive integer. Assume that for <math>n = k</math>, the lemma is true. For any <math>k + 1</math> complex numbers <math>z_{1}, z_{2}, \ldots, z_{k+1}</math>, there exist <math>k + 1</math> complex numbers <math>b_{1}, b_{2}, \ldots, b_{k+1}</math> such that the polynomial <math>R\left(z\right)=\left(\ldots\left( \left(z-b_{1}\right)^{2}-b_{2}\right)^{2}\ldots-b_{k}\right)^{2}-b_{k+1}</math> satisfies <math>R\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;k+1\right\}</math>.
+
Let <math>k</math> be a positive integer. Assume that for <math>n = k</math>, the lemma is true. Therefore, there exist <math>k</math> complex numbers <math>a_{1}, a_{2}, \ldots, a_{k}</math> such that the polynomial <math>Q\left(z\right)=\left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-a_{k}</math> satisfies <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;k\right\}</math>. Then we wish to prove that for any <math>k + 1</math> complex numbers <math>z_{1}, z_{2}, \ldots, z_{k+1}</math>, there exist <math>k + 1</math> complex numbers <math>b_{1}, b_{2}, \ldots, b_{k+1}</math> such that the polynomial <math>R\left(z\right)=\left(\ldots\left( \left(z-b_{1}\right)^{2}-b_{2}\right)^{2}\ldots-b_{k}\right)^{2}-b_{k+1}</math> satisfies <math>R\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;k+1\right\}</math>. We will construct this polynomial <math>R</math> from the polynomial <math>Q</math>.
  
−
In fact, after our assumption, there exist <math>k</math> complex numbers <math>a_{1}, a_{2}, \ldots, a_{k}</math> such that the polynomial <math>Q\left(z\right)=\left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-a_{k}</math> satisfies <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;k\right\}</math>. We want to construct our polynomial <math>R</math> from this polynomial <math>Q</math>.
+
Let <math>b_{i}=a_{i}</math> for every <math>i\le k-1</math>, and let <math>b_{k}=a_{k}+\frac{1}{2}Q\left(z_{k+1}\right)</math> and <math>b_{k+1}=\frac{1}{4}\left(Q\left(z_{k+1}\right)\right)^{2}</math>. Then,
−
 
 
−
In fact, let <math>b_{i}=a_{i}</math> for every <math>i\le k-1</math>, then let <math>b_{k}=a_{k}+\frac{1}{2}Q\left(z_{k+1}\right)</math> and <math>b_{k+1}=\frac{1}{4}\left(Q\left(z_{k+1}\right)\right)^{2}</math>. Then,
 
  
 
<br/>
 
<br/>
−
<math> R\left(z\right)=\left(\ldots\left(\left(\left(z-b_{1}\right)^{2}-b_{2}\right)^{2}\ldots-b_{k-1}\right)^{2}-b_{k}\right)^{2}-b_{k+1} </math>
+
<cmath>
−
 
+
\begin{align*}
−
<math> =\left(\ldots\left(\left(\left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-\left(a_{k}+\frac{1}2Q\left(z_{k+1}\right)\right)\right)^{2}-</math> <math>\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2} </math>
+
R\left(z\right)&=\left(\ldots\left(\left(\left(z-b_{1}\right)^{2}-b_{2}\right)^{2}\ldots-b_{k-1}\right)^{2}-b_{k}\right)^{2}-b_{k+1}\\
−
 
+
& =\left(\ldots\left(\left(\left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-\left(a_{k}+\frac{1}2Q\left(z_{k+1}\right)\right)\right)^{2}-\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2} \\
−
<math> =\left(\left(\ldots\left(\left(\left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-a_{k}\right)-\frac{1}2Q\left(z_{k+1}\right)\right)^{2}-</math> <math>\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2} </math>
+
& =\left(\left(\ldots\left(\left(\left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-a_{k}\right)-\frac{1}2Q\left(z_{k+1}\right)\right)^{2}-\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2}\\
 +
&=\left(Q\left(z\right)-\frac{1}2Q\left(z_{k+1}\right)\right)^{2}-\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2}=Q\left(z\right)\left(Q\left(z\right)-Q\left(z_{k+1}\right)\right).
 +
\end{align*}
 +
</cmath>
  
−
<math> =\left(Q\left(z\right)-\frac{1}2Q\left(z_{k+1}\right)\right)^{2}-\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2}=Q\left(z\right)\left(Q\left(z\right)-Q\left(z_{k+1}\right)\right) </math>
 
  
 +
Then as <math>Q\left(z_{i}\right)=0</math> for <math>i\in\left\{1;\;2;\;\ldots;\;k\right\}</math>, we have
 +
<cmath>R\left(z_{i}\right)=Q\left(z_{i}\right)\left(Q\left(z_{i}\right)-Q\left(z_{k+1}\right)\right)=0</cmath>
 +
for all <math>i\in\left\{1;\;2;\;\ldots;\;k\right\}</math>. Also,
 +
<cmath>R\left(z_{k+1}\right)=Q\left(z_{k+1}\right)\left(Q\left(z_{k+1}\right)-Q\left(z_{k+1}\right)\right)=0.</cmath>
 +
Thus, <math>R\left(z_{i}\right)=0</math> holds for every <math>i\in\left\{1;\;2;\;\ldots;\;k+1\right\}</math>, and this proves the lemma for <math>n = k + 1</math>. Hence, the induction step is complete, and the lemma is proven.
  
−
Hence, for <math>i\in\left\{1;\;2;\;\ldots;\;k\right\}</math>, we have <math>R\left(z_{i}\right)=Q\left(z_{i}\right)\left(Q\left(z_{i}\right)-Q\left(z_{k+1}\right)\right)=0 </math> because <math>Q\left(z_{i}\right)=0,</math> and <math>R\left(z_{k+1}\right)=</math><math>Q\left(z_{k+1}\right)\left(Q\left(z_{k+1}\right)-Q\left(z_{k+1}\right)\right)=0</math>. Thus, <math>R\left(z_{i}\right)=0</math> holds for every <math>i\in\left\{1;\;2;\;\ldots;\;k+1\right\}</math>, and this proves the lemma for <math>n = k + 1</math>. Hence, the induction step is complete, and the lemma is proven.
+
As the problem is a special case of the lemma (<math>n=1992</math>), we are done.
  
 
== See Also ==
 
== See Also ==

Latest revision as of 02:21, 2 September 2016

Problem 5

Let $\, P(z) \,$ be a polynomial with complex coefficients which is of degree $\, 1992 \,$ and has distinct zeros. Prove that there exist complex numbers $\, a_1, a_2, \ldots, a_{1992} \,$ such that $\, P(z) \,$ divides the polynomial $\left( \cdots \left( (z-a_1)^2 - a_2 \right)^2 \cdots - a_{1991} \right)^2 - a_{1992}$.

Solution

Since the zeros $z_{1}, z_{2}, \ldots, z_{1992}$ of the polynomial $P(z)$ are distinct, the polynomial $P(z)$ divides the polynomial \[Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}\] if and only if $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;1992\right\}$. So it is enough to show that for any $1992$ complex numbers $z_{1}, z_{2}, \dots, z_{1992}$, there exist $1992$ complex numbers $a_{1}, a_{2}, \ldots, a_{1992}$, such that the polynomial \[Q\left(z\right) = \left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}\] satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;1992\right\}$. This is a special case of the following lemma.


Lemma: Let $n$ be a positive integer, and $z_{1}, z_{2}, \ldots, z_{n}$ be $n$ complex numbers. Then, there exist $n$ complex numbers $a_{1}, a_{2},\ldots, a_{n}$ such that the polynomial $Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{n-1}\right)^{2}-a_{n}$ satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;n\right\}$.


Proof: We use induction over $n$.

For $n = 1$, the lemma is trivial, since $Q\left(z\right)=z-a_{1}$, so we can take $a_{1}=z_{1}$, and then the polynomial $Q\left(z\right)=z-z_{1}$ clearly satisfies $Q\left(z_{1}\right)=0$.


Let $k$ be a positive integer. Assume that for $n = k$, the lemma is true. Therefore, there exist $k$ complex numbers $a_{1}, a_{2}, \ldots, a_{k}$ such that the polynomial $Q\left(z\right)=\left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-a_{k}$ satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;k\right\}$. Then we wish to prove that for any $k + 1$ complex numbers $z_{1}, z_{2}, \ldots, z_{k+1}$, there exist $k + 1$ complex numbers $b_{1}, b_{2}, \ldots, b_{k+1}$ such that the polynomial $R\left(z\right)=\left(\ldots\left( \left(z-b_{1}\right)^{2}-b_{2}\right)^{2}\ldots-b_{k}\right)^{2}-b_{k+1}$ satisfies $R\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;k+1\right\}$. We will construct this polynomial $R$ from the polynomial $Q$.

Let $b_{i}=a_{i}$ for every $i\le k-1$, and let $b_{k}=a_{k}+\frac{1}{2}Q\left(z_{k+1}\right)$ and $b_{k+1}=\frac{1}{4}\left(Q\left(z_{k+1}\right)\right)^{2}$. Then,


\begin{align*} R\left(z\right)&=\left(\ldots\left(\left(\left(z-b_{1}\right)^{2}-b_{2}\right)^{2}\ldots-b_{k-1}\right)^{2}-b_{k}\right)^{2}-b_{k+1}\\ & =\left(\ldots\left(\left(\left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-\left(a_{k}+\frac{1}2Q\left(z_{k+1}\right)\right)\right)^{2}-\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2} \\ & =\left(\left(\ldots\left(\left(\left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-a_{k}\right)-\frac{1}2Q\left(z_{k+1}\right)\right)^{2}-\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2}\\ &=\left(Q\left(z\right)-\frac{1}2Q\left(z_{k+1}\right)\right)^{2}-\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2}=Q\left(z\right)\left(Q\left(z\right)-Q\left(z_{k+1}\right)\right). \end{align*}


Then as $Q\left(z_{i}\right)=0$ for $i\in\left\{1;\;2;\;\ldots;\;k\right\}$, we have \[R\left(z_{i}\right)=Q\left(z_{i}\right)\left(Q\left(z_{i}\right)-Q\left(z_{k+1}\right)\right)=0\] for all $i\in\left\{1;\;2;\;\ldots;\;k\right\}$. Also, \[R\left(z_{k+1}\right)=Q\left(z_{k+1}\right)\left(Q\left(z_{k+1}\right)-Q\left(z_{k+1}\right)\right)=0.\] Thus, $R\left(z_{i}\right)=0$ holds for every $i\in\left\{1;\;2;\;\ldots;\;k+1\right\}$, and this proves the lemma for $n = k + 1$. Hence, the induction step is complete, and the lemma is proven.

As the problem is a special case of the lemma ($n=1992$), we are done.

See Also

1992 USAMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Last Question
1 • 2 • 3 • 4 • 5
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=1992_USAMO_Problems/Problem_5&oldid=80178"