Wednesday, September 17, 2008

Knights and knaves puzzle variations

My guess is that nearly all my readers have heard the basic knights/knaves puzzle, but I have recently come across interesting modifications of the problem. (It took four -- count them! -- theory grad students to figure out the "challenge" below, and it is probably within ε (i.e., nigh) of murderously frustrating for non-mathematical laypeople.) I have not solved the last three, although two of them have solutions posted on Wikipedia.

As so often occurs in puzzles, you find yourself shipwrecked on an island. The population of this island can be partitioned into two groups: knights and knaves. Knights answer all questions truthfully; knaves always lie. While wandering, you come upon a building with two doors, each guarded by one native islander. You know that one of the doors leads to a pile of treasure, and the other leads to a hungry, man-eating lion. You may ask a single yes/no question to one of the guards. Then you must select a door, and meet your fortune/death.

Warm-up: If you know that exactly one of the guards is a knave and one is a knight, what question do you ask? This is the standard knights and knaves puzzle.

Challenge: If you know nothing about the distribution of the two islanders (maybe two knights, maybe two knaves, maybe one of each), what question do you ask?

Hard challenge: The island also contains some residents who reply at random. You happen upon three islanders, and know that there is one of each type (Knave, Knight, Random). You may ask three yes/no questions. (Each question can be addressed to only one of the islanders.) What do you ask in order to determine their identities?

Harder challenge: Same as the hard challenge, except that the islanders reply in their language, where {yes, no} = {foo, bar} but the exact correlation is unknown. Wikipedia lists this as "the hardest logic puzzle ever."


This post's theme word: ambisinister, "clumsy with both hands." Unfortunately, it does not mean that you are equally sinister with both sides of your body.

No comments: