Problem 1 · AMC 8 Stretch
Core
Counting & Probability
reduce-and-expandsequence-of-figures
A rabbit climbs a staircase of 10 steps, hopping either 1 step or 2 steps at a time. In how many different orders can it reach the top?
Show answer
Answer: 89 ways
Show hints
Hint 1 of 3
Start tiny: how many ways for a 1-step staircase? A 2-step one? A 3-step one? Write every hopping pattern out.
Still stuck? Show hint 2 →
Hint 2 of 3
The counts go 1, 2, 3, 5, 8, ... — each new count is the sum of the previous two, because the very last hop is either a 1 or a 2.
Still stuck? Show hint 3 →
Hint 3 of 3
Keep that adding going all the way up to step 10.
Show solution
Approach: Reduce and expand — shrink to tiny staircases, find the pattern, grow it back
- The last hop onto step n comes from step n−1 (a 1-hop) or step n−2 (a 2-hop), so ways(n) = ways(n−1) + ways(n−2).
- Tiny cases by listing: a 1-step staircase has 1 way; a 2-step staircase has 2 ways (1+1 or 2).
- Now add the two previous each time: 3→3, 4→5, 5→8, 6→13, 7→21, 8→34, 9→55, 10→89.
- So the rabbit can climb the 10 steps in 89 different orders. (These are the Fibonacci numbers.)
Mark:
· log in to save