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,001^{st} 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.

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.

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.

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.

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.

August 13, 2010 at 11:12 am

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?

August 13, 2010 at 11:19 am

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.

August 13, 2010 at 12:25 pm

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

January 2, 2011 at 12:10 am

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

March 23, 2012 at 9:42 am

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