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"
(→‎Solution 6 (Very easy, PM me if you have any questions))
Line 106: Line 106:
 
Multiplying, we get <math>(1-x^{2})^{-1}(1-x^{5})^{-1}(1-x^{10})^{-1}.</math>
 
Multiplying, we get <math>(1-x^{2})^{-1}(1-x^{5})^{-1}(1-x^{10})^{-1}.</math>
  
−
== Solution 6 (stars and bars and logic) ==
+
== Solution 6 (easy logic) ==
  
−
We know that there must be a least one type of each bill, so we subtract those bills from the total, <math>800-</math>100-<math>50-</math>20=<math>630. After subtracting the bills we are left with </math>630. Since there is only one way to get <math>130 with these bills which is 1x</math>50+4x<math>20, we can remove this from </math>630 as well leaving us with <math>500. Each </math>100 can either be formed using 1 <math>100, 2 </math>50's, or 5 <math>20's, because we have 5 </math>100's we can split them up into three groups each corresponding to a way to form <math>100, we then use stars and bars to find out how many ways there are to put 5 hundred's into three groups, and using stars and bars we get </math>\dbinom{5+2}2=\dbinom72=21. So the answer is 21 ways.
+
We can see in the problem that the teller gave her at least one of <math>20, </math>50, and <math>100. Therefore, she has </math>800 - <math>20 - </math>50 - <math>100 = </math>630 "left over".
  
 +
Since all bills and <math>630 are multiples of 10, we can divide by ten.
 +
==> Question becomes: How many different collections of </math>2, <math>5, and </math>10 could she get if her total was <math>63?
 +
 +
We notice that because 63 is odd, we need an odd amount of </math>5 bills. (<math>2 and </math>10 are both even, and 63 is not a multiple of 5, so we need <math>2 and/or </math>10 bills. PM SwordAxe if you don't get this.)
 +
 +
We can do casework.
 +
 +
1: She gets one <math>5 (</math>50) dollar bill.
 +
She has <math>58 (</math>580) left.
 +
  1) She is given only <math>2 (</math>20) bills => ONE COLLECTION (all <math>20 bills with one </math>50)
 +
  2) She is given one <math>10 (</math>100) bill
 +
      1. The rest of the money is given in <math>2 (</math>20) dollar bills. => ONE COLLECTION (one <math>100 and rest </math>20 with one <math>50)
 +
      2. She is given another </math>10 (<math>100) bill
 +
            I) The rest of the money is given in </math>2 (<math>20) dollar bills. => ONE COLLECTION (two </math>100, one <math>50, and rest </math>20)
 +
            II) She is given another <math>10 (</math>100) bill
 +
                    a) The rest of the money is given in <math>2 (</math>20) dollar bills. => ONE COLLECTION (three <math>100, one </math>50, and rest <math>20)
 +
                    b) She is given another </math>10 (<math>100) bill.
 +
                          1) The rest of the money is given in </math>2 (<math>20) dollar bills  => ONE COLLECTION (following same pattern)
 +
                          2)  AND SO ON...
 +
 +
This looks very tedious, but draw a simple tree diagram, and you'll see that its very easy!
 +
 +
If she gets one </math>50, there are 6 ways
 +
If she gets three <math>50, there are 5 ways
 +
...
 +
If she gets nine </math>50, there are 2 ways
 +
If she gets eleven $50, there is one way
 +
 +
We can add them all up, with a grand sum of 6+5+4+3+2+1 = 21.
 +
 +
Therefore, we get the answer (B) 21.
 +
 +
~SwordAxe (PM me if you have any questions! :))
  
 
==Video Solution 1 by OmegaLearn==
 
==Video Solution 1 by OmegaLearn==

Revision as of 12:28, 29 July 2025

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 $0,10,20,30,40,50$ or $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$ ways

Now we should start to see a pattern emerge, 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 \cdots = \frac{1}{1-x^2},$

The $$5$ bills provide $1+x^5+x^{10}+x^{15} \cdots = \frac{1}{1-x^5},$

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

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

Solution 6 (easy logic)

We can see in the problem that the teller gave her at least one of $20,$50, and $100. Therefore, she has$800 - $20 -$50 - $100 =$630 "left over".

Since all bills and $630 are multiples of 10, we can divide by ten. ==> Question becomes: How many different collections of$2, $5, and$10 could she get if her total was $63?

We notice that because 63 is odd, we need an odd amount of$ (Error compiling LaTeX. Unknown error_msg)5 bills. ($2 and$10 are both even, and 63 is not a multiple of 5, so we need $2 and/or$10 bills. PM SwordAxe if you don't get this.)

We can do casework.

1: She gets one $5 ($50) dollar bill. She has $58 ($580) left. 

 1) She is given only $2 ($20) bills => ONE COLLECTION (all $20 bills with one$50)
 2) She is given one $10 ($100) bill
      1. The rest of the money is given in $2 ($20) dollar bills. => ONE COLLECTION (one $100 and rest$20 with one $50)        2. She is given another$10 ($100) bill              I) The rest of the money is given in$2 ($20) dollar bills. => ONE COLLECTION (two$100, one $50, and rest$20)
            II) She is given another $10 ($100) bill
                   a) The rest of the money is given in $2 ($20) dollar bills. => ONE COLLECTION (three $100, one$50, and rest $20)                     b) She is given another$10 ($100) bill.                           1) The rest of the money is given in$2 ($20) dollar bills  => ONE COLLECTION (following same pattern)
                         2)  AND SO ON...

This looks very tedious, but draw a simple tree diagram, and you'll see that its very easy!

If she gets one$ (Error compiling LaTeX. Unknown error_msg)50, there are 6 ways If she gets three $50, there are 5 ways ... If she gets nine$50, there are 2 ways If she gets eleven $50, there is one way

We can add them all up, with a grand sum of 6+5+4+3+2+1 = 21.

Therefore, we get the answer (B) 21.

~SwordAxe (PM me if you have any questions! :))

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 4

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

2023 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AMC_10B_Problems/Problem_11&oldid=255883"