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

Making Change for a Dollar

```
Date: 05/29/2001 at 23:39:33
From: Kathy Holman
Subject: Coin problem

Making change for \$1.00, what is the smallest number of coins you
cannot make change with?

I started by:
1. one silver dollar,
2. two half dollars,
3. one half dollar and two quarters,
4. four quarters,
5. one half dollar, one quarter, two dimes and one nickel.

I got up to 23 - 17 nickels, 1 dime, and 5 pennies (this equals 23
coins).  Now I seem to be stuck finding the smallest number of coins
```

```
Date: 05/30/2001 at 18:24:19
From: Doctor Greenie
Subject: Re: Coin problem

Hi, Kathy -

This is an interesting twist to the old problem of "how many ways can
you make change for a dollar?"

After playing with the problem for a little while, you probably can
get an idea that the number you are looking for is quite large, so
let's do our search from the opposite end of the range - that is,
let's look for combinations using as MANY coins as possible.

If we want to use as many coins as possible, then we don't want to use
half dollars or quarters. So let's look first at the numbers of coins
we can use to make a total of one dollar if we use only dimes,
nickels, and pennies.

With no dimes, I can have from 0 to 20 nickels. With 0 nickels, I have
100 pennies. For each additional nickel, I have 5 fewer pennies,
giving me 4 fewer coins total. With 20 nickels, I have no pennies, for
a total of 20 coins.

Here is a table of the possibilities with nickels and pennies only:

dimes  nickels  pennies  # coins
--------------------------------
0       0       100      100
0       1        95       96
0       2        90       92

0      ...      ...      ...

0      19         5       24
0      20         0       20

So with 0 dimes, I can have any number of coins between 20 and 100
that is a multiple of 4.

Now let's consider the possibilities with only dimes, nickels, and
pennies when I have exactly 1 dime. With 1 dime, I can have from 0 to
18 nickels. With 0 nickels, I have 90 pennies, for a total of 91
coins. As before, for each additional nickel I have 5 fewer pennies,
giving me 4 fewer coins total. With 18 nickels, I have no pennies, for
a total of 19 coins.

Here is a table of the possibilities with dimes, nickels, and pennies
only, and with exactly 1 dime:

dimes  nickels  pennies  # coins
--------------------------------
1       0        90       91
1       1        85       87
1       2        80       83

1      ...      ...      ...

1      17         5       22
1      18         0       19

So with 1 dime, I can have any number of coins between 19 and 91 that
is 3 more than a multiple of 4.

I won't continue with the detailed analysis for the different numbers
of dimes. The results of those analyses show that I can make a total
of one dollar using the following numbers of coins:

number   different total numbers of coins using this number of
of dimes  dimes (and no larger coins) to make a total of one dollar
--------  ---------------------------------------------------------
0      20, 24, 28, ..., 96, 100
1      19, 23, 27, ..., 87, 91
2      18, 22, 26, ..., 78, 82
3      17, 21, 25, ..., 69, 73
4      16, 20, 24, ..., 60, 64
5      15, 19, 23, ..., 51, 55
6      14, 18, 22, ..., 42, 46
7      13, 17, 21, ..., 33, 37
8      12, 16, 20, 24, 28
9      11, 15, 19
10      10

Combining all these results, the numbers of coins that can be used to
make a total of one dollar using just pennies, nickels, and dimes are
the following:

(1) all numbers n, 12 <= n <= 100, of the form 4k (where k is an
integer);
(2) all numbers n, 11 <= n <= 91, of the form 4k+3;
(3) all numbers n, 10 <= n <= 82, of the form 4k+2; and
(4) all numbers n, 13 <= n <= 73, of the form 4k+1

(5) It is easy to find combinations of 1 to 9 coins that total a
dollar.
(6) Also, any combination of coins that has at least one coin larger
than a dime will have a total of at most 76 coins.

From (1) through (6), it follows that the following are the only
numbers of coins with which you can NOT make a total of a dollar:

==> all numbers n, n > 91, of the form 4k+3  (95, 99)
==> all numbers n, n > 82, of the form 4k+2  (86, 90, 94, 98)
==> all numbers n, n > 73, of the form 4k+1  (77, 81, 85, 89, 93, 97)

So the smallest number of coins with which you cannot make a total of

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations
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