# Problem: Coins

In how many ways can 19 coins equal exactly one dollar?

# Discussion/Solution? :

What are the possible types of coins that can be used to obtain a sum of one dollar?

penny, nickel, dime, quarter, half dollar

So there are five different types of coins.

### Strategy:

Consider five cases involving
(1) only one type of coin
(2) only two types of coins
(3) only three types of coins
(4) only four types of coins
(5) all five types of coins

### Solutions:

Case (1): It is impossible to have 19 coins of the same type that equal one dollar.

19 pennies = 19 cents
19 nickels = 95 cents
19 dimes = \$1.90 (too big so quarters and half dollars are also eliminated)

Case (2): There are TWO ways to have one dollar using only two types of coins.

10 pennies and 9 dimes = \$1
18 nickels and 1 dime = \$1

Case (3): There are THREE ways to have one dollar using only three types of coins.

15 pennies, 1 dime, and 3 quarters = \$1
10 pennies, 8 nickels, and 1 half dollar = \$1
5 pennies, 9 nickels, and 5 dimes = \$1

Case (4): There are FOUR ways to have one dollar using only four types of coins.

15 pennies, 2 nickels, 1 quarter, and 1 half dollar = \$1
10 pennies, 3 nickels, 5 dimes, and 1 quarter = \$1
10 pennies, 6 nickels, 1 dime, and 2 quarters = \$1
5 pennies, 12 nickels, 1 dime, and 1 quarter = \$1

Case (5): It is impossible to have all five types of coins.

Suppose we did have all five types of coins. We could have at most one half dollar. So we have accounted for 50 cents. That leaves 50 cents for the other four types of coins. If we are to have all four types then we can have at most one quarter (25 cents). We must now split the remaining 25 cents among the dimes, nickels, and pennies. If we have just one dime, one nickel, and one penny (16 cents), then the remaining 9 cents must be in pennies (i.e. 9 pennies) or made up of another nickel and 4 more pennies. We now have

10 pennies, 1 nickel, 1 dime, 1 quarter, and 1 half dollar = \$1
or 5 pennies, 2 nickels, 1 dime, 1 quarter, and 1 half dollar = \$1

However, we only have 10 + 1 + 1 + 1 + 1 = 14 coins or 5 + 2 + 1 + 1 + 1 = 10 coins
( not the 19 coins we wanted).

Therefore, it is impossible to use all five types of coins to get 19 coins to equal one dollar.

## Observations:

1. The number of half dollars must be 0, 1.
2. The number of quarters must be 0, 1, 2, 3.
3. The number of dimes must be 0, 1, 5, 9.
4. The number of nickels must be 0, 2, 3, 6, 8, 9, 12, 18.
5. The number of pennies must be 0, 5, 10, or 15.

The first two observations are obvious. Since half dollars are worth 50 cents each, we can have at most one. Also, since quarters are worth 25 cents each, we can have at most 3.

What about the other observations? Obviously, we can have at most 9 dimes, but why only 0, 1, 5, or 9? Why not 2, 3, 4, 6, 7, or 8? It may be easier to consider the pennies first.

Let p, n, d, q, hd represent the number of pennies, nickels, dimes, quarter, and half dollars, respectively.

So
p + 5n + 10d + 25q + 50 hd = 100

If we evaluate the equation (mod 5) we get
p = 0 (mod 5)
i.e. p = 0, 5, 10, 15, ... but since we can only have 19 coins, there is at most 15 pennies

Therefore, p = 0, 5, 10, or 15. i.e. p = 5k where k = 0,1,2,3