Answer: Lemming

The problem asked:

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.

Here is a proof using reductio ad absurdum:

First, prove that if the lemming never falls off there must be a closed loop the lemming goes around endlessly.

There are 1,000,000 squares, so by the lemming’s 1,000,001st jump, it must have revisited at least one square. Take the first instance in which the lemming revisited a square. From there it will repeat exactly what it did the first time it hit that square, going on and on in a closed loop.

A closed loop.

An example of a closed loop for the lemming to roam on. The remaining arrows aren't filled in. This turns out not to be a valid path.

So, if the lemming is not going to fall off, there must be loops on the checkerboard, and if there are loops on the checkerboard, then obviously it is possible for the lemming to avoid falling off.

Now we only need to prove that loops do not exist. To begin, we’ll assert that if loops do exist, they must be fairly simple. Specifically, they cannot cross themselves.

Take a look at the green box pasted onto the original example below. It highlights the region where a loop crosses itself. This is not a legal configuration of arrows because the 45 degree rule is violated, but any time a loop crosses itself it must do it this way. Hence loops don’t cross themselves.

Same closed loop.

The same loop as before, but here we see that when a loop crosses itself it must break the rule about rotating only 45 degrees between squares that share an edge.

Now we know that we’re considering simple, non-crossing loops, and we want to prove they don’t exist. We assume they do and find a contradiction.

Simple, closed loops have an inside and an outside. We can categorize loops by how large they are – how many squares are on the inside. If we consider all the possible loops, there must be one (or a set of ones) that are the smallest. This sets a minimum size for loops.

A simple loop.

A candidate simple loop with the inside of the loop shown in green.

We will show the existence of an arbitrary loop implies the existence of a smaller loop, contradicting the existence of a minimal loop size.

Suppose we have checkerboard A with a simple loop. We create a new checkerboard B which is just like A except that every single square has its arrow rotated 45 degrees in the same direction. The direction is chosen so that arrows on the loop are rotated towards the inside of the loop. This new checkerboard is legal if the first one was, because none of the arrows rotate relative to each other.

Rotating arrows on a closed loop.

The loop on board A is old news. On board B, we rotate every arrow from board A 45 degrees (not all arrows shown, of course).

Imagine the lemming starting on board B on a green square. If it ever hits a square where the arrow is drawn, it will be pushed back into the green area on its next move. It can never escape to outside the old loop. The lemming instead runs around indefinitely on a combination of the old loop and the green. This means it finds a new loop, and because that new loop includes at least some green squares, it has a smaller inside.

Whenever there is a legal board with a loop, there must be another legal board with a smaller loop. This contradicts the fact that there must be a smallest loop. Thus there is no legal board with a loop and the lemming dies.

About these ads

5 Responses to “Answer: Lemming”

  1. Riley Says:

    It seems that the smaller loop argument implies that the existence of a loop of any size implies the existence of a loop of size zero (i.e. with no inside eventually). Clearly at that point it can no longer get smaller. Thus, it seems like the proof finally requires a discussion of why loops with zero inside would be invalid. I suppose it’s fairly trivial; maybe I’m just nitpicking. :) Anyway, this was a really interesting problem!

    By the way, how are you doing these days?

  2. Mark Eichenlaub Says:

    Yeah. We need to show that there are no loops of size zero. There actually a lot of details that could be fleshed out more.

    I’m doing well. I spend a lot of time on tricky problems.

  3. Answer: Lemmings (part 2) « Arcsecond Says:

    [...] Arcsecond « Answer: Lemming [...]

  4. New Problem: Lemming « Arcsecond Says:

    [...] Problem: Lemming By Mark Eichenlaub solution 1 solution [...]

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

    [...] you want the answer, I wrote up two different ones on my blog:…Comment downvoted • Just nowCannot add reply if you are logged out.UpvoteDownvote • Repost [...]

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


Get every new post delivered to your Inbox.

Join 54 other followers

%d bloggers like this: