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

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Draw a Diagram

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)".

1STEP 1

Label columns 0-7 left-to-right and rows 0-7 bottom-to-top; from the figure P sits at (0, 5) and Q at (7, 6).

P = (0, 5), Q = (7, 6)

2STEP 2

Let N(r, c) = paths to square (r, c); a square is fed by its two lower diagonals, so N(r, c) = N(r-1, c-1) + N(r-1, c+1), N(0, 5) = 1.

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

3STEP 3

Apply the rule upward - row 1: 1, 1; row 2: 1, 2, 1; row 3: 1, 3, 3 (column 8 is off-board, adding nothing there).

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

4STEP 4

Keep summing to row 6, edges inheriting one value - row 4: 4, 6, 3; row 5: 10, 9; row 6: 19, 9.

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

5STEP 5

Finish at Q: N(7, 6) = 19 + 9 = 28, so there are 28 distinct 7-step paths from P to Q - choice (A).

N(7, 6) = 19 + 9 = 28 → (A)

Answer

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 C(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.

💡Key takeaway

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!

More like this