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 "2023 AMC 10B Problems/Problem 11"
m (→‎Solution 6 (generating functions))
(33 intermediate revisions by 14 users not shown)
Line 1: Line 1:
−
Suzanne went to the bank and withdrew <math>\$800</math>. The teller gave her this ammount using <math>\$20</math> bills, <math>\$50</math> bills, and <math>\$100</math> bills, with at least one of each denomination. How many different collections of bills could Suzanne have received?
+
==Problem==
 +
Suzanne went to the bank and withdrew <math>\$800</math>. The teller gave her this amount using <math>\$20</math> bills, <math>\$50</math> bills, and <math>\$100</math> bills, with at least one of each denomination. How many different collections of bills could Suzanne have received?
  
 
<math>\textbf{(A) } 45 \qquad \textbf{(B) } 21 \qquad \text{(C) } 36 \qquad \text{(D) } 28 \qquad \text{(E) } 32</math>
 
<math>\textbf{(A) } 45 \qquad \textbf{(B) } 21 \qquad \text{(C) } 36 \qquad \text{(D) } 28 \qquad \text{(E) } 32</math>
Line 19: Line 20:
 
We use a classic technique for solving these sorts of problems: stars and bars. We have <math>5</math> stars and <math>3</math> groups, which implies <math>2</math> bars. Thus, the total number of ways is <math>\dbinom{5+2}2=\dbinom72=21.</math>  
 
We use a classic technique for solving these sorts of problems: stars and bars. We have <math>5</math> stars and <math>3</math> groups, which implies <math>2</math> bars. Thus, the total number of ways is <math>\dbinom{5+2}2=\dbinom72=21.</math>  
  
−
~<math>\textbf{Techno}\textcolor{red}{doggo}</math> ~minor edits by lucaswujc
+
~Technodoggo ~minor edits by lucaswujc
  
−
== Solution 2 ==
+
==Solution 2==
−
 
 
−
First, we note that there can only be an even number of <math>50</math> dollar bills.
 
−
 
 
−
Next, since there is at least one of each bill, we find that the amount of <math>50</math> dollar bills is between <math>2</math> and <math>12</math>. Doing some casework, we find that the amount of <math>100</math> dollar bills forms an arithmetic sequence: <math>6</math> + <math>5</math> + <math>4</math> + <math>3</math> + <math>2</math> + <math>1</math>.
 
−
 
 
−
Adding these up, we get <math>21</math>.
 
−
 
 
−
~yourmomisalosinggame (a.k.a. Aaron)
 
−
 
 
−
==Solution 3==
 
  
 
Denote by <math>x</math>, <math>y</math>, <math>z</math> the amount of \$20 bills, \$50 bills and \$100 bills, respectively.
 
Denote by <math>x</math>, <math>y</math>, <math>z</math> the amount of \$20 bills, \$50 bills and \$100 bills, respectively.
Line 73: Line 64:
  
 
Therefore, the number of non-negative integer solutions <math>\left( x'', y'', z'' \right)</math> is <math>\binom{5 + 3 - 1}{3 - 1} = \boxed{\textbf{(B) 21}}</math>.
 
Therefore, the number of non-negative integer solutions <math>\left( x'', y'', z'' \right)</math> is <math>\binom{5 + 3 - 1}{3 - 1} = \boxed{\textbf{(B) 21}}</math>.
 +
 +
~stephen chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
== Solution 3 ==
 +
To start, we simplify things by dividing everything by <math>10</math>, the resulting equation is <math>2x+5y+10z=80</math>, and since the problem states that we have at least one of each, we simplify this to <math>2x+5y+10z=63</math>. Note that since the total is odd, we need an odd number of <math>5</math> dollar bills. We proceed using casework.
 +
 +
Case 1: One <math>5</math> dollar bill
 +
 +
<math>2x+10z=58</math>, we see that <math>10z</math> can be <math>10,20,30,40,50 </math>  or <math>0</math>.
 +
<math>6</math> Ways
 +
 +
Case 2: Three <math>5</math> dollar bills
 +
 +
<math>2x+10z=48</math>, like before we see that <math>10z</math> can be <math>0,10,20,30,40</math>, so <math>5</math> way.
 +
 +
Now we should start to see a pattern emerges, each case there is <math>1</math> less way to sum to <math>80</math>, so the answer is just <math>\frac{6(6+1)}{2}</math>, <math>21</math> or <math>(B)</math>
 +
 +
~andyluo
 +
 +
==Solution 4==
 +
 +
We notice that each \$100 can be split 3 ways: 5 \$20 dollar bills, 2 \$50 dollar bills, or 1 \$100 dollar bill.
 +
 +
There are 8 of these \$100 chunks in total--take away 3 as each split must be used at least once.
 +
 +
Now there are five left--so we use stars and bars.
 +
 +
5 chunks, 3 categories or 2 bars. This gives us <math>\binom{5+2}{2}=\boxed{\textbf{(B) 21}}</math>
 +
 +
~not_slay
 +
 +
== Solution 5 (generating functions) ==
 +
 +
The problem is equivalent to the number of ways to make <math>\$80</math> from <math>\$2</math> bills, <math>\$5</math> bills, and <math>\$10</math> bills. We can use generating functions to find the coefficient of <math>x^{80}</math>:
 +
 +
The <math>\$2</math> bills provide <math>1+x^2+x^4+x^6...+x^{78}+x^{80} = \frac{1-x^{82}}{1-x^2},</math>
 +
 +
The <math>\$5</math> bills provide <math>1+x^5+x^{10}+x^{15}...+x^{75}+x^{80} = \frac{1-x^{85}}{1-x^5},</math>
 +
 +
The <math>\$10</math> bills provide <math>1+x^{10}+x^{20}+x^{30}...+x^{70}+x^{80} = \frac{1-x^{90}}{1-x^{10}}.</math>
 +
 +
Multiplying, we get <math>(x^{82}-1)(x^{85}-1)(x^{90}-1)(x^2-1)^{-1}(x^5-1)^{-1}(x^{10}-1)^{-1}.</math>
 +
 +
==Video Solution 1 by OmegaLearn==
 +
https://youtu.be/UeX3eEwRS9I
 +
 +
==Video Solution 2 by SpreadTheMathLove==
 +
https://www.youtube.com/watch?v=sfZRRsTimmE
 +
 +
==Video Solution 3 by paixiao==
 +
https://youtu.be/EvA2Nlb7gi4?si=fVLG8gMTIC5XkEwP&t=89s
 +
 +
==Video Solution==
 +
 +
https://youtu.be/D-ZvFBiZsaY
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
==Video Solution 5 by Lucas637==
 +
https://www.youtube.com/watch?v=kXLHjclTD44&t=27s

Revision as of 17:58, 1 July 2024

Problem

Suzanne went to the bank and withdrew $$800$. The teller gave her this amount using $$20$ bills, $$50$ bills, and $$100$ bills, with at least one of each denomination. How many different collections of bills could Suzanne have received?

$\textbf{(A) } 45 \qquad \textbf{(B) } 21 \qquad \text{(C) } 36 \qquad \text{(D) } 28 \qquad \text{(E) } 32$

Solution 1

We let the number of $$20$, $$50$, and $$100$ bills be $a,b,$ and $c,$ respectively.

We are given that $20a+50b+100c=800.$ Dividing both sides by $10$, we see that $2a+5b+10c=80.$

We divide both sides of this equation by $5$: $\dfrac25a+b+2c=16.$ Since $b+2c$ and $16$ are integers, $\dfrac25a$ must also be an integer, so $a$ must be divisible by $5$. Let $a=5d,$ where $d$ is some positive integer.

We can then write $2\cdot5d+5b+10c=80.$ Dividing both sides by $5$, we have $2d+b+2c=16.$ We divide by $2$ here to get $d+\dfrac b2+c=8.$ $d+c$ and $8$ are both integers, so $\dfrac b2$ is also an integer. $b$ must be divisible by $2$, so we let $b=2e$.

We now have $2d+2e+2c=16\implies d+e+c=8$. Every substitution we made is part of a bijection (i.e. our choices were one-to-one); thus, the problem is now reduced to counting how many ways we can have $d,e,$ and $c$ such that they add to $8$.

We still have another constraint left, that each of $d,e,$ and $c$ must be at least $1$. For $n\in\{d,e,c\}$, let $n'=n-1.$ We are now looking for how many ways we can have $d'+e'+c'=8-1-1-1=5.$

We use a classic technique for solving these sorts of problems: stars and bars. We have $5$ stars and $3$ groups, which implies $2$ bars. Thus, the total number of ways is $\dbinom{5+2}2=\dbinom72=21.$

~Technodoggo ~minor edits by lucaswujc

Solution 2

Denote by $x$, $y$, $z$ the amount of $20 bills, $50 bills and $100 bills, respectively. Thus, we need to find the number of tuples $\left( x , y, z \right)$ with $x, y, z \in \Bbb N$ that satisfy \[ 20 x + 50 y + 100 z = 800. \]

First, this equation can be simplified as \[ 2 x + 5 y + 10 z = 80. \]

Second, we must have $5 |x$. Denote $x = 5 x'$. The above equation can be converted to \[ 2 x' + y + 2 z = 16 . \]

Third, we must have $2 | y$. Denote $y = 2 y'$. The above equation can be converted to \[ x' + y' + z = 8 . \]

Denote $x'' = x' - 1$, $y'' = y' - 1$ and $z'' = z - 1$. Thus, the above equation can be written as \[ x'' + y'' + z'' = 5 . \]

Therefore, the number of non-negative integer solutions $\left( x'', y'', z'' \right)$ is $\binom{5 + 3 - 1}{3 - 1} = \boxed{\textbf{(B) 21}}$.

~stephen chen (Professor Chen Education Palace, www.professorchenedu.com)

Solution 3

To start, we simplify things by dividing everything by $10$, the resulting equation is $2x+5y+10z=80$, and since the problem states that we have at least one of each, we simplify this to $2x+5y+10z=63$. Note that since the total is odd, we need an odd number of $5$ dollar bills. We proceed using casework.

Case 1: One $5$ dollar bill

$2x+10z=58$, we see that $10z$ can be $10,20,30,40,50$ or $0$. $6$ Ways

Case 2: Three $5$ dollar bills

$2x+10z=48$, like before we see that $10z$ can be $0,10,20,30,40$, so $5$ way.

Now we should start to see a pattern emerges, each case there is $1$ less way to sum to $80$, so the answer is just $\frac{6(6+1)}{2}$, $21$ or $(B)$

~andyluo

Solution 4

We notice that each $100 can be split 3 ways: 5 $20 dollar bills, 2 $50 dollar bills, or 1 $100 dollar bill.

There are 8 of these $100 chunks in total--take away 3 as each split must be used at least once.

Now there are five left--so we use stars and bars.

5 chunks, 3 categories or 2 bars. This gives us $\binom{5+2}{2}=\boxed{\textbf{(B) 21}}$

~not_slay

Solution 5 (generating functions)

The problem is equivalent to the number of ways to make $$80$ from $$2$ bills, $$5$ bills, and $$10$ bills. We can use generating functions to find the coefficient of $x^{80}$:

The $$2$ bills provide $1+x^2+x^4+x^6...+x^{78}+x^{80} = \frac{1-x^{82}}{1-x^2},$

The $$5$ bills provide $1+x^5+x^{10}+x^{15}...+x^{75}+x^{80} = \frac{1-x^{85}}{1-x^5},$

The $$10$ bills provide $1+x^{10}+x^{20}+x^{30}...+x^{70}+x^{80} = \frac{1-x^{90}}{1-x^{10}}.$

Multiplying, we get $(x^{82}-1)(x^{85}-1)(x^{90}-1)(x^2-1)^{-1}(x^5-1)^{-1}(x^{10}-1)^{-1}.$

Video Solution 1 by OmegaLearn

https://youtu.be/UeX3eEwRS9I

Video Solution 2 by SpreadTheMathLove

https://www.youtube.com/watch?v=sfZRRsTimmE

Video Solution 3 by paixiao

https://youtu.be/EvA2Nlb7gi4?si=fVLG8gMTIC5XkEwP&t=89s

Video Solution

https://youtu.be/D-ZvFBiZsaY

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution 5 by Lucas637

https://www.youtube.com/watch?v=kXLHjclTD44&t=27s

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AMC_10B_Problems/Problem_11&oldid=221464"