Maths Olympiad Prep

Library / /97 of 115

Algebra Difficulty 7.7 National olympiad, round 2 Find the answer

Let p(x)p(x) be the polynomial (1x)a(1x2)b(1x3)c(1x32)k(1-x)^a(1-x^2)^b(1-x^3)^c\cdots(1-x^{32})^k , where a,b,,ka, b, \cdots, k are integers. When expanded in powers of xx , the coefficient of x1x^1 is 2-2 and the coefficients of x2x^2 , x3x^3 , ..., x32x^{32} are all zero. Find kk .

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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 p(x)p(x) in reverse order. Therefore, if p(x)=(1x)a1(1x2)a2(1x3)a3(1x32)a32,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)q(x) to be q(x)=(x1)a1(x21)a2(x31)a3(x321)a32,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 nn , then the coefficient of xn1x^{n-1} is 2-2 , while the coefficients of xnkx^{n-k} for k=2,3,,32k=2,3,\dots, 32 are all 00 .
Let PnP_n be the sum of the nn th powers of the roots of q(x)q(x) . In particular, by Vieta's formulas, we know that P1=2P_1=2 . Also, by Newton's Sums, as the coefficients of xnkx^{n-k} for k=2,3,,32k=2,3,\dots,32 are all 00 , we find that P22P1=0P32P2=0P42P3=0P322P31=0.\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 Pn=2nP_n=2^n for n=1,2,,32n=1,2,\dots, 32 . Now we compute P32P_{32} . Note that the roots of (xn1)an(x^n-1)^{a_n} are all nn th roots of unity. If ω=e2πi/n\omega=e^{2\pi i/n} , then the sum of 3232 nd powers of these roots will be an(1+ω32+ω322++ω32(n1)).a_n(1+\omega^{32}+\omega^{32\cdot 2}+\cdots+\omega^{32\cdot(n-1)}). If ω321\omega^{32}\ne 1 , then we can multiply by (ω321)/(ω321)(\omega^{32}-1)/(\omega^{32}-1) to obtain an(1ω32n)1ω32.\frac{a_n(1-\omega^{32n})}{1-\omega^{32}}. But as ωn=1\omega^n=1 , this is just 00 . Therefore the sum of the 3232 nd powers of the roots of q(x)q(x) is the same as the sum of the 3232 nd powers of the roots of (x1)a1(x21)a2(x41)a4(x81)a4(x161)a16(x321)a32.(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 3232 nd power of each of these roots is just 11 , hence the sum of the 3232 nd powers of the roots is P32=232=a1+2a2+4a4+8a8+16a16+32a32.(1)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 P16=216=a1+2a2+4a4+8a8+16a16.(2)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 a32=23221625.a_{32}=\frac{2^{32}-2^{16}}{2^5}. Therefore, a32=227211a_{32}=2^{27}-2^{11} .

Solution 2
By a limiting process, we can extend the problem to that of finding a sequence b1,b2,b_1, b_2, \ldots of integers such that (1z)b1(1z2)b2(1z3)b3=12z.(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 n=1bn(nzn1)1zn=212z,\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-z , this gives us the somewhat simple form n=1nbnzn1zn=2z12z.\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 n=1nbnk=1znk=n=12nzn.\sum_{n = 1}^{\infty} nb_n\sum_{k = 1}^{\infty} z^{nk} = \sum_{n = 1}^{\infty} 2^nz^n. Comparing coefficients, we get dndbd=2n\sum_{d\mid n} db_d = 2^n for all positive integers nn . In particular, as in Solution 1, we get b1+2b2+4b4+8b8+16b16+32b32=232,b1+2b2+4b4+8b8+16b16+32b32=216,\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 b32=227211b_{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 (1z)b1(1z2)b2(1z32)b3212z(modz33);(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 bnb_n 's comes from the fact that we have (1z)b1(1zn1)bn112z(modzn)(1 - z)^{b_1}\cdots (1 - z^{n - 1})^{b_{n - 1}}\equiv 1 - 2z\pmod{z^n} for all n33n\leq 33 by further reduction modulo znz^n (as znz33z^n\mid z^{33} for n33n\leq 33 ), so we could uniquely solve for the bnb_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 z33z^{33} , note that the derivative is not well-defined, as for instance, 11 and 1+z331 + z^{33} are equivalent modulo z33z^{33} , but their derivatives, 00 and 33z3233z^{32} , are not. However, the operator f(z)zf(z)f(z)\mapsto zf'(z) is well-defined. The other key idea is that for any nn , modulo znz^n , polynomials of the form 1zf(z)1 - zf(z) are invertible, with inverse 11zf(z)1(zf(z))n1zf(z)=1+zf(z)++(zf(z))n1).\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)g(z) , we can still form the expression zg(z)/g(z)zg'(z)/g(z) , which is what we originally got by taking the logarithmic derivative and multiplying by zz , and expand it to eventually get n=132nbnk=132znkn=1322nzn(modz33),\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 n32n\leq 32 ).
Solution 3
From the starting point of Solution 2, (1z)b1(1z2)b2(1z3)b3=12z,(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 n=1(k=0zkn)bn=n=02nzn.\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 nn over the field F2\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 bn=number of monic irreducible polynomials of degree n over F2.b_n = \text{number of monic irreducible polynomials of degree }n\text{ over }\mathbb{F}_2. From here, to determine bnb_n , we analyse the elements of F2n\mathbb{F}_{2^n} , of which there are 2n2^{n} in total. Given αF2n\alpha\in\mathbb{F}_{2^n} , if the minimal polynomial fαf_{\alpha} of α\alpha has degree dd , then dnd\mid n and all other roots of fαf_{\alpha} appear in F2n\mathbb{F}_{2^n} . Moreover, if dnd\mid n and ff is an irreducible polynomial of degree dd , then all roots of ff appear in F2n\mathbb{F}_{2^n} . (These statements are all well-known in the theory of finite fields.) As such, for each dnd\mid n , there are precisely dbddb_d elements of F2n\mathbb{F}_{2^n} of degree dd , and we obtain the same equation as in Solution 2, dndbd=2n.\sum_{d\mid n} db_d = 2^n. The rest is as before.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.