Lattice Paths and Blocked Routes: Counting and Proof

← All lessons · Australia’s Olympiad routes

Your goal: Count restricted grid routes and explain why no route is missed or counted twice. Start with a step word, then choose between a checkpoint split, subtraction and a small table.

Preparation context: original counting practice for students building towards the Australian Intermediate Mathematics Olympiad, with a separate proof workshop. AMT lists counting techniques and methods of proof among possible AIMO topics. Its current AIMO page describes a four-hour paper for Years 7–10, with eight integer-answer and two written-solution questions. This lesson uses multiple choice for feedback; it is not an official paper or a calibrated AIMO mock.

Before you start: Read ordered pairs and use the addition and multiplication rules. If needed, revisit basic counting, combinations and one-to-one correspondences. The necessary route encoding is rebuilt below.

Study in three sittings: (1) starting checks, encoding and Example 1; (2) Examples 2–3 and Problems 1–6; (3) Problems 7–9 and one proof challenge. Try a route on paper before opening a hint. A starting estimate is 30–45 minutes per sitting; a written proof may need longer.

Three starting checks

1. Starting at (0,0), follow RURU, where R means one unit right and U means one unit up. Where do you finish? Why does URRU finish at the same point?

Answer and repair route

Both end at (2,2): each word contains two right and two up steps. They are different routes because their intermediate vertices differ. Coordinates count how many of each step have occurred; the word retains their order. If this is unclear, draw the four moves before using formulas.

2. Choose two positions from four positions numbered 1,2,3,4. How many unordered pairs can you choose?

Answer and repair route

The pairs are {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}: six. Alternatively, $4\cdot3$ ordered selections count each pair twice, so divide by 2. If you got twelve, revisit combinations: the up-step positions form a set, not an ordered list.

3. Among a finite collection of routes, seven visit P, six visit Q, and two visit both. How many visit at least one of P and Q?

Answer and repair route

The answer is $7+6-2=11$. The sum counts a both-route twice, so remove one copy. Drawing two overlapping circles is a useful repair before Example 2. This checks counting logic, not whether any particular coordinates produce those figures.

A route is a word you can reverse back into a picture

Throughout this lesson, grid vertices have integer coordinates. A legal step is R: (x,y) to (x+1,y), or U: (x,y) to (x,y+1). There are no left, down or diagonal steps. A route is a sequence of these unit edges, not a choice of grid squares. Different step words count as different routes. Coordinates never decrease, so vertices cannot be revisited.

For nonnegative integers m and n, a route from (0,0) to (m,n) has exactly m right steps and n up steps. Record their order as a word. Conversely, each word containing those numbers of R and U gives exactly one route. It stays inside the endpoint rectangle because neither coordinate can decrease or exceed its final total. These inverse operations establish a bijection: a reversible one-to-one correspondence.

Choose the n positions of U among the $m+n$ positions; all remaining positions must contain R. Write $\binom{a}{b}$ for the number of ways to choose b positions from a positions, with order ignored. Thus the unrestricted count is $\binom{m+n}{n}$. Equivalently choose the R positions and get $\binom{m+n}{m}$. The two expressions count the same words.

To calculate $\binom{a}{b}$, first choose b distinct positions in order: $a(a-1)\cdots(a-b+1)$ choices. Every chosen set occurs in $b!$ orders, where $b!$ means $1\cdot2\cdots b$. Divide by that constant overcount. This gives $\binom ab=\frac{a!}{b!(a-b)!}$ for $0\le b\le a$, with $0!=1$. In particular $\binom{a}{0}$=$\binom{a}{a}$=1: there is one way to make no choices or choose all positions. We will use small values such as $\binom{5}{2}$=$\frac{5\cdot4}{2}=10$.

A segment from (a,b) to (c,d) needs $c-a$ right and $d-b$ up steps. If either difference is negative, there are no permitted routes. If both are nonnegative, use the same position-choice argument on those differences. If both are zero, there is one empty segment; it makes no move but supplies one choice when multiplying.

What changes when a checkpoint is compulsory?

Split a route at its visit to P. The prefix from the start to P and the suffix from P to the finish determine it uniquely. Conversely, concatenating any legal prefix and suffix gives a route through P. Since coordinates only increase, it cannot return to P later. This proves that the number through P is the product of the two segment counts. For several checkpoints, first check that both coordinates can increase through them in the claimed order; then split at all of them.

A blocked vertex removes every route visiting that vertex. A blocked edge removes only routes using that particular step; its endpoints can still be reached along other edges. To count routes using an edge, multiply prefixes to its starting endpoint by suffixes from its ending endpoint. The edge itself is fixed and contributes one choice. Keep these two kinds of blockage separate.

Worked example 1 · A checkpoint and one closed exit

Count routes from (0,0) to (5,3), using only R and U, which visit P=(2,1) but do not use the edge from (2,1) to (2,2). All vertices remain open.

First count all routes through P. The prefix needs two right and one up step, giving $\binom{3}{1}$=3. The suffix needs three right and two up steps, giving $\binom{5}{2}$=10. Therefore there are $3\cdot10=30$ routes through P.

Among these, the forbidden-edge routes consist of a prefix to P, the fixed up step to (2,2), and a suffix with three right and one up step. Their number is 3·$\binom{4}{1}$=12. This split is reversible and does not introduce routes that miss P. Subtract: $30-12=18$.

As a check, once the route reaches P, its next step cannot be up, so it must be right to (3,1). There are $\binom{4}{2}$=6 suffixes from there. The same answer is $3\cdot6=18$. Two methods can confirm a count, but each still needs its own reasoning.

Your turn 1

Keep the start, finish and compulsory P of Example 1, but close the incoming edge from (1,1) to (2,1) instead. The outgoing edges at P are now open. Count the routes.

Hint 1

Begin with the same 30 routes through P.

Hint 2

A forbidden-edge prefix reaches (1,1), uses the fixed right edge, then follows any suffix from P.

Complete solution

There are two prefixes from (0,0) to (1,1), followed by the forbidden edge and ten suffixes from P. Thus $2\cdot10=20$ of the 30 routes are excluded, leaving 10. Equivalently, the only allowed prefix to P is RRU: RUR and URR use the closed edge. Its ten suffixes give the same count.

Worked example 2 · Why two subtractions need an add-back

Count routes from (0,0) to (4,3), using only R and U, which avoid the two blocked vertices P=(1,1) and Q=(3,2).

There are $\binom{7}{3}$=35 unrestricted routes. Routes through P number $\binom{2}{1}$·$\binom{5}{2}$=$2\cdot10=20$. Routes through Q number $\binom{5}{2}$·$\binom{2}{1}$=$10\cdot2=20$. Subtracting both gives a negative number, warning us that the two unwanted collections overlap.

A route visiting both has a prefix to P, a segment from P to Q with two right and one up step, and a suffix from Q to (4,3). Thus there are $2\cdot3\cdot2=12$ both-routes. Such a route starts with coefficient 1 in the total and loses two copies in the subtractions. Add back one copy to bring its coefficient to 0. A route visiting exactly one loses one copy; a route visiting neither keeps its single copy. Hence the required number is $35-20-20+12=7$.

That coefficient check is inclusion–exclusion in this setting. Never assume the intersection is zero just because P and Q are distinct. Reachability decides whether the same route can visit both.

Your turn 2

In the same (4,3) rectangle, instead block P=(1,2) and Q=(3,1). Count routes using only R and U that avoid both.

Hint 1

Check whether a route can visit both checkpoints in either order.

Hint 2

P to Q needs a downward move; Q to P needs a leftward move. The two forbidden collections are disjoint.

Complete solution

Through P there are $\binom{3}{1}$·$\binom{4}{1}$=$3\cdot4=12$ routes. Through Q there are $\binom{4}{1}$·$\binom{3}{1}$=$4\cdot3=12$. No route visits both: each possible order decreases a coordinate. There is no overlap to add back. The number avoiding both is $35-12-12=11$.

Worked example 3 · Let the last step choose the case

Count routes from (0,0) to (4,3), using only R and U, that avoid (1,1), (2,1) and (3,2). With several obstacles, a small table can be safer than many intersecting subtractions.

Let $F(x,y)$ be the number of legal routes to (x,y). Set $F(0,0)=1$ for the one empty route. A blocked vertex has value 0. For any other allowed vertex, the final step comes either from its left neighbour or from its lower neighbour. These cases cannot overlap because the last step cannot be both R and U. Removing that last step gives a reversible correspondence with the earlier routes.

Therefore $F(x,y)=F(x-1,y)+F(x,y-1)$ at each other unblocked vertex, with a missing neighbour outside the rectangle contributing 0. Fill from the origin outwards: a row from left to right, then the row above. Every needed value is already known. This is dynamic programming: remembering correct counts for smaller subproblems instead of recounting routes.

If an edge is closed, omit only the contribution across that edge. Do not put zero at the whole vertex unless the vertex itself is blocked. If a blocked vertex were the start or finish, no route could be valid; our examples keep both open. No recurrence is applied to overwrite the initial 1 at the open start.

The bottom row is 1,1,1,1,1. Row y=1 is 1,0,0,1,2; row y=2 is 1,1,1,0,2; the top row y=3 is 1,2,3,3,5. For example, $F(3,1)=0+1=1$: its left neighbour is blocked, but its lower neighbour can still supply a route. At (4,3), the left entry 3 and lower entry 2 give 5. Thus there are 5 routes, and the last-step argument proves every table entry is valid.

Your turn 3

Keep all three blocked vertices in Example 3. In addition, close the edge from (3,3) to (4,3). Its endpoints stay open. How many routes remain?

Hint 1

Only one incoming edge to the finish is newly closed.

Hint 2

At (4,3), keep the lower-neighbour contribution and omit the left-neighbour contribution.

Complete solution

The new closed edge can be used only as the final step, so all counts at other vertices stay unchanged. Previously the finish received 3 routes from its left neighbour and 2 from below. The left contribution is now disallowed; the 2 routes from below remain. The answer is 2, not 0: a closed incoming edge does not close the finish itself.

Choose the method before calculating

• Only the endpoint matters: encode the steps and choose positions.
• A checkpoint is required: check coordinate order, then split into segments.
• One or two features are forbidden: subtract their route collections, correcting their intersection.
• Several obstacles or a boundary condition: use last-step counts with carefully stated zero and starting values.

When a solution says “multiply”, ask how the smaller choices join into one route. When it says “subtract”, ask which complete routes are being removed. When it fills a table, ask why the last-step cases are disjoint and exhaustive. These questions turn an answer into a proof.

Practise and adjust the level

Foundation checks the route language. Core adds restrictions that change the counting method. Stretch combines restrictions or asks for a new representation. These labels describe this lesson’s sequence, not an official AIMO difficulty scale. The interactive checker evaluates your selected answer; it does not grade your written proof. Use the complete solutions below after an attempt.

Interactive practice loads here. You can also use the complete question set below.

All nine practice questions

Each question is self-contained. Write a counting argument before choosing an option. Open Hint 1 first; return to the problem before opening Hint 2. The figure coordinates and stated rules determine the answer, not measurements from the drawing.

Foundation

1. A route starts at (1,2), ends at (5,4), and must have an up step as its last step. Use only unit steps right or up. How many routes are possible?

1. 4
2. 5
3. 6
4. 15

Hint 1

Reserve the last up step before counting the others.

Hint 2

The earlier five steps contain four right steps and one up step. Choose the position of that earlier up step.

Answer and full reasoning

Answer: 5

The displacement requires four right and two up steps. Fix the last step as up. The other five positions contain exactly one up step; each of its five positions gives one route. Every route counted stays between its starting and ending coordinates. Thus there are 5 routes.

Watch out: The coordinates of the start need not be zero: use the change in each coordinate.

Foundation

2. A route goes from (0,0) to (5,4). Use only unit steps right or up. It must visit both P=(1,3) and Q=(3,1), in either order. How many routes are possible?

1. 0
2. 6
3. 12
4. 24

Hint 1

Neither coordinate can decrease along a permitted route.

Hint 2

From P to Q the second coordinate would decrease; from Q to P the first would decrease.

Answer and full reasoning

Answer: 0

If P came first, moving from (1,3) to (3,1) would require the second coordinate to fall from 3 to 1. If Q came first, moving from (3,1) to (1,3) would require the first coordinate to fall from 3 to 1. Both are forbidden. Distinct visited checkpoints must occur in one order or the other, so there are 0 routes.

Watch out: Multiplying segment counts is valid only after checking that the segments can be travelled.

Core

3. A route goes from (0,0) to (5,3). Use only unit steps right or up. How many routes visit exactly one of P=(1,1) and Q=(3,2)?

1. 12
2. 24
3. 42
4. 60

Hint 1

Count routes through P, routes through Q, and routes through both.

Hint 2

Routes through both are counted twice by the sum, but should contribute zero to an exactly-one count.

Answer and full reasoning

Answer: 24

Through P there are $\binom{2}{1}$·$\binom{6}{2}$=$2\cdot15=30$ routes. Through Q there are $\binom{5}{2}$·$\binom{3}{1}$=$10\cdot3=30$. A route visiting both must visit P before Q. Splitting there gives $\binom{2}{1}$·$\binom{3}{1}$·$\binom{3}{1}$=$2\cdot3\cdot3=18$. The sum 30+30 counts each exactly-one route once and each both-route twice. Subtract those 18 routes twice: $30+30-2\cdot18=24$.

Watch out: For exactly one, subtract the overlap twice. For at least one, subtract it only once.

Core

4. A route goes from (0,0) to (4,2). Use only unit steps right or up. The single edge from (1,1) to (2,1) is closed; its endpoints remain open. How many routes avoid that edge?

1. 3
2. 6
3. 9
4. 12

Hint 1

Subtract routes using the edge from all routes.

Hint 2

A route using it has an arbitrary prefix to (1,1), that fixed right step, and an arbitrary suffix from (2,1).

Answer and full reasoning

Answer: 9

There are $\binom{6}{2}$=15 unrestricted routes. The prefix to (1,1) has $\binom{2}{1}$=2 choices. The forbidden edge contributes one fixed step, not a choice. The suffix from (2,1) to (4,2) has $\binom{3}{1}$=3 choices. Each edge-using route has a unique split, so there are $2\cdot3=6$. The answer is $15-6=9$. The endpoints are not removed, so other visits to them remain legal.

Watch out: Blocking an edge does not block all routes through either endpoint.

Core

5. A route goes from (0,0) to (4,3). Use only unit steps right or up. Immediately after its third step, the first coordinate must be greater than the second. How many routes satisfy this condition?

1. 18
2. 20
3. 22
4. 28

Hint 1

After three steps the coordinates add to 3. List the positions with first coordinate larger.

Hint 2

The possible positions are (3,0) and (2,1). Count routes through each and decide whether the cases overlap.

Answer and full reasoning

Answer: 22

After three steps the only eligible positions are (3,0) and (2,1). Through (3,0), the first three steps are forced; the suffix has one right and three up steps, so there are $\binom{4}{1}$=4 routes. Through (2,1), the prefix has $\binom{3}{1}$=3 choices and the suffix has $\binom{4}{2}$=6, giving 18. A route has exactly one position after its third step, so these cases are disjoint. Total: $4+18=22$.

Watch out: Do not count every point below the diagonal: only points reached at the specified step are relevant.

Core

6. A route goes from (0,0) to (5,3). Use only unit steps right or up. No two up steps may be consecutive. How many routes are possible?

1. 10
2. 15
3. 20
4. 56

Hint 1

First place the five right steps. Look at the gaps before, between and after them.

Hint 2

There are six gaps. Put the three up steps in three different gaps, at most one in each.

Answer and full reasoning

Answer: 20

Write the five right steps first. They create six ordered gaps: one before, four between and one after. To avoid consecutive up steps, put at most one up step in each gap. Conversely, choosing any three of the six gaps gives a valid route, and deleting the up steps recovers that choice uniquely. Thus the answer is $\binom{6}{3}$=20. The two end gaps are allowed because the first and last steps are unrestricted.

Watch out: There are six gaps around five right steps, not merely the four internal gaps.

Stretch

7. A route goes from (0,0) to (4,3). Use only unit steps right or up. On the vertical line $x=2$, the vertices (2,0), (2,1) and (2,3) are blocked; only G=(2,2) is open. All other vertices and edges are open. How many routes remain?

1. 3
2. 6
3. 12
4. 18

Hint 1

Every route must reach column $x=2$. How can it legally enter and leave G?

Hint 2

It must enter from (1,2) and leave to (3,2), since the vertices directly below and above G are blocked.

Answer and full reasoning

Answer: 6

A route cannot skip column $x=2$, so it must visit G. It cannot enter G from below, since (2,1) is blocked. It must arrive along the edge from (1,2). It cannot leave upwards, since (2,3) is blocked, so its next step must go to (3,2). The prefix to (1,2) has $\binom{3}{1}$=3 choices and never reaches column 2. The suffix from (3,2) to (4,3) has two choices and stays to the right of the wall. The two intervening right steps are forced. Thus $3\cdot2=6$, with a unique route for every prefix/suffix choice.

Watch out: Counting every route through G would also count routes that hit a blocked neighbour first or afterwards.

Stretch

8. A route goes from (0,0) to (5,4). Use only unit steps right or up. It must visit P=(1,2) and Q=(4,3), but cannot use the edge from (2,2) to (3,2). How many routes are possible?

1. 6
2. 12
3. 18
4. 24

Hint 1

The checkpoints force three segments. The forbidden edge can occur only in the middle segment.

Hint 2

From P to Q there are three right steps and one up step. Which positions of the up step avoid the forbidden edge?

Answer and full reasoning

Answer: 12

The order must be P then Q because both coordinates increase. There are $\binom{3}{1}$=3 prefixes to P and $\binom{2}{1}$=2 suffixes from Q. The middle segment has three right steps and one up step. Its four step words are URRR, RURR, RRUR and RRRU. The last two use the edge (2,2) to (3,2); the first two move up before that edge and avoid it. Prefixes cannot reach that edge because they end at x=1, and suffixes start at x=4, so no other exclusion is needed. There are $3\cdot2\cdot2=12$ complete routes.

Watch out: Do not subtract forbidden-edge routes that fail the required checkpoints in the first place.

Stretch

9. A route goes from (0,0) to (4,3). Use only unit steps right or up. At every visited vertex (x,y), require $y\le x+1$. How many routes satisfy this condition?

1. 14
2. 21
3. 28
4. 35

Hint 1

Use the last-step recurrence, entering zero at forbidden vertices.

Hint 2

Fill rows from y=0 upwards. In row y=2, the entry at x=0 is forbidden; in row y=3, both x=0 and x=1 are forbidden.

Answer and full reasoning

Answer: 28

Use $F(x,y)$ for the valid-route count, with $F(0,0)=1$. Other allowed entries are the sum of their left and lower entries; forbidden or outside entries contribute 0. For x=0,1,2,3,4, the row y=0 is 1,1,1,1,1. Row y=1 is 1,2,3,4,5. Row y=2 is 0,2,5,9,14. Row y=3 is 0,0,5,14,28. Thus $F(4,3)=28$. Every recurrence entry counts disjoint last-step cases, and the zero entries enforce the condition at every earlier point, not just the endpoint.

Watch out: Checking the final coordinates alone misses routes which crossed the forbidden boundary earlier.

Proof workshop · explain the correspondence

These are written challenges, not automatically marked questions. Work on paper, then compare each logical step with the solution and rubric. A formula without a justified correspondence is not yet a counting proof.

Proof A · A vertical cut partitions every route

Let $m\ge1$ and $n\ge0$ be integers, and choose an integer k with $0\le k<m$. Consider all routes from (0,0) to (m,n) using only unit steps R and U. Classify a route by the height j of its step from column $x=k$ to column $x=k+1$. Prove that summing $\binom{k+j}{j}$·$\binom{m-k-1+n-j}{n-j}$ over $j=0$,1,…,n gives $\binom{m+n}{n}$.

Hint 1

Every route takes exactly one step across the chosen vertical cut: x only increases and must go from 0 to m.

Hint 2

Fix j. Split at the crossing edge: count a prefix to (k,j), the one edge, and a suffix from (k+1,j) to (m,n). Then explain why the height classes do not overlap.

Full proof

Each route increases x from 0 to m in unit steps. It crosses from k to k+1 once, and can never return to column k. The crossing height j is uniquely defined and belongs to {0,1,…,n}. For fixed j, there are $\binom{k+j}{j}$ prefixes to (k,j). The crossing edge is fixed. The suffix has $m-k-1$ right steps and $n-j$ up steps, so it has $\binom{m-k-1+n-j}{n-j}$ choices. Any prefix stays in columns at most k and any suffix in columns at least k+1, so concatenation gives one route in that height class. Splitting reverses it uniquely. Multiply these segment counts. Different j give disjoint classes, and every route belongs to one. Adding their counts therefore equals the unrestricted total $\binom{m+n}{n}$. When $k=0$ or $k=m-1$, a segment may have no right steps; when $j=0$ or $j=n$, it may have no up steps. The count-one convention handles each boundary, including $n=0$.

Self-review: Did you prove exactly one crossing? Identify the two segment displacements? Justify both multiplication and addition? Include boundary heights and cuts?

Proof B · Reflect the first forbidden crossing

For an integer $n\ge1$, count routes from (0,0) to (n,n) using only R and U which never visit a vertex with $y>x$. Prove that their number is $\binom{2n}{n}$−$\binom{2n}{n-1}$. A complete answer must give a reversible correspondence for the unwanted routes.

Bridge: think of $y-x$ as “ups used minus rights used”. An up step increases this difference by 1 and a right step decreases it by 1. If the difference ever becomes positive, its first positive value must be 1. Swapping R and U in a prefix changes the sign of this difference along that prefix; geometrically, it reflects that part across the diagonal.

Hint 1

For an unwanted route, stop at its first vertex with one more U than R. Swap R and U only up to that vertex. Keep the remaining letters unchanged.

Hint 2

The new complete word has $n+1$ right and $n-1$ up steps. For the inverse, use the first prefix of such a word with one more R than U. Why must this prefix exist?

Full proof

There are $\binom{2n}{n}$ unrestricted routes. Call a route bad if some vertex has $y>x$. In a bad word, take the shortest prefix with one more U than R. It exists; the excess changes in single units, so the first positive excess is 1. Before its endpoint every prefix has U count at most R count. Swap R and U in this chosen prefix and leave the suffix unchanged. The whole word gains one R and loses one U, so it ends at ($n+1$,$n-1$). Before the swap point the transformed word has R count at most U count, and at the swap point it first has R count one greater. Thus that point is recoverable from the transformed word. Conversely, take any word with $n+1$ R and $n-1$ U. Its final excess of R over U is 2, so there is a first prefix with excess 1. Swap that prefix. The resulting word has n of each letter. Before the chosen point its U count is at most its R count, and at the chosen point its U count first exceeds its R count by 1; it is a bad route. The two constructions choose the same prefix and undo each other. Therefore the number of bad routes equals the number of words ending at ($n+1$,$n-1$), namely $\binom{2n}{n-1}$. Subtract them to obtain the claimed count. For $n=1$ this gives 2−1=1; for $n=0$, outside the stated hypothesis, the only route is the empty one.

Self-review: Did you specify the first crossing, rather than an arbitrary crossing? Count the transformed letters? Show the inverse prefix exists? Prove the two procedures undo each other? Only then subtract the bad routes.

Choose your next step

If the method choice is still difficult, redo one worked example with its solution closed and explain the correspondence aloud. If the calculation is the obstacle, revisit combinations. If the reasoning is secure, write Proof A or Proof B in your own words before reading further.

Study inclusion–exclusion · Explore counting recurrences · Strengthen proof writing · Return to Australia

Original teaching material · IMOolympiad.com. Report a specific correction through our contact page. Official competition details can change; follow AMT’s current information.