← Sensim Lab Sensim Math

AMC 8 · 2010 · #25

Grade 4 counting
Archetype Branching State Enumeration
recursive-sequencepattern-recognitionsystematic-enumeration tree-enumerationpattern-recognitioneasier-related-problem ↑ Prerequisites: systematic-enumerationpattern-recognition
📏 Long solution 💡 4 insights

Problem

Everyday at school, Jo climbs a flight of 66 stairs. Jo can take the stairs 11, 22, or 33 at a time. For example, Jo could climb 33, then 11, then 22. In how many ways can Jo climb the stairs?

Pick an answer.

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

Toolkit + CCSS Solution

Understand

Restated: 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?

Givens: Total of $6$ stairs to climb; Each step can be $1$, $2$, or $3$ stairs; Sequences are ordered: $1, 2$ and $2, 1$ count as two different ways; Answer choices: (A) $13$, (B) $18$, (C) $20$, (D) $22$, (E) $24$

Unknowns: The number of distinct ordered sequences of $1$s, $2$s, and $3$s whose terms sum to $6$

Understand

Restated: 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?

Givens: Total of $6$ stairs to climb; Each step can be $1$, $2$, or $3$ stairs; Sequences are ordered: $1, 2$ and $2, 1$ count as two different ways; Answer choices: (A) $13$, (B) $18$, (C) $20$, (D) $22$, (E) $24$

Plan

Primary tool: #7 Identify Subproblems

Secondary: #9 Solve an Easier Related Problem, #2 Make a Systematic List, #5 Look for a Pattern

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.

Execute — Answer: E

#9 Solve an Easier Related Problem K.OA.A.1 Step 1
  • Use Tool #9 to shrink the problem.
  • Start with $1$ stair: the only move is a single $1$.
  • So $f(1) = 1$.
$$f(1) = 1$$

💡 Solving the smallest case first is the Tool #9 move — it gives us a foothold.

#2 Make a Systematic List 1.OA.A.1 Step 2
  • List the sequences for $2$ stairs using Tool #2: $(1,1)$ and $(2)$.
  • That's $f(2) = 2$.
  • Then for $3$ stairs: $(1,1,1)$, $(1,2)$, $(2,1)$, $(3)$ — so $f(3) = 4$.
$$f(2) = 2, \quad f(3) = 4$$

💡 Listing strictly by "length of the first move" keeps the count complete and duplicate-free.

#7 Identify Subproblems 4.OA.C.5 Step 3
  • Now apply Tool #7.
  • For any $n \ge 4$, look at Jo's last move: it was either a $1$ (then the previous landing was stair $n-1$), a $2$ (previous was $n-2$), or a $3$ (previous was $n-3$).
  • Each case contributes $f(n-1)$, $f(n-2)$, $f(n-3)$ sequences.
  • Add them.
$$f(n) = f(n-1) + f(n-2) + f(n-3)$$

💡 Splitting by "what the last step was" turns one hard question into three easier ones — the heart of Tool #7.

#5 Look for a Pattern 4.OA.C.5 Step 4
  • Use the rule from Step 3 to extend the pattern with Tool #5.
  • From $f(1) = 1$, $f(2) = 2$, $f(3) = 4$, compute $f(4)$, $f(5)$, $f(6)$ in turn.
$$f(4) = 4 + 2 + 1 = 7$$

💡 Each new term is just the sum of the three before it — a clean numeric pattern to extend.

#5 Look for a Pattern 4.OA.C.5 Step 5

Keep the recurrence rolling to reach $f(6)$.

$$f(5) = 7 + 4 + 2 = 13, \quad f(6) = 13 + 7 + 4 = 24 \;\Rightarrow\; \textbf{(E)}$$

💡 Reaching $f(6)$ took only two more additions — far faster than listing all $24$ sequences.

[1] #9 K.OA.A.1 Use Tool #9 to shrink the problem. Start with $1$ stair: the only move is a sing
[2] #2 1.OA.A.1 List the sequences for $2$ stairs using Tool #2: $(1,1)$ and $(2)$. That's $f(2)
[3] #7 4.OA.C.5 Now apply Tool #7. For any $n \ge 4$, look at Jo's last move: it was either a $1
[4] #5 4.OA.C.5 Use the rule from Step 3 to extend the pattern with Tool #5. From $f(1) = 1$, $f
[5] #5 4.OA.C.5 Keep the recurrence rolling to reach $f(6)$.

Review

Reasonableness: 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.

Alternative: Tool #2 (Systematic List) by partitions: the multisets of $1$s, $2$s, $3$s that sum to $6$ are $\{1,1,1,1,1,1\}$, $\{1,1,1,1,2\}$, $\{1,1,2,2\}$, $\{2,2,2\}$, $\{1,1,1,3\}$, $\{1,2,3\}$, $\{3,3\}$. The number of orderings of each is $1, 5, 6, 1, 4, 6, 1$ respectively. Sum: $1+5+6+1+4+6+1 = 24$. Same answer.

CCSS standards used (min grade 4)

  • K.OA.A.1 Represent addition and subtraction with objects, drawings, etc. (Establishing the base case $f(1) = 1$ — there is exactly one way to climb a single stair.)
  • 1.OA.A.1 Use addition and subtraction within $20$ to solve word problems (Counting the small cases $f(2) = 2$ and $f(3) = 4$ by listing every valid sequence.)
  • 4.OA.C.5 Generate and analyze patterns (Setting up the recurrence $f(n) = f(n-1) + f(n-2) + f(n-3)$ and extending it term by term to compute $f(4) = 7$, $f(5) = 13$, $f(6) = 24$.)

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

⭐ 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

Same archetype — closest grade level first.