George Boolos published a form of this puzzle in 1996, boldly naming it the Hardest Logic Puzzle Ever, and many who try it agree that it deserves that title. This presentation of the puzzle includes some clarifications by later authors, and places the puzzle in the same world as the previous Knights and Knaves puzzles. If you have not yet solved those puzzles, do that first. Although this puzzle is very difficult, when you have solved all the Knights and Knaves puzzles, you have all the tools necessary to solve this one. Other Knights and Knaves puzzles can be found in Raymond Smullyan’s book, What is the Name of This Book?.
You are on an island inhabited by three types of people: knights, who only tell the truth; knaves, who only lie; and spies, who may either tell the truth or lie. In addition, the words for Yes and No on this island are Ja and Da, but you do not know which word means Yes and which word means No.
You encounter three people: Red, Blue and Green. One is a knight, one is a knave, and one is a spy, but you do not know which is which. You are permitted to ask three yes-or-no questions. Each question must be asked of exactly one of the inhabitants, but you may direct two or all three of the questions to one person if you like. What question you ask, and of whom, may depend on the answer to a previous question. The spy will have no strategy and whether he answers Ja or Da should be thought of as random. You must learn the identities of Red, Blue and Green. What three questions will you ask?
Clarifications:
- The spy’s behavior is completely random and should be thought of as a coin flipping in his head: if it comes up heads, he says Ja, and if it comes up tails, he says Da.
- You are not permitted to ask potentially unanswerable questions. For instance, questions about whether an inhabitant would answer a question in the same way the spy would answer it, cannot be answered by the knight or the knave, as the spy’s behavior is unpredictable. Therefore such questions are invalid in this conception of the puzzle.
An Answer
See AnswerFor your first question, ask Red, “If I asked you if Blue is the spy, would you say Ja?” If Red answers Ja, then either Red is the spy and answering randomly, or Blue is the spy. Either way, Green is not the spy. If Red answers Da, then either Red is the spy and answering randomly, or Blue is not the spy. Either way, Blue is not the spy.
Having identified an inhabitant who is not the spy, ask that inhabitant, “If I asked you if you were the knave, would you say Ja?” If the answer is Ja, that person is the knave. If the answer is Da, that person is the knight.
For your last question, ask the same islander, “If I asked you if Red is the spy, would you say Ja?” If the answer is Ja, then Red is the spy. If the answer is Da, then the spy is the islander you have not yet spoken to. The remaining islander is whichever type of inhabitant has not been identified.