Counting & ProbabilityDifficulty 15-808 tagged problems

Grid Paths

Grid Paths is the habit of counting lattice walks with step choices, obstacles, and reflection or complement ideas. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\#(\text{monotone lattice paths from } (0,0) \text{ to } (m,n)) = \binom{m+n}{n}$$

A shortest grid path using only right and up steps is determined by which of its steps are 'up,' giving a binomial count.

Why It Works

1
To reach $(m, n)$ using only unit Right and Up steps, you must take exactly $m$ Rights and $n$ Ups in some order.
2
Every path is a sequence of $m + n$ steps; the path is fixed once you decide which $n$ of those positions are the Up steps.
3
Choosing those $n$ positions out of $m + n$ gives $\binom{m + n}{n}$ (equivalently $\binom{m+n}{m}$).
4
Obstacles or 'stay below the diagonal' constraints are then handled by subtracting bad paths or via reflection.

Worked Examples

Example 1

On a city grid, how many shortest paths go from $(0,0)$ to $(5,3)$ using only east and north unit steps?

1
A shortest path needs $5$ East steps and $3$ North steps, in some order — $8$ steps total.
2
Pick which $3$ of the $8$ steps are North: $\binom{8}{3}$.
3
Compute: $\binom{8}{3} = \dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56$.

Answer:

$56$

Warm-up

How many shortest grid paths from $(0,0)$ to $(4,4)$ pass through the point $(2,1)$?

1
A path through $(2,1)$ splits into two independent legs: $(0,0) \to (2,1)$ and $(2,1) \to (4,4)$. Multiply the counts.
2
First leg: $2$ East and $1$ North steps, $\binom{2+1}{1} = \binom{3}{1} = 3$ paths.
3
Second leg: from $(2,1)$ to $(4,4)$ needs $2$ East and $3$ North, $\binom{2+3}{3} = \binom{5}{3} = 10$ paths.
4
Multiply: $3 \cdot 10 = 30$.

Answer:

$30$

Contest level

How many shortest grid paths from $(0,0)$ to $(5,5)$ AVOID the single forbidden lattice point $(2,2)$?

1
Count all monotone paths, then subtract those that pass through $(2,2)$.
2
All paths $(0,0) \to (5,5)$: $\binom{10}{5} = 252$.
3
Paths through $(2,2)$: from $(0,0)$ to $(2,2)$ is $\binom{4}{2} = 6$, and from $(2,2)$ to $(5,5)$ is $\binom{6}{3} = 20$; multiply for $6 \cdot 20 = 120$.
4
Subtract: $252 - 120 = 132$.

Answer:

$132$

Olympiad / Challenge

How many monotone paths from $(0,0)$ to $(5,5)$ stay weakly below the diagonal $y \le x$ at every step? (A Catalan-type reflection problem.)

1
Such 'never cross above the diagonal' paths from $(0,0)$ to $(n,n)$ are counted by the Catalan number $C_n = \dfrac{1}{n+1}\binom{2n}{n}$.
2
By the reflection principle, the number of BAD paths (touching $y = x + 1$) equals the number of all monotone paths from $(-1,1)$ to $(5,5)$, which is $\binom{10}{4}$.
3
So good paths $= \binom{10}{5} - \binom{10}{4} = 252 - 210 = 42$.
4
Check with the formula: $C_5 = \dfrac{1}{6}\binom{10}{5} = \dfrac{252}{6} = 42$. Match.

Answer:

$42$

Going Deeper

The lattice-path model is a bijection engine: a path to $(m,n)$ is just a binary string with $m$ R's and $n$ U's, so $\binom{m+n}{n}$ also counts multiset arrangements, and paths-through-a-point factor as a product of two binomials. Constrained paths (avoid a point, stay below a line, pass a checkpoint) are handled by subtraction or the reflection principle.
Grid paths appear directly in AMC/AIME 'how many shortest routes' city-block problems, and indirectly as a visual model for binomial coefficients, Pascal's triangle (the value at a cell is the number of paths reaching it), and ballot/Catalan problems. Recognizing a counting problem as a path problem often unlocks a clean binomial answer.
Pitfall: the binomial $\binom{m+n}{n}$ counts MONOTONE paths only — every step must be R or U; if backtracking is allowed the count explodes. For 'avoid a point' problems, subtract paths through the point (multiply the two leg-counts), not just $1$. And for diagonal constraints, be precise whether the path must stay strictly or weakly below, since that shifts the reflection line and changes the count.

Spot the Signal

Look for problems where the key step is counting lattice walks with step choices, obstacles, and reflection or complement ideas.
You can describe the hard part as counting lattice walks with step choices, obstacles, and reflection or complement ideas, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the counting object that calls for grid paths, then rewrite the givens around it.
Name the relation that makes Grid Paths legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Grid Paths just because the surface looks familiar; verify the required condition first.
Applying Grid Paths because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let grid paths reveal the counting structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is counting lattice walks with step choices, obstacles, and reflection or complement ideas.