The Hall Robot: Counting Shortest Routes Around a Pillar
A floor-cleaning robot works in a square hall marked with a 5 × 5 grid of junction points, with coordinates from (0, 0) at the south-west corner to (4, 4) at the north-east corner. The robot starts at (0, 0) and must reach (4, 4). Each move carries it one unit east, increasing x by 1, or one unit north, increasing y by 1; it never moves west or south and never revisits a junction. Its battery allows exactly 8 moves, which is the shortest possible journey, so every valid route is a shortest route. A thick pillar stands on junction (2, 2), and the robot may not pass through it. A trainee claims that removing the pillar would increase the number of possible routes by 'about a third'.
1. How many 8-move routes from (0, 0) to (4, 4) avoid the pillar at (2, 2)?
Read the worked answer
Step 1 - count all shortest routes. Every route uses exactly 4 east and 4 north moves, in some order. Choose which 4 of the 8 moves are east: C(8, 4) = 70 routes.
Step 2 - count routes blocked by the pillar. A route through (2, 2) splits into two independent legs:
- (0, 0) → (2, 2): 2 east + 2 north, C(4, 2) = 6 ways.
- (2, 2) → (4, 4): again 2 east + 2 north, C(4, 2) = 6 ways.
Blocked routes = 6 × 6 = 36.
Step 3 - subtract. 70 − 36 = 34 routes avoid the pillar.
The multiplication in Step 2 is legitimate because the two legs are independent and every route through (2, 2) is formed by one choice from each leg.
2. A maintenance route must pass through the junction (1, 3). How many such 8-move routes exist, and do any of them hit the pillar?
Read the worked answer
Leg 1: (0, 0) → (1, 3). This needs 1 east and 3 north moves, 4 moves in total. Choose the position of the single east move: C(4, 1) = 4 routes.
Leg 2: (1, 3) → (4, 4). This needs 3 east and 1 north move, again 4 moves. Choose the position of the single north move: C(4, 1) = 4 routes.
Total routes through (1, 3) = 4 × 4 = 16.
Do any hit (2, 2)? No. From (1, 3) the robot can only increase coordinates, and (2, 2) has y = 2, which is less than 3. Since the y-coordinate never decreases, the pillar is unreachable from (1, 3).
So all 16 routes are valid, and no subtraction is needed - but that must be justified, not assumed.
3. Is the trainee correct that removing the pillar would raise the route count by about a third? Quantify the effect properly.
Read the worked answer
Not correct - the effect is far larger than a third.
- Routes without the pillar: 70
- Routes with the pillar: 34
- Routes gained by removing it: 36
The correct comparison depends on the base used:
- As a fraction of the restricted count: 36 ÷ 34 ≈ 1.06, i.e. an increase of about 106%, more than double.
- As a fraction of the unrestricted count: 36 ÷ 70 ≈ 51% of all routes pass through that junction.
Neither figure is close to a third. The trainee's error is probably a base error - comparing the 36 blocked routes with the 70 unrestricted routes and mentally rounding - but 36/70 is about 0.51, not 0.33.
A useful general point: junction (2, 2) is the busiest single junction in this grid, precisely because it splits the journey into two equal halves of 6 routes each, which is why one pillar removes so much.