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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum