Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  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. Standard member 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. Standard member theangrystudent
    I am MIGHTY!
    05 Apr '05 04:13 / 1 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.

    The answer is 49.
  5. 05 Apr '05 04:27
    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...
  6. 05 Apr '05 08:14 / 1 edit
    Originally posted by davegage
    If anyone could come up with the general method, I'd be impressed...
    See http://www.cut-the-knot.com/ctk/GeneratingFunctions.shtml

    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