Given that there has recently been a lot of discussion on this blog about this logic puzzle, I thought I would make a dedicated post for it (and move all the previous comments to this post). The text here is adapted from an earlier web page of mine from a few years back.

The puzzle has a number of formulations, but I will use this one:

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).

[

Added, Feb 15: 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 pashave on the tribe?

The interesting thing about this puzzle is that there are two quite plausible arguments here, which give opposing conclusions:

[Note: if you have not seen the puzzle before, I recommend thinking about it first before clicking ahead.]

**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 day, each of the blue eyed people then realizes that they themselves must have blue eyes, and will then commit suicide on the day.

Which argument is valid? I won’t spoil it in this main post, but readers are welcome to discuss the solution in the comments. (Again, for those of you who haven’t seen the puzzle before, I recommend thinking about it first before reading the comments below.)

*Added*, Feb 12: It is undoubtedly true that the assumptions of this logic puzzle are highly unrealistic, and defy common sense. This however does not invalidate the above question, which is to resolve the fact that there are two separate and seemingly valid arguments which start with the same hypotheses but yield contradictory conclusions. This fact requires resolution even if the hypotheses are extremely unlikely to be completely satisfied in any reasonable situation; it is only when the hypotheses are *logically impossible* to satisfy completely that there is no need to analyse the situation further.

[*Update*, Feb 10: wording of the puzzle clarified. (My original version, which did not contain the last parenthetical of the first paragraph, can be found on my web page; it had an unexpectedly interesting subtlety in its formulation, but was not the puzzle I had actually intended to write. See also this formulation of the puzzle by xkcd.)]

## 450 comments

30 November, 2010 at 7:01 pm

lenoxussSuppose there are just five people: Alice, Bob, Charlie, Diane, Elaine. It so happens they are

allblue. (-eyed, not sad.) In such a situation, none will commit suicide, because each will think: “Myeyes might be brown, green, or red.”Now, Alice knows that Elaine is blue, and Alice knows that Diane knows that Elaine is blue — but Alice

doesn’tknow if Bob knows if Charlie knows if Diane knows if Elaine knows that there is at least one blue on the island. She really, really doesn’t! Alice would only know thatifshe knew her own eye color (which she can’t), or if she thought that someone else know their own eye color (which she knows they can’t).What the foreigner’s comment does is cut that bridge short. Now it is the case for any person X that she knows that any person Y knows that there is at least one blue, and further for any possible nesting thereof. So the count begins…

Except it still seems weird to me that there would be that wait. Surely everyone already knows that no one will die on day 1 — and therefore the absence of deaths on day 1 is not new information! Right? If someone

didkill themselves, then every islander would correctly think “Wow, he screwed up.” (Which is, of course, impossible for these islanders to do — so would the survivors’ heads explode?) Hmm. I’malllmostgetting how it works…====

Now, I’m not sure if this quite needs to be a stated part of the problem, but perhaps the most counterintuitive thing is that these weirdo Vulcan islanders

doconsider it horribly wrong to discuss eye color, but simultaneously can’t help themselves fromthinkingabout it, even when doing so carries the risk of death. They don’t shy away from it in their minds the way that actual people operating under taboos tend to, especially if the taboo is specifically about knowledge itself.However, the nature of the problem doesn’t require that dying (or just leaving the island) is something an islander wants to avoid — indeed, great pains have to be taken about just how dead-set the islanders are on following the law. They can even have the

incentiveto die/leave, and it still works exactly as well.So a better phrasing might be this: It’s a group of prisoners who, once per day, have the opportunity to guess their eye color (written down to some independent party) or stay quiet. If they get it right, they go free, but if they get it wrong, they are shot. These highly logical prisoners will therefore only guess if they are rigidly certain, and they know that about the other prisoners. For kicks, it’s not until day 7 that someone says “There is at least one blue”, and no one knows of this announcement until then.

Or have I changed the problem?

21 December, 2010 at 12:17 pm

Matt ZellmanIt appears to me that no one has considered the n=4 case separately from the n=3 case, but there is a serious distinction on this level. You can’t just infer that the n=4 case invokes the n=3 case, because there is a major change in what everyone knows at n=4.

When there are 4 blue-eyed islanders, every islander can deduce that every other islander can see at least 2 other blue-eyed islanders. Since those 2 can see each other, the existence of blue-eyed islanders really is common knowledge, as long as there are 4 or more blue-eyed individuals.

No islander will ever assume that another islander thinks that there are fewer than 2 blue-eyed individuals, because they all *know* that everyone else can see at least that many.

22 December, 2010 at 9:04 am

Matt ZellmanNevermind, I get it now.

15 January, 2011 at 5:47 pm

MarcelDr. Tao,

I believe there is a problem with your proof:

“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. \Box \diamond”

The problem is in the reasoning of the blue-eyed people in the inductive step:

“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”

Of course, we have assumed for the inductive step that the claim holds given n-1 blue eyed people. That is, the claim is true for n-1.

However, we have neither shown nor assumed that the blue-eyed islanders /know/ the claim is true for n-1.

In order for an arbitrary blue-eyed islander to reason by contrapositive that, given that no islanders commit suicide on the n-1’th day, therefore there must be more than n-1 blue-eyed islanders, he first must assume that:

“There are exactly n-1 blue-eyed islanders \Rightarrow All blue-eyed islanders commit suicide on the n-1’th day.”

Obviously this statement is true by hypothesis in the inductive step, but the islander must be shown to know the statement is true for the induction to proceed as stated.

Thank you for all your great work,

Marcel

24 February, 2011 at 6:30 am

David VaccaroAs the tribe are logical they will realise straight-away that the stranger’s comment will eventually lead to mass immolation. Could they therefore avoid most of the bloodshed by killing one blue-eyed person at the outset?

The removal of one blue-eyed isalnder avoids the inductive argument- because, for example, if there were just two blue-eyed islanders the second one would not commit suicide because he would have no way of finding out whether the murdered islander was the only blue-eyed person on the island.

The murder of a blue-eyed islander at the start may be slightly morally dubious- but they would have died anyway.

5 April, 2011 at 8:11 pm

Jack VogtI just came across this web site but I have been following the same puzzle on the xkcd site. It’s also in the Wikipedia section ‘Common Knowledge (Logic)’. Both of them have it wrong. The answer is that the blue-eyed stranger told the islanders nothing and nobody is going to die as a consequence of what the stranger said.

I realize this has been covered before but since it’s still a matter of discussion let me offer a slightly different analysis.

First off, it was stated at the beginning that all the islanders are highly logical, which means that anything that can be logically deduced from the available information and observations will be deduced by every islander, and furthermore, all of the islanders know this. Therefore, every islander has long known the following THEORUM:

If there are n>2 blue eyed islanders then every islander knows that every other islander knows (by direct observation) that there are (n-2)>0 blue-eyed islanders.

If there are three or more blue-eyes in a group it is impossible for any one of the group not to see that every other person in the group sees at least one other blue-eye.

Consider a simplified version of the puzzle: only four blue-eyes imaginativly named A, B, C, and D, mixed in with any number of people with eyes that are not blue. The ‘Common Knowledge’ analysis goes something like this: A can see three blue-eyes, so he knows that B knows that there are at least two blue-eyes, so in turn A knows that B knows that C knows that there is at least one blue-eye, and finally A knows that B knows that C knows that D knows there is at least zero blue-eyes. When the blue-eyed stranger spills the beans D (and everyone else, thus making it ‘Common Knowledge’) knows that the possibility for zero blue-eyes is ruled out, and from that C realizes that one blue-eye is ruled out, and then B knows that the two blue-eyes case is ruled out, and then all of them know that there must be four blue-eyes.

The first part of the analysis is not wrong; it is only irrelevant. From the THEORUM, we know that everyone sees at least three blue-eyes. Each of the four knows that n is either three or four, so they each know that the minimum is either one or two.

The second part is nonsense, because it implicitly assumes that because D does not know by one line of reasoning that there is at least one blue-eye, then he cannot know it by any other line of reasoning, and therefore is dependant upon the information from a stranger.

Something that I find strange is that many have noted that the stranger provides no new information to the islanders and yet his zero information message changes everything. Even the Wikipedia article notes this apparent logical incongruity but makes no attempt to resolve it.

Another thing puzzling to me is this: the stranger informs 1000 people that he sees blue eyes, but the iterative ‘solution’ starts out ‘consider the case of n=1’. There is no mention in the puzzle of an island with only one blue-eye or of a stranger ever visiting that island. Then we are supposed to consider the case n=2. Another island with two blue eyes on it? The Wikipedia article then goes on, and concludes that since the logic works for n=1 and n=2, it must work for all n. But the THEORUM shows that something else applies for n>2.

Even if the islanders thought that the stranger had shown up for cases n=1 and n=2, why would they believe that he would have shown up for all cases from 2 through 100, as apparently required by the iterative ‘solution’?

Of course I think my analysis is correct, but not everyone will agree with it. I would appreciate any feedback from any quarter.

6 April, 2011 at 1:15 am

Henry WegenerHello Jack,

I’m pretty sure that your arguments are wrong. And that Prof. Tao’s arguments are right.

How much comments on this page did you read? I recommend to read at least until Prof. Tao’s post on 8 February, 2008 at 3:57 pm.

To give you a better feedback I could but will not repeat ideas that have already been mentioned many times. But here are two things:

1. The solution does not state that the stranger gives no new information. He does.

2. The solution does not state that the cases n=1 and n=2 imply all other cases. It is an inductive argument that considers the cases n=1 and (n-1) ==> n.

I do not claim that you didn’t understand Prof. Tao’s solution. But in your comment I find no single argument against it.

Greetings

6 April, 2011 at 8:15 am

David vaccaroHey Jack-

A good place to start on a problem like this is to look at the simpleset cases.

On an island with two blue eyed people, A and B, although they both already know that there are blue eyed people on the island, before the foreigner speaks A does *not know* that B knows that this is the case (and vice-versa), because A could believe that his eyes were brown. Once the foreigner has spoken, A knows that B would commit suicide if he saw a brown eyed person and when he fails to do so he can deduce that his eyes are blue.

This is very clear- and I suspect that it why you started your induction at n=3 rather than n=2.

What about the case with three blue eyed people A, B and C? Before the foreigner speaks (even though your theorem holds) there are vital pieces of information missing: e.g. A does *not know* that B knows that C knows that there blue eyed islanders, because if A’s eyes were brown, B could think that C saw two brown eyed islanders.

The problem is hard because for large n it is really difficult to get a grip of what information is given by the foreigner (to start with A *does not* know that B knows that C knows that D knows that…..Z knows that there are blue eyed islanders). However, this new piece of information is precisely what allows the induction to kick-off.

Keep thinking about it and keep reading the blog posts (it’s a wonderful moment when it all clicks)- but Prof Tao’s proof is definitely correct.

7 April, 2011 at 9:13 am

Jack VogtYou are right, sort of. It was late and I thought that I had really thought of something and posted before I thought about what I had thought about or what I had thought about what I had thought about, etc, etc, etc.

That said, and realizing that the puzzle is by necessity quite contrived, I am still not happy with it. The form of the puzzle on the xkcd site is a little more precise (and much less bloody) in that it has a guru who shows up and say that she sees a (that is, one) blue-eye. Consider: the proof relies upon a definite starting point, and it needs a sequence of transition points. The usual assumption is that starting point is one blue-eye on day one, and the transition points are the days. But I remember one version of this puzzle in which the sheriff tells the prisoners something about their hats and all the steps in the induction seem to happen instantaneously.

So consider another version, in which there is a High Priest who is not subject to the rules governing ordinary mortals, and one day the HP announces that he is going to ring a gong, and after he rings it any blue-eye on the island who knows the color of his eyes must jump into the volcano. So he rings it once and nothing happens. Some time later he rings it again. This goes on and then one day when he rings the gong all the blue-eyes rush to the volcano. The question is, how many times did he ring the gong? If we assume that all the very, very logical blue-eyes started counting at n=1, as is normal in a mathematical proof we get one answer. But every logical blue-eye knows (and knows that everyone else knows) that there are no fewer than 99 blue-eyes on the island, so why would they not realize that they could just as well start at n=99? The brown-eyes would start at n=100, but that would cause no problems. Would logical people necessarily think that n=1 is more logical than n=99? What if the HP had added a parenthetical remark such as “I know that you are all aware that there are at least forty-three blue-eyes on this island”? Would logical people now think that n=43 is the most logical starting point?

Isn’t it possible that logical people would conclude that there is no logical reason for picking any one starting point over any other? If they do not just happen to choose the same starting point is the puzzle solvable? I haven’t yet thought through this possibility very carefully so I don’t have an answer. Also, I can’t remember reading about this in any of the posts, but somebody must have discussed it.

The main sticking point for me has always been the conviction that telling them that there are blue-eyes on the island when they already knew that, and knew that everyone else knew it as well, is a message devoid of information. Information is a probability thing and it’s not just some boozy babel heard in a bar. The message can be considered more abstractly as ‘there is at least one blue-eye on the island (True/False)’. If it were possible to assign probabilities to True/False then there would be information in the message. But False is not just an event of probability zero, it is not even a possibility. It’s not a point in the sample space, so to speak.

I think I have this figured out. Consider the scene from countless movies and TV cop shows in which somebody prowls through a dark place, flashlight in hand, and calls out, “Is anybody there?” It doesn’t matter if the responce is “Yes’, “Help”, or “Nobody but us chickens”; the message is the message itself and not the content of the message. It seems to me that the content of the message in this puzzle is immaterial and the only purpose of the message is to provide a starting point, as has been noted by many others. Note that in my version of the puzzle the High Priest did not even acknowledge the existance of any blue-eyes.

7 April, 2011 at 9:26 am

FilipeDear Prof. Tao,

If your conclusion, it will mean the suicide of the entire tribe. If all blue-eyed people suicide themselves on the 100th day after the speech, then the rest of the islanders will know they are brown-eyed, so they are forced to commit suicide the day after.

Greetings.

7 April, 2011 at 9:55 am

The blue-eyed islanders puzzle – repost « What’s new[…] April, 2011 in Uncategorized | by Terence Tao [This is a (lightly edited) repost of an old blog post of mine, which had attracted over 400 comments, and as such was becoming difficult to load; I request that […]

7 April, 2011 at 10:14 am

Terence TaoI’m happy to see that even three years after this puzzle was first posted, it still generates lively discussion; it is my favorite logic puzzle, and the moment when one really understands what is going on with it is quite satisfying.

But at 400+ comments, this page is becoming quite difficult to load; so I am closing the comments and ask that participants continue their discussion at the new thread

https://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/

Thanks!

26 January, 2012 at 10:09 pm

The cost of knowledge « What’s new[…] to merely mutually known. (Amusingly, this distinction is also of crucial importance in my favorite logic puzzle, but that’s another story.) One can also see Elsevier’s side of the story in this […]

23 June, 2012 at 2:07 am

The Blue Eyes Problem and Solution « Summation of z over dj's, parameterized by Time[…] problem is this (Source: Terence Tao blog): There is an island upon which a tribe resides. The tribe consists of 1000 people, with various […]

14 October, 2013 at 4:34 am

用眼神杀人——红蓝眼睛问题的胡思乱想 | 蘅芜散人的小站[…] 陶哲轩提出了这么个有趣的问题。关于这个问题的由来和讨论。 […]

17 October, 2013 at 10:25 pm

用眼神杀人2 — 红蓝眼睛问题续 | 蘅芜散人的小站[…] 首先，依旧是关于这个问题的由来和讨论。然后是我之前的一些胡思乱想。 […]

7 February, 2014 at 1:20 am

猜疑链，Mutual knowledge | fubupc's learning records[…] 陶哲轩原题： https://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/ […]

12 February, 2014 at 7:07 pm

Head banging (1) | Ciocolată cu sare[…] E clasica problema, o referinta ar fi asta: https://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/ […]

26 April, 2014 at 11:30 pm

Arcade of Thoughts » Democracy, Right to Reject, and Common Knowledge[…] [link, link]: There is a tribe residing in an island in which the religion dictates that a person should not […]

22 July, 2014 at 8:32 pm

关于「第 N 天有 N 个红眼睛自杀」的数学题 | 暖黑网[…] 补题源：https://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/ […]

26 September, 2014 at 4:13 am

My great WordPress blog – The blue-eyed islanders puzzle[…] you give up (don’t!) or simply want to check your reasoning, read Terry Tao’s entire post and the subsequent comments. And if you still have problems understanding, you’re welcome to drop a line […]

28 October, 2014 at 6:14 pm

Maryborough Brain Teasers And Logical Thinking Style Thinkers | BestBrainTeasers.net[…] The blue-eyed islanders puzzle | What’s new – Feb 05, 2008 · Given that there has recently been a lot of discussion on this blog about this logic puzzle, I thought I would make a dedicated post for it (and move all …… […]

29 October, 2014 at 3:20 am

Gaspe Brain Teasers And Answers Hard Drive | BestBrainTeasers.net[…] The blue-eyed islanders puzzle | What’s new – Feb 05, 2008 · Given that there has recently been a lot of discussion on this blog about this logic puzzle, I thought I would make a dedicated post for it (and move all …… […]

29 October, 2014 at 7:16 am

Blue River Printable Brain Teasers Puzzles With Answers | BestBrainTeasers.net[…] The blue-eyed islanders puzzle | What’s new – Feb 05, 2008 · Given that there has recently been a lot of discussion on this blog about this logic puzzle, I thought I would make a dedicated post for it (and move all …… […]

31 October, 2014 at 5:15 pm

Blaeberry Brain Teasers Puzzles Pdf | BestBrainTeasers.net1 November, 2014 at 1:15 pm

Delta Hidden Meanings Brain Teasers Puzzles Free | BestBrainTeasers.net27 March, 2015 at 12:14 pm

EDITH JUDIT MARILYN | Silver Lining Mama[…] too? Does Terry Tao, who is listed by many as #1 most intelligent person living, get trolled in his Word Press blog attacking his intelligence? He probably does, judging by the extensive rules he wrote on […]

15 April, 2015 at 6:12 pm

It's often the puzzles that baffle that go viral | Em News[…] The paradox of the blue eyed islanders. […]

15 April, 2015 at 9:17 pm

It’s often the puzzles that baffle that go viral — Ebook Teacher - Education[…] The paradox of the blue eyed islanders. […]

18 April, 2015 at 7:15 am

#thatlogicproblem round-up | The Aperiodical[…] boxes. If you really want to blow your brain sockets, try the blue-eyed islanders puzzle. Terry Tao posted it to his blog once and a gargantuan comments thread full of people not getting it […]

18 June, 2015 at 5:54 am

Joker大人 | 倒霉的红眼[…] 1陶哲轩博客中曾引述此题The blue-eyed islanders puzzle https://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/ […]

18 January, 2016 at 1:21 pm

Some maths puzzles that are actually clever | brain -> blueprint -> build[…] https://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/ […]