I went into the bank to get change for a dollar. The teller said, "How do you want the change, buddy? I mean, there are 292 ways involving pennies, nickels, dimes, quarters, and half-dollars to give change for a dollar!"
Since I didn't like her attitude, I didn't answer her question. I simply said, "Well, I certainly don't want any pennies."
How many ways are there for her to give me change now?
(Note: Americans, always shunning simplicity have chosen to name their coins in the following easy-to-remember manner: Penny=1 cent, Nickel=5 cents, Dime=10 cents, Quarter=25 cents, Half Dollar=50 cents)
(In reply to
Challenge by DJ)
I know this is an old problem, but it is a classic that happened to be on my mind recently.
Lets build up the number of ways recursively, one denomination at a time, starting with the smallest and working up. Also I'm only going to look at multiples of 5 since that is what is actually important. (A spreadsheet is very useful to make the calculations quickly.)
Trivially there is exactly one way to make some quantity using just nickels.
Total: 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Nickels: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Then lets add the dimes. Either there is a dime in the change or there is not. In the first case we just add one dime to the amount of change from 10 cents less, otherwise we are just taking the nickels only change.
More mathematically, If D(n) is the number of ways to make change out of dimes and nickels then D(n) = D(n-10)+1.
Total: 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Nickels: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
N+Dimes: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
Now onto quarters. By a similar argument as with the dimes we can define Q(n) as the way to make change out of quarters, dimes and nickels, where Q(n) = Q(n-25) + D(n).
Total: 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Nickels: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
N+Dimes: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
N+D+Quarters: 1 2 2 3 4 5 6 7 8 10 11 13 14 16 18 20 22 24 26 29
Then the half-dollars. Same as before we can define H(n) as the way to make change out of half-dollars, quarters, dimes and nickels, where H(n) = H(n-25) + Q(n).
Total: 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Nickels: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
N+Dimes: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
N+D+Quarters: 1 2 2 3 4 5 6 7 8 10 11 13 14 16 18 20 22 24 26 29
N+D+Q+Half-Ds: 1 2 2 3 4 5 6 7 8 11 12 15 16 19 22 25 28 31 34 40
And there at the end of the last row is our answer 40 ways.
Just for fun, lets do this again with the pennies! Just the final table:
Total: 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Pennies: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
P+Nickels: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
P+N+Dimes: 2 4 6 9 12 16 20 25 30 36 42 49 56 64 72 81 90 100 110 121
P+N+D+Quarters: 2 4 6 9 13 18 24 31 39 49 60 73 87 103 121 141 163 187 213 242
P+N+D+Q+Half-Ds: 2 4 6 9 13 18 24 31 39 50 62 77 93 112 134 159 187 218 252 292
And now we have confirmed the 292 ways stated in the flavor text.
re: Challenge Accepted (Solution)
