I was trying to figure out this problem, “How many different ways can we make change of $ 1.00, given half-dollars, quarters, dimes, nickels, and pennies?” This problem is featured in this Ramblings of a Geek blog post and is also in section 1.2.2 of the book Structure and Interpretation of Computer Programs (PDF version).

I think it involves the pigeonhole principle when trying to figure out how the recursive formula works. Here’s part of the set up from the Ramblings of a Geek blog post:

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

So if you’re trying to figure out Dn=100 as in the post, where n=the amount, and D is a combination of quarters, dimes, nickels and pennies, you use the “pigeonhole principle” and split the choices into combinations using quarters and combinations without using quarters first.

So, if you use 0 quarters, that could be C100 combinations, where Cn is the number of combinations using dimes, nickels, and pennies but no quarters. That’s your “no quarters” box. Then your other box, to begin with, for a combination to belong in the “using quarters” box, you know automatically that the combination must be using at least one quarter to belong in that box. So since the any combination is for sure using at least one quarter (25 cents), you will have a remaining 75cents (the beginning 100 cents minus the quarter you’re sure exists in the combination) that you’re unsure of the composition of, that is, you have 75 cents that will be made up of a combination of 0-3 quarters, 0-7 dimes, 0-15 nickels, and 0-75 pennies. Since it could be a combination of quarters, nickels, and pennies, that can fit in category “D”, and since the amount is 75 cents, you can label that as D75.

So, D100=C100 + D75. So technically, like in the SICP book and the Ramblings of a Geek blog post, you can think of a recursive formula:

The number of ways to change amount a using n kinds of coins equals the number of ways to change amount a using all but the first kind of coin, plus the number of ways to change amount a – d using all n kinds of coins, where d is the denomination of the first kind of coin.

So we’ve determined above, that D100=C100 + D75. You can use the same logic as above on the D75 to reduce that to a C. For example, for D75, you might get 75 cents by using zero quarters, so you could categorize that as C75…and if you were using at least one quarter, you would know for sure what 25 cents of that 75 cents was made out of (that one quarter), that would leave you with 50 cents you were not sure about the composition of, that might be made up of quarters, dimes, nickels, and pennies, which could be categorized as D50, so D75=C75 + D50. You can do that with the recursive formula, you can then examine D75, that would be equal to D75=C75+D50. And on down the chain until the Ds disappear completely, replaced by all Cs, then replace the Cs with Bs and As.

And with As, there will always only be one way to make anything out of pennies; $1 is 100 pennies, 50 cents is 50 pennies, etc. So when you examine the Bs, the formula is n/5 + 1. The 1 is for one way you can make anything using all pennies, and the n/5 is how many nickels fit in the amount n. So, say n=15. Here n/5 is 15/5=3. B15=4, using the formula n/5 + 1. That corresponds here to these four situations: you use one nickel and ten pennies, or two nickels and five pennies, or three nickels and no pennies, or no nickels and 15 pennies!

So starting at Dn, you reduce down to Cs, then to Bs and As. Here’s the rest of the Rambling Geek’s example:

We want D_{100}, let’s use some substitution here:

D_{100} = C_{100}+D_{75}

D_{100} = C_{100}+C_{75}+D_{50}

D_{100} = C_{100}+C_{75}+C_{50}+D_{25}

D_{100} = C_{100}+C_{75}+C_{50}+C_{25}+1

Similarly:

C_{100} = B_{100}+B_{90}+B_{80+}B_{70}+B_{60}+B_{50}+B_{40}+B_{30}+B_{20}+B_{10}+1

C_{75} = B_{75}+B_{65}+B_{55}+B_{45}+B_{35}+B_{25}+B_{15}+B_{5 }(note no +1, since C_{5 }= B_{5})

C_{50 }= B_{50}+B_{40}+B_{30}+B_{20}+B_{10}+1

C_{25 }= B_{25}+B_{15}+B_{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_{75 }= 16+14+12+10+8+6+4+2 = **72**

C_{50 }= 11+9+7+5+3+1 = **36**

C_{25 }= 6+4+2 = **12**

Finally:

D_{100 }= C_{100}+C_{75}+C_{50}+C_{25}+1_{ }= 121+72+36+12+1 = **242**

So there are 242 ways to uniquely make change for $1 using pennies, nickels, dimes, and quarters.

Another way of thinking about part of the problem, is, say the amount n is 100, and you want to use quarters, dimes, nickels, and pennies, so you’re looking at D100, is to think about the quarters in the following way: we decided with Bs, you look at how many times nickels divide into n, that would be n/5, and then add 1 for the number of ways you can make n with pennies for combinations where you don’t use any nickels at all. With Ds, we can look at how many times quarters can divide into n, so that would be n/25, and then add C100 for the combinations possible for which you use no quarters, and you make the $1 out of combinations of 0-10 dimes, 0-20 nickels, and 0-100 pennies. So if you use no quarters, that’s C100. Add that to if you use one quarter, then you have 75 cents you don’t know the consistency of, possibly made out of dimes, nickels, and pennies, C75. Then add all that to the combinations if you use two quarters, then you have 50 cents you don’t know about, that could be C50. Then add that all to if you use three quarters, then you have 25 cents which could be made out of dimes, nickels, and pennies, C25. Then add that all to the number of combinations where you use four quarters, in which case you would have no combinations made of dimes, nickels, and pennies left over (C0), so if you use four quarters, there’s only one possible combination for n=100, using those four quarters. So that’s D100=C100 + C75 + C50 + C25 + 1.

Each time you subtract the denomination of the type of coin being examined from the amount, that’s because you’re setting up the case where you are using that type of coin, such as quarters; so C100 is all the ways to make 100 cents made of 0 quarters and 0-10 dimes, 0-20 nickels, and 0-100 pennies; C75 is all the ways to make 100 cents using 1 quarter, 0-7 dimes, 0-15 nickels, and 0-75 pennies; C50 is all the ways to make 100 cents using two quarters, 0-5 dimes, 0-10 nickels, and 0-50 pennies; C25 is all the ways to make 100 cents using three quarters, 0-2 dimes, 0-5 nickels, and 0-25 pennies; C0 is all the ways to make 100 cents using four quarters, namely, 1.

Disclaimer, I hope that helps explain the logic behind the problem and the solution and hope that my explanation is correct, it might not be! 😉

internal tag: math

(Why doesn’t the search function on wordpress.com blogs search post tags too? I can’t believe that when I search my blog with the term “math,” only posts with “math” in the actual post text are retrieved; if the post is tagged “math” but doesn’t contain the term “math” in the post text, the post won’t be retrieved…hence the “internal tag” I had to add. Bah.)

See these other math related posts including:

Filed under: math, Uncategorized | Tagged: computers, discrete math, math | 2 Comments »