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 --

My first comment about this extra credit problem is that it is far 
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 
questions about any of this.

- 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