In this maze of 8×8 rooms, each room has an arrow that points up, down, left, or right – and it will only let you move to the adjacent room in the direction of the arrow.

After you leave a room, or if you are unable to move because there is no adjacent room in the direction of the arrow (i.e., the arrow points outside the maze but there is no exit), the arrow in that room will rotate 90 degrees clockwise.

You start in the bottom left room, and the only exit is the right door in the top-right room.

Maze to escape from

Prove that no matter what the initial arrangement is, you will eventually escape the maze.


Hint

Might want to try proof by contradiction.

Solution

  1. Assume that you will never escape the maze.
  2. This means you will make an infinite number of moves.
  3. Since there are a finite number of rooms, that means you must enter at least one room an infinite number of times.
  4. Since the arrow rotates every time you visit the room, you will enter every adjacent room an infinite number of times as well.
  5. The same is true for those adjacent rooms, so this means you enter every room an infinite number of times – including the top-right room!
  6. That means at some point you will enter the top-right room when the arrow is pointing toward the exit, so the original assumption that you will never escape the maze is false.

Leave a Reply

Your email address will not be published. Required fields are marked *