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"
(→‎Solution 2)
 
(4 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
Let <math>p(x)</math> be the polynomial <math>(1-x)^a(1-x^2)^b(1-x^3)^c\cdots(1-x^{32})^k</math>, where <math>a, b, \cdots, k</math> are integers. When expanded in powers of <math>x</math>, the coefficient of <math>x^1</math> is <math>-2</math> and the coefficients of <math>x^2</math>, <math>x^3</math>, ..., <math>x^{32}</math> are all zero. Find <math>k</math>.
 
Let <math>p(x)</math> be the polynomial <math>(1-x)^a(1-x^2)^b(1-x^3)^c\cdots(1-x^{32})^k</math>, where <math>a, b, \cdots, k</math> are integers. When expanded in powers of <math>x</math>, the coefficient of <math>x^1</math> is <math>-2</math> and the coefficients of <math>x^2</math>, <math>x^3</math>, ..., <math>x^{32}</math> are all zero. Find <math>k</math>.
  
−
==Solution==
+
==Solutions==
−
{{solution}}
+
 
 +
===Solution 1===
 +
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=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>
 +
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>.
 +
 
 +
 
 +
===Solution 2===
 +
 
 +
By a limiting process, we can extend the problem to that of finding a sequence <math>b_1, b_2, \ldots</math> of integers such that
 +
<cmath> (1 - z)^{b_1}(1 - z^2)^{b_2}(1 - z^3)^{b_3}\cdots = 1 - 2z. </cmath>
 +
(The notation comes from the Alcumus version of this problem.)
 +
 
 +
If we take logarithmic derivatives on both sides, we get
 +
<cmath> \sum_{n = 1}^{\infty}\frac{b_n\cdot (-nz^{n - 1})}{1 - z^n} = \frac{-2}{1 - 2z}, </cmath>
 +
and upon multiplying both sides by <math>-z</math>, this gives us the somewhat simple form
 +
<cmath> \sum_{n = 1}^{\infty} nb_n\cdot\frac{z^n}{1 - z^n} = \frac{2z}{1 - 2z}. </cmath>
 +
Expanding all the fractions as geometric series, we get
 +
<cmath> \sum_{n = 1}^{\infty} nb_n\sum_{k = 1}^{\infty} z^{nk} = \sum_{n = 1}^{\infty} 2^nz^n. </cmath>
 +
Comparing coefficients, we get
 +
<cmath> \sum_{d\mid n} db_d = 2^n </cmath>
 +
for all positive integers <math>n</math>. In particular, as in Solution 1, we get
 +
<cmath>\begin{array}{ll}
 +
b_1 + 2b_2 + 4b_4 + 8b_8 + 16b_{16} + 32b_{32} &= 2^{32}, \\
 +
b_1 + 2b_2 + 4b_4 + 8b_8 + 16b_{16}\phantom{ + 32b_{32}} &= 2^{16},
 +
\end{array}</cmath>
 +
from which the answer <math>b_{32} = 2^{27} - 2^{11}</math> follows.
 +
 
 +
'''Remark:''' To avoid the question of what an infinite product means in the context of formal power series, we could instead view the problem statement as saying that
 +
<cmath> (1 - z)^{b_1}(1 - z^2)^{b_2}\cdots (1 - z^{32})^{b_{32}}\equiv 1 - 2z\pmod{z^{33}}; </cmath>
 +
modular arithmetic for polynomials can be defined in exactly the same way as modular arithmetic for integers. Uniqueness of the <math>b_n</math>'s comes from the fact that we have
 +
<cmath> (1 - z)^{b_1}\cdots (1 - z^{n - 1})^{b_{n - 1}}\equiv 1 - 2z\pmod{z^n} </cmath>
 +
for all <math>n\leq 33</math> by further reduction modulo <math>z^n</math> (as <math>z^n\mid z^{33}</math> for <math>n\leq 33</math>), so we could uniquely solve for the <math>b_n</math>'s one at a time. (This idea can be pushed further to explain why it's fine to pass to the infinite product version of the problem.)
 +
 
 +
To convert the above solution to one that works with polynomials modulo <math>z^{33}</math>, note that the derivative is not well-defined, as for instance, <math>1</math> and <math>1 + z^{33}</math> are equivalent modulo <math>z^{33}</math>, but their derivatives, <math>0</math> and <math>33z^{32}</math>, are not. However, the operator <math>f(z)\mapsto zf'(z)</math> ''is'' well-defined. The other key idea is that for any <math>n</math>, modulo <math>z^n</math>, polynomials of the form <math>1 - zf(z)</math> are invertible, with inverse
 +
<cmath> \frac{1}{1 - zf(z)}\equiv\frac{1 - (zf(z))^n}{1 - zf(z)} = 1 + zf(z) + \cdots + (zf(z))^{n - 1}). </cmath>
 +
Therefore, for the polynomial in the problem, call it <math>g(z)</math>, we can still form the expression <math>zg'(z)/g(z)</math>, which is what we originally got by taking the logarithmic derivative and multiplying by <math>z</math>, and expand it to eventually get
 +
<cmath> \sum_{n = 1}^{32} nb_n\sum_{k = 1}^{32} z^{nk}\equiv\sum_{n = 1}^{32} 2^nz^n\pmod{z^{33}}, </cmath>
 +
which gets us the same relations (for <math>n\leq 32</math>).
 +
 
 +
===Solution 3===
 +
 
 +
From the starting point of Solution 2,
 +
<cmath> (1 - z)^{b_1}(1 - z^2)^{b_2}(1 - z^3)^{b_3}\cdots = 1 - 2z, </cmath>
 +
taking reciprocals and expanding with geometric series gives us
 +
<cmath> \prod_{n = 1}^{\infty}\left(\sum_{k = 0}^{\infty} z^{kn}\right)^{b_n} = \sum_{n = 0}^{\infty} 2^nz^n. </cmath>
 +
On the right, we have the generating function for the number of monic polynomials of degree <math>n</math> over the field <math>\mathbb{F}_2</math> of two elements, and on the left, we have the factorisation of this generating function that considers the breakdown of any given monic polynomial into monic irreducible factors. As such, we have the interpretation
 +
<cmath> b_n = \text{number of monic irreducible polynomials of degree }n\text{ over }\mathbb{F}_2. </cmath>
 +
From here, to determine <math>b_n</math>, we analyse the elements of <math>\mathbb{F}_{2^n}</math>, of which there are <math>2^{n}</math> in total. Given <math>\alpha\in\mathbb{F}_{2^n}</math>, if the minimal polynomial <math>f_{\alpha}</math> of <math>\alpha</math> has degree <math>d</math>, then <math>d\mid n</math> and all other roots of <math>f_{\alpha}</math> appear in <math>\mathbb{F}_{2^n}</math>. Moreover, if <math>d\mid n</math> and <math>f</math> is an irreducible polynomial of degree <math>d</math>, then all roots of <math>f</math> appear in <math>\mathbb{F}_{2^n}</math>. (These statements are all well-known in the theory of finite fields.) As such, for each <math>d\mid n</math>, there are precisely <math>db_d</math> elements of <math>\mathbb{F}_{2^n}</math> of degree <math>d</math>, and we obtain the same equation as in Solution 2,
 +
<cmath> \sum_{d\mid n} db_d = 2^n. </cmath>
 +
The rest is as before.
 +
 
  
 
==See Also==
 
==See Also==

Latest revision as of 08:44, 25 June 2022

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$.

Solutions

Solution 1

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}$.


Solution 2

By a limiting process, we can extend the problem to that of finding a sequence $b_1, b_2, \ldots$ of integers such that \[(1 - z)^{b_1}(1 - z^2)^{b_2}(1 - z^3)^{b_3}\cdots = 1 - 2z.\] (The notation comes from the Alcumus version of this problem.)

If we take logarithmic derivatives on both sides, we get \[\sum_{n = 1}^{\infty}\frac{b_n\cdot (-nz^{n - 1})}{1 - z^n} = \frac{-2}{1 - 2z},\] and upon multiplying both sides by $-z$, this gives us the somewhat simple form \[\sum_{n = 1}^{\infty} nb_n\cdot\frac{z^n}{1 - z^n} = \frac{2z}{1 - 2z}.\] Expanding all the fractions as geometric series, we get \[\sum_{n = 1}^{\infty} nb_n\sum_{k = 1}^{\infty} z^{nk} = \sum_{n = 1}^{\infty} 2^nz^n.\] Comparing coefficients, we get \[\sum_{d\mid n} db_d = 2^n\] for all positive integers $n$. In particular, as in Solution 1, we get \[\begin{array}{ll} b_1 + 2b_2 + 4b_4 + 8b_8 + 16b_{16} + 32b_{32} &= 2^{32}, \\ b_1 + 2b_2 + 4b_4 + 8b_8 + 16b_{16}\phantom{ + 32b_{32}} &= 2^{16}, \end{array}\] from which the answer $b_{32} = 2^{27} - 2^{11}$ follows.

Remark: To avoid the question of what an infinite product means in the context of formal power series, we could instead view the problem statement as saying that \[(1 - z)^{b_1}(1 - z^2)^{b_2}\cdots (1 - z^{32})^{b_{32}}\equiv 1 - 2z\pmod{z^{33}};\] modular arithmetic for polynomials can be defined in exactly the same way as modular arithmetic for integers. Uniqueness of the $b_n$'s comes from the fact that we have \[(1 - z)^{b_1}\cdots (1 - z^{n - 1})^{b_{n - 1}}\equiv 1 - 2z\pmod{z^n}\] for all $n\leq 33$ by further reduction modulo $z^n$ (as $z^n\mid z^{33}$ for $n\leq 33$), so we could uniquely solve for the $b_n$'s one at a time. (This idea can be pushed further to explain why it's fine to pass to the infinite product version of the problem.)

To convert the above solution to one that works with polynomials modulo $z^{33}$, note that the derivative is not well-defined, as for instance, $1$ and $1 + z^{33}$ are equivalent modulo $z^{33}$, but their derivatives, $0$ and $33z^{32}$, are not. However, the operator $f(z)\mapsto zf'(z)$ is well-defined. The other key idea is that for any $n$, modulo $z^n$, polynomials of the form $1 - zf(z)$ are invertible, with inverse \[\frac{1}{1 - zf(z)}\equiv\frac{1 - (zf(z))^n}{1 - zf(z)} = 1 + zf(z) + \cdots + (zf(z))^{n - 1}).\] Therefore, for the polynomial in the problem, call it $g(z)$, we can still form the expression $zg'(z)/g(z)$, which is what we originally got by taking the logarithmic derivative and multiplying by $z$, and expand it to eventually get \[\sum_{n = 1}^{32} nb_n\sum_{k = 1}^{32} z^{nk}\equiv\sum_{n = 1}^{32} 2^nz^n\pmod{z^{33}},\] which gets us the same relations (for $n\leq 32$).

Solution 3

From the starting point of Solution 2, \[(1 - z)^{b_1}(1 - z^2)^{b_2}(1 - z^3)^{b_3}\cdots = 1 - 2z,\] taking reciprocals and expanding with geometric series gives us \[\prod_{n = 1}^{\infty}\left(\sum_{k = 0}^{\infty} z^{kn}\right)^{b_n} = \sum_{n = 0}^{\infty} 2^nz^n.\] On the right, we have the generating function for the number of monic polynomials of degree $n$ over the field $\mathbb{F}_2$ of two elements, and on the left, we have the factorisation of this generating function that considers the breakdown of any given monic polynomial into monic irreducible factors. As such, we have the interpretation \[b_n = \text{number of monic irreducible polynomials of degree }n\text{ over }\mathbb{F}_2.\] From here, to determine $b_n$, we analyse the elements of $\mathbb{F}_{2^n}$, of which there are $2^{n}$ in total. Given $\alpha\in\mathbb{F}_{2^n}$, if the minimal polynomial $f_{\alpha}$ of $\alpha$ has degree $d$, then $d\mid n$ and all other roots of $f_{\alpha}$ appear in $\mathbb{F}_{2^n}$. Moreover, if $d\mid n$ and $f$ is an irreducible polynomial of degree $d$, then all roots of $f$ appear in $\mathbb{F}_{2^n}$. (These statements are all well-known in the theory of finite fields.) As such, for each $d\mid n$, there are precisely $db_d$ elements of $\mathbb{F}_{2^n}$ of degree $d$, and we obtain the same equation as in Solution 2, \[\sum_{d\mid n} db_d = 2^n.\] The rest is as before.


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=175292"