Difference between revisions of "2021 AIME I Problems/Problem 4"

(Solution 4)
m
(7 intermediate revisions by 2 users not shown)
Line 3: Line 3:
  
 
==Solution 1==
 
==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)+</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  
 
+
<cmath>\begin{align*}
<math>(29+26+23+\ldots+2)=176+155=\boxed{331}</math>.
+
31+29+28+26+25+\cdots+4+2+1 &= (31+28+25+22+\cdots+1)+(29+26+23+\cdots+2) \\
 +
&= 176+155 \\
 +
&= \boxed{331}.
 +
\end{align*}</cmath>
  
 
==Solution 2==
 
==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.
+
We make an equation: <math>a+b+c=66,</math> where <math>a<b<c.</math> We don't have a clear solution, so we'll try complementary counting. First, let's find where <math>a\geq b\geq c.</math> We have <math>\dbinom{65}{2}=2080</math> by stars and bars for <math>a>b>c.</math> Now we need to subtract off the cases where it doesn't satisfy the condition.
  
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.
+
We first by starting out with <math>a = b.</math> We can write that as <math>2b + c = 66.</math> We can find there are 32 integer solutions to this equation. There are <math>32</math> solutions for <math>b=c</math> and <math>a = c</math> by symmetry. We also need to add back <math>2</math> because we subtracted <math>(a,b,c)=(22,22,22)</math> for <math>3</math> times.
 +
 +
We then have to divide by <math>6</math> because there are <math>3!=6</math> ways to order the <math>a, b,</math> and <math>c.</math> Therefore, we have <math>\dfrac{\dbinom{65}{2}-96+2}{6} = \dfrac{1986}{6} = \boxed{331}.</math>
  
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.
+
~Arcticturn
 
 
Hence, the answer is <math>\frac{\binom{65}{2} - 96 + 2}{6} = \boxed{331}.</math>
 
  
 
==Solution 3==
 
==Solution 3==
Line 23: Line 25:
 
If <math>a = 1</math>, then <math>2k_1 + k_2 = 63 \implies 1 \leq k_1 \leq 31</math>. Each value of <math>k_1</math> corresponds to a unique value of <math>k_2</math>, so there are <math>31</math> solutions in this case. Similarly, if <math>a = 2</math>, then <math>2k_1 + k_2 = 60 \implies 1 \leq k_1 \leq 29</math>, for a total of <math>29</math> solutions in this case. If <math>a = 3</math>, then <math>2k_1 + k_1 = 57 \implies 1 \leq k_1 \leq 28</math>, for a total of <math>28</math> solutions. In general, the number of solutions is just all the numbers that aren't a multiple of <math>3</math>, that are less than or equal to <math>31</math>.  
 
If <math>a = 1</math>, then <math>2k_1 + k_2 = 63 \implies 1 \leq k_1 \leq 31</math>. Each value of <math>k_1</math> corresponds to a unique value of <math>k_2</math>, so there are <math>31</math> solutions in this case. Similarly, if <math>a = 2</math>, then <math>2k_1 + k_2 = 60 \implies 1 \leq k_1 \leq 29</math>, for a total of <math>29</math> solutions in this case. If <math>a = 3</math>, then <math>2k_1 + k_1 = 57 \implies 1 \leq k_1 \leq 28</math>, for a total of <math>28</math> solutions. In general, the number of solutions is just all the numbers that aren't a multiple of <math>3</math>, that are less than or equal to <math>31</math>.  
  
We then add our cases to get <cmath>1 + 2 + 4 + 5 + \cdots + 31 = 1 + 2 + 3 + \cdots + 31 - 3(1 + 2 + 3 + \cdots + 10) = \frac{31(32)}{2} - 3(55) = 31 \cdot 16 - 165 = 496 - 165 = \boxed{331}</cmath> as our answer.
+
We then add our cases to get  
 +
<cmath>\begin{align*}
 +
1 + 2 + 4 + 5 + \cdots + 31 &= 1 + 2 + 3 + \cdots + 31 - 3(1 + 2 + 3 + \cdots + 10) \\
 +
&= \frac{31(32)}{2} - 3(55) \\
 +
&= 31 \cdot 16 - 165 \\
 +
&= 496 - 165 \\
 +
&= \boxed{331}
 +
\end{align*}</cmath>
 +
as our answer.
  
==Solution 4==
 
  
We make an equation for how this is true. a+b+c = 66, where a is less than b, is less than c. We don't have a clear solution, so we'll try complementary counting. First, let's find where a doesn't have to be less than b, which doesn't have to be less than c. We have <math>\dbinom{65}{2}</math> =2080 by stars and bars. Now we need to subtract off the cases where it doesn't satisfy the condition.
+
==Video Solution ==
 +
https://youtu.be/f7KtovZ4GAk
  
We first by starting out with a = b. We can write that as 2b + c = 66. We can find there are 32 integer solutions to this equation. There are 32 solutions for b=c, and a = c by symmetry. We also need to subtract 2 from the 96, because we counted 22, 22, 22 3 times.
 
We then have to divide by 6 because there are 3! ways to order the a, b, and c. Therefore, we have <math>\dfrac{\dbinom{65}{2}-94}{6}</math> = <math>\dfrac{1986}{6} = </math><math>\boxed{331}</math>
 
  
~Arcticturn
 
  
==Video Solution #1 ==
+
==Video Solution ==
 
https://youtu.be/M3DsERqhiDk?t=1073
 
https://youtu.be/M3DsERqhiDk?t=1073
  

Revision as of 18:10, 26 May 2022

Problem

Find the number of ways $66$ 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 $1$ coin in the first pile. Then $(1, 2, 63), (1, 3, 62), \ldots, (1, 32, 33)$ all work for a total of $31$ piles. Suppose we have $2$ coins in the first pile, then $(2, 3, 61), (2, 4, 60), \ldots, (2, 31, 33)$ all work, for a total of $29$. Continuing this pattern until $21$ coins in the first pile, we have the sum \begin{align*} 31+29+28+26+25+\cdots+4+2+1 &= (31+28+25+22+\cdots+1)+(29+26+23+\cdots+2) \\ &= 176+155 \\ &= \boxed{331}. \end{align*}

Solution 2

We make an equation: $a+b+c=66,$ where $a<b<c.$ We don't have a clear solution, so we'll try complementary counting. First, let's find where $a\geq b\geq c.$ We have $\dbinom{65}{2}=2080$ by stars and bars for $a>b>c.$ Now we need to subtract off the cases where it doesn't satisfy the condition.

We first by starting out with $a = b.$ We can write that as $2b + c = 66.$ We can find there are 32 integer solutions to this equation. There are $32$ solutions for $b=c$ and $a = c$ by symmetry. We also need to add back $2$ because we subtracted $(a,b,c)=(22,22,22)$ for $3$ times.

We then have to divide by $6$ because there are $3!=6$ ways to order the $a, b,$ and $c.$ Therefore, we have $\dfrac{\dbinom{65}{2}-96+2}{6} = \dfrac{1986}{6} = \boxed{331}.$

~Arcticturn

Solution 3

Let the piles have $a, b$ and $c$ coins, with $0 < a < b < c$. Then, let $b = a + k_1$, and $c = b + k_2$, such that each $k_i \geq 1$. The sum is then $a + a+k_1 + a+k_1+k_2 = 66 \implies 3a+2k_1 + k_2 = 66$. This is simply the number of positive solutions to the equation $3x+2y+z = 66$. Now, we take cases on $a$.

If $a = 1$, then $2k_1 + k_2 = 63 \implies 1 \leq k_1 \leq 31$. Each value of $k_1$ corresponds to a unique value of $k_2$, so there are $31$ solutions in this case. Similarly, if $a = 2$, then $2k_1 + k_2 = 60 \implies 1 \leq k_1 \leq 29$, for a total of $29$ solutions in this case. If $a = 3$, then $2k_1 + k_1 = 57 \implies 1 \leq k_1 \leq 28$, for a total of $28$ solutions. In general, the number of solutions is just all the numbers that aren't a multiple of $3$, that are less than or equal to $31$.

We then add our cases to get \begin{align*} 1 + 2 + 4 + 5 + \cdots + 31 &= 1 + 2 + 3 + \cdots + 31 - 3(1 + 2 + 3 + \cdots + 10) \\ &= \frac{31(32)}{2} - 3(55) \\ &= 31 \cdot 16 - 165 \\ &= 496 - 165 \\ &= \boxed{331} \end{align*} as our answer.


Video Solution

https://youtu.be/f7KtovZ4GAk


Video Solution

https://youtu.be/M3DsERqhiDk?t=1073

See Also

2021 AIME I (ProblemsAnswer KeyResources)
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. AMC logo.png