55 Cents, Seven Coins

Date: 05/15/2001 at 17:08:42
From: Erik 
Subject: Money

How can you get 55 cents with seven coins (quarters, dimes, nickels or 
pennies only) eight ways?

Date: 05/16/2001 at 15:40:36
From: Doctor TWE
Subject: Re: Money

Hi Erik - thanks for writing to Dr. Math.

I only count three ways of doing it - and more importantly, I can 
prove there aren't any other solutions.

Let's start by thinking about how we can simplify this problem. 
Pennies aren't worth very much and 'use' a lot of coins, so let's see 
if we can't eliminate some combinations.

Since the amount we are trying to get is a multiple of 5 cents, and 
since all other coins (nickels, dimes, and quarters) are also 
multiples of 5 cents, any solution involving pennies would have to use 
a multiple of 5. Otherwise we'd have a few cents 'left over'.

We are only allowed seven coins total, and the only multiples of 5 
that are less than 7 are 5 and 0, so our solutions have to have either 
five pennies or zero pennies. Let's consider solutions with five 
pennies.

If five of the coins are pennies, then the other 7-5 = 2 coins must be 
worth 55-5 = 50 cents. The only way to get 50 cents with exactly two 
coins is with two quarters. So that's one solution:

     2 quarters and 5 pennies

Furthermore, that's the ONLY solution that uses pennies. (We know all 
solutions must have a multiple of five pennies and can't have more 
than seven pennies; and we know that that is the only solution with 
exactly five pennies. Thus all other solutions must have no pennies.)

Now we have to find solutions that involve only nickels, dimes, and 
quarters. Can we narrow it down more? Let's look at the other extreme 
- quarters. The solutions obviously can't have more than two quarters 
(otherwise the total would be more than 55 cents). Let's consider 
solutions with exactly two quarters.

If two of the coins are quarters, then the other 7-2 = 5 coins must be 
worth 55-50 = 5 cents. The only way to get 5 cents with exactly five 
coins is with five pennies. But that's the solution we already came up 
with. Using only nickels and dimes, there's no way to get 5 cents 
using exactly five coins.

So we know that any further solutions must have either one quarter or 
no quarters. Let's next consider solutions with exactly one quarter.

If one of the coins is a quarter, then the other 7-1 = 6 coins must be 
worth 55-25 = 30 cents. (And we know that there are no pennies 
involved.) Can you come up with ways of getting 30 cents with exactly 
six coins that are nickels or dimes only? Furthermore, can you *prove* 
that you've found all solutions?

Finally, we consider the case of no quarters (and no pennies). Can you 
come up with ways of getting 55 cents with exactly seven coins that 
are nickels or dimes only? Can you prove that you've found all 
solutions?

I'll let you finish the work on those last two cases. Once you've 
found them, you're done.

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

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