2022 AIME II Problems/Problem 13
Contents
Problem
There is a polynomial with integer coefficients such thatholds for every Find the coefficient of in .
Solution 1
Because , we have
Denote by the coefficient of . Thus,
Now, we need to find the number of nonnegative integer tuples that satisfy
Modulo 2 on Equation (1), we have . Hence, we can write . Plugging this into (1), the problem reduces to finding the number of nonnegative integer tuples that satisfy
Modulo 3 on Equation (2), we have . Hence, we can write . Plugging this into (2), the problem reduces to finding the number of nonnegative integer tuples that satisfy
Modulo 5 on Equation (3), we have . Hence, we can write . Plugging this into (3), the problem reduces to finding the number of nonnegative integer tuples that satisfy
Modulo 7 on Equation (4), we have . Hence, we can write . Plugging this into (4), the problem reduces to finding the number of nonnegative integer tuples that satisfy
The number of nonnegative integer solutions to Equation (5) is .
~Steven Chen (www.professorchenedu.com)
Solution 2
Note that . Since the only way to express in terms of , , , or is , we are essentially just counting the number of ways to express in terms of these numbers. Since , it can only be expressed as a sum in terms of only one of the numbers (, , , or ). Thus, the answer is (by sticks and stones)
~Bigbrain123
Solution 3
We know that . Applying this, we see that The last factor does not contribute to the term, so we can ignore it. Thus we only have left to solve the equation , and we can proceed from here with Solution 1.
~MathIsFun286
Solution 4 (Generating Function Bash)
Essentially we want the coefficient of in the expansion
As does not contribute to the expansion, we omit it.
Notice , so we can rewrite the generating function as
Notice to obtain a value, the must be used, so we can reduce the problem to finding the coefficient of in
If is expanded, it will only generate multiples of 210. To compensate this, notice , which means we need terms with a power of a 90 to acheive what we want (300 and larger values can be shown to be impossible upon inspection). This implies that the first two brackets do not contribute and we are left with
This reduces to finding the coefficient of for the expansion , which is
Solution 5 (Similar to solution 1)
Expand the numerator and divide each term in the denominator separately to get
Since the factor of is too big so we choose the -1 from both the 2 factors to get a 1. So now we need to find the number of quadruples of non negative integers such that . By considering modulo , , , we can reduce the above expression to something that can be solved using stars-and-bars.
.
Now we put in , , and to get
By stars-and-bars the answer is .
~Lakshya Pamecha
Video Solution
~MathProblemSolvingSkills.com
Video Solution by The Power of Logic
See Also
2022 AIME II (Problems • Answer Key • Resources) | ||
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.