Art of Problem Solving
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
During AMC 10A/12A testing, the AoPS Wiki is in read-only mode and no edits can be made.

1992 USAMO Problems/Problem 5: Difference between revisions

← Older editNewer edit →
Etude (talk | contribs)
181 edits
No edit summary
1=2 (talk | contribs)
4,129 edits
Line 34: Line 34:
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.
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.


== Resources ==
== See Also ==


{{USAMO box|year=1992|num-b=4|after=Last Question}}
{{USAMO box|year=1992|num-b=4|after=Last Question}}
{{MAA Notice}}
{{MAA Notice}}
[[Category:Olympiad Algebra Problems]]

Revision as of 06:53, 19 July 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}, \;dpts, 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 can be generalized:


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. 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\}$.

In fact, after our assumption, 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\}$. We want to construct our polynomial $R$ from this polynomial $Q$.

In fact, let $b_{i}=a_{i}$ for every $i\le k-1$, then 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,


$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)$


Hence, 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$ because $Q\left(z_{i}\right)=0,$ and $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.

See Also

1992 USAMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: Unable to save thumbnail to destination

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1992_USAMO_Problems/Problem_5&oldid=79524"