Problem 7 · 2010 AMC 8
Medium
Logic & Word Problems
greedy-coin
Using only pennies, nickels, dimes, and quarters, what is the smallest number of coins Freddie would need so he could pay any amount of money less than a dollar?
Show answer
Answer: B — 10 coins.
Show hints
Hint 1 of 2
You only need enough coins to fill the gaps each bigger coin can't reach by itself.
Still stuck? Show hint 2 →
Hint 2 of 2
Pennies cover the 1¢–4¢ gaps below a nickel; nickels cover the gap below a dime; dimes-and-nickels cover the gap below a quarter — carry just enough of each to bridge to the next coin.
Show solution
Approach: carry just enough small coins to bridge to the next-bigger coin
- To make any 1¢–4¢ ending you need 4 pennies. To reach 5¢–9¢ you need a nickel. To reach 10¢–24¢ you need a dime and a second nickel (a dime alone can't make 15¢).
- Now the four pennies, two nickels, and one dime can make every amount up to 24¢. Three quarters then stack on top to push that all the way to 99¢.
- Total: 4 + 2 + 1 + 3 = 10 coins.
- Why this transfers: ‘cover every amount up to N’ problems are built bottom-up — carry the smallest coins/units needed to bridge each gap, then the next size stacks on top. The dime trap (it can't make 15¢ alone, so you still need a spare nickel) is the kind of gap you must check at every level.
Mark:
· log in to save