Monday, January 7, 2008

The Exile of Sir Floyd Puzzle

The Exile of Sir Floyd Puzzle
Sir Floyd was an amorous knight, it was little surprise when he was caught wooing the king's daughter Mitzi. The king was quite angry, but being a merciful monarch, he decided merely to exile Sir Floyd.

He put it to him this way:

"It is my wish that you leave this town by any road you choose, and move to a neighboring town. You may stay there a single night. The next day you must set out to a neighbor of that town, where again you may stay a single day, and so on for eternity."

Princess Mitzi silently handed him a map of the kingdom. Sir Floyd opened it up, and saw that every town in the kingdom sat at the junction of three roads, each of which led to another town in the kingdom. None of the roads crossed on their way from one town to another.

"A man could truly get lost forever in such a rat's maze!" said Sir Floyd.

"I have a suggestion," whispered Princess Mitzi. "Tonight, choose any of the three neighboring towns as your goal. Tomorrow, choose your next town by taking the leftmost of the two roads you have not traveled. From the following town, leave by the rightmost of the two roads, and alternate in this manner."

"Now go", thundered the king, "and I hope never to see you again!"

"Now go," whispered Princess Mitzi, "and I pray that you will return!"

What are the chances that Sir Floyd will return? What (outlandish) loophole must you rule out to make your calculation?