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

### Change for a Dollar

```
Date: 01/22/2001 at 17:35:06
From: maria E. Lacey
Subject: Coins used to change one dollar

Could you please tell me the two hundred plus ways in which coins are
used to make change for one dollar?
```

```
Date: 01/23/2001 at 11:43:55
From: Doctor Greenie
Subject: Re: Coins used to change one dollar

Hi, Maria -

It wouldn't do you any good for us to tell you the 292 different ways
to make change for a dollar. We are here to teach mathematics - that
is, to help you learn ways to answer questions like this for yourself.

I will provide a sketch below of how I would go about enumerating all
of the different ways to make change for a dollar. You can also find
several pages in the Dr. Math archives where this problem is discussed
(using slightly different approaches). To find these pages, click on
the "Search the Archives" link on the main Dr. Math page and enter
"change for a dollar" as the phrase to look for. (Be sure to click on
the button that makes the search engine look for the entire phrase
instead of the individual words.)

The key to answering this question correctly and completely is to
organize your list of ways to make change for a dollar in such a way
that you make sure that you (a) count every possibility, and (b) don't
count any possibilities more than once. With this goal in mind, there
are two key features to my approach to this problem:

(1) Break the problem into smaller parts. I will enumerate all the
possible combinations I can have for the numbers of half dollars and
quarters; then for each of those combinations I will enumerate the
number of ways I can make up the remaining part of a dollar using
dimes, nickels, and pennies.

(2)  Keep the list in either strictly ascending or strictly descending
order in terms of the numbers of coins of different denominations. I
personally prefer to order my list with the largest numbers of
largest-denomination coins at the top. I hope this will be clear from
my outline below.

So here is a list of all the possible combinations I can have of half
dollars and quarters.  The list also shows, for each combination of
half dollars and quarters, the remaining amount to made up using
dimes, nickels, and pennies.

remaining
half                amount
dollars  quarters   (cents)
-------------------------------
2        0          0

1        2          0
1        1         25
1        0         50

0        4          0
0        3         25
0        2         50
0        1         75
0        0        100

Notice the arrangement of this list. The first entry is the one that
uses the maximum number (2) of the largest-denomination coin (half
dollars).  The next three entries are those that use the next largest
number (1) of half dollars; these three entries are arranged with the
one using the largest number of quarters (2) first and the smallest
number of quarters (0) last. Similarly, the last five entries use the
smallest number (0) of half dollars; and they are arranged with the
entry having the largest number of quarters (4) first and the smallest
number of quarters (0) last.

To complete the answer to the problem, you now need to find the
numbers of different ways to make either 0, 25, 50, 75, or 100 cents
using only dimes, nickels, and pennies. Once you have done that, you
can find the total number of ways to make change for a dollar by
adding a column to the table above showing the number of ways to make
change for a dollar using each of the possible combinations of half
dollars and quarters. Then your table will look like this:

remaining     number of ways to make
half                amount      remaining amount using
dollars  quarters   (cents)    dimes, nickels, and pennies
-------------------------------------------------------------
2        0          0              1

1        2          0              1
1        1         25             12
1        0         50             36

0        4          0              1
0        3         25             12
0        2         50             36
0        1         75             72
0        0        100            121
-----
Total number of ways to make   292
change for a dollar

I have filled in the numbers in the last column for you. Clearly if
the amount to be made up using dimes, nickels, and pennies is 0 (i.e.,
the whole dollar is made up using half dollars and/or quarters) then
there is exactly one way to make up the remaining "0 cents": 0 dimes,
0 nickels, and 0 pennies. To determine the other numbers in the last
column, you can make an organized list of all the possibilities, as I
have done for the first part of the problem above.

For example, below is an outline of the organized list showing that
there are 36 ways to make change for 50 cents using dimes, nickels,
and pennies. In this list, I have not listed all the possible
combinations. Instead, I have only indicated, for each possible number
of dimes, the possible numbers of nickels I can use. I can do this
because, since any amount of money can be made using all pennies, I am
able to choose any number of nickels and make up the remaining amount
with pennies. Notice again the arrangement of the entries, with the
largest possible number of dimes first and the smallest possible
number of dimes last.

Number of Ways to Make Change for 50 Cents Using Dimes, Nickels,
Pennies:

choices for
dimes    number of nickels    number of choices
-------------------------------------------------
5              0                 1
4          0, 1, or 2            3
3            0 to 4              5
2            0 to 6              7
1            0 to 8              9
0            0 to 10            11
----
Total number of ways to make      36
change for 50 cents using
dimes, nickels, and pennies

See if you can build the tables showing that the numbers of ways to
make change for 25 cents, 75 cents, and 100 cents using dimes,
nickels, and pennies are as shown in the table above (12, 72, and 121,
respectively). When you have done so, you will have enumerated all 292
possible ways for making change for a dollar.

Your original question asked for us to show you all the possible ways
to make change for a dollar.  As you can see, doing so would be very
tedious. But at this point, you should know what the 292 different
ways are, without having to write them out.

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search