Difference between revisions of "2021 AIME I Problems/Problem 4"
Sugar rush (talk | contribs) |
|||
Line 2: | Line 2: | ||
Find the number of ways <math>66</math> 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. | Find the number of ways <math>66</math> 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== | + | ==Solution 1== |
Suppose we have <math>1</math> coin in the first pile. Then <math>(1, 2, 63), (1, 3, 62), \ldots, (1, 32, 33)</math> all work for a total of <math>31</math> piles. Suppose we have <math>2</math> coins in the first pile, then <math>(2, 3, 61), (2, 4, 60), \ldots, (2, 31, 33)</math> all work, for a total of <math>29</math>. Continuing this pattern until <math>21</math> coins in the first pile, we have the sum <math>31+29+28+26+25+\ldots+4+2+1=(31+28+25+22+\ldots+1)+(29+26+23+\ldots+2)=176+155=\boxed{331}</math>. | Suppose we have <math>1</math> coin in the first pile. Then <math>(1, 2, 63), (1, 3, 62), \ldots, (1, 32, 33)</math> all work for a total of <math>31</math> piles. Suppose we have <math>2</math> coins in the first pile, then <math>(2, 3, 61), (2, 4, 60), \ldots, (2, 31, 33)</math> all work, for a total of <math>29</math>. Continuing this pattern until <math>21</math> coins in the first pile, we have the sum <math>31+29+28+26+25+\ldots+4+2+1=(31+28+25+22+\ldots+1)+(29+26+23+\ldots+2)=176+155=\boxed{331}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | Let the three piles have <math>a, b, c</math> coins respectively. If we disregard order, then we just need to divide by <math>3! = 6</math> at the end. | ||
+ | |||
+ | We know <math>a + b + c = 66</math>. Since <math>a, b, c</math> are positive integers, there are <math>\binom{65}{2}</math> ways from Stars and Bars. | ||
+ | |||
+ | However, we must discard the cases where <math>a = b</math> or <math>a = c</math> or <math>b = c</math>. The three cases are symmetric, so we just take the first case and multiply by 3. We have <math>2a + c = 66 \implies a = 1, 2, \dots 32</math> for 32 solutions. Multiplying by 3, we will subtract 96 from our total. | ||
+ | |||
+ | But we undercounted where <math>a = b = c = 22</math>. This is first counted 1 time, then we subtract it 3 times, so we add it back twice. There is clearly only 1 way, for a total of 2. | ||
+ | |||
+ | Hence, the answer is <math>\frac{\binom{65}{2} - 96 + 2}{6} = \boxed{331}.</math> | ||
==See also== | ==See also== |
Revision as of 18:33, 11 March 2021
Contents
[hide]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
Let the three piles have coins respectively. If we disregard order, then we just need to divide by at the end.
We know . Since are positive integers, there are ways from Stars and Bars.
However, we must discard the cases where or or . The three cases are symmetric, so we just take the first case and multiply by 3. We have for 32 solutions. Multiplying by 3, we will subtract 96 from our total.
But we undercounted where . This is first counted 1 time, then we subtract it 3 times, so we add it back twice. There is clearly only 1 way, for a total of 2.
Hence, the answer is
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.