Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1988 USAMO Problems/Problem 5"
Line 3: Line 3:
  
 
==Solution==
 
==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 14:42, 27 June 2016

Problem

Let $p(x)$ be the polynomial $(1-x)^a(1-x^2)^b(1-x^3)^c\cdots(1-x^{32})^k$, where $a, b, \cdots, k$ are integers. When expanded in powers of $x$, the coefficient of $x^1$ is $-2$ and the coefficients of $x^2$, $x^3$, ..., $x^{32}$ are all zero. Find $k$.

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 $p(x)$ in reverse order. Therefore, if \[p(x)=(1-x)^{a_1}(1-x^2)^{a_2}(1-x^3)^{a_3}\cdots(1-x^{32})^{a_{32}},\] we define the polynomial $q(x)$ to be \[q(x)=(x-1)^{a_1}(x^2-1)^{a_2}(x^3-1)^{a_3}\cdots(x^{32}-1)^{a_{32}},\] noting that if the polynomial has degree $n$, then the coefficient of $x^{n-1}$ is $-2$, while the coefficients of $x^{n-k}$ for $k=2,3,\dots, 32$ are all $0$.

Let $P_n$ be the sum of the $n$th powers of the roots of $q(x)$. In particular, by Vieta's formulas, we know that $P_1=2$. Also, by Newton's Sums, as the coefficients of $x^{n-k}$ for $k=2,3,\dots,32$ are all $0$, we find that \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*} Thus $P_n=2^n$ for $n=1,2,\dots, 32$. Now we compute $P_{32}$. Note that the roots of $(x^n-1)^{a_n}$ are all $n$th roots of unity. If $\omega=e^{2\pi i/n}$, then the sum of $32$nd powers of these roots will be \[a_n(1+\omega^{32}+\omega^{32\cdot 2}+\cdots+\omega^{32\cdot(n-1)}).\] If $\omega^{32}\ne 1$, then we can multiply by $(\omega^{32}-1)/(\omega^{32}-1)$ to obtain \[\frac{a_n(1-\omega^{32n})}{1-\omega^{32}}.\] But as $\omega^n=0$, this is just $0$. Therefore the sum of the $32$nd powers of the roots of $q(x)$ is the same as the sum of the $32$nd powers of the roots of \[(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}}.\] The $32$nd power of each of these roots is just $1$, hence the sum of the $32$nd powers of the roots is \[P_{32}=2^{32}=a_1+2a_2+4a_4+8a_8+16a_{16}+32a_{32}.\tag{1}\] On the other hand, we can use the same logic to show that \[P_{16}=2^{16}=a_1+2a_2+4a_4+8a_8+16a_{16}.\tag{2}\] Subtracting (2) from (1) and dividing by 32, we find \[a_{32}=\frac{2^{32}-2^{16}}{2^5}.\] Therefore, $a_{32}=2^{27}-2^{11}$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1988_USAMO_Problems/Problem_5&oldid=79106"