Paths & Grids

## What you need to know
- Lattice paths: paths from $(0,0)$ to $(m,n)$ by unit steps right and up number $\binom{m+n}{m}$: choose which of the $m+n$ steps go right.
- Paths through a required point $P$: (paths to $P$) $\times$ (paths from $P$). Paths avoiding $P$: total minus through.
- Vertex labeling: on a grid with blocked cells or one-way edges, write at each vertex the number of ways to reach it, summing over predecessors.
- Diagonal steps change the count; with steps $\{R, U, D\}$ do casework on the number of diagonals.
- An $m \times n$ grid of cells contains $\binom{m+1}{2}\binom{n+1}{2}$ rectangles and $\sum_k (m-k+1)(n-k+1)$ squares.

## How AMC 10 tests it
- Problems 8–15: a direct $\binom{m+n}{m}$ count, often with a forced or forbidden intersection.
- Problems 12–20: paths on an irregular grid (missing edges, one-way streets), intended for vertex labeling.
- Counting squares or rectangles in a figure, or colorings of a $2 \times n$ or $3 \times 3$ board with adjacency rules.
- Problems 18–24: paths with an extra constraint (exactly $k$ direction changes, never crossing the diagonal), where the trick is choosing where turns happen.
- Random-walk variants combining path counts with $2^{-n}$ or $3^{-n}$.

## Standard approaches
1. If steps are only right and up, use $\binom{m+n}{m}$ with through-point multiplication and complement for forbidden points.
2. Otherwise label vertices with counts in order (the Pascal-triangle method); it always works on small grids.
3. For "exactly $k$ turns," count how the R's and U's split into blocks.
4. For colorings and tilings, fix the first row or the most constrained cell and count extensions.
5. Cross-check a row of vertex labels against a known binomial when nothing is blocked.

## 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. Total paths: $\binom{9}{5} = 126$. Through $(2,2)$: $\binom{4}{2}\binom{5}{3} = 6 \cdot 10 = 60$. Through $(3,3)$: $\binom{6}{3}\binom{3}{2} = 20 \cdot 3 = 60$. Through both: $\binom{4}{2}\binom{2}{1}\binom{3}{2} = 6 \cdot 2 \cdot 3 = 36$. Paths through at least one of the points: $60 + 60 - 36 = 84$. Paths avoiding both: $126 - 84 = 42$, so the answer is $\boxed{\textbf{(C)}\ 42}$.

## Pitfalls
- Writing $\binom{m+n}{m}$ with the wrong top: the number of steps is $m + n$, not $mn$ or $m + n - 1$.
- Handling "avoids $A$ and $B$" as total minus through-$A$ minus through-$B$ without adding back paths through both.
- Confusing lattice points with unit cells when a grid is called "$4 \times 4$."
- In vertex labeling, adding a neighbor's count across an edge 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)