Answer: Lemmings (part 2)

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.

An example path.

An example path. It ignores the arrows underneath it, which in this example are in a legal configuration.

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.

A 2x2 path.

A 2x2 path must have rotation zero. Red are the arrows. Green is the path. Blue are the jumps.

Similarly for a triangular path like this:

A small triangular path.

A small triangular path like this must also have rotation zero.

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.

A 3x2 composite path.

If you traverse the green path, then the purple path, the transition you do twice cancels, and all the other transitions sum to the same thing as the gold path.

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.

A big composite path.

Our original example path made up of lots of little squares and triangles. Some squares are used twice.

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.

3 Responses to “Answer: Lemmings (part 2)”

  1. New Problem: Lemming « Arcsecond Says:

    […] solution 1 solution 2 […]

  2. What is your favorite logic puzzle? - Quora Says:

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

  3. sujil pv Says:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: