Friday, January 5, 2007

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:

Kimota94 aka Matt said...

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!

Anonymous said...

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,

Anonymous said...

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

Anonymous said...

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].