Problem 25 · 2010 AMC 8
Hard
Counting & Probability
recurrencecomposition
Everyday at school, Jo climbs a flight of 6 stairs. Jo can take the stairs 1, 2, or 3 at a time. For example, Jo could climb 3, then 1, then 2. In how many ways can Jo climb the stairs?
Show answer
Answer: E — 24 ways.
Show hints
Hint 1 of 3
Don't try to list all the ways for 6 stairs — that's a mess. Instead ask: what was Jo's last step? It was a 1, 2, or 3, landing on stair 6 from stair 5, 4, or 3. So the count for 6 is built from the counts for 5, 4, and 3.
Still stuck? Show hint 2 →
Hint 2 of 3
That ‘classify by the final move’ idea gives a recurrence: ways(n) = ways(n−1) + ways(n−2) + ways(n−3). Build the small cases up to 6.
Still stuck? Show hint 3 →
Hint 3 of 3
Anchor the start: ways(1)=1, ways(2)=2 (1+1 or 2), ways(3)=4 (1+1+1, 1+2, 2+1, 3).
Show solution
Approach: build up by classifying the last step (recurrence)
- The last step onto stair n was a 1, 2, or 3, coming from stair n−1, n−2, or n−3. Those cases don't overlap and cover everything, so ways(n) = ways(n−1) + ways(n−2) + ways(n−3).
- Base counts: ways(1)=1, ways(2)=2, ways(3)=4.
- Climb the ladder: ways(4) = 1+2+4 = 7, ways(5) = 2+4+7 = 13, ways(6) = 4+7+13 = 24.
- Why this transfers: ‘in how many ways’ counting problems with a repeated choice (step sizes, tiles, coin sequences) crack open by conditioning on the last move — turning one hard count into a sum of smaller solved counts. (With only 1- and 2-steps it's the Fibonacci numbers.)
Another way — count which inner stairs she lands on, then forbid big jumps:
- Think of stairs 1–5 as optional landing spots (she must finish on 6). Each of the 5 inner stairs is either stepped on or skipped, giving 25 = 32 raw sequences of step-sizes.
- But some of those imply a jump of 4, 5, or 6 stairs, which isn't allowed. Counting the sequences that contain such an over-long gap gives exactly 8 bad ones.
- Valid ways = 32 − 8 = 24 — a complementary-counting route that confirms the recurrence.
Mark:
· log in to save