### 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 A* _{n }*be the number of ways to make

*n*cents with pennies.

Let B

*be the number of ways to make*

_{n }*n*cents with pennies and nickels.

Let C

*be the number of ways to make*

_{n }*n*cents with pennies, nickels, and dimes.

Let D

*be the number of ways to make*

_{n }*n*cents with pennies, nickels, dimes, and quarters.

The question is asking us to find D_{100}

The number of ways to make D* _{n}* when

*n >*= 25 if at least 1 quarter is used is D

*, while the number of ways to make D*

_{n-25}*when no quarter is used is C*

_{n }*.*

_{n}Therefore: D* _{n}* = C

*+ D*

_{n}*,*

_{n-25}*n*>= 25

Similarly:

C* _{n}* = B

*+ C*

_{n}*,*

_{n-10}*n>*=10

B

*= A*

_{n}*+ B*

_{n}*,*

_{n-5}*n>*=5

It is obvious that A* _{n}* is always 1.

It is slightly less obvious, but fairly clear to see that B* _{n}* 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 B* _{5}* = 2, B

*= 3, B*

_{10}*= 4, ..., B*

_{15}*=21.*

_{100}We want D* _{100}*, let's use some substitution here:

D

*= C*

_{100}*+D*

_{100}

_{75}D

*= C*

_{100}*+C*

_{100}*+D*

_{75}

_{50}D

*= C*

_{100}*+C*

_{100}*+C*

_{75}*+D*

_{50}

_{25}D

*= C*

_{100}*+C*

_{100}*+C*

_{75}*+C*

_{50}*+1*

_{25}Similarly:

C* _{100}* = B

*+B*

_{100}*+B*

_{90}*B*

_{80+}*+B*

_{70}*+B*

_{60}*+B*

_{50}*+B*

_{40}*+B*

_{30}*+B*

_{20}*+1*

_{10}C

*= B*

_{75}*+B*

_{75}*+B*

_{65}*+B*

_{55}*+B*

_{45}*+B*

_{35}*+B*

_{25}*+B*

_{15}*(note no +1, since C*

_{5 }*= B*

_{5 }*)*

_{5}C

*= B*

_{50 }*+B*

_{50}*+B*

_{40}*+B*

_{30}*+B*

_{20}*+1*

_{10}C

*= B*

_{25 }*+B*

_{25}*+B*

_{15}

_{5}Substituting with the values of B_{n} in the formula above we see:

C* _{100 }*= 21+19+17+15+13+11+9+7+5+3+1 =

**121**

C

*= 16+14+12+10+8+6+4+2 =*

_{75 }**72**

C

*= 11+9+7+5+3+1 =*

_{50 }**36**

C

*= 6+4+2 =*

_{25 }**12**

Finally:

D* _{100 }*= C

*+C*

_{100}*+C*

_{75}*+C*

_{50}*+1*

_{25}*= 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