AMC 8 · 2020 · #21

Grade 5 counting

Archetype Branching State Enumeration └ Sub-archetype Constrained Sequence or Path Count

pattern-recognitioncombinations-basicsystematic-enumeration tree-enumerationpattern-recognitionidentify-subproblems ↑ Prerequisites: systematic-enumeration

📏 Long solution 💡 4 insights 📊 Diagram

📘 View easy version →

Problem

A game board consists of $64$ squares that alternate in color between black and white. The figure below shows square $P$ in the bottom row and square $Q$ in the top row. A marker is placed at $P.$ A step consists of moving the marker onto one of the adjoining white squares in the row above. How many $7$ -step paths are there from $P$ to $Q?$ (The figure shows a sample path.)

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

Try it yourself first — the explanation is most useful after you’ve attempted it.

View mode:

Toolkit + CCSS Solution

Understand

Restated: A checkerboard has $64$ alternating black and white squares. A marker starts on white square $P$ in the bottom row. Each step moves the marker diagonally up-left or up-right to an adjoining white square in the row above. The marker needs to reach white square $Q$ in the top row using exactly $7$ steps. How many distinct $7$-step paths from $P$ to $Q$ are there?

Givens: An $8 \times 8$ checkerboard with alternating black and white squares; Marker starts at $P$ (white square in the bottom row); Target square $Q$ is in the top row (white); Each step moves the marker to a white square diagonally above (up-left or up-right) and must stay on the board; Exactly $7$ steps are taken (bottom row to top row); Answer choices: (A) $28$, (B) $30$, (C) $32$, (D) $33$, (E) $35$

Unknowns: The number of distinct $7$-step paths from $P$ to $Q$

Understand

Plan

Primary tool: #1 Draw a Diagram

Secondary: #5 Look for a Pattern, #7 Identify Subproblems

Path-counting on a grid is the textbook job for Tool #1 (Draw a Diagram): redraw the board with $P$ at the bottom and write the number of paths into each reachable white square, working one row at a time. Tool #5 (Look for a Pattern) shows up because the count at each square is the sum of the counts at the two diagonal squares below it — exactly the Pascal's-triangle pattern, modified at the edges where one diagonal falls off the board. Tool #7 (Identify Subproblems) makes the bookkeeping clean: "how many ways to reach $(r,c)$" is solved by adding the answers to the two smaller subproblems "how many ways to reach $(r-1, c-1)$" and "how many ways to reach $(r-1, c+1)$".

Execute — Answer: A

#1 Draw a Diagram 5.G.A.1 Step 1

Set up a coordinate system: label columns $0$-$7$ left to right and rows $0$-$7$ bottom to top.
From the figure, $P$ is at (row $0$, col $5$) and $Q$ is at (row $7$, col $6$).
Confirm that every legal move goes from a white square to a white square diagonally one row up; the marker can never land on a black square or step sideways.

$$P = (0, 5), \quad Q = (7, 6)$$

💡 Setting up rows and columns on the board is the Grade 5 coordinate-grid idea: every white square gets an address $(r, c)$.

#7 Identify Subproblems 4.OA.C.5 Step 2

State the counting rule.
Let $N(r, c)$ be the number of $r$-step paths from $P$ to the white square at $(r, c)$.
A white square at $(r, c)$ is reachable only from $(r-1, c-1)$ or $(r-1, c+1)$ (and only when those squares are on the board), so $N(r, c) = N(r-1, c-1) + N(r-1, c+1)$.
Seed the recursion with $N(0, 5) = 1$ (there is exactly one way to be at $P$ to start).

$$N(r, c) = N(r-1, c-1) + N(r-1, c+1), \quad N(0, 5) = 1$$

💡 Splitting "reach $(r, c)$" into the two smaller subproblems "reach the two diagonal neighbors below" is the Grade 4 "generate a pattern from a rule" move.

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

Fill in the counts row by row, using the rule from Step 2.
Row $1$ from $P$: $(1, 4) = 1$ and $(1, 6) = 1$.
Row $2$: $(2, 3) = 1$, $(2, 5) = 1 + 1 = 2$, $(2, 7) = 1$.
Row $3$: $(3, 2) = 1$, $(3, 4) = 1 + 2 = 3$, $(3, 6) = 2 + 1 = 3$ (the square at $(3, 8)$ is off the board, so nothing is added there).

$$N(1, 4) = 1,\; N(1, 6) = 1; \quad N(2, 3) = 1,\; N(2, 5) = 2,\; N(2, 7) = 1; \quad N(3, 2) = 1,\; N(3, 4) = 3,\; N(3, 6) = 3$$

💡 Each new number is the sum of the two diagonal numbers right below it — the same Pascal's-triangle pattern from Grade 4.

#1 Draw a Diagram 4.OA.C.5 Step 4

Continue the row-by-row sums to row $6$, watching the right edge of the board (column $8$ doesn't exist, so squares like $(4, 7)$ inherit only the count from $(3, 6)$).
Row $4$: $(4, 3) = 1 + 3 = 4$, $(4, 5) = 3 + 3 = 6$, $(4, 7) = 3$.
Row $5$: $(5, 4) = 4 + 6 = 10$, $(5, 6) = 6 + 3 = 9$.
Row $6$: $(6, 5) = 10 + 9 = 19$, $(6, 7) = 9$.

$$N(4, 3) = 4,\; N(4, 5) = 6,\; N(4, 7) = 3; \quad N(5, 4) = 10,\; N(5, 6) = 9; \quad N(6, 5) = 19,\; N(6, 7) = 9$$

💡 Writing the running total into each white square keeps the bookkeeping visual, with edge squares getting only one contribution.

#1 Draw a Diagram 4.NBT.B.4 Step 5

Compute $N(7, 6) = N(6, 5) + N(6, 7) = 19 + 9 = 28$.
So there are exactly $28$ distinct $7$-step paths from $P$ to $Q$, which is choice (A).

$$N(7, 6) = 19 + 9 = 28 \;\Rightarrow\; \textbf{(A)}$$

💡 Adding the two contributions $19 + 9 = 28$ is a Grade 4 multi-digit addition.

[1] #1 5.G.A.1 Set up a coordinate system: label columns $0$-$7$ left to right and rows $0$-$7$

[2] #7 4.OA.C.5 State the counting rule. Let $N(r, c)$ be the number of $r$-step paths from $P$

[3] #5 4.OA.C.5 Fill in the counts row by row, using the rule from Step 2. Row $1$ from $P$: $(1

[4] #1 4.OA.C.5 Continue the row-by-row sums to row $6$, watching the right edge of the board (c

[5] #1 4.NBT.B.4 Compute $N(7, 6) = N(6, 5) + N(6, 7) = 19 + 9 = 28$. So there are exactly $28$ d

Review

Reasonableness: Sanity-check with the unconstrained version: without any edge or board limits, a $7$-step random walk that ends up shifted by exactly $+1$ to the right (from column $5$ to column $6$) needs $4$ right-steps and $3$ left-steps, giving $\binom{7}{4} = 35$ paths. Our answer $28$ is a bit smaller, which makes sense because the right edge of the board cuts off some paths (a marker reaching $(4, 7)$ on the right edge only has one continuation instead of two). The leak is exactly $35 - 28 = 7$ paths killed by the edge, which is a believably small correction.

Alternative: Tool #16 (Change Focus / Complement) gives the slick alternative above: count $\binom{7}{4} = 35$ free paths first, then subtract the paths that would step off the right edge using the reflection principle. For students who haven't met binomial coefficients yet, Tool #2 (Systematic List) also works — enumerate all $7$-step sequences of L/R, throw out the ones that go off-board, and count what's left.

CCSS standards used (min grade 5)

5.G.A.1 Use a pair of perpendicular number lines forming a coordinate system (Labeling rows $0$-$7$ and columns $0$-$7$ on the board so every white square has an address $(r, c)$, locating $P = (0, 5)$ and $Q = (7, 6)$.)
4.OA.C.5 Generate a number or shape pattern following a given rule (Applying the rule $N(r, c) = N(r-1, c-1) + N(r-1, c+1)$ row by row to build the path-count pattern (a Pascal's-triangle style growth).)
4.NBT.B.4 Fluently add and subtract multi-digit whole numbers (Adding small whole numbers like $10 + 9 = 19$ and $19 + 9 = 28$ during the row-by-row fill.)

⭐ This AMC 8 problem only needs Grade 5 coordinate grids and the Grade 4 "add the two numbers below" Pascal's-triangle pattern you already know!

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: A

Review

CCSS standards used (min grade 5)

More like this