Difference between revisions of "1988 USAMO Problems/Problem 5"
5849206328x (talk | contribs) |
5849206328x (talk | contribs) (→Solution 2) |
||
(One intermediate revision by the same user not shown) | |||
Line 36: | Line 36: | ||
===Solution 2=== | ===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 | + | 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> | <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 | If we take logarithmic derivatives on both sides, we get | ||
Line 45: | Line 45: | ||
<cmath> \sum_{n = 1}^{\infty} nb_n\cdot\frac{z^n}{1 - z^n} = \frac{2z}{1 - 2z}. </cmath> | <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 | Expanding all the fractions as geometric series, we get | ||
− | <cmath> \sum_{n = 1}^{\infty} nb_n\sum_{k = 1}^{\infty} z^{nk} = \sum_{ | + | <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 | Comparing coefficients, we get | ||
<cmath> \sum_{d\mid n} db_d = 2^n </cmath> | <cmath> \sum_{d\mid n} db_d = 2^n </cmath> | ||
Line 55: | Line 55: | ||
from which the answer <math>b_{32} = 2^{27} - 2^{11}</math> follows. | 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=== | ===Solution 3=== |
Latest revision as of 09:44, 25 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 integers such that
(The notation comes from the Alcumus version of this problem.)
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.
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
modular arithmetic for polynomials can be defined in exactly the same way as modular arithmetic for integers. Uniqueness of the
's comes from the fact that we have
for all
by further reduction modulo
(as
for
), so we could uniquely solve for the
'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 , note that the derivative is not well-defined, as for instance,
and
are equivalent modulo
, but their derivatives,
and
, are not. However, the operator
is well-defined. The other key idea is that for any
, modulo
, polynomials of the form
are invertible, with inverse
Therefore, for the polynomial in the problem, call it
, we can still form the expression
, which is what we originally got by taking the logarithmic derivative and multiplying by
, and expand it to eventually get
which gets us the same relations (for
).
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.