Kevin Purbhoo invented this vivid puzzle while a student at Northern Secondary School in Toronto:
On a remote Norwegian mountain top, there is a huge checkerboard, 1000 squares wide and 1000 squares long, surrounded by steep cliffs to the north, south, east, and west. Each square is marked with an arrow pointing in one of the eight compass directions, so (with the possible exception of some squares on the edges) each square has an arrow pointing to one of its eight nearest neighbors. The arrows on squares sharing an edge differ by at most 45 degrees. A lemming is placed randomly on one of the squares, and it jumps from square to square following the arrows. Prove that the poor creature will eventually plunge from a cliff to its death.
|
SelectClick for Answer |
In order to avoid falling, the lemming must follow some closed loop on the mountaintop. This loop can’t cross itself, because adjacent arrows at the crossing point would disagree by more than 45 degrees. So it’s just a simple loop. Is this possible? There are various ways to show that it’s not; one is to assume that it is possible and then to show that this assumption leads to a contradiction.
If such loops are possible, then they might come in various sizes. One of these must be the smallest possible (meaning that it encloses the smallest number of squares). Suppose the path along this loop runs clockwise. Rotate every arrow on the board 45 degrees clockwise. The resulting board must be legal, because no arrow has rotated relative to its neighbors. But now we seem to have defined a new smallest path — because of the new orientation of the arrows, a lemming dropped inside the ring we’d defined can never escape it (see the diagrams here).
This means that the lemming on this new board must be following some closed loop smaller than the “smallest” one we’d been considering. That’s a contradiction, so our initial assumption must be wrong: No legal board can exist with a closed loop that can save the lemming.
(Via Ravi Vakil, A Mathematical Mosaic, 1996. Peter Winkler discusses this also in Mathematical Puzzles, 2021.)
|
