The Puzzle: Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

  • It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).
  • What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)
  • Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.
  • Random will answer ‘da’ or ‘ja’ when asked any yes-no question.

[ Boolos, George (1996). "The hardest logic puzzle ever". The Harvard Review of Philosophy 6: 62–65. ]

History: The so-called "hardest logic puzzle ever" was coined as such by George Boolos. Boolos credits the logician Raymond Smullyan as the originator of the puzzle (and the computer scientist John McCarthy with adding the difficulty of not knowing what ‘da’ and ‘ja’ mean). Related puzzles can be found throughout Smullyan's writings, e.g. in Smullyan's 1978 What Is the Name of This Book?, pp. 149–56, he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth) and explains that "the situation is enormously complicated by the fact that although all the natives understand English perfectly, an ancient taboo of the island forbids them ever to use non-native words in their speech. Hence whenever you ask them a yes-no question, they reply 'Bal' or 'Da'---one of which means yes and the other no. The trouble is that we do not know which of 'Bal' or 'Da' means yes and which means no". Other related puzzles can also be found in Smullyan's 1997 The Riddle of Scheherazade. More generally the puzzle is based on Smullyan's famous Knights and Knaves puzzles (e.g. on a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. The puzzles involve a visitor to the island who must ask a number of yes/no questions in order to discover what he needs to know). A version of these puzzles was popularized by this scene in the 1986 fantasy film Labyrinth. There are two doors with two guards. One guard lies and one guard does not. One door leads to the castle and the other leads to 'certain death'. The puzzle is to find out which door leads to the castle by asking one of the guards one question. In the movie, the protagonist, named Sarah, does this by asking, "Would he [the other guard] tell me that this door leads to the castle?

Published academic articles on the hardest logic puzzle ever:
  • Stefan Wintein (2010). What makes a knight? In Lecture Notes in Computer Science, Volume 6211/2010, 25--37.

More articles on the hardest logic puzzle ever:

"Are you going to answer 'no' to this question?"

"Since the puzzle places no restrictions on the type of yes-no questions to which the gods will grant an answer we feel compelled (as a child in Sunday school feels compelled) to smash it. The gods sit before us and we ask each of them:
  • Are you going to answer ‘ja’ to this question?
If ‘ja’ means no, then True will be unable to respond with the truth. If ‘ja’ means yes, then False will be unable to respond with a lie. But they are infallible gods! They have but one recourse---their heads explode." (Rabern and Rabern 2008, pages 108-109)

                                             [New Scientist, Volume 216] [Image: Richard Wilkinson]

      George Boolos
George Boolos was a philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.  He was an early proponent and pioneer of applying modal logic to the theory of mathematical proof. He was also an authority on the 19th-century German mathematician and philosopher Gottlob Frege. Boolos once delivered a public lecture explaining Gödel's second incompleteness theorem entirely in words of one syllable. He was also an expert on puzzles of all kinds---in 1993 he reached the London Regional Final of The Times crossword competition. Published books: The Unprovability of Consistency (1979), The Logic of Provability (1993), Logic, Logic, and Logic (1998), Computability and Logic (2007).

      Raymond Smullyan
Raymond Smullyan is a philosopher, a mathematician, and a logician (and one of the many logicians to have studied under Alonzo Church). While a graduate student Smullyan published a paper in the 1957 Journal of Symbolic Logic showing that Gödelian incompleteness held for formal systems considerably more elementary than that of Gödel's 1931 landmark paper.

He was a professor of philosophy at City College in New York and is now Professor Emeritus of Philosophy at Indiana University. Smullyan is the author of, at least, fourteen books and of numerous research articles on the topics of mathematical logic, set theory, theory of computable functions, mathematical games and puzzles, and Eastern philosophy. His many books on recreational mathematics and recreational logic include What Is the Name of This Book? (1978), The Lady or the Tiger? (1982), Alice in Puzzle-Land (1982) , To Mock a Mockingbird (1985) , Satan, Cantor and Infinity (1992) , The Riddle of Scheherazade (1997), among others. 

In addition to his academic work in mathematical logic (Gödel's Incompleteness Theorems (1992), Recursion Theory for Metamathematics (1993), Diagonalization and Self-Reference (1994)), he has also written short philosophical parables and dialogues such as Is God a Taoist? and An Epistemological Nightmare. He is also a concert pianist, a Taoist, and a magician.

There are two doors with two guards. One guard lies and one guard does not. One door leads to the castle and the other leads to "certain death". Can you determine which door leads to the castle by asking one of the guards one question?

[©Krayevsky] This page was created and is maintained by Joachim Krayevsky. Please email corrections to joachim.krayevsky at gmail.