Here is another answer to the Lemming problem, complementing yesterday’s answer.

In case you’re behind, the problem was:

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.

For this proof, we’ll again focus on closed loops, this time proving they cannot not have a “rotation”, and so the lemming must fall.

As before, we argue that because the number of squares is finite, the lemming will run around a closed loop if and only if it never falls off. Also, the loop must be simple, specifically it cannot cross itself (see previous solution for detail).

Next we introduce the new concept of a path. A path is like a closed loop – a sequence of squares next to or diagonal from each other that you can trace your way around. The difference is that a loop is something the lemming would actually follow because the arrows point from one square on the loop to the next, whereas in creating a path we ignore the arrows. So a loop is a special case of a path. Because we know that any viable loop doesn’t cross itself, we will only consider paths that also do not cross themselves.

Although we don’t look at the arrows when creating a path, we can still notice the arrows once the path is created. That is what we’ll do, using the arrows to define a “rotation” for each path.

Consider an arbitrary path. Trace your way around the path, noting each jump involved. For each jump, the arrow underneath where you are will, in general, rotate. It can rotate up to 45 degrees when moving between squares that share an edge and up to 90 degrees when moving diagonally.

If the arrow rotates 45 degrees clockwise as you jump, call that +45. If it rotates 45 degrees counterclockwise, call the -45. Similarly for 90 degrees. If the arrow remains the same, call that zero. Sum the rotations from all the jumps going around the path and call that the path’s rotation.

A path that closes on itself must have rotation that is a multiple of 360, because it starts and ends with the same arrow.

Consider a 2×2 path. There are four transitions, each with a rotation of at most 45 degrees. Since this cannot let you build up to 360 degrees, any 2×2 path must have rotation zero.

Similarly for a triangular path like this:

How about a 3×2 path? Such a path is built up from two 2×2 paths. When placing the two 2×2 paths on top each other, the overlapping parts cancel because they are traversed in opposite directions. Hence, the rotation for a 3×2 path is the sum of the rotations for the two 2×2 paths. All 3×2 paths have rotation zero.

We can build up an arbitrary non-crossing path from lots of 2×2 squares and triangles. An arbitrary path’s rotation is the sum of its constituent little paths. Since the little paths’ rotations are zero, all big paths have rotation zero, too.

On the other hand, a loop like the lemming would follow is also a path, and it must have rotation +/- 360 since loops cannot cross themselves. A loop cannot have rotation zero and rotation 360. These loops cannot exist, and the lemming dies.

January 2, 2011 at 12:11 am

[…] solution 1 solution 2 […]

March 23, 2012 at 9:42 am

[…] a loop of…”Mark Eichenlaub If you want the answer, I wrote up two different ones on my blog:https://arcsecond.wordpress.com/2… https://arcsecond.wordpress.com/2…Comment downvoted • Just nowCannot add reply if you are […]

December 10, 2013 at 4:49 am

There is a saying that goes “going around, behind your head, to hold your nose. “