2022 AIME II Problem 13

Attempt Problem 13 of the 2022 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2022 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

13.

There is a polynomial P(x)P(x) with integer coefficients such that P(x)=(x23101)61(x1051)(x701)1(x421)(x301) \begin{aligned} P(x) &= (x^{2310}-1)^6 \\ &\quad {}\cdot \frac{1}{(x^{105}-1)(x^{70}-1)} \\ &\quad {}\cdot \frac{1}{(x^{42}-1)(x^{30}-1)} \end{aligned} holds for every 0<x<1.0 \lt x \lt 1. Find the coefficient of x2022x^{2022} in P(x).P(x).

Answer: 220
Concepts:generating functionsDiophantine Equationstars and bars
Difficulty rating: 3270
Solution:

For 0<x<1,0 \lt x \lt 1, P(x)=(1x2310)61(1x105)(1x70)1(1x42)(1x30), \begin{aligned} P(x) &= (1-x^{2310})^6 \\ &\quad {}\cdot \frac{1}{(1-x^{105})(1-x^{70})} \\ &\quad {}\cdot \frac{1}{(1-x^{42})(1-x^{30})}, \end{aligned} and each factor 11xk\frac{1}{1 - x^k} expands as a geometric series. Since 2022<2310,2022 \lt 2310, the factor (1x2310)6(1 - x^{2310})^6 contributes only its constant term 1,1, so the coefficient of x2022x^{2022} is the number of nonnegative integer solutions of 105a+70b+42c+30d=2022.105a + 70b + 42c + 30d = 2022.

Reducing modulo 22 gives 105a2022,105a \equiv 2022, so aa is even; modulo 33 gives 70b20220,70b \equiv 2022 \equiv 0, so 3b;3 \mid b; modulo 55 gives 2c20222,2c \equiv 2022 \equiv 2, so c1(mod5);c \equiv 1 \pmod 5; modulo 77 gives 2d20226,2d \equiv 2022 \equiv 6, so d3(mod7).d \equiv 3 \pmod 7. Writing a=2a,a = 2a', b=3b,b = 3b', c=5c+1,c = 5c' + 1, d=7d+3d = 7d' + 3 turns the equation into 210(a+b+c+d)+42+90=2022, \begin{aligned} &210(a' + b' + c' + d') + 42 \\ &\quad {}+ 90 = 2022, \end{aligned} so a+b+c+d=9.a' + b' + c' + d' = 9.

By stars and bars there are (123)=220\binom{12}{3} = 220 solutions, so the coefficient is 220.220.

← Problem 12#12
Full Exam

Problem 13 in Other Years