Making Change - The Answer
How many unique ways are there to make change for a dollar?
This is a much harder problem than it initially seems. Credit goes to Kimota94 for attempting it - he had the right idea but used multiplication between the steps instead of addition which resulted in a much larger answer. Nobody else seemed brave enough to venture an answer.
I used a recursive approach to come up with the answer.
Let An be the number of ways to make n cents with pennies.
Let Bn be the number of ways to make n cents with pennies and nickels.
Let Cn be the number of ways to make n cents with pennies, nickels, and dimes.
Let Dn be the number of ways to make n cents with pennies, nickels, dimes, and quarters.
The question is asking us to find D100
The number of ways to make Dn when n >= 25 if at least 1 quarter is used is Dn-25, while the number of ways to make Dn when no quarter is used is Cn.
Therefore: Dn = Cn + Dn-25, n >= 25
Similarly:
Cn = Bn + Cn-10, n>=10
Bn = An + Bn-5, n>=5
It is obvious that An is always 1.
It is slightly less obvious, but fairly clear to see that Bn is 1+x where x is n/5 truncated to the integer portion of the quotient. We can show this obvious solution by proving it true for the first few values of n and then relying on the recursive definition above.
If n <>n = 1 (only pennies are possible). For n = 5, there are two choices: 1 nickel or 5 pennies. If 5 < n <>
Therefore B5 = 2, B10 = 3, B15 = 4, ..., B100=21.
We want D100, let's use some substitution here:
D100 = C100+D75
D100 = C100+C75+D50
D100 = C100+C75+C50+D25
D100 = C100+C75+C50+C25+1
Similarly:
C100 = B100+B90+B80+B70+B60+B50+B40+B30+B20+B10+1
C75 = B75+B65+B55+B45+B35+B25+B15+B5 (note no +1, since C5 = B5)
C50 = B50+B40+B30+B20+B10+1
C25 = B25+B15+B5
Substituting with the values of Bn in the formula above we see:
C100 = 21+19+17+15+13+11+9+7+5+3+1 = 121
C75 = 16+14+12+10+8+6+4+2 = 72
C50 = 11+9+7+5+3+1 = 36
C25 = 6+4+2 = 12
Finally:
D100 = C100+C75+C50+C25+1 = 121+72+36+12+1 = 242
So there are 242 ways to uniquely make change for $1 using pennies, nickels, dimes, and quarters.
4 comments:
If only I'd stuck with my original, brute force approach, I'd have gotten the right answer! I just finished it now, to see if I had been on the right track after all, and I got 242. Here's the approach I was using (no real algebra or recursion involved, sadly):
I looked at it in terms of how many Quarters, or Q's you used. So..
4 Q's has 1 combination only.
3 Q's has combinations involving 2 Dimes (2 D's), 1 D, or 0 D. When you have 2 D's, you're making up the remaining 5 cents in combos of Nickels (N's) and Pennies (P's). Since choosing the value for N dictates the value for P, you really only have to figure out how many N combinations there are. And that number is essentially 0 through x, where 5x is less than or equal to the remaining value after Q's and D's. For 5 cents, there are only 2 combinations (0 N's, 1 N).
When you have 3 Q's and 1 D, you're making up 15 cents in N's and P's, so there are 4 combinations (0 N's, 1 N, 2 N's, 3 N's).
And when you have 3 Q's and 0 D's, you're making up 25 cents, so there are 6 combinations.
Shortening my notation then:
4 Q's = 1 combination
3 Q's = (2 D's + 1 D + 0 D's) = 2 + 4 + 6 = 12
2 Q's = (5 D's + 4 D's + ... + 0 D's) = 1 (no N's or P's) + 3 (for 10 cents) + 5 (for 20 cents) + 7 (for 30 cents) + 9 (for 40 cents) + 11 (for 50 cents) = 36
1 Q's = (7 D's + 6 D's + ... + 0 D's) = 2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 = 72
0 Q's = (10 D's + 9 D's + ... + 0 D's) = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21 = 121
So all combinations = 1 + 12 + 36 + 72 + 121 = 242
When I was doing this the first time, I didn't hit on the fact that, when fixing the # of Q's, and then breaking down the possible # of D's for each, that I then only had to look at each increment of N's (since the # of P's is fixed by the # of N's). Instead, I stupidly thought I had cascading permutations, meaning that I had Q's fixed, then had to enumerate D's, and then N's within D's, and then P's within N's. Had I spent 10 more minutes following this path I might've even gotten the right answer.
Oh well... I guess I'm not the math whiz I was 25 years ago!
http://markonzo.edu Thank you, actual ashley furniture [url=http://jguru.com/guru/viewbio.jsp?EID=1536072]actual ashley furniture[/url], htimxf, watch allegiant air [url=http://jguru.com/guru/viewbio.jsp?EID=1536075]watch allegiant air[/url], lxrxame, best pressure washers [url=http://jguru.com/guru/viewbio.jsp?EID=1536078]best pressure washers[/url], judcn, follow dishnetwork [url=http://jguru.com/guru/viewbio.jsp?EID=1536080]follow dishnetwork[/url], ryjiim, fresh adt security [url=http://jguru.com/guru/viewbio.jsp?EID=1536076]fresh adt security[/url], erawcl,
http://lumerkoz.edu Best Wishes!, aricept side effects destiny adalat side effects basketry thep levaquin side effects conifers barone zolpidem side effects lumber amaryl malware sowerby
top [url=http://www.001casino.com/]online casinos[/url] coincide the latest [url=http://www.casinolasvegass.com/]online casinos[/url] unshackled no set aside perk at the leading [url=http://www.baywatchcasino.com/]baywatch casino
[/url].
Post a Comment