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.

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. How he did it turns out to be one of the best lessons in logic and truth I have ever received. If you’d like to give the puzzle a try yourself, you can stop reading here. Good luck! If you succeed, you have my congrats. But if you don’t, come on back and you can go over Boolos’ solution with me below.

The first thing Boolos tells us is you shouldn’t make the mistake of crafting your questions all at once, like I did, hoping that the assume-and-deduce strategy would pay off. Instead, the first thing you must do is figure out a question that will identify who can’t be Random—or who can only be either True or False. This will, by process of elimination, help you reveal the identity of Random. And once you’ve identified Random, it’s easy work exposing the other two.

To better understand that approach, Boolos says, we need to see how it works in three simpler puzzles.

The first simple puzzle is actually an iteration 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, based on what they say, who’s who.

So for our first puzzle, suppose that you can’t remember whether Pluto is a dwarf planet, and you need to find out by asking someone nearby—but you don’t know whether that person is a knight or a knave. What’s the one yes-no question you can ask to figure out whether Pluto is a dwarf planet?

As Boolos explains, you want to trap the knight or knave into giving you what you want. And you set that trap with the phrase if and only if—a logical construction called a “biconditional.” So in this case your question would be: “Are you a knight if and only if Pluto is a dwarf planet?”

When you insert if and only if “between two statements that are either both true or both false, you get a statement that is true; but if you insert it between one true and one false statement, you get a false statement,” Boolos writes. It’s like a multiplication sign: Just as inserting a multiplication sign between either two positive or two negative numbers gets you a number that is always positive, inserting if and only if between either two true or two false statements gets you a statement that is always true.

Given that you could be addressing your question to either a knight or knave, there are four possible responses (assuming we don’t know that Pluto is in fact a dwarf planet):

1. If the person’s a knight and Pluto is a dwarf planet, then you get the answer “yes,” since both statements on each side of if and only if are true, and knights always speak truly.
2. If the person’s a knight and Pluto is not a dwarf planet, you get “no,” since the question contains a false statement.
3. If the person’s a knave and Pluto is a dwarf planet, you get “yes,” since knaves always speak falsely, and the correct answer is “no.”
4. If the person’s a knave and Pluto is not a dwarf planet, you get “no,” since the correct answer is “yes.”

Look what just happened: By phrasing the question using a biconditional, you get the information you want— if Pluto is a dwarf planet you get “yes” in response, and if it’s not you get “no”—whether you’re speaking to someone honest or not. However, remember that in the Hardest Logic Puzzle Ever, the knight and knave—unlike in this example—don’t speak English.

To trap them into giving away whether “da” and “ja” mean “yes” and “no” or vice versa, consider Boolos’ second simple puzzle.

In this puzzle, you know you’re asking a knight—who always tells the truth—but he only responds with “da” and “ja.” What one yes-no question can you ask to figure out whether Pluto is a dwarf planet? Taking your lead from the last puzzle, you’ve got this: Ask the knight, “Does “da” mean “yes” if and only if Pluto is a dwarf planet?” Bingo: You get the answer “da” if Pluto is a dwarf planet and “ja” if not, even though we don’t know what those words mean. The result is as profitable as the one above: Not knowing whether the person was a knight or a knave wasn’t an obstacle, so neither is not knowing the meaning of “da” and “ja.”

Boolos tells us that the Hardest Logical Puzzle Ever is essentially the first two simple puzzles plus a third. Before we solve that, though, take a look at how the first two puzzles combine: You need to find out whether Pluto is a dwarf planet, and you have to ask someone who could be either a knight or knave and he’ll only respond in “da” or “ja.” What question would you ask? If you think that, since this is a compound puzzle, the right thing to ask is a compound question, you’d be right! Ask: “Does “da” mean “yes” if and only if you’re a knight, and if and only if Pluto is a dwarf planet?” By asking this, you will get the answer “da” if Pluto is a dwarf planet and “ja” if it’s not, regardless of whether you’re addressing a knight or a knave. That well-crafted question is like a lock’s key.

Every statement is either true or false—there is no middle ground.

Now here’s the third simple puzzle. Its rules go like this. 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. By asking me one yes-no question, while pointing at one of the cards, you’ll be able to identify, with certainty, one of the cards as an ace. 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 the Random god. Where will you point, and what will you ask?

This one may seem slightly trickier, but it’s really not. Point to any card and ask if one of the other cards is an ace. Let’s say you point to the middle card and ask whether the left card is an ace. “Whether the middle card is an ace or not,” says Boolos, “you are certain to find an ace by choosing the left card if you hear me say ‘yes’ and choosing the right card if you hear ‘no.’ ” Why? Well, if the middle card is an ace, then when I say “yes,” the left card is also an ace; if I say “no,” the right card is. If the middle card is a jack, it’s irrelevant whether I say “yes” or “no” randomly: Both the left and right cards must be aces since the middle is a jack. So, whether you’ve pointed at an ace or not, my answer to your question, “yes” or “no,” will always locate the other ace as long as the card you’re wondering about is an ace is not the one you’re pointing to.

Pointing at any card, and asking about the identity of another, is the trapping strategy you need to adapt to figure out who must be either True or False in the Hardest Logic Puzzle Ever. The way you translate pointing at any card into words, as part of your question, is to substitute the factual statement “Pluto is a dwarf planet” in the compound puzzle above with an assertion of who Random is—which, you’ll notice, is just as equally an arbitrary decision as which card to point at. Who we say Random is in the question will depend on who we decide to pose the question to. It doesn’t matter; it could be any of the three gods.

Let’s pose the question to god A and assert that B is Random: “Does ‘da’ mean ‘yes’ if and only if you are True if and only if B is Random?” This is the equivalent of pointing at B while asking about the identity of A. In the card puzzle, whether or not I answered truthfully or randomly, you could depend on my “yes” or “no” response to find an ace with certainty. The same applies here. “No matter whether A is True, False, or Random,” says Boolos, “if you get the answer ‘da,’ C is either True or False, and if you get the answer ‘ja,’ B is either True or False!”

Let’s suppose we got “ja,” (we have to suppose one or the other). This makes B either True or False, which is precisely what we wanted—we already know how to expose someone like this: Ask B, “Does ‘da’ mean ‘yes’ if and only if Pluto is a dwarf planet?” Since we know Pluto is in fact a dwarf planet, there are two possible responses:

1. If B’s True, then you get the answer “da.”
2. If B’s False, then you get “ja,” since the correct answer is “da,” and False always speaks falsely.

Let’s assume we got “da,” which makes B True. Now ask True your third and final question: “Does ‘da’ mean ‘yes’ if and only if A is Random?” Given that Random must be A or C, there’s only one possible response:

1. Since B’s True, you get ‘da,’ which means A is Random, and therefore C is False.

To recap: Employing all of Boolos’ logic, our three questions to determine which god is True, False, and Random, go like this:

1. To god A: “Does ‘da’ mean ‘yes’ if and only if you are True and if and only if B is Random?” (We supposed A said, “ja,” making B True or False).
2. To god B: “Does “da” mean ‘yes’ if and only if Pluto is a dwarf planet?” (We supposed B said, “da,” making B True.)
3. And to god B (True) again: “Does ‘da’ mean ‘yes’ if and only if A is Random?” Since B’s True, he must say “da,” which means A is Random, leaving C to be False.

Solved!

So what does the Hardest Logic Puzzle Ever teach us? According to Boolos, it shows us how essential one of the supposed fundamental laws of logic—the law of excluded middle—seems to be. “Our ability to reason about alternative possibilities,” says Boolos, “even in everyday life, would be almost completely paralyzed were we to be denied the use of the law of excluded middle.” The law of excluded middle is simply this: Every statement is either true or false—there is no middle ground. That’s a sobering thought. But we have only to thank Smullyan, that most devilish of puzzlers, for making us ponder it with such edifying delight.

Brian Gallagher is an assistant editor at Nautilus.

Get the Nautilus newsletter

Cutting-edge science, unraveled by the very brightest living thinkers.

NL – In Page Mobile

Email: *

Captcha

Sign up for free