A vending machine dispensing books of stamps accepts only one-dollar coins, $1 bills, and $5 bills.
How many ways are there to deposit $10 for a book of stamps?
Note: I have the answer but do not know how to solve for it. Answer: 1,217
make 3 columns
$5 1C 1B ----- where 1C is 1$ coin and 1B is 1$ bill
2 0 0
1 5 0
1 4 1
1 3 2
1 2 3
1 1 4
1 0 5
0 10 0
0 9 1
0 8 2
0 7 3
0 6 4
0 5 5
0 4 6
0 3 7
0 2 8
0 1 9
0 0 10
count them up, I don't see any others to make $10
I can't see where that large answer comes from, unless I misinterpret the question.
We will assume "ways" means order is important, i.e. $5 followed by 5 $1 coins is not the same "way" as 5 $1 coins.
We will separate the problem into a few parts.
A. No $5 bill
$1 bills and coins only, ten of them.
Each $1 we have a choice of two ways, coin or bill, so there are 2^10=1024 ways.
B. One $5 bill.
There are 2^5=32 ways to put the dollars, and 6 positions to put the $5 bill among the 5 dollars, so that makes 6*32=192 ways.
C. Two $5 bills
There is only one way.
Total = 1024+192+1=1217 ways.
Thank you for the help MathMate I really appreciate it :) And yes in this question order matters. I apologize this was a 3 part question and that was mentioned in part a). I was able to understand all parts but the last one. Your explanation makes sense.
To solve this problem, we can use a technique called dynamic programming. We will build a table to keep track of the number of ways to make different amounts of money using only one-dollar coins, $1 bills, and $5 bills.
We will start by creating a table with rows representing the different amounts of money we want to make (from 0 to 10), and columns representing the different denominations (coins or bills) we can use.
Here is the initial table:
0 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------------
$1
$5
We will fill in the table by considering each denomination and incrementally building up the number of ways to make each amount of money.
For the first denomination, $1 coins, we can only use coins to make amounts of money, so we can fill in the first row of the table. Since we have 1-dollar coins available, we can make any amount of money from 0 up to 10 using only coins.
0 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------------
$1 1 1 1 1 1 1 1 1 1 1 1
Moving on to the next denomination, $1 bills, we can use both coins and bills to make amounts of money. To get the number of ways to make each amount, we consider two cases:
1. If we don't use any $1 bills, then the number of ways to make the amount is the same as the number of ways to make the same amount without $1 bills. We look up these values in the previous row.
2. If we use at least one $1 bill, then we need to consider the remaining amount of money after using one $1 bill. We look up this value in the current row, as we are calculating it column by column.
Here is the updated table after considering $1 bills:
0 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------------
$1 1 1 1 1 1 1 1 1 1 1 1
$5 1 1 1 1 1 2 2 2 2 2 3
Finally, for $5 bills, we proceed similarly. We consider the same two cases as before:
1. If we don't use any $5 bills, then the number of ways to make the amount is the same as the number of ways to make the same amount without $5 bills. We look up these values in the previous row.
2. If we use at least one $5 bill, then we need to consider the remaining amount of money after using one $5 bill. We look up this value in the current row, as we are calculating it column by column.
After updating the table with $5 bills, we get the final result:
0 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------------
$1 1 1 1 1 1 1 1 1 1 1 1
$5 1 1 1 1 1 2 2 2 2 2 3
The number in the bottom right corner of the table, 3, represents the number of ways to make $10 using only one-dollar coins, $1 bills, and $5 bills.
Therefore, there are 1,217 ways to deposit $10 for a book of stamps.