https://artofproblemsolving.com/wiki/index.php?title=1992_USAMO_Problems/Problem_5&feed=atom&action=history
1992 USAMO Problems/Problem 5 - Revision history
2024-03-28T23:11:50Z
Revision history for this page on the wiki
MediaWiki 1.31.1
https://artofproblemsolving.com/wiki/index.php?title=1992_USAMO_Problems/Problem_5&diff=80178&oldid=prev
Mathgeek2006: /* Solution */
2016-09-02T06:21:27Z
<p><span dir="auto"><span class="autocomment">Solution</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 06:21, 2 September 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l5" >Line 5:</td>
<td colspan="2" class="diff-lineno">Line 5:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Solution ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Solution ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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 <<del class="diffchange diffchange-inline">math</del>>Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}</<del class="diffchange diffchange-inline">math</del>> 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}, \<del class="diffchange diffchange-inline">;dpts</del>, z_{1992}</math>, there exist <math>1992</math> complex numbers <math>a_{1}, a_{2}, \ldots, a_{1992}</math>, such that the polynomial <<del class="diffchange diffchange-inline">math</del>>Q\left(z\right) = \left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}</<del class="diffchange diffchange-inline">math</del>> satisfies <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;1992\right\}</math>. This <del class="diffchange diffchange-inline">can be generalized:</del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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  </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><<ins class="diffchange diffchange-inline">cmath</ins>>Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}</<ins class="diffchange diffchange-inline">cmath</ins>></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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}, \<ins class="diffchange diffchange-inline">dots</ins>, z_{1992}</math>, there exist <math>1992</math> complex numbers <math>a_{1}, a_{2}, \ldots, a_{1992}</math>, such that the polynomial  </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><<ins class="diffchange diffchange-inline">cmath</ins>>Q\left(z\right) = \left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{1991}\right)^{2}-a_{1992}</<ins class="diffchange diffchange-inline">cmath</ins>></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>satisfies <math>Q\left(z_{i}\right)=0</math> for every <math>i\in\left\{1;\;2;\;\ldots;\;1992\right\}</math>. This <ins class="diffchange diffchange-inline">is a special case of the following lemma.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br/></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br/></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><b>Lemma</b><del class="diffchange diffchange-inline">) </del>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>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><b>Lemma<ins class="diffchange diffchange-inline">:</ins></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>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br/></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br/></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Proof: We use induction over <math>n</math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><b></ins>Proof:<ins class="diffchange diffchange-inline"></b> </ins>We use induction over <math>n</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br/></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br/></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Let <math>k</math> be a positive integer. Assume that for <math>n = k</math>, the lemma is true. <del class="diffchange diffchange-inline">For </del>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>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Let <math>k</math> be a positive integer. Assume that for <math>n = k</math>, the lemma is true. <ins class="diffchange diffchange-inline">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 </ins>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\}<ins class="diffchange diffchange-inline"></math>. We will construct this polynomial <math>R</math> from the polynomial <math>Q</ins></math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">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>.</del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Let </ins><math>b_{i}=a_{i}</math> for every <math>i\le k-1</math>, <ins class="diffchange diffchange-inline">and </ins>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,</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">In fact, let </del><math>b_{i}=a_{i}</math> for every <math>i\le k-1</math>, <del class="diffchange diffchange-inline">then </del>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,</div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br/></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><br/></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><<del class="diffchange diffchange-inline">math</del>> 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} <del class="diffchange diffchange-inline"></math></del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><<ins class="diffchange diffchange-inline">cmath</ins>></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\begin{align*}</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline"><math> </del>=\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}-<del class="diffchange diffchange-inline"></math> <math></del>\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2} <del class="diffchange diffchange-inline"></math></del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>R\left(z\right)<ins class="diffchange diffchange-inline">&</ins>=\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}<ins class="diffchange diffchange-inline">\\</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">& </ins>=\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} <ins class="diffchange diffchange-inline">\\</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline"><math> </del>=\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}-<del class="diffchange diffchange-inline"></math> <math></del>\frac{1}4\left(Q\left(z_{k+1}\right)\right)^{2} </<del class="diffchange diffchange-inline">math</del>></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">& </ins>=\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}<ins class="diffchange diffchange-inline">\\</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">&=\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).</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\end{align*}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></<ins class="diffchange diffchange-inline">cmath</ins>></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"><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></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Then as <math>Q\left(z_{i}\right)=0</math> for <math>i\in\left\{1;\;2;\;\ldots;\;k\right\}</math>, we have </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><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></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">for all <math>i\in\left\{1;\;2;\;\ldots;\;k\right\}</math>. Also, </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><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></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">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.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">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 </del>the lemma <del class="diffchange diffchange-inline">for </del><math>n = <del class="diffchange diffchange-inline">k + 1</del></math><del class="diffchange diffchange-inline">. Hence</del>, <del class="diffchange diffchange-inline">the induction step is complete, and the lemma is proven</del>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">As the problem is a special case of </ins>the lemma <ins class="diffchange diffchange-inline">(</ins><math>n=<ins class="diffchange diffchange-inline">1992</ins></math><ins class="diffchange diffchange-inline">)</ins>, <ins class="diffchange diffchange-inline">we are done</ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See Also ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== See Also ==</div></td></tr>
</table>
Mathgeek2006
https://artofproblemsolving.com/wiki/index.php?title=1992_USAMO_Problems/Problem_5&diff=79524&oldid=prev
1=2: /* Resources */
2016-07-19T11:53:46Z
<p><span dir="auto"><span class="autocomment">Resources</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 11:53, 19 July 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l34" >Line 34:</td>
<td colspan="2" class="diff-lineno">Line 34:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>== <del class="diffchange diffchange-inline">Resources </del>==</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>== <ins class="diffchange diffchange-inline">See Also </ins>==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{USAMO box|year=1992|num-b=4|after=Last Question}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{USAMO box|year=1992|num-b=4|after=Last Question}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{MAA Notice}}</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:Olympiad Algebra Problems]]</ins></div></td></tr>
</table>
1=2
https://artofproblemsolving.com/wiki/index.php?title=1992_USAMO_Problems/Problem_5&diff=53621&oldid=prev
Etude at 00:57, 4 July 2013
2013-07-04T00:57:52Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 00:57, 4 July 2013</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l37" >Line 37:</td>
<td colspan="2" class="diff-lineno">Line 37:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{USAMO box|year=1992|num-b=4|after=Last Question}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{USAMO box|year=1992|num-b=4|after=Last Question}}</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">{{MAA Notice}}</ins></div></td></tr>
</table>
Etude
https://artofproblemsolving.com/wiki/index.php?title=1992_USAMO_Problems/Problem_5&diff=34381&oldid=prev
Moplam: Created page with '==Problem 5== Let <math>\, P(z) \,</math> be a polynomial with complex coefficients which is of degree <math>\, 1992 \,</math> and has distinct zeros. Prove that there exist com…'
2010-04-23T03:38:21Z
<p>Created page with '==Problem 5== Let <math>\, P(z) \,</math> be a polynomial with complex coefficients which is of degree <math>\, 1992 \,</math> and has distinct zeros. Prove that there exist com…'</p>
<p><b>New page</b></p><div>==Problem 5==<br />
<br />
Let <math>\, P(z) \,</math> be a polynomial with complex coefficients which is of degree <math>\, 1992 \,</math> and has distinct zeros. Prove that there exist complex numbers <math>\, a_1, a_2, \ldots, a_{1992} \,</math> such that <math>\, P(z) \,</math> divides the polynomial <math>\left( \cdots \left( (z-a_1)^2 - a_2 \right)^2 \cdots - a_{1991} \right)^2 - a_{1992}</math>.<br />
<br />
== Solution ==<br />
<br />
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:<br />
<br />
<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>.<br />
<br />
<br/><br />
Proof: We use induction over <math>n</math>.<br />
<br />
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 />
<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>.<br />
<br />
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>.<br />
<br />
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 />
<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><br />
<br />
<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><br />
<br />
<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><br />
<br />
<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><br />
<br />
<br />
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.<br />
<br />
== Resources ==<br />
<br />
{{USAMO box|year=1992|num-b=4|after=Last Question}}</div>
Moplam