Problem 20 · 2026 AMC 8
Stretch
Counting & Probability
recursioncomposition
The land of Catania uses gold coins (1 mm thick) and silver coins (3 mm thick). In how many ways can Taylor make a stack exactly 8 mm tall using any arrangement of gold and silver coins, where order matters?
Show answer
Answer: D — 13.
Show hints
Hint 1 of 2
Listing every 8 mm stack by hand is error-prone. Instead build the answer from smaller stacks: focus on just the top coin — it's either gold (1 mm) or silver (3 mm). What height of stack sits underneath in each case?
Still stuck? Show hint 2 →
Hint 2 of 2
If f(n) counts stacks of height n, a gold top leaves f(n−1) below it and a silver top leaves f(n−3). So f(n) = f(n−1) + f(n−3). Build up from small heights.
Show solution
Approach: recursion by the top coin: f(n) = f(n−1) + f(n−3)
- Sort stacks of height n by what the top coin is. If it's gold (1 mm), the rest is any stack of height n−1; if it's silver (3 mm), the rest is any stack of height n−3. Those cases don't overlap and cover everything, so f(n) = f(n−1) + f(n−3).
- Seed the small cases: f(0) = 1 (the empty stack), f(1) = 1, f(2) = 1 (only gold fits). Then climb: f(3)=2, f(4)=3, f(5)=4, f(6)=6, f(7)=9, f(8)=13.
- So there are 13 stacks.
- Why this transfers: ‘order matters’ counting with a few fixed step sizes is almost always a recursion — condition on the last piece, and the count for n becomes a sum of counts for smaller totals (this is the same engine behind staircase / tiling problems).
Mark:
· log in to save