Competition · AMC preparation · step 4 of 4

AMC 8 · 2010 · #25

Grade 4 counting
Archetype Branching State Enumeration └ Sub-archetype Constrained Sequence or Path Count
recursive-sequencepattern-recognitionsystematic-enumeration tree-enumerationpattern-recognitioneasier-related-problem ↑ Prerequisites: systematic-enumerationpattern-recognition
📏 Long solution 💡 4 insights
Problem
Jo climbs a 6-stair flight, and each move covers 1, 2, or 3 stairs. Counting the order in which the moves are made (so 3, 1, 2 and 2, 1, 3 are different), in how many different sequences can Jo reach the top?

Pick an answer.

(A)
13
(B)
18
(C)
20
(D)
22
(E)
24

AMC 8 2010 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Identify Subproblems

Listing all sequences for 6 stairs by hand is error-prone, so we use Tool #9 first: solve the easier versions f(1), f(2), f(3) by Tool #2 (systematic listing). Then Tool #7 (Identify Subproblems) gives the key idea: whatever Jo's last move was — a 1, a 2, or a 3 — the rest of the climb is just a smaller version of the same problem. That splits f(n) into three subproblems: f(n-1) + f(n-2) + f(n-3). Tool #5 (Pattern) then lets us extend the rule from the easy cases up to n = 6 without writing out a single full sequence.

1STEP 1

Count one-stair sequences

Shrink the problem first (Tool #9): with just 1 stair there is a single move, so f(1) = 1.

f(1) = 1
2STEP 2

Count two and three stairs

List them out (Tool #2): 2 stairs give (1,1),(2) so f(2) = 2; 3 stairs give four routes so f(3) = 4.

f(2) = 2, f(3) = 4
3STEP 3

Build the recurrence

Split by Jo's last move (Tool #7): a 1, 2, or 3 means the prior spot was n-1, n-2, or n-3, so add f(n-1) + f(n-2) + f(n-3).

f(n) = f(n-1) + f(n-2) + f(n-3)
4STEP 4

Extend to four stairs

Now just extend the pattern (Tool #5): from 1, 2, 4 the rule gives f(4) = 7.

f(4) = 4 + 2 + 1 = 7
5STEP 5

Roll on to six stairs

Roll the recurrence once more: f(5) = 13, then f(6) = 24 — that's (E).

f(5) = 7 + 4 + 2 = 13, f(6) = 13 + 7 + 4 = 24 → (E)
Answer
24
The answer 24 is the largest choice, which fits intuition: a 6-stair climb with three different step sizes gives many ordered combinations. We can spot-check f(4) = 7 by listing — (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2), (1,3), (3,1) — exactly 7. The recurrence holds, so f(6) = 24 is consistent.
💡Key takeaway

This AMC 8 problem only needs Grade 4 pattern reasoning — split by the last step and add the smaller cases — that you already know!

  • Count one-stair sequences
  • Count two and three stairs
  • Build the recurrence
  • Extend to four stairs
  • Roll on to six stairs

A parent dashboard for the family lives at sensimlab.com.

More like this

Same problem type. Tags show what each one shares with this problem.