2021 AIME I Problems/Problem 4
Contents
Problem
Find the number of ways identical coins can be separated into three nonempty piles so that there are fewer coins in the first pile than in the second pile and fewer coins in the second pile than in the third pile.
Solution 1
Suppose we have coin in the first pile. Then all work for a total of piles. Suppose we have coins in the first pile, then all work, for a total of . Continuing this pattern until coins in the first pile, we have the sum
Solution 2
We make an equation: where We don't have a clear solution, so we'll try complementary counting. First, let's find where By stars and bars, we have to assign positive integer solutions to Now we need to subtract off the cases where it doesn't satisfy the condition.
We start with We can write that as We can find there are 32 integer solutions to this equation. There are solutions for and by symmetry. We also need to add back because we subtracted times.
We then have to divide by because there are ways to order and Therefore, we have
~Arcticturn
Solution 3
Let the piles have and coins, with . Then, let , and , such that each . The sum is then . This is simply the number of positive solutions to the equation . Now, we take cases on .
If , then . Each value of corresponds to a unique value of , so there are solutions in this case. Similarly, if , then , for a total of solutions in this case. If , then , for a total of solutions. In general, the number of solutions is just all the numbers that aren't a multiple of , that are less than or equal to .
We then add our cases to get as our answer.
Solution 4
Let the first pile have coins, the second coins, and the third coins, where , , and are strictly positive integers. Thus the total number of coins is . Perform the substitution , , and to yield the equation , where , , and are instead nonnegative integers.
From here we can set up the generating function . We need to find the coefficient of . Multiplying the second and third polynomials with clever reasoning returns
where in the second polynomial, for every two terms, the coefficient increases or decreases by one (depending on which side of the polynomial the term resides).
One can notice here that for every term in the first polynomial there exists one and only one term in the second polynomial that, when multiplied, yield . Furthermore, we need only consider the coefficients of the second polynomial.
The corresponding coefficient for is , for is , and for is . We notice the pattern: increase by one, increase by two, and so on. When does this pattern stop? For , the corresponding coefficient is , and we notice that . As a result, we know that the pattern has terms, and we can take advantage of the first by symmetry.
The answer is simply .
~eevee9406
Video Solution
~MathProblemSolvingSkills.com
Video Solution
https://youtu.be/M3DsERqhiDk?t=1073
See Also
2021 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
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.