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)

50 x 0 ; 25 x 0 ; 10 x 0 ; 5 x 20
50 x 0 ; 25 x 0 ; 10 x 1 ; 5 x 18
50 x 0 ; 25 x 0 ; 10 x 2 ; 5 x 16
50 x 0 ; 25 x 0 ; 10 x 3 ; 5 x 14
50 x 0 ; 25 x 0 ; 10 x 4 ; 5 x 12
50 x 0 ; 25 x 0 ; 10 x 5 ; 5 x 10
50 x 0 ; 25 x 0 ; 10 x 6 ; 5 x 8
50 x 0 ; 25 x 0 ; 10 x 7 ; 5 x 6
50 x 0 ; 25 x 0 ; 10 x 8 ; 5 x 4
50 x 0 ; 25 x 0 ; 10 x 9 ; 5 x 2
50 x 0 ; 25 x 0 ; 10 x 10
50 x 0 ; 25 x 1 ; 10 x 0 ; 5 x 15
50 x 0 ; 25 x 1 ; 10 x 1 ; 5 x 13
50 x 0 ; 25 x 1 ; 10 x 2 ; 5 x 11
50 x 0 ; 25 x 1 ; 10 x 3 ; 5 x 9
50 x 0 ; 25 x 1 ; 10 x 4 ; 5 x 7
50 x 0 ; 25 x 1 ; 10 x 5 ; 5 x 5
50 x 0 ; 25 x 1 ; 10 x 6 ; 5 x 3
50 x 0 ; 25 x 1 ; 10 x 7 ; 5 x 1
50 x 0 ; 25 x 2 ; 10 x 0 ; 5 x 10
50 x 0 ; 25 x 2 ; 10 x 1 ; 5 x 8
50 x 0 ; 25 x 2 ; 10 x 2 ; 5 x 6
50 x 0 ; 25 x 2 ; 10 x 3 ; 5 x 4
50 x 0 ; 25 x 2 ; 10 x 4 ; 5 x 2
50 x 0 ; 25 x 2 ; 10 x 5
50 x 0 ; 25 x 3 ; 10 x 0 ; 5 x 5
50 x 0 ; 25 x 3 ; 10 x 1 ; 5 x 3
50 x 0 ; 25 x 3 ; 10 x 2 ; 5 x 1
50 x 0 ; 25 x 4
50 x 1 ; 25 x 0 ; 10 x 0 ; 5 x 10
50 x 1 ; 25 x 0 ; 10 x 1 ; 5 x 8
50 x 1 ; 25 x 0 ; 10 x 2 ; 5 x 6
50 x 1 ; 25 x 0 ; 10 x 3 ; 5 x 4
50 x 1 ; 25 x 0 ; 10 x 4 ; 5 x 2
50 x 1 ; 25 x 0 ; 10 x 5
50 x 1 ; 25 x 1 ; 10 x 0 ; 5 x 5
50 x 1 ; 25 x 1 ; 10 x 1 ; 5 x 3
50 x 1 ; 25 x 1 ; 10 x 2 ; 5 x 1
50 x 1 ; 25 x 2
50 x 2

from:
DECLARE SUB changeIt (n!, tot!)
DATA 50,25,10,5
DIM SHARED den(10), denCt(10)
DIM SHARED ct, nickCt
FOR i = 1 TO 4: READ den(i): NEXT

changeIt 1, 0

PRINT ct, nickCt

SUB changeIt (n, tot)
  num = 0
  DO
   denCt(n) = num
   remain = 100 - tot - num * den(n)
   IF remain < 0 THEN EXIT DO
   IF remain = 0 THEN
     ct = ct + 1
     IF n = 4 THEN nickCt = nickCt + num
     FOR i = 1 TO n
       IF i > 1 THEN PRINT ";";
       PRINT den(i); "x"; denCt(i);
     NEXT
     PRINT
   ELSEIF n < 4 THEN
     changeIt n + 1, tot + num * den(n)
   END IF
   num = num + 1
  LOOP
END SUB

The count is indeed 40, and the program also totals the number of nickels involved in each solution. That count indicates how many more solutions would be achieved by allowing pennies as each nickel could or could not be converted to 5 pennies. That count does indeed add up to 252, which, added to the 40 without pennies gives the original 292 quoted by the teller

40 252

Posted by Charlie on 2003-06-18 09:39:45