Change for a Dollar

Date: 03/07/99 at 13:32:09
From: jay
Subject: Ways to make a change for a dollar?

How many different ways are there to make a change for a dollar?

Thanks.

Date: 03/26/99 at 00:50:08
From: Doctor Schwa
Subject: Re: Ways to make a change for a dollar?

This problem is discussed in _How To Solve It_, by George Polya, which 
is a book I'd certainly recommend for anyone.

A computer program that solves this problem is in our Dr. Math archives
(I found it by searching for "change dollar ways") at

  http://mathforum.org/dr.math/problems/odonnell10.2.97.html   

Some more hints can be found at

  http://mathforum.org/dr.math/problems/change.html   

Another method:

Make a list of the number of ways to make change using only pennies;
there's only one way, namely all pennies.

   5  10  15  20  25  30  35  40  45  50
P  1   1   1   1   1   1   1   1   1   1

Then try making a list of the number of ways to do it with nickels and
pennies:

With 5 cents, there are 2 ways: a nickel or 5 pennies.

With 10 cents, either you use NO nickels (1 way) or you use a nickel
and then make the remaining 5 cents (2 ways).  Total, 3 ways.

Keep going like that, and you'll get a row like

NP  2   3   4 ....

Then you can include dimes, and make a DNP row like
DNP 2   4   6  ...

How did I figure out those numbers? Well, for 5 cents, dimes are 
useless, so it's the same as the NP row. For 10 cents, a dime gives you 
one extra way compared to the NP row. For 15 cents, you can use NO 
dimes (4 ways; that comes from the NP row) or you can use a dime and 
then make the remaining 5 cents somehow (2 ways, from the DNP row), for
a total of 6 ways.

Continuing on like that, you can make a complete table of the number of 
ways to make change for n cents using just pennies, or allowing 
nickels, or dimes, or quarters....

Have fun!

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/