Change for a dollar
In how many ways can 100 cents be made from coins of 1, 5, 10, 25 and 50 cents? The order of the coins does not matter.
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Count by the number of 50-cent and 25-cent coins first; the rest is made of 10, 5 and 1.
With 1, 5 and 10 cent coins only, an amount can be made in as many ways as there are choices of the number of dimes and nickels with .
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Fix the large coins first. Once the 50s and 25s are chosen, count the ways to fill the rest with 10s and 5s; the pennies then fill the gap in exactly one way.
Step 1: small coins. With 10, 5 and 1 cent coins, the number of ways to make cents is the number of pairs with . For (a multiple of 5) this is This gives:
- 100 cents: ;
- 75 cents: ;
- 50 cents: ;
- 25 cents: ;
- 0 cents: 1.
Step 2: the large coins. The 50s and 25s leave cents:
- no 50-cent coin: 0 to 4 quarters leave 100, 75, 50, 25, 0 cents: ways;
- one 50-cent coin: 0 to 2 quarters leave 50, 25, 0: ways;
- two 50-cent coins: 1 way.
Step 3.
Remark. If a 1-dollar coin is allowed too, the answer is 293.