1 Dollar, 50 Coins

Date: 02/22/2002 at 22:13:10
From: Wanda Parton
Subject: Changing a dollar bill using exactly 50 coins

I'm looking for two ways to change a dollar bill using exactly 50 
coins. The first way is 40 pennies, 8 nickels, 2 dimes. What's a 
second way?

Date: 02/22/2002 at 22:46:09
From: Doctor Twe
Subject: Re: Changing a dollar bill using exactly 50 coins

Hi Wanda - thanks for writing to Dr. Math.

I won't give you the answer, but I'll give you a few hints to find it 
yourself. I'll also tell you that there's only one other way to make 
change for a dollar with exactly 50 coins, so once you've found a 
solution, it's the only one.

First, we know we'll have to use pennies, because without any pennies 
the smallest value 50 coins could be is 50 * $.05 = $2.50 (since a 
nickel is the next smallest coin). We also know that the number of 
pennies must be a multiple of 5 since all other coins are multiples of 
$.05, and so is $1.00.

You listed a solution with 40 pennies. Let's consider solutions with 
less than 40 pennies. The next smallest amount of pennies to consider 
would be 35. With 35 pennies, the remaining 50 - 35 = 15 coins must 
equal $1.00 - $.35 = $.65. But the minimum value of 15 coins (no 
pennies) is 15 * $.05 = $.75, so our total of the 50 coins (35 pennies 
plus 15 larger coins) would be at least $.35 + $.75 = $1.10. With 
fewer than 35 pennies, the problem only gets worse. So there are no 
solutions with fewer than 40 pennies.

Of course, if all 50 coins are pennies we only have $.50, not $1.00.

So any solutions must have either 40 or 45 pennies. With 40 pennies, 
the remaining 50 - 40 = 10 coins must total $1.00 - $.40 = $.60 (like 
your listed solution). With 45 pennies, the remaining 50 - 45 = 5 
coins must total $1.00 - $.45 = $.55. Can you come up with a 
systematic way of generating or testing combinations of 10 coins to 
see if they total $.60, and combinations of 5 coins to see if they 
total $.55?

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.com/dr.math/