Gridlock

A courier walks from the south-west corner to the north-east corner of a grid, moving only east or north along the streets. In this activity an \(a \times b\) grid means \(a\) blocks east and \(b\) blocks north. For a \(2 \times 2\) grid, list every possible route. Then find the number of routes for a \(3 \times 2\) grid, a \(3 \times 3\) grid and a \(4 \times 4\) grid.

Write each route as a string of R’s (east) and U’s (north). Use this to find a formula for the number of routes across an \(a \times b\) grid, and use it for a \(5 \times 5\) grid.

Task 2c: A route is completely decided by which of its steps are the east steps. Use this to write the number of routes as a choose-number, and prove that it equals your formula from 2b.

(i) How many routes are there in a \(7 \times 4\) grid?

(ii) Show that an \(a \times b\) grid and a \(b \times a\) grid always have the same number of routes, in two different ways: once with algebra, and once with a story about the city.

(iii) What is the smallest square grid, \(n \times n\), with more than 1,000,000 routes? You may use your calculator for the final check, but state which formula you are typing in.

The council closes the intersection \((2,2)\): no route may pass through it. How many routes remain?

Instead, every courier must pass through the intersection \((2,3)\) to collect a package. How many routes are there?

Now \((2,2)\) is closed and couriers must still pass through \((2,3)\). How many routes are there?

The intersections \((2,2)\) and \((3,3)\) are both closed. How many routes remain?

Task 3e: The council can close exactly one intersection, other than D and the destination. Predict which one removes the most routes, then find out whether you were right. Prove your final answer.

Label every intersection of the \(5 \times 5\) grid with the number of different routes from D to that intersection. Find a rule that lets you fill in each label from labels you already know, and use it to fill in the entire grid.

Task 4b: Prove your rule for a general intersection. Then rewrite it as an equation about choose-numbers, and say where you have seen these numbers before.

Task 4c: Look at all the intersections that are exactly \(n\) blocks from D, that is, with \(x + y = n\). Add up their labels for several values of \(n\) (up to 5). What do you find? Prove it for any \(n\), using routes.