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 byProblem 4 Followed byLast Question 1 • 2 • 3 • 4 • 5 All USAMO Problems and Solutions