I've come across a lot of interesting
math problems over the years that can be
solved without the need for high-level knowledge of math. If this idea doesn't
fail miserably, I think I'll make it a regular
feature. So, without further
ado, here's today's question:
Satan proposes a contest to God. (If you like, you can substitute, say, Deep Blue and its evil twin. The numbers involved are positively staggering.) Satan will construct a board as follows:
It will consist of an 8X8-square partitioned grid, the only restrictions being that partitions must only occur between squares and that any square must be accessible from any other by a path that doesn't cross a partition.
Satan will place a pawn on this board on a square of his choice. The challenge for God is to specify a sequence of moves (up, down, left, or right) that will guarantee that the pawn touches every square on the board at least once. Illegal moves (off the board, through a wall) will be ignored. God is to be given no foreknowledge of the structure of the partition or the starting position of the pawn.
Can God write a sequence of moves that will ensure victory, and if so, how?
Happy solving.
Alright then, here's the
solution.