In my puzzle blog earlier today I set you the following puzzle:
Imagine you are in a grid 100 squares long and 100 squares wide. (The grid is fixed to the compass directions: up/down is N/S, and left/right is W/E.) On each square of the grid, there’s an arrow. Each arrow is pointing either N, S, W or E.
Choose any square. That’s your starting position. Now the game begins.
The rules are that you must always follow the arrow. So, if the arrow in your starting square points N, you move to the square due north. If the arrow points E, you move to the square due east.
But there is an extra thing you need to do. Once you arrive in a new square, you must rotate the arrow in the square you came from by 90 degrees clockwise. So if the square you came from pointed N, then once you leave that square you must rotate that arrow to E. If the square you came from pointed E, once you leave that square you must rotate that arrow to S.
Safely in your new square, you repeat the process: follow the arrow to a new square, and then rotate the arrow in the square you came from by 90 degrees clockwise.
If you are in a square on the top edge and the arrow points north, then the following move you are going to get out the grid. Hurrah! You win! Likewise if you are on any of the other edge squares of the grid, and the arrow in the square points out, you get out.
But if you are not on an edge, you will probably start roaming around the grid. Here’s a statement:
“No matter which directions the arrows are pointing at the start, and no matter which square you choose to begin, you will always eventually get OUT OF THE GRID”
True or false? Prove it one way or the other.
TRUE! You will always get out of the grid.
What is lovely about this puzzle is that there is a very elegant way to solve it. You do NOT need to make any complicated calculations about combinations.
To start, let’s assume the statement is false. In other words, let’s suppose that you never get out of the grid. You roam around the grid forever. Since there are a finite number (10,000) of squares in the grid but during your eternal roam you are making an infinite number of steps, then you will start repeating squares and eventually there will be a square that you visit an infinite number of times. Let’s call this square A.
After each time you visit A, the arrow in A turns by 90 degrees clockwise. After four visits to A, its arrow will have pointed to each of the four compass directions, meaning that after those four visits you will have moved out into each of the four squares horizontally and vertically adjacent to A.
But since you are visiting A an infinite number of times, you must also visit the four squares horizontally and vertically adjacent to A an infinite number of times. And using the same logic, as above, you must also visit the squares that are vertically and horizontally adjacent to these squares an infinite number of times, and the ones adjacent to these ones, and so on. Eventually you will visit a square on an edge.
The arrow in this edge square might be pointing out the grid, in which case you get out the grid. If it is not, you know you will return to this square, since we said above that you will visit the square that pointed to it an infinite number of times. On the second visit the arrow is rotated 90 degrees clockwise. Either it points out, in which case you get out the grid, or it doesn’t, in which case you will return to it a third time, when it is rotated by another 90 degrees. Again, either it points out, or you return for the fourth time, when it must be pointing out, since all the four possible compass directions have been covered. You MUST eventually get out the grid!
We started by assuming that you CANNOT get out the grid, and this led us to the conclusion out that you CAN get out the grid. So the assumption that you cannot get out the grid is false…meaning that you can always get out the grid. The statement in the question is TRUE!
I hope you enjoyed today’s puzzle. I’ll be back in two weeks.
Thanks again to Adrian Paenza for telling me about the puzzle.
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.