This post is about the best logic puzzle I’ve seen in absolutely ages. It’s easy to explain and doesn’t require any silly tricks, but has a decent amount of depth to it and challenges your intuition. I’m going to present the puzzle, an extended version of the puzzle, and a general solution to the extended version.
The “classic” puzzle was told to me by David Cushing, who was told it by Alistair Bird, who himself found it on the MathOverflow “math puzzles for dinner” thread.
The setup goes like this:
- there is a castle with 17 rooms in it, arranged in a line.
- the princess who lives in the castle sleeps in a different room each night, but always one adjacent to the one she slept in the previous night. She is free pick any room to sleep in on the first night.
- a prince would like to find the princess, but she will not tell him where she is going to sleep each night.
- the prince can look in a single room each night, with no other restrictions
And the puzzle is:
Is there a strategy the prince can follow to guarantee he looks in the room the princess is sleeping in within a finite number of days?
If you haven’t seen this puzzle before, look away from the screen now and spend some time working out the solution. Try starting with castles of just a few rooms, and see if you can spot a pattern in the winning strategies. This version of the puzzle is definitely solvable by just sitting and thinking for a while.
Read more…