Difference between revisions of "2023 AMC 10B Problems/Problem 11"
(→Video Solution by Lucas637) |
m (→Video Solution) |
||
(4 intermediate revisions by one other user not shown) | |||
Line 22: | Line 22: | ||
~Technodoggo ~minor edits by lucaswujc | ~Technodoggo ~minor edits by lucaswujc | ||
− | ==Solution | + | ==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 67: | Line 67: | ||
~stephen chen (Professor Chen Education Palace, www.professorchenedu.com) | ~stephen chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
− | == Solution | + | == 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. | 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. | ||
Line 83: | Line 83: | ||
~andyluo | ~andyluo | ||
− | ==Solution | + | ==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. | We notice that each \$100 can be split 3 ways: 5 \$20 dollar bills, 2 \$50 dollar bills, or 1 \$100 dollar bill. | ||
Line 95: | Line 95: | ||
~not_slay | ~not_slay | ||
− | == Solution | + | == 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 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>: | ||
Line 116: | Line 116: | ||
https://youtu.be/EvA2Nlb7gi4?si=fVLG8gMTIC5XkEwP&t=89s | https://youtu.be/EvA2Nlb7gi4?si=fVLG8gMTIC5XkEwP&t=89s | ||
− | ==Video Solution== | + | ==Video Solution 4== |
https://youtu.be/D-ZvFBiZsaY | https://youtu.be/D-ZvFBiZsaY |
Latest revision as of 15:56, 24 July 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)