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}. \]
Problem
Source: USAMO 1992
Tags: algebra, polynomial, induction, complex numbers, algebra solved
07.07.2006 19:48
I was asked for a solution of this, so let me post one. Since the zeros $z_{1}$, $z_{2}$, ..., $z_{1992}$ of the polynomial P(z) are distinct, the polynomial P(z) divides the polynomial $Q\left(z\right) = \left( ... \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}...-a_{1991}\right)^{2}-a_{1992}$ if and only if $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;...;\;1992\right\}$. So it is enough to show that for any 1992 complex numbers $z_{1}$, $z_{2}$, ..., $z_{1992}$, there exist 1992 complex numbers $a_{1}$, $a_{2}$, ..., $a_{1992}$, such that the polynomial $Q\left(z\right) = \left( ... \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}...-a_{1991}\right)^{2}-a_{1992}$ satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;...;\;1992\right\}$. This can be generalized: Theorem. Let n be a positive integer, and $z_{1}$, $z_{2}$, ..., $z_{n}$ be n complex numbers. Then, there exist n complex numbers $a_{1}$, $a_{2}$, ..., $a_{n}$ such that the polynomial $Q\left(z\right) = \left( ... \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}...-a_{n-1}\right)^{2}-a_{n}$ satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;...;\;n\right\}$. Proof. We use induction over n. For n = 1, the theorem 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$. The interesting part is the induction step: Let k be a positive integer. Assume that for n = k, the theorem is proven, i. e. for any k complex numbers $z_{1}$, $z_{2}$, ..., $z_{k}$, there exist k complex numbers $a_{1}$, $a_{2}$, ..., $a_{k}$ such that the polynomial $Q\left(z\right)=\left(...\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}...-a_{k-1}\right)^{2}-a_{k}$ satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;...;\;k\right\}$. We have to prove the theorem for n = k + 1, so we have to prove that for any k + 1 complex numbers $z_{1}$, $z_{2}$, ..., $z_{k+1}$, there exist k + 1 complex numbers $b_{1}$, $b_{2}$, ..., $b_{k+1}$ such that the polynomial $R\left(z\right)=\left(...\left( \left(z-b_{1}\right)^{2}-b_{2}\right)^{2}...-b_{k}\right)^{2}-b_{k+1}$ satisfies $R\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;...;\;k+1\right\}$. In fact, after our assumption, there exist k complex numbers $a_{1}$, $a_{2}$, ..., $a_{k}$ such that the polynomial $Q\left(z\right)=\left(...\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}...-a_{k-1}\right)^{2}-a_{k}$ satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;...;\;k\right\}$. We want to construct our polynomial R from this polynomial Q. In fact, let $b_{i}=a_{i}$ for every $i\leq k-1$, then let $b_{k}=a_{k}+\frac12Q\left(z_{k+1}\right)$ and $b_{k+1}=\frac14\left(Q\left(z_{k+1}\right)\right)^{2}$. Then, $R\left(z\right)=\left(...\left( \left(\left(z-b_{1}\right)^{2}-b_{2}\right)^{2}...-b_{k-1}\right)^{2}-b_{k}\right)^{2}-b_{k+1}$ $=\left(...\left( \left(\left(z-a_{1}\right)^{2}-a_{2}\right)^{2}...-a_{k-1}\right)^{2}-\left(a_{k}+\frac12Q\left(z_{k+1}\right)\right) \right)^{2}-\frac14\left(Q\left(z_{k+1}\right)\right)^{2}$ $=\left(\left(...\left( \left(\left(z-a_{1}\right)^{2}-a_{2}\right)^{2}...-a_{k-1}\right)^{2}-a_{k}\right)-\frac12Q\left(z_{k+1}\right)\right)^{2}-\frac14\left(Q\left(z_{k+1}\right)\right)^{2}$ $=\left(Q\left(z\right)-\frac12Q\left(z_{k+1}\right)\right)^{2}-\frac14\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;\;...;\;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;\;...;\;k+1\right\}$, and this proves the theorem for n = k + 1. Hence, the induction step is complete, and the Theorem is proven. Darij
18.08.2007 07:46
Here's a different approach: Lemma: Consider the equation $ p((f-a)^{2}) = 0$, where $ p$ is a polynomial, $ a$ is a constant, and $ f$ is a variable. Let's say we can choose the polynomial $ p$ to have any set of $ k-1$ distinct roots for an integer $ k\ge 2$ and that we can choose $ a$ to be any complex number. Then for any set of $ k$ distinct complex numbers $ f_{1}, ..., f_{k}$, we can choose a value of $ a$ and a set of $ k-1$ distinct roots for $ p$ such that $ p((f-a)^{2}) = 0$, when viewed as a polynomial in $ f$, has $ f_{1},...,f_{k}$ as roots. Choose $ a =\frac{f_{1}+f_{k}}{2}$ and let $ p$ have roots $ (f_{1}-a)^{2}, ... , (f_{k-1}-a)^{2}$. Then $ p((f-a)^{2})$ is clearly $ 0$ for $ f = f_{1},...,f_{k-1}$. For $ f_{k}$, we have $ p((f_{k}-a)^{2}) = p((-(f_{1}-a))^{2}) = p((f_{1}-a)^{2}) = 0$, so $ f$ has all of the possible values $ f_{1},...,f_{k}$.
We now use induction to show that $ (...((z-a_{1})^{2}-a_{2})^{2}...-a_{n-1})^{2}-a_{n}= 0$ can have any given $ n$ distinct roots for $ z$ if we appropriately choose $ a_{1},...,a_{n}$. For $ n = 1$ we choose $ a_{1}$ to be the one distinct root since our equation is $ z-a_{1}= 0$. Then let's assume it's true for $ n-1$. Consider $ (...((z-a_{1})^{2}-a_{2})^{2}...-a_{n-1})^{2}-a_{n}= 0$. By the induction hypothesis we can get any $ n-1$ distinct possible values for $ (z-a_{1})^{2}$ with an appropriate choice of $ a_{2},...,a_{n}$. By the lemma, we can thus choose $ a_{1}$ so that we have the desired $ n$ possible values of $ z$, and the induction is complete. If we replace $ n$ with $ 1992$, we see that we can achieve any desired set of $ 1992$ roots in $ z$, and if we choose those to be the roots of $ P(z)$, it follows that $ P(z)$ must divide this polynomial. QED
23.03.2011 04:41
What was Darij's motivation behind letting: $b_k=a_k+1/2Q(a_k+1)$
05.10.2022 02:02
Let $z_1, z_2, \cdots$ be the roots of $P$. We prove the case for general $n$ via induction. The base case is trivial; take $a_1 = z_1$. Now suppose that there exist constants $b_1, b_2, \cdots, b_n$ such that setting $a_i = b_i$ for each $i$ creates a valid polynomial. Then, this means that$$(\dotsb ((z_i - b_1)^2 - b_2)^2 \dots - b_{n-1})^2 = k$$for some constant $k$ for each $1 \leq i \leq n$. Furthermore, let the value of this expression for $z_{n+1}$ be $r$. Then, we need to pick $b_n, b_{n+1}$ such that$$(k-b_n)^2 = (r - b_n)^2 = b_{n+1}.$$As the roots of the quadratic$$(x-a)^2 = b$$can be any pair of complex numbers by choosing suitable $a$ and $b$, such $b_n$ and $b_{n+1}$ clearly exist, as required.
06.11.2024 12:04
We prove the general result (the original problem is essential $n=1992$): Let $\, P_n(z) \,$ be a polynomial with complex coefficients which is of degree $\, n \,$ and has distinct zeros. Prove that there exist complex numbers $\, a_1, a_2, \ldots, a_{n} \,$ such that $\, P(z) \,$ divides the polynomial \[ \left( \cdots \left( (z-a_1)^2 - a_2 \right)^2 \cdots - a_{n-1} \right)^2 - a_{n}. \] We proceed by induction on $n$. Base case is trivial. Assume that the result holds for some $n$. We will prove that it holds for $n+1$ too. Let $P_{n+1}(z)$ have roots $r_1, \cdots, r_{n+1}$. There exists complex numbers $a_1, \cdots, a_n$ such that: $Q_n(z)=\left( \cdots \left( (z-a_1)^2 - a_2 \right)^2 \cdots - a_{n-1} \right)^2 - a_{n}$ with $Q(r_i)=0$ for all $1 \le i \le n$. Let $Q_n(r_{n+1}) = c$. Now, consider: $$Q_{n+1}(z) = \left( Q_n(z) - \frac{c}{2} \right)^2 - \frac{c^2}{4}.$$Notice that $Q_{n+1}(r_k) = 0$ for all $1 \le k \le n+1$ which implies $P_{n+1} | Q_{n+1}$ and we are done.