Problem of the Week
Problem A and Solution
Amazing Navigation

Problem

Juanita and AJ create mazes on grid paper. Each maze is a rectangular grid containing white squares and grey squares. One white square is marked $A$ and another is marked $Z$.

To complete a maze, they start at $A$ and need to reach $Z$ by moving one square at a time in one of the following directions: north ($N$), east ($E$), south ($S$), or west ($W)$, where the top of the page is considered north. They cannot go through any of the grey squares and must go through each of the white squares exactly once. That is, they must go through all of the white squares but cannot go through any of them more than once.

1. Determine the directions they need to follow to successfully complete the given maze.

   

   Hide/Reveal Description of Maze

   A rectangular grid with $4$ rows, each with $8$ squares. We number the rows from top to bottom, and number the squares in each row from left to right.

   • The first square in the third row is marked $A$ and the eighth square in the first row is marked $Z$.
   • There are no grey squares in the first row.
   • In the second row, the fourth, fifth, and eighth squares are grey.
   • In the third row, the second, fourth, fifth, and eighth squares are grey.
   • In the fourth row, the fourth, fifth, sixth, seventh, and eighth squares are grey.

   ---

2. AJ creates another maze by changing where the grey squares are in the maze from part (a). (The locations of $A$ and $Z$ remain unchanged.) Juanita successfully completes this new maze by following these directions:

   $E$, $S$, $E$, $E$, $E$, $N$, $E$, $N$, $W$, $W$, $W$, $W$, $N$, $E$, $E$, $E$, $E$, $E$, $E$

   What does AJ’s maze look like?

Solution

1. The first direction must be either $N$ or $S$, because there is a grey square to the right of $A$. Suppose they start with $N$. Then at some point, they must go through the square that is directly below $A$. However, once they reach that square they will be stuck because they can’t go through any white square more than once. So the first direction must be $S$.

   Using similar reasoning, we can complete the maze as shown.

   

   Hide/Reveal Description of Diagram for (a)

   Starting at the first square in the third row, which is marked $A$, the following moves are shown using arrows.

   • Move $S$ one square to the first square in the fourth row.
   • Move $E$ two squares to the third square in the fourth row.
   • Move $N$ two squares to the third square in the second row.
   • Move $W$ two squares to the first square in the second row.
   • Move $N$ one square to the first square in the first row.
   • Move $E$ five squares to the sixth square in the first row.
   • Move $S$ two squares to the sixth square in the third row.
   • Move $E$ one square to the seventh square in the third row.
   • Move $N$ two squares to the seventh square in the first row.
   • Move $E$ one square to the eighth square in the first row, which is marked $Z$.

   ---

   The directions followed are then

   $S$, $E$, $E$, $N$, $N$, $W$, $W$, $N$, $E$, $E$, $E$, $E$, $E$, $S$, $S$, $E$, $N$, $N$, $E$

2. We first mark the given directions on the maze, as shown.

   

   Hide/Reveal Description of Diagram for (b)

   Starting at the first square in the third row, which is marked $A$, the following moves are shown using arrows.

   • Move $E$ one square to the second square in the third row.
   • Move $S$ one square to the second square in the fourth row.
   • Move $E$ three squares to the fifth square in the fourth row.
   • Move $N$ one square to the fifth square in the third row.
   • Move $E$ one square to the sixth square in the third row.
   • Move $N$ one square to the sixth square in the second row.
   • Move $W$ four squares to the second square in the second row.
   • Move $N$ one square to the second square in the first row.
   • Move $E$ six squares to the eighth square in the first row, which is marked $Z$.

   ---

   Since Juanita cannot go through any of the grey squares, and must go through each of the white squares exactly once, the squares that are blank after marking the path must be the grey squares. Thus, AJ’s maze is as shown.