Monday, August 31, 2009

Knights and knaves

This kind of puzzle makes use of knights and knaves. A knight is a person who always tells the truth. A knave is a person who always lies. This sort of puzzle was invented, or at least popularized by Raymond Smullyan. They are fun times.

Classic #1:
You are trying to reach the legendary Knight's Village, where everyone is a knight. But you've reached a fork in the road, and you know that if you take a wrong turn, you will instead end up at the Knave's Village, where everyone is a knave. The fork is unmarked, but you see a villager, and resolve to ask him for directions. What single question should you ask him to get to the Knight's Village?
Classic #2:
You are in a labyrinth, and have reached a fork. One of the paths lead out, and the other will certainly lead to your doom (it's that kind of labyrinth). Two guards stand nearby, identical twin sisters. You have heard of these guards, and know that one is a knight, while the other is a knave. What single question can you ask the guards to get out of the labyrinth?


Comic comes from xkcd. Phrasings of the classics are mine. Some of my readers have already seen the classics, so I also wrote a bonus problem just for you.

Bonus problem:
Twenty-five knights and knaves sit around a round table. They all know each other well, but I don't know any of them. But I know that there's at least one knight at the table. I ask them all to point to the next knight on their left. Each one of them points to another person at the table. To my disappointment, even after carefully considering their answers, there is not a single person at the table who is certainly a knight, or certainly a knave. However, I now know how many knights are at the table in total!

How many knights are at the table?


As usual, solutions are posted. Hesitating to look is highly encouraged.