Problem 1 · AMC 8 Stretch
Core
Counting & Probability
Algebra & Patterns
reduce-and-expandpattern-recognitionorganizing-data
Laura is training her pet white rabbit, Ghost, to climb a flight of 10 steps. Ghost can hop up 1 step or 2 steps at a time. He never hops down, only up. How many different ways can Ghost hop up the whole flight of 10 steps?
Show answer
Answer: 89 ways
Show hints
Hint 1 of 4
The number 10 is big and a little scary. Start tiny! How many ways can Ghost climb a staircase with just 1 step? With just 2 steps? Write out every possible hopping pattern for the small cases.
Still stuck? Show hint 2 →
Hint 2 of 4
Make a table. For 1, 2, 3, 4, 5 steps, list every sequence of 1-hops and 2-hops and count them. You should get 1, 2, 3, 5, 8. Careful: 1, 2, 3 looks like ordinary counting, but keep going — the next number is 5, not 4!
Still stuck? Show hint 3 →
Hint 3 of 4
Think about Ghost's very last hop. To land on step \(n\), he either came from step \(n-1\) (a 1-hop) or from step \(n-2\) (a 2-hop). So the number of ways to reach step \(n\) is the ways to reach step \(n-1\) PLUS the ways to reach step \(n-2\).
Show solution
Approach: Reduce and expand — shrink to tiny staircases, find the Fibonacci pattern, grow it back
- Ghost's final hop onto step \(n\) came 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 to build the table:
Steps Ways 1 1 2 2 3 3 4 5 5 8 6 13 7 21 8 34 9 55 10 89 - These are the Fibonacci numbers. Reading the table at 10 steps gives the answer: Ghost can climb the flight in \(89\) different ways.
Mark:
· log in to save