# Is there no solution to the blue-eyed islander puzzle?

Text below copied from here

The Blue-Eyed Islander problem is one of my favorites. You can read about it here on Terry Tao's website, along with some discussion. I'll copy the problem here as well.

There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

[For the purposes of this logic puzzle, "highly logical" means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.]

Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople).

One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.

One evening, he addresses the entire tribe to thank them for their hospitality.

However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.

What effect, if anything, does this faux pas have on the tribe?

The possible options are

Argument 1. The foreigner has no effect, because his comments do not tell the tribe anything that they do not already know (everyone in the tribe can already see that there are several blue-eyed people in their tribe).

Argument 2. 100 days after the address, all the blue eyed people commit suicide. This is proven as a special case of

Proposition. Suppose that the tribe had $n$ blue-eyed people for some positive integer $n$. Then $n$ days after the traveller’s address, all $n$ blue-eyed people commit suicide.

Proof: We induct on $n$. When $n=1$, the single blue-eyed person realizes that the traveler is referring to him or her, and thus commits suicide on the next day. Now suppose inductively that $n$ is larger than $1$. Each blue-eyed person will reason as follows: “If I am not blue-eyed, then there will only be $n-1$ blue-eyed people on this island, and so they will all commit suicide $n-1$ days after the traveler’s address”. But when $n-1$ days pass, none of the blue-eyed people do so (because at that stage they have no evidence that they themselves are blue-eyed). After nobody commits suicide on the $(n-1)^{st}$ day, each of the blue eyed people then realizes that they themselves must have blue eyes, and will then commit suicide on the $n^{th}$ day.

It seems like no-one has found a suitable answer to this puzzle, which seems to be, "which argument is valid?"

My question is... Is there no solution to this puzzle?

-
Why would it not have a solution? You stated the perfectly valid proof (that the 100 blue-eyed people kill themselves after 100 days) yourself. –  Gregor Bruns Nov 15 '12 at 23:02
The day after the blue-eyed people commit suicide, everyone else gathers in the square and commits suicide, leaving the stunned foreigner alone on the island. –  Neal Nov 15 '12 at 23:06
The new information is burrowed in the chain of thought inferences the people do (precisely at the end - the $n=1$ case). The people on the island are quick and logical thinkers, they are not mind-readers. For sure, it does not have to be an outsider who speaks, it could as well be one of the persons on the island. That is why there is this law prohibiting discussing eye-colors. –  Gregor Bruns Nov 15 '12 at 23:28
This problem is discussed on this wikipedia page on common knowledge. From what I understand, I believe this type of problem cannot be handled with our usual logic, and requires the use of modal logic, but this out of my qualifications. –  Vincent Nivoliers Nov 15 '12 at 23:37
As is common in these sorts of things, this isn't a logic problem, it's a modeling problem. As soon as you write down a specific logic to represent how the villagers reason, the outcome becomes indisputable. The "paradox" comes from the fact that there is no well-known model for this sort of reasoning. If you make the logic strong enough, the villagers will kill themselves even without the foreigner's comment. If you make it weak enough, they will not kill themselves even with the foreigner's comment. Thus it is entirely a question of which logic the villagers use to reason about knowledge. –  Carl Mummert Nov 16 '12 at 13:16

Argument 1 is clearly wrong.

Consider the island with only two blue-eyed people. The foreigner arrives and announces "how unusual it is to see another blue-eyed person like myself in this region of the world." The induction argument is now simple, and proceeds for only two steps; on the second day both islanders commit suicide.

Now, what did the foreigner tell the islanders that they did not already know? Say that the blue-eyed islanders are $A$ and $B$. Each already knows that there are blue-eyed islanders, so this is not what they have learned from the foreigner. Each knows that there are blue-eyed islanders, but neither one knows that the other knows this. But when $A$ hears the foreigner announce the existence of blue-eyed islanders, he gains new knowledge: he now knows that $B$ knows that there are blue-eyed islanders. This is new; $A$ did not know this before the announcement. The information learned by $B$ is the same, but mutatis mutandis.

Analogously, in the case that there are three blue-eyed islanders, none learns from the foreigner that there are blue-eyed islanders; all three already knew this. And none learns from the foreigner that other islanders knew there were blue-eyed islanders; all three knew this as well. But each of the three does learn something new, namely that all the islanders now know that (all the islanders know that there are blue-eyed islanders). They did not know this before, and this new information makes the difference.

Apply this process 100 times and you will understand what new knowledge was gained by the hundred blue-eyed islanders in the puzzle.

-
Argument 2 claims "if there are $n$ blue eyed islanders and everyone knows 'everyone knows there is a blue eyed islander' then they will commit suicide after $n$ days". Accepting that as given, if there are at least 4 blue eyed islanders, they can all deduce 'everyone knows there is a blue eyed islander' already. This is because each of them knows that anyone who can see at least 2 blue eyed islanders has deduced 'everyone knows there is a blue eyed islander', and if there are 4 with blue eyes then each of them knows that everyone can see at least 2 blue eyed islanders. –  Carl Mummert Nov 16 '12 at 13:35
In other words the arguments 1 and 2 are not in tension. 1 is correct: if there are 4 or more, every one of them already knows 'everyone knows there is someone with blue eyes' so the foreigner gave them no new information. But argument 2 does not argue that the foreigner did give them new information, it just argues about the consequences of them having that information. –  Carl Mummert Nov 16 '12 at 13:41
No. If there are 4 blue-eyed islanders, then: 1. Every islander knows that there are blue-eyed islanders. 2. Every islander knows (1). 3. Every islander knows (2). 4. But no islander knows (3). And the foreigner's statement informs all the islanders of 3. To make this clearer, reconsider the case with 2 blue-eyed islanders and an unspecified number of brown-eyed islanders. Clearly (1) is true, but (2) is not. But after the foreigner's statement, (2) is true. –  MJD Nov 16 '12 at 14:12
I am somewhat confused by your numbers, but I think the issue I am raising is whether "argument 2" assumes that the foreigner has told them more than just (2). Of course it is impossible to tell without actually formalizing argument 2 in some particular logic. As is typical of this sort of problem, the argument is phrased in a somewhat vague way that makes it hard to tell what assumptions are being used (there is not even a precise statement of what claim is being proved in argument 2, much less a precise proof). –  Carl Mummert Nov 16 '12 at 14:27
@Graphth: they might not know what the other ones know. For example, with three people, if Cathy has blue eyes then Alice knows that Bob sees Cathy has blue eyes, so Alice knows "Bob knows someone has blue eyes". But Alice does not know her own eye color, and Bob does not know his own eye color, so Alice does not know whether Bob knows "Cathy knows someone has blue eyes"; the only way Bob would know that Cathy sees blue eyes is if Alice has them, and Alice does not know her own eye color. –  Carl Mummert Nov 16 '12 at 17:20

This isn't a solution to the puzzle, but it's too long to post as a comment. If one reads further in the post (second link), for clarification:

In response to a request for the solution shortly after the puzzle was posted, Terence Tao replied:

I don’t want to spoil the puzzle for others, but the key to resolving the apparent contradiction is to understand the concept of “common knowledge”; see http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29

Added much later, Terence Tao poses this question:

[An interesting moral dilemma: the traveler can save 99 lives after his faux pas, by naming a specific blue-eyed person as the one he referred to, causing that unlucky soul to commit suicide the next day and sparing everyone else. Would it be ethical to do so?]

Now that is truly a dilemma!

Added: See also this alternate version of same problem - and its solution, by Peter Winkler of Dartmouth (dedicated to Martin Gardner). See problem/solution $(10)$.

-
The traveler can say on closer inspection they are more a blue/violet color. The next day 1000 tribesmen show up to kill themselves, which gives them a chance to realize that they can't trust the traveler. Who has ideally left town by then. –  psr Nov 16 '12 at 2:30

Easiest case to show what's wrong with the solution offered here and all other solutions like on wikipedia etc is to consider case of 4 blue eyed people.

Proposition 0: If there are 4 blue eyed people than everyone sees other 3 and also all of them can conclude(even without knowing their own eye color) that all of them know(not a typo) that there are at least 2 blue eyed people on the island. So if blue eyed people are A,B,C & D than A can say that B knows that C knows that D knows that A knows that there are at least 2 blue eyed, B can make similar assumption etc.

This would be enough for a pure mathematical proof, since if all of them know that all of them know that there are at least 2 blue eyed people than visitors anouncement that there is one blue eyed among them does not introduce new knowledge.

Let's find out what's wrong with the proof:

General argument for any kid of proof: If proof/solution assumes something that is impossible or contradicts to initial conditions than every conclusion based on such an assumption is useless.

All solutions I've seen so far include some variations of :

Suggestion A: Suppose/if there was only person (same as suppose n=1)
Suggestion B: Suppose/If there was only one blue eyed person

Clearly if there are 4 blue eyed person we can't suggest that there is only one person on the island so Suggestion A is clearly wrong and all proof based on such a suggestion are wrong. This also invalidates all recursive proofs that assume that n=1 / day one . One can abstract from the concrete example and say suppose n=1/day one, but than you can't imply the knowledge that on day one you knew that there is one blue eyed person.

Now what's wrong with the suggestion B? remember proposition 0. Everybody knows that all of them know that there are at least 2 blue eyed people on the island. But suggestion B says suppose there is only one blue eyed person. This Suggestion is also wrong since we know that there are at least two of them. So, all profs/conclusions based on suggestion B are also wrong.

That's it.

If you find a proof that does not use some variation of A or B than we can reopen this discussion.

-
This is like that one problem where a professor tells his students that he will give a "surprise" exam in the next week. –  Joe Z. Feb 14 '13 at 18:18
The foreigner doesn't introduce the literal information "there is someone with blue eyes here". If the foreigner told only one person that then that person would never kill themselves, for the reason you stated. It has to be made common knowledge. You've only gone up one level in the "knowledge hierarchy" with your four person example, which isn't what the foreigner does. Do they "know that the others know that they know"? How deep can their knowledge of other people's knowledge go? That's the crux of the argument, and you don't seem to address it here. –  Robert Mastragostino Feb 17 '13 at 19:13
In case of four, knowledge goes to all hierarchical levels. I can see 3 blue eyed, I also can see that everybody sees at least 2 ( my eye color does not count). So I can say that all of them know that all of them know(up to any hierarchical level if you wish) that there are at least 2 blue eyed people –  imachabeli Feb 19 '13 at 22:45
With his statement, the foreigner tells them the following: "You will all start reasoning NOW'. This is something new, which they didn't know before. And the key to the "induction argument" is the fact that all can reason in the same time. –  N. S. Dec 11 '13 at 22:30
The flaw to your argument is the following: You can see 3 blue eyed people, you can also see that everyone can see two blue eyed people. But what you cannot know, and that is what the visitor is introducing, is that everyone can reason now that 2 is not possible...... To put it simple, before the visitor came there is no way for you to know that everyone else now knows that you are thinking: "I can see 3 blue eyed, I also can see that everybody sees at least 2 ( my eye color does not count)"... –  N. S. Dec 11 '13 at 22:42

Here's my answer as to why the outsider gives new info. I'm considering the situation of (A)lice, (B)ob and (C)athy as mentioned in a post above, where all 3 have blue eyes. For argument's sake, I'll be Alice.

• I know there are at least two people with blue eyes
• I know Bob and Cathy know at least one person has blue eyes
• Here's the tricky part: What do I know about what Bob knows about Cathy's knowledge?
• As far I know, I may have brown eyes, and Bob may think he has brown eyes. So when Bob looks at Cathy, he may think she sees no one with blue eyes. So from Bob's point of view, Cathy may not know there are blue eyed people.

Simply put, I know there are blue eyed people. I know that Bob and Cathy know. But I don't know that Bob knows that Cathy knows. When the outsider announces it, I now know that everyone knows, and everyone knows that everyone knows.

It's also easier to imagine that everyone assumes they have brown eyes. So when Alice thinks about Bob's thoughts on Cathy's thoughts, everyone down the line assumes they themselves have brown eyes. When Alice thinks of Bob's thoughts, she's assumes he thinks they both have brown eyes, and only Cathy has blue. When Alice thinks of Bob's thoughts on Cathy's thoughts, she imagines Bob will conclude that Cathy will not see blue eyes.

This scales up to four or more, and it's easier (for me) to think of the fourth being 'above' A (Alice), let's say Omega. So Omega must imagine what Alice thinks that Bob is thinking about what Cathy thinks, not just what Cathy herself thinks.

So when Omega imagines Alice's thoughts, he's assuming she thinks they both have brown eyes. When he imagines Alice's thoughts on Bob's thoughts, same thing, everyone assumes they have brown eyes in their own mind. That's why Omega concludes that Alice may imagine Bob could think that Cathy may not know there are blue eyed people.

Very deep and difficult, but the 'everyone assumes they have brown eyes' POV helped me wrap my head around it.

-