Maths Olympiad Prep

Library / /18 of 28

Algebra Difficulty 8.5 Shortlist Prove it China

Let A={a1,a2,,a2010}A = \{a_1, a_2, \ldots, a_{2010}\} and B={b1,b2,,b2010}B = \{b_1, b_2, \ldots, b_{2010}\} be two sets of complex numbers, such that the equality
1i<j2010(ai+aj)n=1i<j2010(bi+bj)n \sum_{1 \le i < j \le 2010} (a_i + a_j)^n = \sum_{1 \le i < j \le 2010} (b_i + b_j)^n
holds for every n=1,2,,2010n = 1, 2, \ldots, 2010. Prove that A=BA = B.

Solution

Proof Let Sk=i=12010aikS_k = \sum_{i=1}^{2010} a_i^k and S~k=i=12010bik\tilde{S}_k = \sum_{i=1}^{2010} b_i^k. We first show by induction that Sk=S~kS_k = \tilde{S}_k for k=1,2,,2010k = 1, 2, \ldots, 2010.

Setting n=1n = 1 in the given equality, we have 2009S1=2009S~12009S_1 = 2009\tilde{S}_1, and hence S1=S~1S_1 = \tilde{S}_1. Assume that Sj=S~jS_j = \tilde{S}_j for j=1,2,,k1j = 1, 2, \ldots, k-1, where 2k20102 \le k \le 2010; we are going to show that Sk=S~kS_k = \tilde{S}_k.

By the binomial expansion theorem, we have
1i<j2010(ai+aj)k=1i<j2010l=0k(kl)ailajkl=2009Sk+1i<j2010l=0k1(kl)ailajkl=2009Sk+121i<j2010l=1k1(kl)ailajkl=2009Sk+12l=1k1i=12010(kl)ail(Sklaikl)=2009Sk+12l=1k1((kl)Skli=12010aili=12010(kl)aik)=2009Sk+12l=1k1((kl)SklSl(kl)Sk)=12l=1k1(kl)SklSl+(20102k1)Sk.1 \begin{align*} \sum_{1 \le i < j \le 2010} (a_i + a_j)^k &= \sum_{1 \le i < j \le 2010} \sum_{l=0}^{k} \binom{k}{l} a_i^l a_j^{k-l} \\ &= 2009S_k + \sum_{1 \le i < j \le 2010} \sum_{l=0}^{k-1} \binom{k}{l} a_i^l a_j^{k-l} \\ &= 2009S_k + \frac{1}{2} \sum_{1 \le i < j \le 2010} \sum_{l=1}^{k-1} \binom{k}{l} a_i^l a_j^{k-l} \\ &= 2009S_k + \frac{1}{2} \sum_{l=1}^{k-1} \sum_{i=1}^{2010} \binom{k}{l} a_i^l (S_{k-l} - a_i^{k-l}) \\ &= 2009S_k + \frac{1}{2} \sum_{l=1}^{k-1} \left( \binom{k}{l} S_{k-l} \sum_{i=1}^{2010} a_i^l - \sum_{i=1}^{2010} \binom{k}{l} a_i^k \right) \\ &= 2009S_k + \frac{1}{2} \sum_{l=1}^{k-1} \left( \binom{k}{l} S_{k-l} S_l - \binom{k}{l} S_k \right) \\ &= \frac{1}{2} \sum_{l=1}^{k-1} \binom{k}{l} S_{k-l} S_l + (2010 - 2^{k-1}) S_k. \quad \textcircled{1} \end{align*}

Similarly, we have
1i<j2010(bi+bj)k=12l=1k1(kl)S~klS~l+(20102k1)S~k.2 \sum_{1 \le i < j \le 2010} (b_i + b_j)^k = \frac{1}{2} \sum_{l=1}^{k-1} \binom{k}{l} \tilde{S}_{k-l} \tilde{S}_l + (2010 - 2^{k-1}) \tilde{S}_k. \quad \textcircled{2}

Since
1i<j2010(ai+aj)k=1i<j2010(bi+bj)k, \sum_{1 \le i < j \le 2010} (a_i + a_j)^k = \sum_{1 \le i < j \le 2010} (b_i + b_j)^k,
by ①, ② and inductive hypothesis Si=S~iS_i = \tilde{S}_i for i=1,2,,k1i = 1, 2, \dots, k-1, we have Sk=S~kS_k = \tilde{S}_k (it is worth noting that 20102010 is not a power of 22, i.e. 20102k102010 - 2^{k-1} \neq 0). This completes the inductive proof that Sk=S~kS_k = \tilde{S}_k for all k=1,2,,2010k = 1, 2, \dots, 2010.

Set
(xa1)(xa2010)=x2010+A1x2009++A2010,3 (x - a_1) \cdots (x - a_{2010}) = x^{2010} + A_1 x^{2009} + \cdots + A_{2010}, \quad \textcircled{3}
(xb1)(xb2010)=x2010+B1x2009++B2010.4 (x - b_1) \cdots (x - b_{2010}) = x^{2010} + B_1 x^{2009} + \cdots + B_{2010}. \quad \textcircled{4}
By Newton's formula, we have
Sk+A1Sk1++Ak1S1+kAk=0,5 S_k + A_1 S_{k-1} + \cdots + A_{k-1} S_1 + k A_k = 0, \quad \textcircled{5}
S~k+B1S~k1++Bk1S~1+kBk=0,6 \tilde{S}_k + B_1 \tilde{S}_{k-1} + \cdots + B_{k-1} \tilde{S}_1 + k B_k = 0, \quad \textcircled{6}
for k=1,2,,2010k = 1, 2, \dots, 2010.

It follows from ⑤, ⑥ and Sk=S~kS_k = \tilde{S}_k, k=1,2,,2010k = 1, 2, \dots, 2010, by the easy inductive argument, we have
Ak=Bk,k=1,2,,2010. A_k = B_k, \quad k = 1, 2, \dots, 2010.
The right hand sides of equations ③ and ④ are equal, and so are their left hand sides, i.e. A=BA = B.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.