Coin Combinations to Make a DollarDate: 11/12/96 at 07:42:16 From: The Rosol's Subject: Dollars and coins What is the number of combinations you need to get a dollar by using pennies, nickles, dimes, quarters, and half dollars, and what is the equation you use to get it from? Date: 12/12/96 at 23:51:21 From: Doctor Donald Subject: Re: Dollars and coins It is possible to answer this question by systematically listing all the possibilities, but it is laborious. There is a fairly sophisticated solution to the problem in Introductory Combinatorics by Bogart, a 1983 text; it uses generating functions. The discussion there is too elaborate to go into here; my guess is that there are no substantially simpler approaches, though of course brute force enumeration is "simpler". Apparently the problem is due to Polya, in an article in the American Mathematical Monthly, December 1956 Hope this helps. -Doctor Donald, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 12/12/96 at 23:51:21 From: Doctor Donald Subject: Re: Dollars and coins There really isn't an equation for doing a problem like this. But you can use an organized way of counting. For example: Half-dollars Quarters Dimes Nickels Pennies 2 0 0 0 0 1 2 0 0 0 1 1 2 1 0 1 1 1 3 0 1 1 1 2 5 1 1 1 1 10 1 1 1 0 15 1 1 0 5 0 1 1 0 4 5 1 1 0 3 10 You keep going this way. If you can see patterns along the way, you may not have to list every possibility. Another way to shorten the counting is to smaller amounts, then add them up. For example, what are the ways to make 25 cents? Quarters Dimes Nickels Pennies 1 0 0 0 0 2 1 0 0 2 0 5 0 1 3 0 0 1 2 5 0 1 1 10 Keep going. When you get this, every time you see a quarter in the large table above, you can write this number in its place. This way you don't keep repeating the dimes, nickels, and pennies every time. Have fun. -Doctor Gerald, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/