Change for a Dollar

Date: 14 Mar 1995 11:00:30 -0500
From: Anonymous
Subject: Math

How many different ways can you give change for a dollar? 
Is there a formula?  Thanks.

Date: 27 Mar 1995 13:08:36 -0500
From: Dr. Sydney
Subject: Re: Math

Hello!  

You ask a good question, and I think you will find it fun to 
think about, so instead of giving you the answer, I am going 
to suggest how you might find the answer.  

One way to approach a problem like this is to deal with 
cases.  By that, I mean that you should figure out how many 
possible cases there are in a systematic way.  So, let's start 
with the biggest change we have.  For $1, we can give 2 half 
dollars.  That is case 1.  Or, we could separate one of those 
half dollars, say into 2 quarters (Next you would say 5 dimes, 
then you would say 10 nickels, then 50 pennies, then figure 
out what all the combinations of pennies, nickels and dimes 
would give you 50 cents, and test those).  We could then 
separate one of those quarters into 2 dimes and a nickel, or 5 
nickels, ..... and so on. 

Do you see how you might go about figuring this out?  It would 
take a long time and it would be best to write it out in some 
kind of organized chart, I think.  Unfortunately , I don't know 
of a nice formula for figuring out how many ways there are to 
give change for a dollar.  

Another way you could approach this problem is to think of it 
in terms of the number 5.  Here is what I mean....For the moment 
ignore the existence of pennies.  Then, all you have to deal with 
are nickels, dimes, quarters, and half-dollars, right?  Well, you 
could figure out what are the different combos of 5's that 
produce 100, and then figure out for each combo of fives what 
change will work (when doing this, take into account the 
existence of pennies again!).  For instance, 5*2 + 5*3 + 5*15 = 100, 
so for the first 5*2 we could have a dime or 2 nickels or 10 
pennies or 5 pennies and a nickel.  Figure out the possiblities 
for the 5*3 and the 5*15, and then write down all the possible 
combinations of these combinations.  Do this for all combos of 
5's you can think of, and you should have a list of all possible 
ways you can give change for a dollar (be careful though, 
duplication will happen!).

I hope this helps you get an idea of how to approach the problem.  
If you are confused by anything, write back and we'll try to clear 
it up!
 
--Sydney, "Dr. Math"