### Problem request: 2022 AIME II #13

Hi everyone,

I hope you had a great summer!

I was not posting for about a month or so because not many people were viewing the blog in the summer.

I'm going to start to post frequently again, and for now I have a problem request I got a couple days ago.

There is a polynomial $P(x)$ with integer coefficients such that\[P(x)=\frac{(x^{2310}-1)^6}{(x^{105}-1)(x^{70}-1)(x^{42}-1)(x^{30}-1)}\]holds for every $0<x<1.$ Find the coefficient of $x^{2022}$ in $P(x)$.

Note that $$\tfrac{x^{mn}-1}{x^n-1}=x^{(m-1)n}+x^{(m-2)n}+\dots+x^n+1.$$ Then

$$P(x)=(x^{21\cdot105}+x^{20\cdot105}+\dots+x^{105}+1)(x^{32\cdot70}+x^{31\cdot70}+\dots+x^{70}+1)$$

$$(x^{54\cdot42}+x^{53\cdot42}+\dots+x^{53}+1)(x^{76\cdot30}+x^{75\cdot30}+\dots+x^{30}+1)(x^{2310}-1)^2.$$

We want to compute the number of ways to choose a term from each of the $6$ factors above such that the product of all $6$ terms is $x^{2022}$. A term from the first factor is of the form $x^{105a}$, a term from the second factor is of the form $x^{70b}$, a term from the third factor is of the form $x^{42c}$, and a term from the fourth factor is of the form $x^{30d}$. The terms chosen from the last two factors must be $-1$, because $x^{2310}$ causes the degree of the term to already be too high.

Now, we need to find the number of nonnegative integer solutions to the equation $$105a+70b+42c+30d=2022 \qquad \qquad \qquad (1)$$

Now, notice that $22\cdot105$, $33\cdot70$, $55\cdot42$, and $77\cdot30$ are all equal to $2310$. From this, we see that each of $105$, $70$, $42$, and $30$ aren't divisible by a prime that is divisible by the other three numbers. These $4$ primes are $2$, $3$, $5$, and $7$, and taking $(1)$ modulo each of these primes gives us $a=2a'$, $b=3b'$, $c=5c'+1$, and $d=7d'+2$. Substituting these, we obtain $$105(2a')+70(3b')+42(5c'+1)+30(7d'+3)=210a'+210b'+210c'+210d'+132=2022$$

$$\implies a'+b'+c'+d'=9.$$By Stars and Bars, the number of solutions $(a,b,c,d)$ in nonnegative integers to the above equation is $\tbinom{12}{3}=\boxed{220}$.

yay he's back!

ReplyDelete