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.

Jeffrey Ellis said...

Classic #1: Which way would someone from the other village (not yours) tell me to go to get to the Kight's Village? If the villager is a Kight he will truthfully answer with the path to the Knave's village; if the villager is a Knave he will falsely answer with the path to the Knave's village. In either case, take the other path.

Classic #2: Identical twin sisters? Are they hawt? Maybe just hang here for a while. ;-)

Bonus problem: um... sheesh, I need some coffee first...

miller said...

I intentionally made the bonus problem significantly more difficult than the classics. :P I gotta keep the experts busy, or they'll start overanalyzing the classics.

Secret SquÃ¯rrel said...

*looks over shoulder

The knights will each point to the next knight forming a closed loop. If there was only 1 closed loop (given that there is at least 1 knight) you would know who the knight(s) were. (The closed loop might be a knight pointing to himself).

So, there is more than one closed loop. Since you can't distinguish between a loop of truth-telling knights and one of lying knaves, but know how many knights there are, the loops must be the same size.

Furthermore, since you don't know the identity of a single person, they must all be members of a same-sized loop.

I think that there are 5 loops of 5 members; hence 5 knights.

@Jeffrey re Classic 2, "Are they hot?" They're twin sisters! OF COURSE THEY'RE HOT!!!

Question: Ask one of them "Does the knight swing?" If she says "Yes", pick her, otherwise choose the other one.

matt said...

classic1: "which way to your village?" both will point to the knights' village. right?