1992 USAMO Problems/Problem 5

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.

Resources

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

Page

Toolbox

Search

1992 USAMO Problems/Problem 5

Problem 5

Solution

Resources