Change for a Dollar

Date: 11/05/1999 at 00:03:14
From: Sarah
Subject: Puzzle

When changing a dollar bill, you can give one coin (1 silver dollar), 
2 coins (2 half-dollars), 3 coins (2 quarters and 1 half-dollar), and 
so on. What is the least positive number of coins that is impossible 
to give as change for a dollar bill?

Date: 11/15/1999 at 19:23:58
From: Doctor TWE
Subject: Re: Puzzle

Hi Sarah - thanks for writing to Dr. Math.

You ask a good question. A total of 292 combinations of coins add up 
to $1.00, or 293 if you count the one-dollar coin. I found this out by 
looking in our archives:

  Ways to Make Change for $1.00
  http://mathforum.org/dr.math/problems/odonnell10.2.97.html   

Writing out all 293 possibilities would be both time-consuming and 
difficult.

Since we're looking for the fewest number of coins, beginning with the 
number of coins and figuring out combinations seems like a good 
starting point. You found 1, 2 and 3-coin combinations. Lets continue: 
(I'll use H for half-dollar, Q for quarter, D for dime, N for nickel, 
and P for penny.)

      4 coins = 4 Q
      5 coins = 1 H + 1 Q + 2 D + 1 N
      6 coins = 1 H + 5 D (or 2 other ways)
      7 coins = 2 Q + 5 D (or 3 other ways)
      8 coins = 3 Q + 5 N (or 2 other ways)
      9 coins = 1 Q + 7 D + 1 N (or 3 other ways)
     10 coins = 10 D (or 5 other ways) ...

Gee, it seems that we're getting more and more ways instead of fewer. 
Let's look at it another way.

For each combination that has a dime, I can exchange that dime for 2 
nickels. So if there is a combination with n coins including at least 
1 dime, there is a combination with n+1 coins (replacing the dime with 
2 nickels). We can start with 10 D and exchange 1 D for 2 N repeatedly 
until we get to 20 N. That covers the combinations for 11 to 20 coins. 
(We already covered 1 to 10 coins, above.)

Next, for every combination with at least 1 nickel, we can exchange 
the nickel for 5 pennies. So if there is a combination with n coins 
including at least 1 nickel, there is a combination with n+4 coins 
(replacing the nickel with 5 pennies). By continuing to exchange 1 N 
for 5 P and starting with 20 N, we can get 24 (19 N + 5 P), 28 (18 N + 
10 P), 32 (17 N + 15 P), ..., 100 (100 P).

Using the same exchange, but starting with 1 D + 18 N, we can get 23 
(1 D + 17 N + 5 P), 27 (1 D + 16 N + 10 P), 31 (1 D + 15 N + 15 P), 
..., 91 (1D + 90 P).

Using the same exchange again, but starting with 2 D + 16 N, we can 
get 22 (2 D + 15 N + 5 P), 26 (2 D + 14 N + 10 P), 30 (2 D + 13 N + 
15 P), ..., 82 (2D + 80 P).

Using the same exchange one more time, but starting with 3 D + 14 N, 
we can get 21 (3 D + 13 N + 5 P), 25 (3 D + 12 N + 10 P), 29 (3 D + 
11 N + 15 P), ..., 73 (3D + 70 P).

Do you see why I used these combinations? By doing that, I've covered 
multiples of 4 with remainders of 0, 1, 2 and 3. This covers all 
combinations from 21 through 76 (plus a few more.)

Wow! I'm glad I didn't try to eliminate them one by one! We still have 
to check 77, 81, 85, 86, 89, 90, 93, 94, 95, 97, 98 and 99. It turns 
out that all of these remaining combinations are impossible. (I 
checked this by writing a program that generated all 292 
combinations.) Can you prove this?

This was fun for me to work on, I hope you have fun working on this 
kind of problem, too!

Here's a "bonus question" for you: how many ways can you make change 
for a dollar using 5 different types of coins (i.e. using at least 1 
each of pennies, nickels, dimes, quarters and half dollars)?

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/