(Don't even bother until you've looked over the question.)


"How?" you ask? Well, I'll tell you:

First off: There are clearly a finite number of legal partitions. (significantly less than 2112, to be a little more precise) Then if God/Deep Blue/the garbage man can construct a successful sequence for any given partition, s/he/it can merely string the sequences for each partition together into one program the size of something very, very large.

That being said,
it is now our duty to specify a method for the construction of a successful sequence for any given partition. This right here is the hard part.

Say we have a given legal partition in front of us. Let's number the squares 1 to 64, any way we please. For any given starting square, we can clearly construct a successful sequence on this partition. Now let's define a couple of functions as a useful shorthand:

Let S(i) be some successful sequence for starting square i.
Let f(i,j) be the final resting place of the pawn if the sequence of moves S(i) is made from starting square j.

Thus, S(i) is a sequence of moves and f(i,j) is the number of a square.

Now, let's start with S(1). Let the starting square be j. If the j=1, then the pawn has touched all the squares. Yay! Otherwise, the pawn may or may not have completed its rounds, and it currently resides at f(1,j) by definition. If j=2, appending the (well-defined) sequence S(f(1,2)) will result in success.

(Bear with me, now.)

If j is neither 1 nor 2, then the pawn again may or may not have touched all the squares and is now sitting pretty on square f(2,f(1,j)). Then if j=3, we can complete the sequence by appending the sequence S(f(2,f(1,3))).

Continuing this process, we see that appending S(f(3,f(2,f(1,4)))) will round out the sequence if j=4; further appending S(f(4,f(3,f(2,f(1,5))))) will finish it off if j=5, and so on up to S(f(63,f(62,...,f(2,f(1,64))...) if j=64. If we string all these together in the order they were derived (S(1),S(f(1,2)), and so forth), we will find that we have miraculously constructed a sequence of moves that will be successful for any starting square on this partition.

Since this process is applicable to any legal partition, God can make such a sequence for each partition and then string them all together into one gargantuan sequence, hand it to Satan, and gloat.

Damnit, God always wins.

The determination of the exact length of the final sequence is left as an exercise for the unbelievably masochistic reader.

Log in or register to write something here or to contact authors.