Difference between revisions of "2023 AMC 10B Problems/Problem 11"
m (→Solution 4) |
m (→Solution 5) |
||
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. |
Revision as of 18:58, 1 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 6 (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
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)