Difference between revisions of "1988 USAMO Problems/Problem 5"
Mathgeek2006 (talk | contribs) m (→Solution) |
5849206328x (talk | contribs) |
||
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 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 | 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> | <cmath>p(x)=(1-x)^{a_1}(1-x^2)^{a_2}(1-x^3)^{a_3}\cdots(1-x^{32})^{a_{32}},</cmath> | ||
Line 30: | Line 32: | ||
<cmath>a_{32}=\frac{2^{32}-2^{16}}{2^5}.</cmath> | <cmath>a_{32}=\frac{2^{32}-2^{16}}{2^5}.</cmath> | ||
Therefore, <math>a_{32}=2^{27}-2^{11}</math>. | 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 positive integers such that | ||
+ | <cmath> (1 - z)^{b_1}(1 - z^2)^{b_2}(1 - z^3)^{b_3}\cdots = 1 - 2z. </cmath> | ||
+ | (We could make the limiting process more formal by invoking the "usual" (<math>(z)</math>-adic) topology on the space of formal power series in <math>z</math>, or if we want to avoid the high-powered stuff, we could also stick to the finite situation in the problem and suppress large powers with big-oh notation. We'll use the power series approach here in anticipation of Solution 3 (and because power series appear anyway).) | ||
+ | |||
+ | 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_{m = 1}^{\infty} 2^mz^m. </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. | ||
+ | |||
+ | |||
+ | ===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== |
Revision as of 22:36, 24 June 2022
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 .
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 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, .
Solution 2
By a limiting process, we can extend the problem to that of finding a sequence of positive integers such that (We could make the limiting process more formal by invoking the "usual" (-adic) topology on the space of formal power series in , or if we want to avoid the high-powered stuff, we could also stick to the finite situation in the problem and suppress large powers with big-oh notation. We'll use the power series approach here in anticipation of Solution 3 (and because power series appear anyway).)
If we take logarithmic derivatives on both sides, we get and upon multiplying both sides by , this gives us the somewhat simple form Expanding all the fractions as geometric series, we get Comparing coefficients, we get for all positive integers . In particular, as in Solution 1, we get from which the answer follows.
Solution 3
From the starting point of Solution 2, taking reciprocals and expanding with geometric series gives us On the right, we have the generating function for the number of monic polynomials of degree over the field 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 From here, to determine , we analyse the elements of , of which there are in total. Given , if the minimal polynomial of has degree , then and all other roots of appear in . Moreover, if and is an irreducible polynomial of degree , then all roots of appear in . (These statements are all well-known in the theory of finite fields.) As such, for each , there are precisely elements of of degree , and we obtain the same equation as in Solution 2, 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.