Difference between revisions of "1988 USAMO Problems/Problem 5"

m (Solution)
Line 21: Line 21:
 
If <math>\omega^{32}\ne 1</math>, then we can multiply by <math>(\omega^{32}-1)/(\omega^{32}-1)</math> to obtain
 
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>
 
<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
+
But as <math>\omega^n=1</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>
 
<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
 
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

Revision as of 14:46, 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=1$, 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 (ProblemsResources)
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