Difference between revisions of "2022 AIME II Problems/Problem 13"

(Solution 1)
Line 81: Line 81:
  
 
~Steven Chen (www.professorchenedu.com)
 
~Steven Chen (www.professorchenedu.com)
 +
 +
== Solution 1 Modification ==
 +
 +
Note that <math>2022 = 210\cdot 9 +132</math>. Since the only way to express <math>132</math> in terms of <math>105</math>, <math>70</math>, <math>42</math>, or <math>30</math> is <math>135 = 30+30+30+42</math>, we are essentially just counting the number of ways to express <math>210*9</math> in terms of these numbers. This is simply (by sticks and stones) <cmath>\boxed{\textbf{(220)}}</cmath>
 +
 +
~Bigbrain123
  
 
==Solution 2==
 
==Solution 2==

Revision as of 21:42, 1 June 2022

Problem

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)$.

Solution 1

Because $0 < x < 1$, we have \begin{align*} P \left( x \right) & = \sum_{a=0}^6  \sum_{b=0}^\infty \sum_{c=0}^\infty \sum_{d=0}^\infty \sum_{e=0}^\infty \binom{6}{a} x^{2310a} \left( - 1 \right)^{6-a} x^{105b} x^{70c} x^{42d} x^{30e} \\ & = \sum_{a=0}^6 \sum_{b=0}^\infty \sum_{c=0}^\infty \sum_{d=0}^\infty \sum_{e=0}^\infty \left( - 1 \right)^{6-a} x^{2310 a + 105 b + 70 c + 42 d + 30 e} . \end{align*}

Denote by $c_{2022}$ the coefficient of $P \left( x \right)$. Thus, \begin{align*} c_{2022} & = \sum_{a=0}^6 \sum_{b=0}^\infty \sum_{c=0}^\infty \sum_{d=0}^\infty \sum_{e=0}^\infty \left( - 1 \right)^{6-a} \Bbb I \left\{ 2310 a + 105 b + 70 c + 42 d + 30 e = 2022 \right\} \\ & =  \sum_{b=0}^\infty \sum_{c=0}^\infty \sum_{d=0}^\infty \sum_{e=0}^\infty \left( - 1 \right)^{6-0} \Bbb I \left\{ 2310 \cdot 0 + 105 b + 70 c + 42 d + 30 e = 2022 \right\} \\ & = \sum_{b=0}^\infty \sum_{c=0}^\infty \sum_{d=0}^\infty \sum_{e=0}^\infty \Bbb I \left\{ 105 b + 70 c + 42 d + 30 e = 2022 \right\} . \end{align*}

Now, we need to find the number of nonnegative integer tuples $\left( b , c , d , e \right)$ that satisfy \[ 105 b + 70 c + 42 d + 30 e = 2022 . \hspace{1cm} (1) \]

Modulo 2 on Equation (1), we have $b \equiv 0 \pmod{2}$. Hence, we can write $b = 2 b'$. Plugging this into (1), the problem reduces to finding the number of nonnegative integer tuples $\left( b' , c , d , e \right)$ that satisfy \[ 105 b' + 35 c + 21 d + 15 e = 1011 . \hspace{1cm} (2) \]

Modulo 3 on Equation (2), we have $2 c \equiv 0 \pmod{3}$. Hence, we can write $c = 3 c'$. Plugging this into (2), the problem reduces to finding the number of nonnegative integer tuples $\left( b' , c' , d , e \right)$ that satisfy \[ 35 b' + 35 c' + 7 d + 5 e = 337 . \hspace{1cm} (3) \]

Modulo 5 on Equation (3), we have $2 d \equiv 2 \pmod{5}$. Hence, we can write $d = 5 d' + 1$. Plugging this into (3), the problem reduces to finding the number of nonnegative integer tuples $\left( b' , c' , d' , e \right)$ that satisfy \[ 7 b' + 7 c' + 7 d' + e = 66 . \hspace{1cm} (4) \]

Modulo 7 on Equation (4), we have $e \equiv 3 \pmod{7}$. Hence, we can write $e = 7 e' + 3$. Plugging this into (4), the problem reduces to finding the number of nonnegative integer tuples $\left( b' , c' , d' , e' \right)$ that satisfy \[ b' + c' + d' + e' = 9 . \hspace{1cm} (5) \]

The number of nonnegative integer solutions to Equation (5) is $\binom{9 + 4 - 1}{4 - 1} = \binom{12}{3} =  \boxed{\textbf{(220) }}$.

~Steven Chen (www.professorchenedu.com)

Solution 1 Modification

Note that $2022 = 210\cdot 9 +132$. Since the only way to express $132$ in terms of $105$, $70$, $42$, or $30$ is $135 = 30+30+30+42$, we are essentially just counting the number of ways to express $210*9$ in terms of these numbers. This is simply (by sticks and stones) \[\boxed{\textbf{(220)}}\]

~Bigbrain123

Solution 2

We know that $\frac{a^n-b^n}{a-b}=\sum_{i=0}^{n-1} a^{n-1-i}b^i$. Applying this, we see that \[P(x)=(1+x^{105}+x^{210}+...)(1+x^{70}+x^{140}+...)(1+x^{42}+x^{84}+...)(1+x^{30}+x^{60}+...)(x^{4620}-2x^{2310}+1)\] The last factor does not contribute to the $x^{2022}$ term, so we can ignore it. Thus we only have left to solve the equation $105b+70c+42d+30e=2022$, and we can proceed from here with Solution 1.

~MathIsFun286

See Also

2022 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 12
Followed by
Problem 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png