by Tom Ellis
George Boolos coined the title The Hardest Logic Puzzle Ever for a puzzle that Wikipedia gives in this form:
Three gods A, B, and C are called, in some 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.
I have some comments on that definition:
Rabern and Rabern and Roberts have presented simple solutions to the puzzle (detailed at Wikipedia).
Rabern and Rabern note that the problem is harder if Random's answers are random, rather than his choice as to whether he should tell the truth or lie (noted at Wikipedia).
We should suppose that the gods may take an arbitrarily long time to answer questions. This precludes us from asking questions which at least one of the gods cannot answer: if we were to ask it to him, we'd never know if he couldn't answer or if he just hadn't answered yet (cf. recursive enumerability). In this way we avoid the possibility of Rabern and Rabern's "exploding head" answers.
The gods speak one of two languages from the set L ={ "Daisyesjaisno", "Jaisyesdaisno" }. It's not clear from the Wikipedia article which of the following is to be assumed:
Clearly the former leads to (on the face of it) an easier problem, and I suspect that's what the definition intended.
Now I wish to extend the puzzle and make it even harder! Then I'll demonstrate how to solve it.
You don't know how many of each type there are, except that there are no more than N randomers.
Each god speaks one of the two languages in L, but they might not all share the same language.
There is a fork in the road. One path leads to the castle. Your task is to find the way to the castle in 2N questions.
(The "castle" question is arbitrary. It's just a question you don't originally know the answer to.)
If you'd like to know how to solve this puzzle, you will find the answer on a separate page.
Thanks to Jon Pretty and Richard Smith without whose input I would never have written this article. Thanks to Brian Rabern for his comments on use-mention.