lotus

previous page: 93 combinatorics/alphabet.blocks.p
  
page up: Puzzles FAQ
  
next page: 95 combinatorics/coinage/dimes.p

94 combinatorics/coinage/combinations.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

94 combinatorics/coinage/combinations.p


Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many
ways are there to make change for a dollar?

combinatorics/coinage/combinations.s

292. The table is shown below:

Amount  00 05 10 15 20 25 30 35 40 45 50 55 60 65  70  75  80  85  90  95  100
Coins  
.01      1  1  1  1  1  1  1  1  1  1  1  1  1  1   1   1   1   1   1   1   1
.05      1  2  3  4  5  6  7  8  9 10 11 12 13 14  15  16  17  18  19  20  21
.10      1  2  4  6  9 12 16 20 25 30 36 42 49 56  64  72  81  90 100 110 121
.25      1  2  4  6  9 13 18 24 31 39 49 60 73 87 103 121 141 163 187 214 242
.50      1  2  4  6  9 13 18 24 31 39 49 62 77 93 112 134 159 187 218 253 292

The meaning of each entry is as follows:
If you wish to make change for 50 cents using only pennies, nickels and dimes,
go to the .10 row and the 50 column to obtain 36 ways to do this.

To calculate each entry, you start with the pennies. There is exactly one
way to make change for every amount. Then calculate the .05 row by adding
the number of ways to make change for the amount using pennies plus the number
of ways to make change for five cents less using nickels and pennies. This
continues on for all denominations of coins.

An example, to get change for 75 cents using all coins up to a .50, add the
number of ways to make change using only .25 and down (121) and the number of
ways to make change for 25 cents using coins up to .50 (13). This yields the
answer of 134.

 

Continue to:













TOP
previous page: 93 combinatorics/alphabet.blocks.p
  
page up: Puzzles FAQ
  
next page: 95 combinatorics/coinage/dimes.p