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

### Coin Combinations Quickened by Process of Elimination

```Date: 11/04/2013 at 21:02:55
From: Albert
Subject: What is an efficient way of solving this problem

Dear Dr. Math,

How many different amounts of money can be made from 4 pennies, 2 nickels,
1 dime, and 1 quarter if one or more coins can be used in each amount?

I could not figure out what is a good way to tackle a problem like this. I
tried listing all the possibilities and creating a tree diagram, but both
of those approaches were confusing.

... and time-consuming: this problem is from a 1988 Olympiad, which
allowed 3 minutes to work out the problem. Could you tell me a way that
will work out in the allotted time?

I would really appreciate a thorough response.

Thank you.

```

```
Date: 11/05/2013 at 16:02:15
From: Doctor Greenie
Subject: Re: What is an efficient way of solving this problem

Hi, Albert --

(1) Find the total value of all the coins; that will give you the maximum

(2) See if any of the total values less than the overall total can NOT be

The total value of the coins is 49 cents; so the largest possible answer
to the question is 49.

Some quick analysis shows that you can make any total from 1 to 24 cents
using the dime, nickels, and pennies. Then the quarter itself makes 25
cents; and adding the quarter to each of the combinations using the
smaller coins will allow you to make any total from 26 to 49 cents.

So there are no totals that you can NOT make using the given coins; and
the number of different totals you can make is 49.

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

```

```
Date: 11/08/2013 at 13:57:47
From: Albert
Subject: Thank you (What is an efficient way of solving this problem)

Thanks, Dr. Greenie! That is an awesome solution.
```
Associated Topics: