Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Problem)
(→‎Video Solution)
 
(24 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
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 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
 +
<cmath>\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*}</cmath>
 +
 +
==Solution 2==
 +
 +
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> By stars and bars, we have <math>\dbinom{65}{2}=2080</math> to assign positive integer solutions to <math>a + b + c = 66.</math> Now we need to subtract off the cases where it doesn't satisfy the condition.
 +
 +
We start 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> <math>3</math> times.
 +
 +
We then have to divide by <math>6</math> because there are <math>3!=6</math> ways to order <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>
 +
 +
~Arcticturn
 +
 +
==Solution 3==
 +
Let the piles have <math>a, b</math> and <math>c</math> coins, with <math>0 < a < b < c</math>. Then, let <math>b = a + k_1</math>, and <math>c = b + k_2</math>, such that each <math>k_i \geq 1</math>. The sum is then <math>a + a+k_1 + a+k_1+k_2 = 66 \implies 3a+2k_1 + k_2 = 66</math>. This is simply the number of positive solutions to the equation <math>3x+2y+z = 66</math>. Now, we take cases on <math>a</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_2 = 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>\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==
 
==Solution 4==
 +
Let the first pile have <math>a</math> coins, the second <math>a+b</math> coins, and the third <math>a+b+c</math> coins, where <math>a</math>, <math>b</math>, and <math>c</math> are strictly positive integers. Thus the total number of coins is <math>3a+2b+c=66</math>. Perform the substitution <math>x=a-1</math>, <math>y=b-1</math>, and <math>z=c-1</math> to yield the equation <math>3x+2y+z=60</math>, where <math>x</math>, <math>y</math>, and <math>z</math> are instead nonnegative integers.
  
−
==Solution 1==
+
From here we can set up the [[generating function]] <math>(x^0+x^3+\cdots+x^{60})(x^0+x^2+\cdots+x^{60})(x^0+x^1+\cdots+x^{60})</math>. We need to find the coefficient of <math>x^{60}</math>. Multiplying the second and third polynomials with clever reasoning returns
−
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>
 
  
−
<math>(29+26+23+\ldots+2)=176+155=\boxed{331}</math>.
+
<math>(x^0+x^3+\cdots+x^{60})(x^0+x^1+2x^2+2x^3+\cdots+31x^{60}+\cdots+2x^{117}+2x^{118}+x^{119}+x^{120})</math>
  
−
(Minor edit to make everything fit in the page made by KingRavi)
+
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).
  
−
==Solution 2==
+
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 <math>x^{60}</math>. Furthermore, we need only consider the <u>coefficients</u> of the second polynomial.
−
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.
+
The corresponding coefficient for <math>x^{60}</math> is <math>1</math>, for <math>x^{57}</math> is <math>2</math>, and for <math>x^{54}</math> is <math>4</math>. We notice the pattern: increase by one, increase by two, and so on. When does this pattern stop? For <math>x^0</math>, the corresponding coefficient is <math>31</math>, and we notice that <math>31\equiv1\mod3</math>. As a result, we know that the pattern has <math>21</math> terms, and we can take advantage of the first <math>20</math> by symmetry.
  
−
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.
+
The answer is simply <math>10(1+29)+31=\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.
+
~eevee9406
  
−
Hence, the answer is <math>\frac{\binom{65}{2} - 96 + 2}{6} = \boxed{331}.</math>
+
Solution 4
  
−
==Solution 3==
 
−
Let the piles have <math>a, b</math> and <math>c</math> coins, with <math>0 < a < b < c</math>. Then, let <math>b = a + k_1</math>, and <math>c = b + k_2</math>, such that each <math>k_i \geq 1</math>. The sum is then <math>a + a+k_1 + a+k_1+k_2 = 66 \implies 3a+2k_1 + k_2 = 66</math>. This is simply the number of positive solutions to the equation <math>3x+2y+z = 66</math>. Now, we take cases on <math>a</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>.
+
==Video Solution ==
 +
https://youtu.be/f7KtovZ4GAk
  
−
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.
+
~MathProblemSolvingSkills.com
 +
**
  
−
==Video Solution #1 ==
+
==Video Solution ==
 
https://youtu.be/M3DsERqhiDk?t=1073
 
https://youtu.be/M3DsERqhiDk?t=1073
  
−
==See also==
+
==See Also==
 
{{AIME box|year=2021|n=I|num-b=3|num-a=5}}
 
{{AIME box|year=2021|n=I|num-b=3|num-a=5}}
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 19:09, 7 August 2024

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.$ By stars and bars, we have $\dbinom{65}{2}=2080$ to assign positive integer solutions to $a + b + c = 66.$ Now we need to subtract off the cases where it doesn't satisfy the condition.

We start 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)$ $3$ times.

We then have to divide by $6$ because there are $3!=6$ ways to order $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_2 = 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.

Solution 4

Let the first pile have $a$ coins, the second $a+b$ coins, and the third $a+b+c$ coins, where $a$, $b$, and $c$ are strictly positive integers. Thus the total number of coins is $3a+2b+c=66$. Perform the substitution $x=a-1$, $y=b-1$, and $z=c-1$ to yield the equation $3x+2y+z=60$, where $x$, $y$, and $z$ are instead nonnegative integers.

From here we can set up the generating function $(x^0+x^3+\cdots+x^{60})(x^0+x^2+\cdots+x^{60})(x^0+x^1+\cdots+x^{60})$. We need to find the coefficient of $x^{60}$. Multiplying the second and third polynomials with clever reasoning returns

$(x^0+x^3+\cdots+x^{60})(x^0+x^1+2x^2+2x^3+\cdots+31x^{60}+\cdots+2x^{117}+2x^{118}+x^{119}+x^{120})$

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 $x^{60}$. Furthermore, we need only consider the coefficients of the second polynomial.

The corresponding coefficient for $x^{60}$ is $1$, for $x^{57}$ is $2$, and for $x^{54}$ is $4$. We notice the pattern: increase by one, increase by two, and so on. When does this pattern stop? For $x^0$, the corresponding coefficient is $31$, and we notice that $31\equiv1\mod3$. As a result, we know that the pattern has $21$ terms, and we can take advantage of the first $20$ by symmetry.

The answer is simply $10(1+29)+31=\boxed{331}$.

~eevee9406

Solution 4


Video Solution

https://youtu.be/f7KtovZ4GAk

~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_4&oldid=224716"