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

### 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/
```
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