Five Dollars in Change

Date: 10/07/97 at 21:29:03
From: Anonymous
Subject: Brain Teaser

Hi,

I have a math problem that seems to be for lower grades than grade 10,
yet for the life of me I can not figure this one out.

I need to make $5.00. I have to use 100 coins but I can not use 
nickels.

My whole family took a half-hour to figure out this problem and 
failed. It is a brain teaser that was at Mom's work and she got us to 
try to figure it out.

Theresa 

Date: 10/09/97 at 15:25:52
From: Doctor Rob
Subject: Re: Brain Teaser

Start with 100 nickels.

You can trade 9 nickels for 5 pennies and 4 dimes.
You can trade 6 nickels for 5 pennies and 1 quarter.
You can trade 49 nickels for 45 pennies and 4 half-dollars.
You can trade 99 nickels for 95 pennies and 4 dollars.

99 is too close to 100 to leave any room to do anything useful.
Now make 100 out of sums of 6's, 9's, and 49's.  You should be
able to finish with these facts.

I found three solutions, one each using 75, 80, or 85 pennies.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   
    

Date: 11/14/2006 at 11:24:06
From: Noah
Subject: More solutions

Hi,

I used algebra to find what I believe to be a complete list of solutions 
to the problem. 

I began by assigning variables to the numbers of pennies, dimes, quarters,
half-dollars, and dollars:

  p - # of pennies
  d - # of dimes
  q - # of quarters
  h - # of half-dollars
  s - # of dollars (s for silver dollar, d is already taken)

They must satisfy the following 2 equations:

  p +   d +   q +   h +    s = 100 (100 total coins)

  p + 10d + 25q + 50h + 100s = 500 ($5.00, or 500 cents total)

They also must all be nonnegative integer values to make sense as 
a solution to the problem.

Subtracting the one equation from the other, we can eliminate the 
variable p:

  9d + 24q + 49h + 99s = 400

Observe that all the coefficients on the left, except 49, are divisible 
by 3, while 3 does not divide 400.  This indicates that all solutions 
must include some number of half dollars.  To simplify the equation, 
we can work case by case on the number of dollar coins.  As we can only 
have $5.00 total, there will not be very many cases to consider.
 
We start with s=0.  We then have:

  9d + 24q + 49h = 400

If we make h=1, we get 

  9d + 24q = 351

Now all terms are divisible by 3.  We could also make h = 4, 7, 10, 13, 
etc., but not 2, 3, 5, or 6, for instance.  

With h=1, we simplify the above equation (dividing by 3) and get 

  3d + 8q = 117

       3d = 117 - 8q

In other words, we must choose q such that (117-8q) is a multiple of 3.  
The choice q=0 works, and so we have (s=0, h=1, q=0), and so

  3d = 117 

   d = 39

and returning to our original problem, we need still 60 pennies to 
make 100 coins.  The half dollar is $0.50, the dimes make $3.90, and 
the pennies are $0.60, which adds up to $5.00.

We had several places to make choices, I chose 0 dollars, then 
1 half dollar, then 0 quarters.  We can choose different amounts for 
each of these to yield other solutions.  

If we keep (s=0, h=1), then we still have

  3d = 117 - 8q

If the right hand side is to be a multiple of 3, q must be a multiple 
of 3, so we can get solutions for q=0 (above), 3, 6, 9, and 12.  15 is 
too high:

  8 * 15 = 120

which would give us 

  3d = -3 
   
   d = -1

which doesn't make sense in the context of the problem.

You can follow the above procedure with (s=0, h=4) for 3 more 
solutions.  Choosing (s=0, h=7) gives another solution, for 9 total 
solutions without using dollar coins.  With 1 silver dollar, you get 
an additional 6 solutions, 3 more using 2 silver dollars, and 1 solution 
using 3 silver dollars.

Regards,
-Noah