"The Hardest Logical Puzzle Ever"
Upon reading in Wikipedia this evening that George Boolos practiced constrained writing by delivering a speech on Gödel's Incompleteness Theorem in words of a single syllable, I pulled out Boolos's Logic, Logic, and Logic, where I found the speech. It's pretty good, although it only explains Gödel's Theorem, without proving it. Still.
There's some fabulously fun stuff at the end of Logic, Logic, and Logic, including a new typography for a limerick about W. V. O. Quine, a refutation of Penrose on humans' noncomputational ability to "see" that Gödel sentences are correct, and the thing I want to mention here, which Boolos calls "the hardest logical puzzle ever".
When I read it, I realized that someone some years ago had presented me with a slightly easier version of the puzzle, that I had worked on it for about three days, and that I had come up with a proof that the puzzle was impossible to solve. (My proof turned out to be wrong!) The original version that was presented to me was Raymond Smullyan's version; Boolos explains in a footnote that John McCarthy (yes, that John McCarthy) proposed the change that makes it even harder (but still solvable).
This puzzle is an extreme twist on the familiar liar/truthteller puzzles, which have already been elaborated in all directions by Raymond Smullyan. In Boolos's view, this puzzle is at the apex of Smullyan's work in the genre.
Here is how Boolos phrases the puzzle (omitting his footnote on McCarthy's contribution):
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.
My impossibility argument came back to me as I was thinking about this puzzle. Here it is: Each question you ask will yield at most one bit of information. The number of bits necessary to express who is who will be ld(3 P 2) (the dual logarithm of the number of permutations of three elements taken two at a time), which is about 2.58 bits. However, when you ask the first question, since you don't know who is random, it is possible that the answer you get will be random, and hence independent of the assignment of names to gods, and hence not yielding any information whatsoever. (That is to say, the answer may not decrease your uncertainty about which god is which in any respect, because the answer could be "ja" completely independently of which god was which, and the answer could be "da" completely independently of which god was which.) Even if you had a way to get one bit of information from each of the two remaining yes/no questions, the total amount of information you could get would be 2.0 bits, which is not enough.
My argument is wrong and the puzzle can actually be solved in a deterministic way. When I first heard the puzzle, I was attached to my impossibility argument and could not be talked out of it until someone told me the solution, whereupon I agreed that it was right.
This is a great puzzle, and I wish I could remember who first asked me about it.
