AMC 10 · 2006 · #18

Grade 7 countinggeometry-2d
Archetype Branching State Enumeration └ Sub-archetype Numeric Operation Tree
lattice-pathsparity-coloringsystematic-enumeration systematic-enumeration ↑ Prerequisites: lattice-paths
📏 Long solution 💡 4 insights
Problem
A marker hops ten times on a grid, one unit in one of four directions each time. Count how many distinct points it can finish on.

Pick an answer.

(A)
120
(B)
121
(C)
221
(D)
230
(E)
231
How to solve
Strategy Draw a Diagram

Counting endpoints means first describing the set of endpoints, so Tool #1 (Draw a Diagram) carries the work: the reachable points turn out to fill a tilted square, and once that picture is right the count is easy. Getting the picture right takes three separate pieces. Tool #4 (Introduce a Variable) names how many steps go each direction, which converts a path into two coordinates. Tool #14 (Extreme Principle) then pins the outer boundary — you cannot get farther than 10 units of grid distance. A checkerboard coloring adds a second restriction that the boundary alone misses. The step most easily skipped is the converse: those two restrictions rule points out, but nothing so far shows any surviving point is actually hit. Tool #9 (Solve an Easier Related Problem) supplies that missing half — reach the point in the fewest steps, then burn the leftover steps — and only after both halves are proved does Tool #2 (Make a Systematic List) count the region column by column.

1STEP 1

Turn a path into two numbers

A whole path collapses into just two numbers.

x = R-L, y = U-D, R+L+U+D = 10, R,L,U,D ≥ 0
2STEP 2

Find the outer boundary

The hop count caps the distance, giving an outer boundary.

|x|+|y| = |R-L| + |U-D| ≤ (R+L) + (U+D) = 10
3STEP 3

Color the grid like a checkerboard

A checkerboard colouring rules out half the points inside.

x + y = (R+U) - (L+D) = 10 - 2(L+D) → x+y is even
4STEP 4

Prove the survivors really are reachable

Wasted back-and-forth pairs show every survivor is reachable.

d = |x|+|y| ≤ 10, d ≡ x+y ≡ 0 (mod 2) → (10-d)/2 ∈ {0,1,…,5} wasted right-left pairs
5STEP 5

Count the diamond column by column

Counting column by column gives 121, choice (B).

Σ_x=-10¹⁰ (11-|x|) = 11 + 2(10+9+…+1) = 11 + 2 · 55 = 121 → (B)
Answer
121
The wrong answers say exactly which step was skipped, which is a good way to test the work. Counting the whole diamond |x|+|y| ≤ 10 without the color rule gives 1 + 4(1+2+…+10) = 221, which is choice (C) — the answer for someone who proved the boundary but never noticed parity. That number also checks the real count: the diamond's white points are the ones a nine-step path can reach, and the same column count gives 10² = 100 of them, and 121 + 100 = 221 closes the books on every point in the diamond. Choice (A) 120 is 121 minus the origin, the slip of forgetting that returning home counts as an endpoint (five right-left pairs do it). The result is also stable under a shrink test: repeating the argument with n steps gives (n+1)², and direct listing confirms 4 endpoints for n=1 and 9 for n=2 — but that pattern is a check, not a proof, since three small cases cannot rule out a change later.
💡Key takeaway

Before you count the places you can land, prove both halves — which points are blocked, and that every point left over can really be reached.

  • Turn a path into two numbers
  • Find the outer boundary
  • Color the grid like a checkerboard
  • Prove the survivors really are reachable
  • Count the diamond column by column

More like this

Same archetype — closest grade level first.