An island is home to 100 people with blue eyes and 100 with brown eyes. There are no mirrors, and nobody may talk about eye colour. Anyone who works out their own eye colour must take the ferry at midnight that day and leave the island for good. All islanders are perfect logicians, and everyone knows it. One day a visitor says in front of everyone: "I can see someone with blue eyes." Everyone already knew that. What happens?
It seems that nothing happens: everyone sees at least 99 pairs of blue eyes. But the visitor changed not what each person knows, but what everyone knows about what the others know. The blue-eyed count the nights: if the 99 blue-eyed people I see have not left by night 99, I must be blue-eyed too. On night 100 all 100 leave together.
This puzzle has been called the hardest logic puzzle in the world, Terence Tao has written about it, and it is a favourite of interview-prep collections. Behind it stands a whole branch of logic: how what people know about each other's knowledge changes what they do.
200 people live here: 100 have blue eyes, 100 have brown. The islanders do not know these numbers: each one just sees everyone else's eyes.
No mirrors, no puddles, no photos. Nobody talks about eye colour or hints at it. Nobody has ever seen their own eyes.
A ferry comes every night at midnight. Anyone who worked out their own eye colour during the day must leave on it. In the morning everyone sees who left.
Every islander reasons perfectly and never slips. Everyone knows the island's rules, and everyone knows that everyone knows them.
One day a visitor arrives and says in front of everyone: "I can see someone with blue eyes." What happens next?
"Nothing: the visitor told them nothing new"
Everyone sees at least 99 blue-eyed people, so "there are blue-eyed people here" is news to nobody. Yet on night 100 all 100 blue-eyed leave together. What is new is that now everyone knows that everyone knows that everyone knows… without end.
100 blue-eyed, 100 brown-eyed, one sentence everyone already knew. Pick an answer.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
Don't tackle 100 at once. Shrink the island: what happens if only one person has blue eyes?
Now take two blue-eyed people. Each one waits to see what the other does, and a night when nobody leaves is a message too.
Suppose you already know what would happen on an island with k blue-eyed people. Now there are k + 1. What does each of them think when the night comes on which k people would already have left?
A smaller island. Choose how many people have blue and brown eyes, and how the visitor delivers the news: to everyone at once, to nobody, to each person in a whisper, or to all but one. Step through the nights and watch who leaves. Click an islander to see the island through their eyes.
No dice are needed here: the logic can be checked completely. An island of n people has 2n ways to assign who is blue-eyed. The page keeps all these "possible worlds" in memory, marks for each person which worlds they cannot tell apart, and every night strikes out the worlds that contradict what was seen at the pier. This is how logic has modelled knowledge since Kripke and Hintikka.
Row k means "k of the n people have blue eyes". Each cell shows the night when someone first leaves, the same for every island with that k; "never" is checked n + 2 nights ahead, after which the model no longer changes. The column "brown, if only two colours" adds the assumption that everyone knows eyes are only blue or brown. The islander who "missed it" did not hear the visitor, and everyone knows that. A private whisper changes the knowledge only of someone who hears something new.
Let's start with tiny islands and climb to 100. Then we'll see exactly what the visitor added to the island's knowledge.
If only Ann has blue eyes, she sees nothing but brown. The visitor says he sees blue eyes, so they must be hers. She leaves on the very first night. For her the visitor's words really are news, and this is the only case where they are.
Ann and Bob are blue-eyed. Ann sees Bob and thinks: "If my eyes are not blue, Bob sees no blue eyes and will leave on the first night." Bob thinks the same about Ann. In the morning both are still there. So each of them does see blue eyes, and the only ones Ann cannot see are her own. They leave together on the second night.
Brown-eyed Carl sees two blue-eyed people and waits for night three. But they leave on night two, exactly as they would if his eyes were not blue. So Carl learns only that he is not blue-eyed.
A blue-eyed islander sees 99 blue-eyed people. He reasons: "If my eyes are not blue, there are exactly 99, and 99 blue-eyed people, by the same logic, will leave on night 99." He waits. On night 99 nobody leaves. So there are not 99 blue-eyed people but 100, and he is the hundredth. All 100 reason the same way, so they leave together on night 100.
A brown-eyed islander sees 100 blue-eyed people and would wait for night 100. They leave right then, so he learns only that his eyes are not blue. If everyone knows there are only two colours, he leaves on the next night, night 101; under our rules he stays.
The argument "the visitor added nothing" checks only the first level: does everyone know the fact. But the blue-eyed reasoning rests on level 100: "I know that Ann knows that Bob knows that… knows there are blue-eyed people." Before the visitor this chain broke at step 100. After a public sentence it became endless, and that is why the count of nights began.
Each corner of the cube is a possible world: which of the three people A, B, C have blue eyes. An edge in a person's colour joins two worlds that this person cannot tell apart: they differ only in that person's own eyes. A person knows a statement if it holds in every world their edges reach from the current one. The visitor's public sentence deletes the world "nobody is blue-eyed", and every night cuts the edges between worlds where the morning pier looks different.
The philosopher David Lewis gave the first full analysis of common knowledge in his 1969 book "Convention", and Robert Aumann gave it a mathematical form in his 1976 paper "Agreeing to Disagree": an event is common knowledge if it holds in every world reachable by any chain of edges.
Statement P(k): if exactly k people are blue-eyed and the visitor's sentence is common knowledge, then all k leave on night k, and nobody leaves earlier.
Base: for k = 1 the blue-eyed person sees no blue eyes, so knows it is them. Step: a blue-eyed person sees k others; if they were not blue, by P(k) those would leave on night k. They don't, so they are blue-eyed.
Without the visitor: with k blue-eyed, "everyone knows that…" holds exactly k − 1 times in a row. Depth k already fails, and that is the depth the induction step needs.
Generalisation: if the visitor says "I see at least m blue-eyed people", the count starts at m, and all k leave on night k − m + 1.
Both halves are needed. Without the base the induction has nowhere to start: at k = 1 it is the visitor's sentence that gives the blue-eyed person knowledge. Without the step it is unclear why a silent night means anything: it does only because everyone knows how the others would reason.
The islanders open the door to three worlds. In mathematics the depth of knowledge becomes a number you can measure. In logic it turns out that common knowledge cannot be built from unreliable messages. And in practice network engineers, central banks and even storytellers have long lived with that fact.
Mathematics
Click a child to muddy or wash its forehead. Each child sees the other foreheads but not its own. Father says how many children at least are muddy, and asks again and again: "Who knows whether their forehead is muddy?" The children answer all at once.
This is the same puzzle in a school uniform, known as the muddy children puzzle. Here there are only two states, muddy and clean, and everyone knows it, so right after the muddy ones the clean ones answer too.
If father says "at least m", then with k muddy children they answer "I know" at question k − m + 1. The phrase "at least m" makes m levels common knowledge at once, and the count starts at m. If father says nothing, nobody ever finds out: only the depth k − 1 the children already have is available, and depth k is needed.
Logic
Generals A and B stand on two hills. They win only together. Messengers cross a valley where the enemy may catch them. The plan: messengers go in turn A → B → A → …, each one sets off only after the previous one arrived, and a general attacks only if every messenger addressed to him has arrived. Choose how many messengers the plan uses, and click the messenger the enemy will catch.
However many confirmations the plan uses, the enemy only needs to catch the last messenger. Its sender got everything he was waiting for and attacks, while its addressee is still waiting and stays put. Make the rule more cautious, and the attack simply shifts to another messenger.
In 1990 Joseph Halpern and Yoram Moses proved the general statement in the journal JACM: if messages can get lost, no finite exchange of them creates common knowledge. After m delivered messengers the depth of "A knows that B knows that…" is m, and no more. The islanders were lucky: they had one public sentence that everyone heard together.
Practice
A client and a server agree on a connection with three packets: SYN, SYN-ACK, ACK. Choose which packet gets lost first.
After three packets the server knows that the client knows that the server got its request. That is three levels, not infinity: the client that sent the ACK does not know whether it arrived. TCP (RFC 793, 1981; now RFC 9293) simply does not require certainty. The client treats the connection as open right after its ACK, and if the ACK was lost, the server repeats SYN-ACK after a timeout. Mistakes can happen, but they are fixed by retrying, not by logic.
Where common knowledge is what you need, you make a public statement, like the visitor on the island. Central banks announce rate decisions at a press conference for everyone at once rather than phoning each bank: what matters is that everyone knows that everyone else knows too. And in Andersen's tale "The Emperor's New Clothes" (1837) a child says out loud what everyone saw. After his words the naked emperor is seen by all together, and nobody can pretend any more.
In "A Mathematician's Miscellany" John Littlewood described three ladies in a railway carriage: each has a dirty face, and each laughs at the others. Suddenly one of them realises that she is dirty too. Littlewood put it first among his favourites and already extended it to n ladies by induction, the same argument as the islanders'.
In his book "Convention" David Lewis explained how agreements such as "drive on the right" hold together. For that he needed common knowledge: everyone knows the rule, knows that the others know it, and so on.
Robert Aumann proved that if two rational people share a common prior and their probability estimates for an event are common knowledge, those estimates must be equal. In 2005 Aumann received the Nobel Prize in economics together with Thomas Schelling.
The unreliable messengers problem was described in 1975 by Akkoyunlu, Ekanadham and Huber, as two gangs of gangsters. Jim Gray recast it as a paradox of two generals in his 1978 notes on database operating systems.
Halpern and Moses received the Gödel Prize for their paper "Knowledge and Common Knowledge in a Distributed Environment" (JACM, 1990). It showed that the language of knowledge is a handy way to reason about distributed computer systems. In 2009 the same paper won the Dijkstra Prize as well.
In the mid-2000s Randall Munroe of xkcd posted a version with a guru (a stranger on a Boston street told it to him) and called it the hardest logic puzzle in the world. Our version, with its midnight ferry, follows his. In February 2008 Terence Tao posted the puzzle on his blog with two conflicting arguments, "the visitor changes nothing" and "after 100 days all the blue-eyed leave", and invited readers to find the flaw.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.