Math Detours · Grade 5 · Around the corner · 29

Number the maze from the exit

Flood a maze with numbers, starting at the exit. Then every reachable square knows how far it is from safety.

Name ____________________Date ____________

Tonight's idea

Imagine a wave spreading backward from the exit, one square each beat. Write 0 at the exit. On beat 1, write 1 in every open neighbour. On beat 2, write 2 in every still-empty open neighbour. Keep going in whole waves.

Neighbours share an edge. Diagonal squares are not neighbours, and a wall cannot be crossed.

The first wave to reach a square has used as few moves as possible. Its number is therefore the length of a shortest route to the exit.

Except at the exit: a square's number is 1 plus the smallest neighbouring number.

This local best-choice rule is a tiny grid version of a Hamilton-Jacobi value equation. To escape by a shortest route, walk downhill by 1 each move. A square that never receives the wave has no route to the exit.

Watch one: let the exit flood backward

Fill waves:0, then all 1s,then all 2s, ...Escape:8, 7, 6, ... , 0 6540 7321 842 76543 654 SEXIT Dark squaresare walls.The orange routealways drops by 1.
Filling in waves solves every starting square at once. The marked start is 8 moves from the exit.

The exit gets 0. Its only open neighbour gets 1. The 2s are the open neighbours of the 1, and the wave continues. From S, the orange route reads (8,7,6,5,4,3,2,1,0), so it uses 8 moves.

No shorter route is hiding elsewhere. The wave would have reached S on an earlier beat if one existed.

Your turn

SstartEexitUtrapped squarewall SEU Write 0 at E.Fill whole waves.Moves cross edges,never corners.
Write distance numbers in the open squares. Do not write in walls.
  1. Fill the maze from E: all 1s, then all 2s, and so on. Leave any square the wave cannot reach empty.
  2. Trace a shortest route from S to E by walking downhill through the numbers. How many moves does it use?
  3. The square diagonally up-left from E has number 2. It cannot move diagonally, but it has two edge-sharing downhill choices. Trace both. Why are both routes shortest?
  4. Why does U stay empty? Now erase the wall directly below U. What number enters that newly opened square, and what number then reaches U?

Stretch: how many shortest routes?

There is 1 finished route at E. At every other square, add the route counts from its downhill neighbours. How many different shortest routes lead from S to E?

Answers

  1. Rows from top to bottom are: 10 9 8 7 6 5; 9 10 wall 6 5 4; 8 wall blank wall 4 3; 7 6 wall 4 3 2; 6 5 4 wall 2 1; 5 4 3 2 1 0. U is the blank square.
  2. 10 moves. One route goes right across the whole top row, then down the whole right edge. Its numbers are (10,9,8,7,6,5,4,3,2,1,0). Other shortest routes are possible.
  3. The two choices have number 1: move right, then down to E, or move down, then right to E. Each route uses two edge moves. A diagonal jump would use one move but is not allowed.
  4. Every edge-neighbour of U is a wall, so no wave can enter it. If the wall below U opens, that new square gets 5: it touches squares numbered 4. Then U gets 6.

Stretch. 16 routes. Count backward from E. The square right of S begins 11 shortest routes, and the square below S begins 5. Every shortest route from S must start one of those two ways, so (11+5=16).

← PreviousNext: Instructions a robot can follow →