Matt Pavelle

The Hardest Logic Puzzle in the World?

[Update 2012-12]:>

New Scientist (Vague Scientist?) had a writeup in their Christmas issue about The Three Gods problem, and linked to the following, "A simple solution to the hardest logic puzzle ever"...

Three Gods

In 1996, The Harvard Review of Philosophy published George Boolos' Three Gods logic puzzle, and as of now that holds the title of "hardest logic puzzle in the world".

Three gods A, B, and C are called, in no particular 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. 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.

The following clarifications are provided:

  • It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).
  • What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)
  • Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.

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.

Blue Eyes

As with any other "[insert qualitative] [noun] in the world" statement, the "hardest logic puzzle in the world" is a moving target.

Prior to the Three Gods puzzle above, the Blue Eyes puzzle below was considered to be the hardest logic puzzle in the world.

A group of 201 silent people live on an island. There are 100 blue-eyed people, 100 brown-eyed people, and 1 golden-eyed Guru. All are perfect logicians: if a conclusion can be logically deduced, they will do so flawlessly and instantly.

None communicate via any means -- no speaking, no writing, no telepathy, etc. There are no mirrors or reflective surfaces, so no one knows their own eye color. Subsequently no one actually knows there are 100 blue-eyed people, 100 brown-eyed people, and 1 golden-eyed Guru on the island. As far as any person knows, there could be 101 brown, 99 blue, and 1 gold; or 100 brown, 99 blue, 1 green, and 1 gold. Everyone can see everyone else and can count the number of people they see with each eye color. Everyone on the island knows all the rules mentioned so far.

Every night at midnight a ferry stops at the island. Any islanders who have determined the color of their own eyes leave the island, all the others stay.

On one miraculous day, after endless years on the island, The Guru is manages to speak one sentence. Standing before the islanders, she says the following: "I can see someone who has blue eyes."

Who leaves the island, and on what night?

The solutions to both problems can be readily found via searching, but if you break them down and start with a simple premise, you might be surprised at how accessible these puzzles are.