# Making Change

davegage
Posers and Puzzles 05 Apr '05 03:05
1. 05 Apr '05 03:05
I think this problem was first posed in a mathematics journal in the mid 1950s. I hope it hasn't already been posted before on this site:

How many different (distinguishable) ways are there to pay out exactly 50 cents? You can make the payment with any number of pennies, nickels, dimes, or quarters.
2. Bowmann
Non-Subscriber
05 Apr '05 03:08
Can I use proper money?
3. 05 Apr '05 03:15
Originally posted by Bowmann
Can I use proper money?
ha ha. you could try, but the customer really wants his change in american money (he likes a weak dollar or something). 😉
4. theangrystudent
I am MIGHTY!
05 Apr '05 04:131 edit
Originally posted by davegage
I think this problem was first posed in a mathematics journal in the mid 1950s. I hope it hasn't already been posted before on this site:

How many different (distinguishable) ways are there to pay out exactly 50 cents? You can make t ...[text shortened]... e payment with any number of pennies, nickels, dimes, or quarters.
Stay with me, I'm not very good with grids.

25--10--5
2 + 0 + 0 = 50
1 + 2 + 1 = 50
1 + 1 + 3 = 50
1 + 0 + 5 = 50
0 + 5 + 0 = 50
0 + 4 + 2 = 50
0 + 3 + 4 = 50
0 + 2 + 6 = 50
0 + 1 + 8 = 50
0 + 0 +10= 50

There are ten ways to create fifty cents using quarter, dimes, and nickles. Since 50, 25, 10, and 5 have the greatest common divisor of 5; then pennies are only going to be used in mulitples of five. So any time I used a nickle on the above chart, I could replace it with five pennies. After working with the penny vs nickle conversion for awhile you can notice that if say a row ended in three nickles, there are three more ways to create the same row (swapping out a nickle for five pennies; repeate as long as there are still nickles).
So add the number of rows to the number of nickles used throughout the chart and you get the number of combination to create fifty cents out of quarters, dimes, nickles, and pennies.