How to Solve the Hardest Logic Puzzle Ever

How to Solve the Hardest Logic Puzzle Ever
A step-by-step guide to True, False, and Random.
By BRIAN GALLAGHER
Nov 5 2016
http://nautil.us/issue/30/identity/how-to-solve-the-hardest-logic-puzzle-ever

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.

[snip]

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s