Let P(z) be a polynomial with complex coefficients which is of degree 1992 and has distinct zeros. Prove that there exist complex numbers a1,a2,…,a1992 such that P(z) divides the polynomial (⋯((z−a1)2−a2)2⋯−a1991)2−a1992.
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 z1, z2, ..., z1992 of the polynomial P(z) are distinct, the polynomial P(z) divides the polynomial Q(z)=(...((z−a1)2−a2)2...−a1991)2−a1992 if and only if Q(zi)=0 for every i∈{1;2;...;1992}. So it is enough to show that for any 1992 complex numbers z1, z2, ..., z1992, there exist 1992 complex numbers a1, a2, ..., a1992, such that the polynomial Q(z)=(...((z−a1)2−a2)2...−a1991)2−a1992 satisfies Q(zi)=0 for every i∈{1;2;...;1992}. This can be generalized: Theorem. Let n be a positive integer, and z1, z2, ..., zn be n complex numbers. Then, there exist n complex numbers a1, a2, ..., an such that the polynomial Q(z)=(...((z−a1)2−a2)2...−an−1)2−an satisfies Q(zi)=0 for every i∈{1;2;...;n}. Proof. We use induction over n. For n = 1, the theorem is trivial, since Q(z)=z−a1, so we can take a1=z1, and then the polynomial Q(z)=z−z1 clearly satisfies Q(z1)=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 z1, z2, ..., zk, there exist k complex numbers a1, a2, ..., ak such that the polynomial Q(z)=(...((z−a1)2−a2)2...−ak−1)2−ak satisfies Q(zi)=0 for every i∈{1;2;...;k}. We have to prove the theorem for n = k + 1, so we have to prove that for any k + 1 complex numbers z1, z2, ..., zk+1, there exist k + 1 complex numbers b1, b2, ..., bk+1 such that the polynomial R(z)=(...((z−b1)2−b2)2...−bk)2−bk+1 satisfies R(zi)=0 for every i∈{1;2;...;k+1}. In fact, after our assumption, there exist k complex numbers a1, a2, ..., ak such that the polynomial Q(z)=(...((z−a1)2−a2)2...−ak−1)2−ak satisfies Q(zi)=0 for every i∈{1;2;...;k}. We want to construct our polynomial R from this polynomial Q. In fact, let bi=ai for every i≤k−1, then let bk=ak+12Q(zk+1) and bk+1=14(Q(zk+1))2. Then, R(z)=(...(((z−b1)2−b2)2...−bk−1)2−bk)2−bk+1 =(...(((z−a1)2−a2)2...−ak−1)2−(ak+12Q(zk+1)))2−14(Q(zk+1))2 =((...(((z−a1)2−a2)2...−ak−1)2−ak)−12Q(zk+1))2−14(Q(zk+1))2 =(Q(z)−12Q(zk+1))2−14(Q(zk+1))2=Q(z)(Q(z)−Q(zk+1)). Hence, for i∈{1;2;...;k}, we have R(zi)=Q(zi)(Q(zi)−Q(zk+1))=0 because Q(zi)=0, and R(zk+1)=Q(zk+1)(Q(zk+1)−Q(zk+1))=0. Thus, R(zi)=0 holds for every i∈{1;2;...;k+1}, 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≥2 and that we can choose a to be any complex number. Then for any set of k distinct complex numbers f1,...,fk, 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 f1,...,fk as roots. Choose a=f1+fk2 and let p have roots (f1−a)2,...,(fk−1−a)2. Then p((f−a)2) is clearly 0 for f=f1,...,fk−1. For fk, we have p((fk−a)2)=p((−(f1−a))2)=p((f1−a)2)=0, so f has all of the possible values f1,...,fk.
We now use induction to show that (...((z−a1)2−a2)2...−an−1)2−an=0 can have any given n distinct roots for z if we appropriately choose a1,...,an. For n=1 we choose a1 to be the one distinct root since our equation is z−a1=0. Then let's assume it's true for n−1. Consider (...((z−a1)2−a2)2...−an−1)2−an=0. By the induction hypothesis we can get any n−1 distinct possible values for (z−a1)2 with an appropriate choice of a2,...,an. By the lemma, we can thus choose a1 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: bk=ak+1/2Q(ak+1)
05.10.2022 02:02
Let z1,z2,⋯ be the roots of P. We prove the case for general n via induction. The base case is trivial; take a1=z1. Now suppose that there exist constants b1,b2,⋯,bn such that setting ai=bi for each i creates a valid polynomial. Then, this means that(⋯((zi−b1)2−b2)2⋯−bn−1)2=kfor some constant k for each 1≤i≤n. Furthermore, let the value of this expression for zn+1 be r. Then, we need to pick bn,bn+1 such that(k−bn)2=(r−bn)2=bn+1.As the roots of the quadratic(x−a)2=bcan be any pair of complex numbers by choosing suitable a and b, such bn and bn+1 clearly exist, as required.
06.11.2024 12:04
We prove the general result (the original problem is essential n=1992): Let Pn(z) be a polynomial with complex coefficients which is of degree n and has distinct zeros. Prove that there exist complex numbers a1,a2,…,an such that P(z) divides the polynomial (⋯((z−a1)2−a2)2⋯−an−1)2−an. 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 Pn+1(z) have roots r1,⋯,rn+1. There exists complex numbers a1,⋯,an such that: Qn(z)=(⋯((z−a1)2−a2)2⋯−an−1)2−an with Q(ri)=0 for all 1≤i≤n. Let Qn(rn+1)=c. Now, consider: Qn+1(z)=(Qn(z)−c2)2−c24.Notice that Qn+1(rk)=0 for all 1≤k≤n+1 which implies Pn+1|Qn+1 and we are done.