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 
you CANNOT make change with. Please help!

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 
a dollar (the answer to the question you asked) is 77.

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