Different Combinations of Coins

Date: 2/18/96 at 17:32:11
From: "Susan L. Riglin"
Subject: Help with Problem

Hello Dr. Math:

Here is a problem my son brought home from 6th grade.  Usually 
the problems are much harder and my husband (a college graduate) 
would get together with another father (also a college graduate) 
to try to solve them.  They spend a lot of time solving the 
problems and then try to explain them to the kids.  We thought 
we would give your service a try for help.  
*****************
Francisco had some change in his pocket.  He gave his friends, 
Mike and Kevin, these three clues to see if they could guess how 
much he had:

* The coins equaled exactly one dollar.
* He had no more than 100 coins.
* He had at least one coin.

What combination of coins could Francisco have had in his 
pocket?
*****************
We started doing the tedious task by doing the following, but 
decided that there must be a formula or something to help 
instead of doing what we started below.

Example of what we started:
100 pennies
95 pennies, 5 nickel
90 pennies, 1 dime
90 pennies, 2 nickels
85 pennies, 1 dime, 2 nickel
80 pennies, 4 nickels

We appreciate any help you can give.

Thanks.

Date: 3/17/96 at 3:34:45
From: Doctor Jodi
Subject: Re: Help with Problem

Hi Susan!
Thanks for your question. 

There are two formulae that must be satisfied:

1 < number of coins < 100
 
and

100 cents = 1*silver_dollars + 50 * half_dollars + 25 * quarters 
+ 10 * dimes + 5 * nickels + 1 * pennies.

There are a LOT of solutions to this problem.  I would first 
make a list of the maximum number of each sort of coin:

1 silver dollar
2 half dollars
4 quarters
10 dimes
20 nickels 
100 pennies 

Here we have 6 different solutions, using the maximum number of 
each coin.  Now we can go through other solutions using these 
coins.

silver dollar - this is the only solution with this coin, since 
all by itself this makes a dollar.

half dollar - could use one coin; how many ways can you make up 
the other 50 cents:  2 quarters, 5 dimes, 10 nickels, 50 
pennies, 1 quarter and 2 dimes and 1 nickel, 1 quarter and 1 
dime and two nickels, 1 quarter and 25 pennies, etc.

With the pennies, you should find that any multiple of 5 will 
work, since you can add nickels, dimes, etc. (since you can't 
have 97 pennies - this doesn't make a dollar, and you can't make 
a dollar out of just pennies unless you have 100)

so that means that you can use
 
95
90
85
.
.
.
pennies with combinations of other coins.

This process goes on.... I can't think of any way to shorten it, 
but please let us know if you find one.  

-Doctor Jodi,  The Math Forum