I went into the bank to get change for a dollar. The teller said, "How do you want the change, buddy? I mean, there are 292 ways involving pennies, nickels, dimes, quarters, and half-dollars to give change for a dollar!"

Since I didn't like her attitude, I didn't answer her question. I simply said, "Well, I certainly don't want any pennies."

How many ways are there for her to give me change now?

(Note: Americans, always shunning simplicity have chosen to name their coins in the following easy-to-remember manner: Penny=1 cent, Nickel=5 cents, Dime=10 cents, Quarter=25 cents, Half Dollar=50 cents)

Here are the exhaustive possibilities:

half-dollars quarters dimes nickels
------------ -------- ----- -------
2 0 0 0
1 2 0 0
1 1 2 1
1 1 1 3
1 1 0 5
1 0 5 0
1 0 4 2
1 0 3 4
1 0 2 6
1 0 1 8
1 0 0 10
0 4 0 0
0 3 2 1
0 3 1 3
0 3 0 5
0 2 5 0
0 2 4 2
0 2 3 4
0 2 2 6
0 2 1 8
0 2 0 10
0 1 7 1
0 1 6 3
0 1 5 5
0 1 4 7
0 1 3 9
0 1 2 11
0 1 1 13
0 1 0 15
0 0 10 0
0 0 9 2
0 0 8 4
0 0 7 6
0 0 6 8
0 0 5 10
0 0 4 12
0 0 3 14
0 0 2 16
0 0 1 18
0 0 0 20
-------------------------------------
A total of 40 combinations. 40 different ways for her to give you change, ranging from 2 half-dollars to 20 nickels.

Posted by Dan Erickson on 2003-08-23 05:01:05