Facebook
Twitter
Pocket
Reddit
Email
While a doctoral student at Princeton University in 1957, studying under a founder of theoretical computer science, Raymond Smullyan would occasionally visit New York City. On one of these visits, he met a “very charming lady musician” and, on their first date, Smullyan, an incorrigible flirt, proceeded very logically—and sneakily.
“Would you please do me a favor?” he asked her. “I am to make a statement. If the statement is true, would you give me your autograph?”
Content to play along, she replied, “I don’t see why not.”
“If the statement is false,” he went on, “you don’t give me your autograph.”
“Alright …”
His statement was: “You’ll give me neither your autograph nor a kiss.”
It takes a moment, but the cleverness of Smullyan’s ploy eventually becomes clear.
A truthful statement gets him her autograph, as they agreed. But Smullyan’s statement, supposing it’s true, leads to contradiction: It rules out giving an autograph. That makes Smullyan’s statement false. And if Smullyan’s statement is false, then the charming lady musician will give him either an autograph or a kiss. Now you see the trap: She has already agreed not to reward a false statement with an autograph.
With logic, Smullyan turned a false statement into a kiss. (And into a beautiful romance: The two would eventually marry.)
It is this sort of logical playfulness that Smullyan loves, and that everyone seems to love him for. His books on the subjects of recreational math and logic, with titles like What Is the Name of This Book? and To Mock a Mockingbird, not only encouraged people to pursue careers in these topics but also changed how math and logic are taught. Over his near century of life, Smullyan, 96, became an accomplished pianist and magician, made fundamental contributions to modern logic, and wrote about Taoist philosophy and chess. “He is the undisputed master of logical puzzles,” Bruce Horowitz, one of his former Ph.D. students, has said.
One mark of Smullyan’s legacy is the interest philosophers and logicians still have in his most difficult puzzle, known as the Hardest Logic Puzzle Ever. The title was given by a philosopher of logic at the Massachusetts Institute of Technology, a colleague of Smullyan’s named George Boolos, who—no slouch himself—adored logical challenges of any sort. He once tested himself by giving a lecture on Gödel’s second incompleteness theorem, “one of the most important results in modern logic,” using only single syllable words.
The Hardest Logic Puzzle Ever goes like this:
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.
Always up for a challenge, I sat down on my couch, pen and paper in hand, confident I could conquer the puzzle in two hours tops. It seemed to me that all I had to do was start by coming up with three questions at once and then work out their consequences. I asked A, for example, whether B was True; asked B whether A was True; and asked C whether he was True. Hours later, having asked the gods every yes and no question I could think of, I understood how the puzzle got its name. Clearly my questions weren’t compelling the gods to answer the way I wanted them to.
Frustrated, I went in search of enlightenment. The master atop the mountain turned out to be Boolos, who solved the puzzle in 1996. His approach to the solution is to combine the solutions to three simpler puzzles. The first is one of Smullyan’s classic knights and knaves riddles, introduced in his book, What Is the Name of This Book? In the puzzles, knights always tell the truth, knaves always lie, and your task is to find out who’s who. The solution is to ask a question like, “Are you a knight if and only if two plus two is four?”
In the second puzzle, you know you’re asking a knight—but he only responds with “da” and “ja.” The strategy here is a variant of that in the first puzzle: You ask, “Does ‘da’ mean ‘yes’ if and only if two plus two equals four?”
The third puzzle tosses in the element of randomness: Suppose I place three cards in a row in front of you—two aces and a jack—face down. You don’t know how they’re ordered, but I do. You can ask one yes-no question, while pointing at one of the cards. If you happen to point at one of the two aces, I’ll answer the question truthfully, like a knight; if you point at a jack instead, I’ll answer “yes” or “no” at random, like Random. Where will you point, and what will you ask?
The answer: Point to any card and ask if one of the other cards is an ace.
Now, to solve the Hardest Logic Puzzle Ever, you just need to combine the solutions to these three simpler ones. That, I’ll leave up to you.
Brian Gallagher is the editor of Facts So Romantic, the Nautilus blog. Follow him on Twitter @brianga11agher.
Watch: People who chronically lie lack an emotional reaction to the facts of their deception.
A version of this article was originally published in our “Identity” issue in November, 2015.
Get the Nautilus newsletter
Cutting-edge science, unraveled by the very brightest living thinkers.
