Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Puzzles
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search