Difference between revisions of "1988 USAMO Problems/Problem 5"
Mathgeek2006 (talk | contribs) |
|||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | {{ | + | First, note that if we reverse the order of the coefficients of each factor, then we will obtain a polynomial whose coefficients are exactly the coefficients of <math>p(x)</math> in reverse order. Therefore, if |
+ | <cmath>p(x)=(1-x)^{a_1}(1-x^2)^{a_2}(1-x^3)^{a_3}\cdots(1-x^{32})^{a_{32}},</cmath> | ||
+ | we define the polynomial <math>q(x)</math> to be | ||
+ | <cmath>q(x)=(x-1)^{a_1}(x^2-1)^{a_2}(x^3-1)^{a_3}\cdots(x^{32}-1)^{a_{32}},</cmath> | ||
+ | noting that if the polynomial has degree <math>n</math>, then the coefficient of <math>x^{n-1}</math> is <math>-2</math>, while the coefficients of <math>x^{n-k}</math> for <math>k=2,3,\dots, 32</math> are all <math>0</math>. | ||
+ | |||
+ | Let <math>P_n</math> be the sum of the <math>n</math>th powers of the roots of <math>q(x)</math>. In particular, by Vieta's formulas, we know that <math>P_1=2</math>. Also, by Newton's Sums, as the coefficients of <math>x^{n-k}</math> for <math>k=2,3,\dots,32</math> are all <math>0</math>, we find that | ||
+ | <cmath>\begin{align*} | ||
+ | P_2-2P_1&=0\ | ||
+ | P_3-2P_2&=0\ | ||
+ | P_4-2P_3&=0\ | ||
+ | &\vdots\ | ||
+ | P_{32}-2P_{31}&=0. | ||
+ | \end{align*}</cmath> | ||
+ | Thus <math>P_n=2^n</math> for <math>n=1,2,\dots, 32</math>. Now we compute <math>P_{32}</math>. Note that the roots of <math>(x^n-1)^{a_n}</math> are all <math>n</math>th roots of unity. If <math>\omega=e^{2\pi i/n}</math>, then the sum of <math>32</math>nd powers of these roots will be | ||
+ | <cmath>a_n(1+\omega^{32}+\omega^{32\cdot 2}+\cdots+\omega^{32\cdot(n-1)}).</cmath> | ||
+ | If <math>\omega^{32}\ne 1</math>, then we can multiply by <math>(\omega^{32}-1)/(\omega^{32}-1)</math> to obtain | ||
+ | <cmath>\frac{a_n(1-\omega^{32n})}{1-\omega^{32}}.</cmath> | ||
+ | But as <math>\omega^n=0</math>, this is just <math>0</math>. Therefore the sum of the <math>32</math>nd powers of the roots of <math>q(x)</math> is the same as the sum of the <math>32</math>nd powers of the roots of | ||
+ | <cmath>(x-1)^{a_1}(x^2-1)^{a_2}(x^4-1)^{a_4}(x^{8}-1)^{a_4}(x^{16}-1)^{a_{16}}(x^{32}-1)^{a_{32}}.</cmath> | ||
+ | The <math>32</math>nd power of each of these roots is just <math>1</math>, hence the sum of the <math>32</math>nd powers of the roots is | ||
+ | <cmath>P_{32}=2^{32}=a_1+2a_2+4a_4+8a_8+16a_{16}+32a_{32}.\tag{1}</cmath> | ||
+ | On the other hand, we can use the same logic to show that | ||
+ | <cmath>P_{16}=2^{16}=a_1+2a_2+4a_4+8a_8+16a_{16}.\tag{2}</cmath> | ||
+ | Subtracting (2) from (1) and dividing by 32, we find | ||
+ | <cmath>a_{32}=\frac{2^{32}-2^{16}}{2^5}.</cmath> | ||
+ | Therefore, <math>a_{32}=2^{27}-2^{11}</math>. | ||
==See Also== | ==See Also== |
Revision as of 13:42, 27 June 2016
Problem
Let be the polynomial , where are integers. When expanded in powers of , the coefficient of is and the coefficients of , , ..., are all zero. Find .
Solution
First, note that if we reverse the order of the coefficients of each factor, then we will obtain a polynomial whose coefficients are exactly the coefficients of in reverse order. Therefore, if we define the polynomial to be noting that if the polynomial has degree , then the coefficient of is , while the coefficients of for are all .
Let be the sum of the th powers of the roots of . In particular, by Vieta's formulas, we know that . Also, by Newton's Sums, as the coefficients of for are all , we find that Thus for . Now we compute . Note that the roots of are all th roots of unity. If , then the sum of nd powers of these roots will be If , then we can multiply by to obtain But as , this is just . Therefore the sum of the nd powers of the roots of is the same as the sum of the nd powers of the roots of The nd power of each of these roots is just , hence the sum of the nd powers of the roots is On the other hand, we can use the same logic to show that Subtracting (2) from (1) and dividing by 32, we find Therefore, .
See Also
1988 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.