On the street grid shown you may only walk right or down. One junction is closed. How many routes go from the top-left corner to the bottom-right corner?
Text description of the figure
A grid of streets with junctions arranged 4 across and 4 down. The junction one step right and one step down from the top-left corner is marked closed with a cross.
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Write a number into every junction.
2The strategy
The number of routes to a junction is the number of routes to the junction above it plus the number to the junction on its left. A closed junction simply gets a zero and everything downstream follows.
3The full solution
Fill the grid from the top-left. The top row and left column are all 1, the closed junction is 0, and adding down and across gives 8 at the bottom-right corner.
Solution
The reliable way
Label each junction with the number of routes that reach it. The top-left is 1, and every junction on the top row and the left column is 1 because there is a single way along the edge. Any other junction gets the sum of the junction above and the junction to its left, and the closed junction is set to 0. The rows come out as 1 1 1 1, then 1 0 1 2, then 1 1 2 4, then 1 2 4 8. So there are 8 routes. The transferable idea: build the count up junction by junction, and treat a blockage as a zero.
The elegant way
The open grid has 20 routes. The closed junction is reached by 2 routes and leads onward by 6, so 12 routes pass through it and 20 - 12 = 8 survive.
Why this is on the test: Grid paths are a classic 5-point figure, and filling the grid is the only method that keeps working once a junction is blocked.