A Russian problem from the 1999 Mathematical Olympiad:
Each cell in an 8×8 grid contains an arrow that points up, down, left, or right. There’s an exit at the top edge of the top right square. You begin in the bottom left square. On each turn, you move one square in the direction of the arrow, and then the square you have departed turns 90° clockwise. If you’re not able to move because the edge of the board blocks your path, then you remain on the square and it turns 90° clockwise. Prove that eventually you’ll leave the maze.
|
SelectClick for Answer |
Suppose by way of contradiction that you’ll stay in the maze forever. Because the grid contains a finite number of squares, this means you’ll visit at least one square an infinite number of times. And because this square rotates after each visit, it follows that you’ll visit each of its adjacent squares an infinite number of times. By extension this means that you’ll visit every square on the board an infinite number of times. This includes the square in the upper right, which at some point will point out the exit. Hence it’s not possible to stay in the maze forever.
|
