Make $5 Using One of Each Coin

Date: 07/07/2001 at 14:01:21
From: Steve Thur
Subject: 100 coins = $5 dollars, use 1 of each coins

Dr. Math, 

My teacher asked my class to find solutions for this problem:

You have 100 coins: pennies, nickels, dimes, quarters, and half 
dollars. Use at least one of each to add up to $5.00.

Can you help?
Steve

Date: 07/09/2001 at 16:33:50
From: Doctor Greenie
Subject: Re: 100 coins = $5 dollars, use 1 of each coins

Hi Steve -

Here are what I think are the two keys to going about finding 
solutions to almost any problem involving making certain total amounts 
using certain numbers of pennies, nickels, dimes, quarters, and half 
dollars:

(1) Because any total amount (in cents) using only nickels, dimes, 
quarters, and half dollars is a multiple of 5, the desired total for a 
particular problem limits the possible numbers of pennies. If the 
desired total is $2.53, then the number of pennies must be one of the 
numbers 3, 8, 13, 18, ..., 248, 253. In your problem, the desired 
total is $5.00, or 500 cents; you also have the restrictions that 
there is at least one penny and that there are 100 coins in all. So 
the number of pennies must be one of the numbers 5, 10, 15, ..., 85, 
90, 95.

(2) Given n coins that are all nickels and/or dimes, you can make any 
total number of cents that is a multiple of 5 between 5n (all nickels) 
and 10n (all dimes). For example, with 4 nickels and/or dimes, you 
can make any total that is a multiple of 5 between 5*4 = 20 cents and 
10*4 = 40 cents:

    dimes  nickels  cents
   -----------------------
      0       4      20
      1       3      25
      2       2      30
      3       1      35
      4       0      40

In your problem, you have the restriction that there must be at least 
one of each type of coin.  This means that with n coins that are all 
nickels and/or dimes (with at least one of each), you can make any 
total number of cents that is more than 5n and less than 10n.

Using these two facts, you can search for solutions to your problem as 
follows:

(1) Arbitrarily choose the numbers of half dollars and quarters you 
want to try.

(2) For that combination of half dollars and quarters, consider all 
the possible numbers of pennies you could have.

(3) For each combination of half dollars, quarters, and pennies you 
have, determine (a) the number n of remaining coins (nickels and 
dimes) and (b) the remaining number c of cents required to achieve the 
total of $5.00. If the remaining cents required, c, is more than 
5 times n and less than 5 times n, then the combination will work.  
(You will still have some work to do to determine the numbers of 
nickels and dimes... but you know there will be a solution.)

Here is a table of the results of this process assuming an initial 
guess of 2 half dollars and 6 quarters:

  column 1: number of half dollars
  column 2: number of quarters
  column 3: number of pennies
  column 4: total number of half dollars, quarters, and pennies
  column 5: total amount using half dollars, quarters, and pennies
  column 6: remaining number of coins (nickels and/or dimes)
  column 7: remaining amount using nickels and/or dimes
  column 8: can this remaining number of cents (column 7) be made 
            using the remaining number of coins (column 6) if there is 
            at least one nickel and at least one dime? In other words, 
            is the number in column 7 more than 5 times the number in 
            column 6 and less than 10 times the number in column 6?
  column 9: solution (half dollars, quarters, dimes, nickels, pennies)

 (1) (2)  (3)   (4)    (5)     (6)    (7)     (8)          (9)
 --------------------------------------------------------------------
  2   6    5    13    $2.55    87    $2.45     no
  2   6   10    18    $2.60    82    $2.40     no
  2   6   15    23    $2.65    77    $2.35     no
  2   6   20    28    $2.70    72    $2.30     no
  2   6   25    33    $2.75    67    $2.25     no
  2   6   30    38    $2.80    62    $2.20     no
  2   6   35    43    $2.85    57    $2.15     no
  2   6   40    48    $2.90    52    $2.10     no
  2   6   45    53    $2.95    47    $2.05     no
  2   6   50    58    $3.00    42    $2.00     no
  2   6   55    63    $3.05    37    $1.95    yes   (2, 6,  2, 35, 55)
  2   6   60    68    $3.10    32    $1.90    yes   (2, 6,  6, 26, 60)
  2   6   65    73    $3.15    27    $1.85    yes   (2, 6, 10, 17, 65)
  2   6   70    78    $3.20    22    $1.80    yes   (2, 6, 14,  8, 70)
  2   6   75    83    $3.25    17    $1.75     no
  2   6   80    88    $3.30    12    $1.70     no
  2   6   85    93    $3.35     7    $1.65     no
  2   6   90    98    $3.40     2    $1.60     no

You can make similar tables for any initial guess for the numbers of 
half dollars and quarters.

Having some extra time to play around with this, I made an exhaustive 
analysis of this problem and found 177 different ways to make change 
for $5 using 100 coins. (However, I could easily have made a simple 
arithmetic mistake or two along the way, so that may not be the 
correct number of solutions...)

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