Difference between revisions of "2023 AMC 10B Problems/Problem 11"
m |
|||
(36 intermediate revisions by 16 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==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> | ||
+ | |||
==Solution 1== | ==Solution 1== | ||
Line 15: | 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> | ||
− | ~ | + | ~Technodoggo ~minor edits by lucaswujc |
− | == Solution 2 | + | ==Solution 2== |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
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 69: | 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 4== | ||
+ | |||
+ | 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 | ||
+ | {{AMC10 box|year=2023|ab=B|num-b=10|num-a=12}} |
Latest revision as of 21:44, 24 August 2024
Contents
Problem
Suzanne went to the bank and withdrew . The teller gave her this amount using
bills,
bills, and
bills, with at least one of each denomination. How many different collections of bills could Suzanne have received?
Solution 1
We let the number of ,
, and
bills be
and
respectively.
We are given that Dividing both sides by
, we see that
We divide both sides of this equation by :
Since
and
are integers,
must also be an integer, so
must be divisible by
. Let
where
is some positive integer.
We can then write Dividing both sides by
, we have
We divide by
here to get
and
are both integers, so
is also an integer.
must be divisible by
, so we let
.
We now have . 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
and
such that they add to
.
We still have another constraint left, that each of and
must be at least
. For
, let
We are now looking for how many ways we can have
We use a classic technique for solving these sorts of problems: stars and bars. We have stars and
groups, which implies
bars. Thus, the total number of ways is
~Technodoggo ~minor edits by lucaswujc
Solution 2
Denote by ,
,
the amount of $20 bills, $50 bills and $100 bills, respectively.
Thus, we need to find the number of tuples
with
that satisfy
First, this equation can be simplified as
Second, we must have . Denote
.
The above equation can be converted to
Third, we must have . Denote
.
The above equation can be converted to
Denote ,
and
.
Thus, the above equation can be written as
Therefore, the number of non-negative integer solutions is
.
~stephen chen (Professor Chen Education Palace, www.professorchenedu.com)
Solution 3
To start, we simplify things by dividing everything by , the resulting equation is
, and since the problem states that we have at least one of each, we simplify this to
. Note that since the total is odd, we need an odd number of
dollar bills. We proceed using casework.
Case 1: One dollar bill
, we see that
can be
or
.
Ways
Case 2: Three dollar bills
, like before we see that
can be
, so
way.
Now we should start to see a pattern emerges, each case there is less way to sum to
, so the answer is just
,
or
~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
~not_slay
Solution 5 (generating functions)
The problem is equivalent to the number of ways to make from
bills,
bills, and
bills. We can use generating functions to find the coefficient of
:
The bills provide
The bills provide
The bills provide
Multiplying, we get
Video Solution 1 by OmegaLearn
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
~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 |