2021 AIME I Problems/Problem 4
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.
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
We make an equation: where We don't have a clear solution, so we'll try complementary counting. First, let's find where We have by stars and bars for Now we need to subtract off the cases where it doesn't satisfy the condition.
We first by starting out 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 for times.
We then have to divide by because there are ways to order the and Therefore, we have
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.
|2021 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|