Problem 9 · AMC 8 Stretch
Stretch
Algebra & Patterns
Counting & Probability
recursion-and-iterationpattern-recognition
You have a tower of \(n\) discs stacked biggest-on-bottom on one of three rods. Move the whole tower to another rod, moving only one disc at a time and never putting a bigger disc on a smaller one. What is the fewest moves needed, as a formula in \(n\)?
Show answer
Answer: 2^n - 1 moves
Show hints
Hint 1 of 4
Play it by hand. With 1 disc it takes 1 move. With 2 discs, 3 moves. With 3 discs, 7 moves. Write these down.
Still stuck? Show hint 2 →
Hint 2 of 4
Clever idea: to move a tower of \(n\), first move the top \(n-1\) discs to the spare rod, then the big bottom disc, then the \(n-1\) discs back on top.
Still stuck? Show hint 3 →
Hint 3 of 4
So \(H(n) = 2 \times H(n-1) + 1\). Build the list: 1, 3, 7, 15, 31, ... How does each compare to a power of 2?
Show solution
Approach: Recursion, then read off the closed form
- Small cases: \(H(1) = 1\), \(H(2) = 3\), \(H(3) = 7\).
- To move an \(n\)-disc tower: move the top \(n-1\) to the spare rod (\(H(n-1)\) moves), move the biggest disc (1 move), move the \(n-1\) back on top (\(H(n-1)\) moves). So \(H(n) = 2H(n-1) + 1\), which is best possible since the bottom disc can't move until everything above it is parked elsewhere.
- The values \(1, 3, 7, 15, 31, \dots\) are each one less than a power of 2, so \(H(n) = 2^n - 1\).
- Check: \(2H(n) + 1 = 2(2^n - 1) + 1 = 2^{n+1} - 1 = H(n+1)\), so the formula \(H(n) = 2^n - 1\) holds forever.
Mark:
· log in to save