The most difficult puzzle in the world

from Wikipedia, the free encyclopedia

The world's most difficult puzzle is originally a Raymond Smullyan logical puzzle that was published in the context of an article by the American philosopher and logician George Boolos . First published in 1992 under the title L'indovinello più difficile del mondo in the Italian daily La Repubblica , it appeared again in 1996 in The Harvard Review of Philosophy under the English title The Hardest Logic Puzzle Ever . The riddle is about three gods, one of whom is always telling the truth, one is always lying and another happens to be telling the truth or lying. Answering in their own language, the three gods need to be identified with just three yes / no questions.

origin

In his article, Boolos pays tribute to the logician Raymond Smullyan as the originator of the riddle and John McCarthy for the additional difficulty that the gods answer in their own language.

The riddle is based on the " Knights and Squires " stories. An imaginary island, inhabited by knights and squires, serves as the setting for the latter. Knights always tell the truth and squires always lie. A visitor to this island has to ask them some yes / no questions to find out what they want to know. As a result, there are several variations of this puzzle, one of which was made famous by the 1986 fantasy film Labyrinth . The scene is about two guards who guard two doors and one of whom is lying and one not. In addition, one door leads to the lock and the other to "certain death". The point is to find out from one of the guards by asking a question which door leads to the lock. The protagonist of the film tries to do this by asking one of the two guards: "Would he [the other guard] tell me that this door leads to the lock?"

Similar puzzles can be found in Smullyan's publications such as B. What is the Name of This Book? (Pp. 149–156), in which he describes a Haitian island on which half zombies (liars) and the other half people (tell the truth) live. He explains:

“The situation is extremely complicated by the fact that, while all natives understand English perfectly, an ancient taboo forbids them to reproduce words in any language other than their own. Whenever you ask them a yes / no question, they will answer you with “Bal” or “Da” - one answer means yes, the other no. The problem is that you don't know which answer is yes and which is no. "

Content of the puzzle

“Behind three people A, B and C are the gods of truth, lies and chance. The God of truth always answers with the truth, the God of lies, on the other hand, only knows the lie and the God of chance answers either with the truth or with a lie. Your job is to uncover the identities of A, B, and C by simply asking three yes / no questions. But each question can only be put to one god. In addition, the gods understand German, but they will answer your question in their own language. H. with DA and BAL. You don't know which answer means yes and which no. "

Boolos adds the following notes:

  • You can ask a god several questions - or none at all to a god.
  • Which God you should ask the second question to may depend on the answer to the first question. The same applies to the third question.
  • The answers of the god of chance can be compared to a coin toss: if he is upside down he will tell the truth, if he is number he will lie.

solution

For a better understanding, the simplification DA = Yes and BAL = No should first be considered. In addition, in the following W, F and Z are the God of truth, the God of lies and the God of chance. Possible questions include the following:

Diagram illustrating the solution to the simplified puzzle
Mit der 1. Frage bestimmt man einen Gott G ≠ Z.
  • Question A: "Are you the God of truth if and only if B is the God of chance?"
Mit der 2. Frage bestimmt man, ob G = W oder G = F.
  • Question G: "Is Rome in Italy?"
Mit der 3. Frage bestimmt man, ob A = Z oder A ≠ Z.
  • Question G: "Is A the god of chance?"

Let us now consider the general case. The added difficulty of language is solved by expanding the above questions:

Diagram illustrating the solution to the puzzle
Mit der 1. Frage bestimmt man einen Gott G ≠ Z.
  • Question A: "Does DA mean yes exactly if you are the God of truth exactly when B is the god of chance?"
Mit der 2. Frage bestimmt man, ob G = W oder G = F.
  • Question G: "Does DA mean yes exactly when Rome is in Italy?"
Mit der 3. Frage bestimmt man, ob A = Z oder A ≠ Z.
  • Question G: "Does DA mean yes exactly if X is the god of chance?"

The approach described above goes back to TS Roberts. The idea is used here that for every yes / no question F with the help of the question: "Would you answer DA if I asked you F?", Which one poses to the God of truth or the God of lies DA receives answer if the appropriate answer to F is yes, and BAL otherwise.

Individual evidence

  1. ↑ George Boolos : The Hardest Logic Puzzle Ever . In: Harvard Review of Philosophy , 6, 1996, pp. 62-65.
  2. ^ Raymond Smullyan : What is the Name of This Book? . Englewood Cliffs, New Jersey: Prentice Hall.
  3. ↑ Brian Rabern, Landon Rabern: A simple solution to the hardest logic puzzle ever . In: Analysis 68, 298, April 2008, pp. 105-112.
  4. ↑ TS Roberts: Some Thoughts About The Hardest Logic Puzzle Ever . In: Journal of Philosophical Logic , 30: 609-612 (4), December 2001.