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

### Making \$5 Using 50 Coins

```Date: 12/02/2005 at 15:41:47
From: Haley
Subject: 50 coins = \$5

How many ways can you make \$5 with 50 coins, without dimes?  My dad
and I found 26, but my teacher says 37 is the most.  My dad made an
Excel page to help me but I'm stuck.  It was for extra credit, but I
would like to know the ones I missed.

```

```
Date: 12/03/2005 at 01:58:24
From: Doctor Greenie
Subject: Re: 50 coins = \$5

Hi, Haley --

too complex for a 12-year-old.  Very few talented high school students
would be able to solve this problem.

And perhaps your teacher can't solve it correctly either--because I
found 38 ways instead of the 37 he says is the most.

Here is a table copied from an Excel spreadsheet showing my solutions.
The first column is the solution number.  The next five columns are,
respectively, the numbers of pennies, nickels, dollar coins, half
dollars, and quarters.  The last two columns are the Excel checks to
show that, for each of the solutions, the number of coins is 50 and
the total value of the coins is \$5.00 (500 cents).

1 40 2 3 1  4 50 500
2 40 2 2 4  2 50 500
3 40 2 1 7  0 50 500
4 35 3 2 0 10 50 500
5 35 3 1 3  8 50 500
6 35 3 0 6  6 50 500
7 30 4 0 2 14 50 500

8 35  8 2 4  1 50 500
9 30  9 2 0  9 50 500
10 30  9 1 3  7 50 500
11 30  9 0 6  5 50 500
12 25 10 0 2 13 50 500

13 30 14 3 1  2 50 500
14 30 14 2 4  0 50 500
15 25 15 2 0  8 50 500
16 25 15 1 3  6 50 500
17 25 15 0 6  4 50 500
18 20 16 0 2 12 50 500

19 25 20 3 1  1 50 500
20 20 21 2 0  7 50 500
21 20 21 1 3  5 50 500
22 20 21 0 6  3 50 500
23 15 22 0 2 11 50 500

24 20 26 3 1  0 50 500
25 15 27 2 0  6 50 500
26 15 27 1 3  4 50 500
27 15 27 0 6  2 50 500
28 10 28 0 2 10 50 500

29 10 33 2 0 5 50 500
30 10 33 1 3 3 50 500
31 10 33 0 6 1 50 500
32  5 34 0 2 9 50 500

33 5 39 2 0 4 50 500
34 5 39 1 3 2 50 500
35 5 39 0 6 0 50 500
36 0 40 0 2 8 50 500

37 0 45 2 0 3 50 500
38 0 45 1 3 1 50 500

I didn't solve the problem using an Excel spreadsheet; I used the
spreadsheet to verify the solutions I found.  The organization of the
spreadsheet does, however, demonstrate the process I used to find the
solutions.  I will try to describe that process below.

To me, the key to finding a method of solution to this problem is the
fact that the dollar coins, half dollars, and quarters together can
only make totals which are multiples of 25 cents.  Since the desired
total is a multiple of 25 cents, this means the total value of the
pennies and nickels must also be a multiple of 25 cents.

I decided, somewhat arbitrarily, to start my investigation with the
largest possible number of pennies.  We obviously couldn't use 50
pennies, so my first try was with 45 pennies.  45 pennies together
with 1 nickel makes 50 cents.  That means we have 4 coins left to make
the remaining \$4.50.  But the largest coin we have is a dollar--so we
can't make \$4.50 with 4 coins.

So next we try 40 pennies; and we need 2 nickels to make a total of 50
cents.  In this case, we need to make the remaining \$4.50 using 8
coins.  If 4 of those other 8 coins are dollars, then we have 4 coins
left to make 50 cents; we can't do that with just quarters and half
dollars.

If 3 of those other 8 coins are dollars, then we have 5 coins left to
make \$1.50.  This we can do--with 1 half dollar and 4 quarters
(solution #1 in the list above).

If 2 of those other 8 coins are dollars, then we have 6 coins left
to make \$2.50.  This too we can do--with 4 half dollars and 2 quarters
(solution #2 in the list above).

If 1 of those other 8 coins are dollars, then we have 7 coins left
to make \$3.50.  And this we can do -- with 7 half dollars (solution
#3 in the list above).

If none of the other 8 coins are dollars, then we have to make \$4.50
with 8 coins, the largest of which is a half dollar.  8 half dollars
does not make \$4.50, so we don't have a solution here.

Now let's look at the combinations of dollars, half dollars, and
quarters we found using 40 pennies and 2 nickels:

dollars  halves  quarters
-------------------------
3        1        4
2        4        2
1        7        0

To get from one solution to the next, we do the following: use one
fewer dollar coin, 3 more half dollars, and two fewer quarters.  We
add three coins and subtract three coins, and the total value stays
the same.

So in the rest of our investigation, whenever we find one solution,
we can find others by using one less dollar, three more half dollars,
and two less quarters.  (Or we might be able to find other solutions
by doing the opposite--using one more dollar, three less half dollars,
and two more quarters.)

I won't go through the details any further; I will just outline a bit
more of the process.

We have found all the solutions using 40 pennies and 2 nickels; the
next thing we should try is finding combinations using 35 pennies and
3 nickels.  It turns out we can't use 4 or 3 dollar coins with this
combination; but with 2 dollar coins we can complete the \$5 using 0
half dollars and 10 quarters (solution #4 in the list above).  From
there, using our method of trading coins, we can find solutions #5 and
6 in the list above.

When we next try combinations using 30 pennies and 4 nickels, we find
solution #7 in the list above.

There are no other solutions in which the total value of the pennies
and nickels is 50 cents.  So next we look for combinations in which
the total value of the pennies and nickels is 75 cents.

Continuing in this fashion, a great deal of work finds the 38
solutions shown in the list....

I hope all this helps.  Please write back if you have any further

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

```

```
Date: 12/03/2005 at 11:06:52
From: Haley
Subject: Thank you (50 coins = \$5)

Thank you for the quick responce.  My dad also tried to show me the
same way, but after a while I could not think of any more.  I'll let
my teacher know there are 38 answers.  Thanks again.  Haley
```
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