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)

(B)

(C)

(D)

(E)

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

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

f(1) = 1

2STEP 2

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

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

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 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

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!

More like this