Paths & Grids

What you need to know

• Grid paths. A path from $(0,0)$ to $(m,n)$ by unit steps right (R) or up (U) has $m+n$ steps: $m$ R's and $n$ U's. Choosing which steps are R's decides the path: $\binom{m+n}{m}$ paths. Example: from $(0,0)$ to $(3,2)$ there are $\binom53 = 10$ paths.
• Through a point, or avoiding it. Paths through a point $P$: (paths to $P$) $\times$ (paths from $P$ to the end). Paths avoiding $P$: all paths minus those through $P$. Example: to $(3,2)$ through $(1,1)$: $\binom21\cdot\binom31 = 6$ paths, so $10-6 = 4$ avoid $(1,1)$.
• Labeling the corners. When some streets are blocked or one-way, write at each corner the number of ways to reach it: the sum of the numbers at the corners you can arrive from.
• Diagonal steps change the count. If a diagonal step D (right and up at once) is also allowed, do casework on the number of D's. Example: to $(2,2)$ with steps R, U, D: no D's gives $\binom42 = 6$ paths, one D gives $3! = 6$ (orders of R, U, D), two D's give $1$, so $13$ in all.
• Rectangles and squares. A grid of $m$ by $n$ unit squares has $\binom{m+1}{2}\binom{n+1}{2}$ rectangles (choose $2$ of the $m+1$ vertical lines and $2$ of the $n+1$ horizontal ones). It has $mn+(m-1)(n-1)+(m-2)(n-2)+\cdots$ squares ($1\times1$, then $2\times2$, and so on), stopping when a factor reaches $0$. Example: a $3\times3$ grid has $\binom42\binom42 = 36$ rectangles and $9+4+1 = 14$ squares.

How AMC 10 tests it

• Problems 8–15: a direct $\binom{m+n}{m}$ count, often with a point the path must pass through or avoid.
• Problems 12–20: paths on an irregular grid (missing streets, one-way streets), meant for labeling the corners.
• Counting squares or rectangles in a figure, or colorings of a $2\times n$ or $3\times3$ board with rules about neighboring cells.
• Problems 18–24: paths with an extra rule (exactly $k$ changes of direction, never crossing the diagonal), where the trick is choosing where the turns happen.
• Random walks: multiply a path count by $\frac{1}{2^n}$ or $\frac{1}{3^n}$, the chance of one particular $n$-step path when each step has $2$ or $3$ equally likely choices.

Standard approaches

1. With only right and up steps, use $\binom{m+n}{m}$. Multiply for a point the path must pass through; subtract for a point it must avoid.
2. Otherwise label the corners in order (the Pascal's Triangle method); it always works on small grids.
3. For "exactly $k$ turns," count how the R's and U's split into runs. Example: $(0,0)$ to $(3,3)$ with exactly $3$ turns has $4$ runs (like RR U R UU): $2$ ways to split the R's into $2$ runs, $2$ for the U's, and $2$ choices of first step, so $8$ paths.
4. For colorings and tilings, fix the first row or the most limited cell, then count the ways to finish.
5. With nothing blocked, the corner labels should match $\binom{m+n}{m}$; use this as a check.

Worked example

A path goes from $(0,0)$ to $(5,4)$ using unit steps right or up. How many such paths pass through neither $(2,2)$ nor $(3,3)$?

(A) $30$ (B) $36$ (C) $42$ (D) $48$ (E) $54$

Solution. Use complementary counting and PIE.

Step 1: all paths. There are $5$ R's and $4$ U's: $\binom95 = 126$ paths.

Step 2: through $(2,2)$. $\binom42 = 6$ ways to get there, then $3$ R's and $2$ U's to finish: $\binom53 = 10$. So $6\cdot10 = 60$.

Step 3: through $(3,3)$. $\binom63 = 20$ ways to get there, then $2$ R's and $1$ U: $\binom32 = 3$. So $20\cdot3 = 60$.

Step 4: through both. $6$ ways to $(2,2)$, then $\binom21 = 2$ to $(3,3)$, then $3$ to the end: $6\cdot2\cdot3 = 36$.

Step 5: combine. Through at least one point: $60+60-36 = 84$. Through neither: $126-84 = 42$.

The answer is $\boxed{\textbf{(C)}\ 42}$.

Pitfalls

• Using the wrong top number in $\binom{m+n}{m}$. The number of steps is $m+n$, not $mn$ or $m+n-1$.
• Treating "avoids $A$ and $B$" as all paths minus those through $A$ minus those through $B$, without adding back those through both. Above, that gives $126-60-60 = 6$ instead of $42$.
• Mixing up points and squares when a grid is called "$4\times4$." A $4\times4$ grid of squares has $5\times5$ points; corner to corner is $\binom84 = 70$ paths, not $\binom63 = 20$.
• In corner labeling, adding a neighbor's number across a street that is actually blocked.

Traps that recur

• Forgetting the two loops that never enter the middle row (the full top-row and full bottom-row rectangles), which gives 144, choice (B). (2024 AMC 10A #25)
• Ignoring the three leftward arrows and counting only monotone paths (1024), or forgetting that the bug may switch between the upper and lower halves at a center vertex. (2012 AMC 10B #25)
• Treating the edge-middle squares as independent choices, or forgetting the two cases (two opposite pairs equal vs. one pair equal) in the cycle count. (2023 AMC 10A #20)
• Forgetting that empty cells with exactly three filled neighbors turn on, including the border midpoints when a full side of the 3×3 is filled. (2022 AMC 10B #19)