Wednesday, January 23, 2008

Solution to The Exile of Sir Floyd Puzzle

This is the Solution/answer to the The Exile of Sir Floyd Riddle posted on 7th January 2008. If you havent tried it as yet, go for it at The Exile of Sir Floyd Puzzle .

It is not hard to see that if the number of towns is infinite, then Sir Floyd can wander away forever and never return. If you don't believe this, look at the hexagonal tiles on a bathroom floor, and consider the cracks between them to the be roads. Going left, then right, takes you steadily away from your starting point.

So let us rule out the "outlandish" possibility that there are an infinite number of towns. Then it should be clear that Sir Floyd will eventually run out of unvisited towns, and so must reach a town he has already visited.

Now it's possible that he enters this town from a different road than he did the first time he visited it. So let's assume that, in that case, we watch him continue in his exile. Eventually, he must re-enter a town and do so from the same road by which he entered it the first time. From that point on, every step he takes must be a repetition of his initial steps. Where he went right the first time, he must go right the second time, and so on.

Our next question is, is the capital city on this loop? And the answer is, it must be! Because it turns out that if we know which city Sir Floyd is in, and what road he left it by, we can determine which road he entered the city by, and hence what neighboring town he came from. So if we reverse Sir Floyd's steps, we must return to the capital. But the loop has the property that it is a loop both forwards and backwards. There is no way that Sir Floyd could have gone through a few towns that were not on the loop, and then suddenly joined it, because that means that a given town has two roads that Sir Floyd used to enter it, but for which in both cases he left by the same third road, a possibility ruled out by his method of choosing the exit road.

Finally, the same reasoning should convince you that the first time Sir Floyd re-enters a town by the same road, he has just left the capital city (though not necessarily the first time he returned to it!).
---