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.
1 edit
Originally posted by davegageStay with me, I'm not very good with grids.
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.
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.
The answer is 49.
yep...49 is right.
There is actually a much more difficult general question that could be asked, ie how many ways can you pay out X cents with pennies, nickels, dimes and quarters, where X could be any positive whole number (X = 1,2,3,...). I'm not smart enough to come up with it myself, but I know the answer. If anyone could come up with the general method, I'd be impressed...
1 edit
Originally posted by davegageSee http://www.cut-the-knot.com/ctk/GeneratingFunctions.shtml
If anyone could come up with the general method, I'd be impressed...
Are you suitably impressed? 😏
For an 'easy' introduction to the general theory of generating functions download the ebook at
http://www.math.upenn.edu/~wilf/DownldGF.html