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 pas have 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 
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.)]
315 comments
Comments feed for this article
4 February, 2008 at 6:23 am
Anonymous
Pro. Tao,
I really can’t figure out the “blue eyed islanders” puzzle, and there is no post option in that web page, so I can only ask you here:
What is the correct answer?
I tent to think the Induction is invalid.
4 February, 2008 at 7:35 am
Terence Tao
Dear Anonymous,
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
5 February, 2008 at 3:36 am
Robinson
The second argument is flawed. The people will never know if there are 101, 100, 99 blue eye people in the tribe, as they wouldn’t know there own eye colour. The person would have to give the number of blue eyed people for the second argument to work, because then the brown eyed people will know they have brown eyes.
5 February, 2008 at 8:29 am
Phillip
Dear Prof. Tao,
I don’t want to spoil the puzzle either. But I think the wikipedia entry misses an important point.
The induction argument is basically right. The blue-eyed islanders will eventually commit suicide. But in my opinion they would commit suicide even if no foreigner visits the island. Proof:
The same is true if the number of blue-eyed islanders is not 100 but any positive integer greater than two. For simplicity asumme that there are exactly three blue-eyed islanders, say A, B and C. (The same argument works for any larger number as well.)
Consider the day of birth (or better the day of religious initiation) of the third blue-eyed person. On that day A, B and C see each other. Person A knows that B knows that there are blue-eyed persons, because A knows that B can see C. The same holds for any permutation of A, B, C. So everybody knows that there are blue-eyed persons.
On the second day nobody commits suicide. Everybody can deduce from this fact that there are at least two blue-eyed islanders: If there was only one blue-eyed islander, (s)he would have committed suicide, because (s)he had encountered to be the only person with blue eyecolor. Furthermore everybody knows that everybody can deduce from this fact that there are at least two blue-eyed persons on the island. The lower bound of two is now “common knowledge”.
On the third day nobody commits suicide. Everybody can deduce from this fact that there are at least three blue-eyed islanders: If there were only two blue-eyed islanders, they would have committed suicide, because they would have known that they are among the two blue-eyed persons. It is now common knowledge that there are at least three islanders with blue eyes.
The islander A now sees only two blue-eyed persons and realizes that (s)he has blue eyes.
On the fourth day A, B and C commit suicide.
Note that the same argument works for any number of blue-eyed persons greater than two. I therefore wonder how the population of blue-eyed persons can grow so high. Everytime there are more than two persons with blue eyes, they shortly thereafter will commit suicide.
The first argument given in your description of the puzzle is therefore also correct, i.e. the stranger’s adress doesn’t change anything because (s)he doesn’t tell anything new.
5 February, 2008 at 9:45 am
John Armstrong
My intuition goes with Philipp. Another way to put it is that both arguments Dr. Tao gives are correct. The visitor has brought no new information, and they would end up killing themselves regardless.
What no solution I’ve seen yet mentions is that the next day, all the other villagers would follow suit, since they would know that anyone with blue eyes would have killed himself the previous day, and so they must have brown eyes.
Actually, the problem might be stated better. Say that there are some with each eye color. Having 0, 1, or 2 blue-eyed villagers seems stable, so those are the only actual possibilities. Now the visitor does bring new information, and changes the game. We now know that there’s at least one blue-eyed villager. If there’s only one, he realizes it since nobody else has blue eyes, and kills himself. If there are two, they’ll realize it soon enough and kill themselves, just as the proposition states.
5 February, 2008 at 9:51 am
Robinson
Oh, yeah now I get it. Everyone would die including the brown eyed people. As after the blue eyed people commit suicide on day 100 the brown eye people will commit suicide on day 101, since they would know they have brown eyes because all the blue eyed people are dead.
5 February, 2008 at 11:25 am
Anonymous
Prof. Tao,
Sorry for having led this web page into the discussion (since it is originally under “career advice”). However, this is what I think:
Mathemacality has a limit as applied to reality. Mathematical induction starts with K=1, but the reality is GIVEN K=100, which does not arrive as a sequence from K=1. So the sequencial reasoning isn’t valid here. The blue-eyed islanders could comprehan their reallity with our induction only when they want to (that is, if they are mathematical souls), but they don’t have too (which does not necessarily violate logic). In fact one could argue that, since induction is not necessary therefore following it is not logical, therefore there will be no effect for the islanders. Or if they are indeed mathematical souls, then I go with Philipp: They will all commit suicide even if the outsider never came. Or K= 100 is an impossible situation to be a reality (so the puzzle contradicts itself).
However, my intuition goes with the limitation of mathematical reasoning. I am reminded another puzzle, though not the same, but also about the mathematical handling of information:
(supposedly a real story, I might not get the time right) During WW2, a city (in Poland?) made an anouncement: A military exercise would be conducted some day in the following week, yet in order to get the residents of the city used to unprepared situations during the war time, the specific day of the exercise would not be given so that it would come as an suprise. A mathematician (name I forgot) immediately reasoned:
The exercise can not take place in Sunday (the last day of the week), since if so, by Saturday night, people will know (therefore not a suprise). But then it can’t be Saturday either since if so by Friday night people will know that it will happen on Saturday since the possibility of Sunday is already ruled out. But then, Friday, Thursday, Wednesday, Tuesday, Monday are not valid days either. Therefore the exercise can never happen!
The exercise still took place on Wednesday, as nobody had induced, therefore still a suprise as promised.
5 February, 2008 at 11:45 am
Anonymous
To my observation, the “foolishness” of mathematical reasoning sets in usually when time dimension is involved, precisely in term of deduction. In the case of the military exercise, the mathematical sequence replaces (improperly) the time order which is a physical reality. In the case of the Blue eyed islanders, it disrecards K is given as 100 as the starting point of reality, and reasons back to K=1, which is only a mathematical reality. Of course this is getting a little philosophical.
5 February, 2008 at 11:56 am
Anonymous
Dear Philip,
In the situation you are considering that is no visitor visits island, if there is only one blue eyed person, how would he know he is blue eyed. Quoting you “If there was only one blue-eyed islander, (s)he would have committed suicide” I think its not true in the scenario you are considering.
I believe rather the visitor is indeed adding some information.
5 February, 2008 at 12:22 pm
Anonymous
Prof. Tao
Thank you for setting up the seperate post.
5 February, 2008 at 12:31 pm
Aaron Bergman
The version I know has only the blue-eyed people killing themselves (why do these puzzles always involve so much death, anyways?). The follow-up question is then to ask what is the new information. It’s easiest to figure out that question by studying the case where only two people have blue eyes.
For the answer, here’s an old thread from rec.puzzles.
5 February, 2008 at 12:40 pm
Isabel
I believe the second argument as a mathematical argument, but somehow I have trouble picturing this actually happening. I mean, come on, exactly one hundred days later a hundred people commit suicide? Nobody mis-counts the number of blue-eyed people? Every single one of the blue-eyed islanders independently thinks of this argument? (Someone it seems strange that the religion in question would permit people to discuss eye-color-related questions in the abstract but not let people talk about their own eye colors.) There are so many things that could go wrong.
And I think that’s why people have trouble with the second argument. It makes sense with, say, two blue-eyed people — then they only have to count one other person each, and keep that information in mind for two days — but probabilistically speaking someone will make an error before the hundredth day, just like books inevitably include errors. The reason the mass suicide seems highly implausible is because we know nobody’s perfect. Perhaps an equivalent problem in which the actors are non-human (I can’t cook one up off the top of my head) would cause less cognitive dissonance.
5 February, 2008 at 1:03 pm
t8m8r
I think the main point of the puzzle was about the common knowledge. Suicide, religion and so on are just wording.
5 February, 2008 at 1:05 pm
avfonarev
Dear Prof. Tao,
I’ve never seen this puzzle before, but the second argument reminds me of the following “problem”:
A number of married couples live in a small village. Every time some husband cheats on his wife, every woman except her finds out about it. If one can deduce that her husband is a cheater, she is allowed to kill him. One day an old lady that never lies comes and tells everyone that there is a least one cheater in the village. What happens next?
5 February, 2008 at 1:16 pm
Maurizio
Philip,
i can’t understand how you proved that A,B and C should suicide.
Consider this: when the 2nd blue eyed is introduced nobody dies. So, when the 3rd blue eyed is introduced, each already-initiated blue-eyed thinks that it is the 2nd that is being introduced, and so he is not surprised if nobody dies. On the other side, from the point of view of the newly introduced guy, nothing changes if he is blue-eyed or brown-eyed, unless someone dies (and this is not happening).
Passing from 2,3 to n,n+1, this should prove by induction that an arbitrary numer of blue eyed people can be introduced and survive.
The funny fact is that in some way the foreigner is “synchronizing” the knowledge about the existence of blue-eyed people.
5 February, 2008 at 1:52 pm
Robert Samal
Dear Prof. Tao,
thank you for posting this nice puzzle.
I have one suggestion, though, to clarify the problem statement
(but perhaps it was left ambiguous on purpose?).
“… one resident can see the eye colors of all other residents”:
this sentence doesn’t seem to tell that everybody really did see everybody
else’s eyes. Perhaps the tribepeople prefer not to look into eyes of too many other
people (to avoid learning about their own eye color :-) ).
Anyway, thanks again.
Robert Samal
5 February, 2008 at 1:53 pm
Anonymous
Dear Prof. Tao,
If the total number of brown and blue eyed color people is known to each individual then they can easily figure out the color of their own eyes.
Thus instead of 100 the answer should be 1000 i.e. all the thousand people try to commit suicide. A brown eye person will wait till 100 days
for all the blue eye people to commit suicide. On 101st day he will think that he is also blue eyed. This applies to everybody.
5 February, 2008 at 1:59 pm
Ryan Reich
Concerning the comment of Anyonymous, at 11:25, 5 Feb 2008: you are not quite appreciating how each islander applies induction in the second proof. I’ll give symbolic names to the groups involved in his reasoning: say the islander in question is named A, and he sees a set S of n - 1 blue-eyed fellows. He reasons that if he himself doesn’t have blue eyes, then S must in fact be the set of all blue-eyed people on the island, and therefore the induction hypothesis applies to THEM: they will all die after n - 1 days of waiting. When this fails to occur, he realizes that he must actually have blue eyes. So although you are correct that the n blue-eyed islanders are not given as a sequence of 1, 2, …, n islanders each independently constituting a sub-puzzle, that is not how n is used in the proof: there, it shows up as “one more than the number of blue-eyed people any blue-eyed person can see”; in other words, the proof implicitly realizes the n islanders as a union of subsets of size n - 1, which are unions of subsets of size n - 2, …. It is not the SET itself which is the termination of a sequence, but its CARDINALITY, and cardinalities are linearly well-ordered and hence amenable to induction.
This technicality showed up in a comment on Timothy Gowers’ blog recently (”A paradox in probability”, comment by JB on 1:04, 4 Feb 2008): slightly reworded, start at time zero and in one hour, put balls 1-10 in a bag. In another half hour, take them out and put in balls 11-20. In another quarter hour, replace those with 21-30, and so on. How many balls are in the bag after two hours have passed? The answer is seemingly both “10″ and “none”, since no particular ball is there, yet at all times preceding, there are ten balls there. The resolution is that the sequence of SETS of balls is not linearly ordered, so that in fact the SET of balls in the bag after two hours is empty (the sense in which we were intuitively viewing the “limit” of the sequence of balls was as the set of all balls which remained for sufficiently large times); however, their CARDINALITIES are ordered (and constant). So if we insist on “abstracting” the contents of the bag away from the particular numbered balls it contains to simply a collection of ten balls, we get a limit; however, it is the limit of a different sequence. A pithy way of saying this is that “the cardinality function is discontinuous”.
For a variety of reasons, this problem is unrealistic; however, it encapsulates the same phenomenon that confounded you with the islanders problem, which is realistic.
5 February, 2008 at 2:20 pm
Alon Amit
This is one of those problems that never fails to produce a lively discussion :-)
A few comments and pointers:
1. A sharp version of this problem can be found in the lovely “7 puzzles you think you must not have heard correctly” by Peter Winkler. In this version the foreigner says something - anything - non-trivial about the number of blue-eyed people. Here’s a link to the doc + solutions:
http://gauss.dartmouth.edu/~pw/solutions.pdf
2. I, too, am unable to follow Philip’s argument (I get stuck at “because (s)he had encountered to be the only person with blue eyecolor”). An island with three people, all blue-eyed, seems fairly stable to me.
3. A related puzzle I like is this one: Alice and Bob each have a number glued to their forehead for the other one to see. The numbers are N and N+1 for some positive integer N and Alice and Bob both know that, but they don’t know what N is and they don’t know which of them has the N and which has the N+1. They are repeatedly interrogated about their state of knowledge - first Alice, then Bob, then Alice again, and so on. For various values of N, what happens?
(for example, if N=1 and if Alice has the 1 and Bob has the 2, Alice would say “I don’t know” since she could either have 1 or 3, but Bob would say “I do know”, following which Alice would say “Now I know, too”. Now if N=2…)
4. Prof. Tao - thanks for a most wonderful blog.
5 February, 2008 at 2:28 pm
Peter
If we’re living in ideal logic-land, then I’m with the “mass suicide” camp — as Aaron says, there is indeed new information. Answering his question a bit more mathematically than the thread he links to does, we can see exactly what that new information is.
Let’s write P_1 for the statement “there is somebody with blue eyes”, P_2 for “everybody knows there’s somebody with blue eyes”, and similarly P_(k+1) for “everybody knows P_k”.
Going back to the island, suppose I’m an islander. If I can’t see anyone with blue eyes, then I’m not sure about P_1. If I can see one person with blue eyes, I know P_1 is true, but I don’t know whether or not he can see one or none, so I don’t know if he knows P_1, so I don’t know about P_2. Carrying on, if I can see n people with blue eyes, I know that P_n is true, but I can’t be sure about P_(n+1), because it depends on my own eye colour. (Formally, we can check this by induction, using the fact that if I can see n blue-eyed people, I know everyone else can see at least n-1.) So at first, I only know finitely many of the statements P_k, limited by how many pairs of blue eyes I can see.
Now, when the visitor speaks up, he says P_0… but since he’s addressing the whole tribe, I also know that everyone else heard, i.e. I know P_1; but since everyone else is logical, I know they’ve also deduced P_1, so now I know P_2… so continuing, I (along with everyone else) can now deduce P_k for /any/ k. (This is one of the weird things about how common knowledge works when everyone’s perfectly logical, and everyone knows that everyone’s logical, and so on…)
So the new information is (well, includes — there may be more) all the P_k’s bigger than I knew before. In the case where there are one or two blue-eyed islanders, it’s very intuitive that this is new information; for bigger k, P_k is a difficult statement to grasp, but the argument still holds.
5 February, 2008 at 2:40 pm
Peter
By the way, Phillip: there’s a hole in your argument, if I’m not mistaken. You write:
—
Consider the day of birth (or better the day of religious initiation) of the third blue-eyed person. On that day A, B and C see each other. Person A knows that B knows that there are blue-eyed persons, because A knows that B can see C. The same holds for any permutation of A, B, C. So everybody knows that there are blue-eyed persons.
On the second day nobody commits suicide. Everybody can deduce from this fact that there are at least two blue-eyed islanders: If there was only one blue-eyed islander, (s)he would have committed suicide, because (s)he had encountered to be the only person with blue eyecolor. Furthermore everybody knows that everybody can deduce from this fact that there are at least two blue-eyed persons on the island. The lower bound of two is now “common knowledge”.
On the third day nobody commits suicide. Everybody can deduce from this fact that there are at least three blue-eyed islanders: If there were only two blue-eyed islanders, they would have committed suicide, because they would have known that they are among the two blue-eyed persons. It is now common knowledge that there are at least three islanders with blue eyes.
—
How does an islander (A, say) know there are at least 3? You say he can argue: if if there were only two, then they would have committed suicide. Why should they have? Well, if there were only two, and they each knew there were at least two, then they would know they’re among them. But if there were only two others, they wouldn’t each know that there were at least two!
You’ve argued why everyone knows that there are at least two, but you worked from the external knowledge that all three of them are blue-eyed. A doesn’t have this knowledge, so can’t go through the same reasoning, so doesn’t deduce on the third day that there are at least three.
5 February, 2008 at 2:45 pm
Anonymous
Part of the issue is the that the problem is very sensitive to rephrasal.
Peter’s argument is a good start. Ideally, the problem should be worded so that P_100 can clearly be deduced.
But you also need something else but similar. The problem says:
“All the tribespeople are highly logical and highly devout, and they all know that each other is also highly logical and highly devout.”
This is insufficient.
If Q_1 = “All the tribespeople are highly logical and highly devout” and Q_(K+1) = “All the tribespeople know Q_K”. You need both P_K and Q_K to prove the Kth step of the induction. So we need to have Q_100 as well. The problem as stated only gives Q_2, which is not powerful enough.
Unrelatedly, when I was an undergraduate, I knew a professor who claimed very adamantly that this problem was “not mathematics.” I never really understood why he cared so much.
5 February, 2008 at 3:16 pm
t8m8r
In Phillip’s argument, everybody knows there is a blue eyed person on the island, and everybody knows everybody knows there is a blue eyed person on the island, and so on; but for any given person Bob, a person Bob knows having blue eyes is never Bob, Bob precisely knows everyone else’s eye color. But the foreigner’s message has a different meaning, it just says somebody has blue eyes, nothing specific. Now for any given Bob, he knows somebody has blue eyes, himself included, and he knows that everybody knows so.
5 February, 2008 at 4:19 pm
Roberta
My english is not good … sorry…
I think the foreigner information is really important. Because we have two different things here: 1) you know the possibility about your eye (it’s blue or not) and 2) you know that everybody knows about blue-eyed. Before the information, you know only 1), but you don’t discuss about eyes with your friends, so you don’t know what they know about eyes. But after the foreigner’s information you know you know that everybody knows.
So I think argument 2 is correct… The tribe consists of 1000 people, and
n=100
1) I am blue-eyed: I can see 99 blue-eyed. So in the 100 day, each blue-eyed person sees 99 blue-eyed and nobody in tribe dies ! So I am blue-eyed and committed suicide.
2) I am not blue-eyed: I can see 100 blue-eyed. I will wait until the 101 day. But in 100 day everybody with blue-eye is dead, if I am a blue-eyed I have to be dead in the 100 day because blue-eyed people saw only 99 blue-eyed and not 100 like me. So, I don’t have blue eye (If I conclude somehow that I am brown-eyed I have to commit suicide)
* no one committed suicide in days < n.
But I’m thinking about that… the foreigner have a wife and he writes in the letter “how unusual it is to see another blue-eyed person like myself in this region of the world and another red-eyed such my wife”.
and the tribe consists of 1100, 100 blue-eyed, 100 red-eyed and 900 brown-eyed
5 February, 2008 at 4:54 pm
t8m8r
Does there any red- eyed person exist? :)
5 February, 2008 at 5:59 pm
christine
terry, i don’t get it. is this supposed to be a fun puzzle? :/
hehe. niki and i watched a movie this weekend and thought of u. guess which one?! :P
5 February, 2008 at 7:02 pm
vlk
I don’t see what the foreigner has to do with anything. Since everybody can see everybody else’s eyes, they should all have an accurate count of the respective populations except for their own. So a blue-eyed person will see that there are 900 browns and 99 blues, and a brown-eyed person will see that there are 899 browns and 100 blues. After 100 days, every blue will realize that none of the other blues have killed themselves, so there must be 100 blues, and so everyone that can see 900 browns will realize that they must be one of the blues, and will therefore kill themselves on day 101. Now, the browns will realize that there are no blues left, because they have all killed themselves, so everyone that is left must be browns, and will kill themselves on day 102.
So the foreigner’s sole function seems to be set up the problem, and perhaps a timer, by having everybody assemble in one place so they can get an accurate count of the populations.
5 February, 2008 at 9:05 pm
t8m8r
No, without the foreigner there would not be a “mass suicide”.
If there is only one blue eyed person then he would not know his eye color and the others would not tell him.
If there are two blue eyed person then each of them knows that the other’s eyes are blue but they cannot be certain that everybody on the island knows there is at least on blue eyed person.
If there are three or more blue eyed person then everybody knows there is at least one blue eyed person on the island, and everybody knows everybody knows and so on. But the induction has to start at n=3 because for the cases n=1 and n=2 are special from this point of view. If n=3 the suicide occurs after 4 days, then the suicide will occur for any n>=3. But for n=3 there will not be any suicide because in order to imply from the fact that there was no suicide for last 3 days that there are 3 blue eyed person on the island, one has to go through n=1 and n=2 cases and we know it does not work for n=1 ad n=2 unless there is a foreigner announcing somebody has blue eyes.
5 February, 2008 at 9:19 pm
richard borcherds
This puzzle occurs in the book “puzzle math” by G. Gamow (as in big bang) and Stern, with an extra twist at the end. In response to concerns about unfaithful wives a sultan announces that anyone may kill his unfaithful wife. (This was in pre PC days.) 40 nights later 40 wives are killed much to the puzzlement of the vizier, who has the solution explained to him by the sultan. It ends by the sultan saying “I am glad that you finally understand the situation. It is nice to have a vizier whose intelligence is so much inferior to that of the average citizen. But what if I tell you that the reported number of unfaithful wives was actually forty-one?”
5 February, 2008 at 9:40 pm
Jian (the first "Anonymous" who started this trouble))
Dear Ryan Reich,
I understood the induction, but I wasn’t sure of its necessity. To reformulate the puzzle to make it more intuitive, the presence of the brown eyeds doesn’t affect the logic, so we can get rid of them:
There are 100 blue eyeds (and only blue eyeds) in the island, one day a vistitor tells them that there exists blue eyed(s) among them. Then all 100 islanders will kill themselves (Or just leave the island in order to make the puzzle less bloody)? No way… Math can be counter-intuitive but irrational!
“There exists blue eyed(s)” is such a fact that each islander can assume it as “common knowledge”, (Can someone give a reason why this can be not a common knowledge given that everyboby sees only blue eyeds in the island?) don’t you think? There must be something went wrong in our reasoning. I tend to think that it is some kind of limitation in mathematics in describing reality (just like in the millitary exercise puzzle (see post of 11:25 am)). I can see the cases of n = 1,2,3… (One can just reason without induction). Perhaps for some strange number (such as strange primes, etc.) the reasoning can no more close, or “common knowledge” (which seems like a very artificial concept too) will be left with some gap. I am unable to pin point it.
5 February, 2008 at 9:49 pm
Marko
I’m not a mathematician but a physicist, so I may be wrong, but I think that mathematical induction can’t be used here. The reason is that you start with case n=1, and then you prove that n follows from n-1. But the case n=1 is impossible in this story, because everyone at the island can see that there is more than one person with blue eyes. To use induction, I think we would have to prove this for some other n, for example n=2, and then show that n follows from n-1. I haven’t thought that much about it, but I think that for n=2 they can’t just figure it out based on the fact that the stranger said that there is at least one person with blue eyes, because everyone on the island sees at least one other person with blue eyes.
5 February, 2008 at 9:59 pm
Jian
Dear Marko,
I am with you that Induction may not be valid here (though perhaps for a different reason). But I also question the legitimacy of “common knowledge”, it just seems too artificial a concept.
5 February, 2008 at 10:11 pm
Jian
Math is dangerous!
5 February, 2008 at 10:34 pm
Jian
because of its foolishness combined with its power!
5 February, 2008 at 10:54 pm
t8m8r
I was just wondering if the islanders know there are only two eye colors among them. If they don’t know then the brown eyed ones will not do suicide after the blue eyed ones did.
5 February, 2008 at 11:00 pm
t8m8r
Dear Jian,
Please do not be too upset. The point is just to illustrate some concept, nobody is trying to make people do suicide.
5 February, 2008 at 11:15 pm
Marko
Dear Jian,
honestly I don’t think that math is foolish and danegerous. t8m8r is right, don’t get too upset :-)
I thought some more about what I said. I think the case n=3 should be proved first and then if we can prove by induction that n follows from n-1 they would all commit suicide. If there were only 2 people with blue eyes then n=1 is still possible, because each of the blue eyes sees only one other and doesn’t know if that’s the only one, and induction is ok. However if n=3 everyone can see at least 2, and I think that they can’t start reasoning from n=1.
5 February, 2008 at 11:26 pm
Jian
Dear t8m8r,
Thanks.
Dear all,
Please do consider the reformulation that there are only blue eyeds in the island (my post of 9:40 pm) (Or show that it is not logically equivelant to the original puzzle). This makes the problem much simpler in showing the ligitimacy of “common knowledge”. When everybody sees only blue eyeds, I just don’t see how “there exists blue eyed(s)” not automatically a “common knoledge” and takes a visitor to create it…
5 February, 2008 at 11:32 pm
Marko
I just looked over some of the posts that I’ve missed, and I saw that t8m8r in his 9:05 pm post has a similar argument to what I said, the difference though is that, if I interpret his post correctly, he thinks that after the foreigner makes the statement the inhabitants will commit suicide, so his statement makes a difference, whereas I think that the foreigner’s statement doesn’t make a difference and the inhabitants won’t commit suicide.
5 February, 2008 at 11:36 pm
t8m8r
I think it is because if you consider someone specific, he/she can really name the persons who have blue eyes in his/her knowledge. He/she does not know about his/her eye color. But when the voyager says someone has blue eyes, there is a possibility that he/she has blue eyes too. It kind of uniformizes the knowledge.
5 February, 2008 at 11:37 pm
t8m8r
Dear Marko,
If the foreigner makes the statement, you can start the induction at n=1.
6 February, 2008 at 1:08 am
Odd Man Out
Argument 2 is invalidated by the fact that there will be some brown-eyed people that will think that he was referring to them (assuming people will assume he was talking to a specific person), and without the ability to verify the information, they’d commit suicide as well; it doesn’t account for the human factor.
The most likely outcome is argument 1 because, as stated above, there is no way to verify who the foreigner was talking to. So, they just go on not knowing anything new.
However, depending on how the tribe views others rights to hold different belief systems, they may “insist” that he commit suicide the next day for speaking about eye colour.
@John Armstrong:
You are incorrect assuming that if one committed suicide that the next day everyone else would. There may have be a different reason why they are killing themselves, such as, making the faux pas on there own earlier or later in the day i.e. there is no way to know if they are killing themselves because of what the foreigner said.
6 February, 2008 at 1:50 am
Marko
Odd Man Out,
the argument doesn’t apply to the brown eyed people, because they see one more blue-eyed person than the blue people, so for example if there are n blue-eyed, the brown eyed will see n but the blue eyed will see n-1. So when no one commits suicide on the n-1 st day all of the n blue eyed people will commit suicide on the nth. From the point of view of the brown-eyed people they see n people committing suicide on the nth day, and they conclude that they don’t have blue eyes. Also, I think that for the problem it’s safe to assume that people only commit suicide because they figure out their eye color, and not for other reason.
I said before that I don’t think that the people will commit suicide, but I’m not so sure anymore. I have to think some more. Interesting puzzle!
6 February, 2008 at 2:37 am
Barks
Argument 1 is wrong since the traveller
adds a crucial bit of information in the case n=1
(for the poor sap n). It is the logical consequences
of this single bit of information that leads to Ragnarök.
6 February, 2008 at 3:47 am
nicolaennio
I do not understand the point of Phillip “Consider the day of birth (or better the day of religious initiation) of the third blue-eyed person. On that day A, B and C see each other. Person A knows that B knows that there are blue-eyed persons, because A knows that B can see C. The same holds for any permutation of A, B, C. So everybody knows that there are blue-eyed persons.”. Because if A see B and C he knows that there are two blue-eyed people, but he cannot know that B and C know the same thing (indeed if he knew it he could magically know its own eye color!). The foreign is used for breaking this chain of disinformation. Interesting concept, though.
6 February, 2008 at 3:57 am
Aus
Well, first of all, I don’t think the tribe can know that there are 100 blue-eyed people and 900 blue-eyed people. If so, everybody should commit suicide long time before, because you can see the rest of people. So, I think the remark will not take any effect.
6 February, 2008 at 3:58 am
Aus
Sorry. 900 “brown-eyed”.
6 February, 2008 at 5:25 am
Arjun Ramakrishnan
Prof Tao,
I guessed the first part, but the second part was quite non-intuitive. On the other hand, a friend of mine found it quite simple
6 February, 2008 at 6:23 am
Aus
Oh, I was silly. Off course they don’t know that there are 100 blue and 900 brown.
Then, both wrong. On the first day nobody dies. On 99th day nobody dies. On 100th day blue-eyed people all dies. On 101th day, brown-eyed people will not commit suicide even though they are not sure of their eye colour.
6 February, 2008 at 6:35 am
Bjoern S.
there at least two simple ways to save the role of the stranger and therefore the puzzle
one:
if you restrict the suicidal-rule to blue-eye-people only
and assume the villagers dont know what blue eyes look like initually
two:
we assume that the normal village life is quite boring, and consist of sleeping and working only
so the day the visiter arrived was the first day they hab a party, and therefore were able to see each other simultainously
6 February, 2008 at 6:56 am
Ken
Bjoern: haha, that is true.
Hey, Aus. You are not quite right. As Bjoern mentioned, they don’t have any intention to kill each other all the time. Even, after the stranger mentioned blue-eyed people, they don’t have to count on everybody. Because sooner or later (100days or 101days later), everyone dies (if all one them started to check calender). It is also interesting to mention that if they counted brown-eyed people instead of blue, they could live longer. As somebody mentioned above, this is the begining of science and the results of it.
6 February, 2008 at 6:56 am
Roberta
Dear t8m8r, we can use the same argument 2 for the red-eyed version. (or not?) =D
I’m going to tell my friends about this puzzle, come on, it’s really fun =P
6 February, 2008 at 7:29 am
Robinson
If everyone leaves the island on the 99th day then everyone would be saved. Theorically they could live in isolation for a day and then join each other for another 99 days. So a population of people like that could survive.
Unless, someone tells the population how many blue eyed people their our or brown eyed people their our they won’t die out.
6 February, 2008 at 7:50 am
Isabel
t8m8r wrote (Feb 5, 1:03 pm), in response to my comment (Feb 5, 12:40 pm)
“I think the main point of the puzzle was about the common knowledge. Suicide, religion and so on are just wording.”
I agree that the main point of the puzzle is about the common knowledge. I was just trying to bring attention to why the result might seem so counterintuitive — basically because we have preconceptions about what actual people (as opposed to imaginary mathematical people) do.
6 February, 2008 at 8:50 am
Jian
Again, we can get rid of the brow eyeds since their presince doesn’t affect the logic. And to Isabel, let’s say, the islanders will leave the island but suicide. So the new puzzle is:
There are 100 blue eyeds and blue eyeds ONLY in the island, if one finds out his/her own eye clolor, he/she leaves the island. One day, a visitor tells that blue eyed(s) exists among them. What will happen?
Let’s stick with this simpler and less violent version unless you don’t think it is logically equivelant to the original.
6 February, 2008 at 8:58 am
Anonymous
A similar puzzle without several agents (as seem to be crucial in the Wikipedia article): On Sunday, a prisoner was told that execution are always at noon and he will be executed on one of the following five days but he will not know the exact day until he is collected by the executioner.
The prisoner deduces that we will not be executed on Friday since he would know this already Thursday at 12:01pm. By the same argument he can then exclude Thursday and eventually all other days of the week.
He was executed on Tuesday and in fact it came as a complete surprise to him.
6 February, 2008 at 9:00 am
Robert
A similar puzzle without several agents (as seem to be crucial in the Wikipedia article): On Sunday, a prisoner was told that executions are always at noon and he will be executed on one of the following five days but he will not know the exact day until he is collected by the executioner.
The prisoner deduces that he will not be executed on Friday since he would know this already Thursday at 12:01pm. By the same argument he can then exclude Thursday and eventually all other days of the week.
He was executed on Tuesday and in fact it came as a complete surprise to him.
Now not anonymous and hopefully with two typos less.
6 February, 2008 at 9:07 am
Jian
Following Prof. Tao’s answer, my speculation is the following:
To make it more intuitive, say n = one million in the new version of the puzzle above. Its seems obvious that the statement that “blue eyed(s) exists” is automatically a “common knowledge”. Yet the induction begins at n = 1 (or 2,3…) , in which case, it does require a visitor to make the anouncement as to create the “common knowledge”. I am unable to locate at what n value “common knowledge” becomes self-edvident. However, I would argue that the induction is invalid since it first reduces n to a value that “common knowledge” is no more a property of the set while with the actual value n = 100, “common knowledge” is a property of the set.
So, intuitively my answer is: at n=100 (or one million), the visitor’s comment has no effect. But then we need to find the special value k such that the visitor has an effect for all n < = k.
6 February, 2008 at 9:17 am
Charlie C
Help me out here. Assume we have a stable, closed system consisting of the islanders. Nothing is changing. They somehow have arrived at a state (assume it doesn’t matter how) in which nobody will ever commit suicide. Then the stranger arrives. He states something that they apparently already know, so it seems that he has done nothing to change the state of the system. So how can anyone then decide to commit suicide?
Put differently, what is the minimal abstract system model describing this situation and what attribute of that minimal system has changed so that the state of the system has been changed, (thus leading to a new action)?
Translate that minimal system description back into the language (people, eye-colors, actions, etc.) compatible with the problem statement so that ordinary folks can understand it. I believe this final step is crucial to achieving a true understanding of this problem. Or is my re-framing of the problem (and/or my assumptions) invalid?
6 February, 2008 at 10:04 am
Scott Randby
There is an unstated assumption that is required for the second argument to work. The assumption is that the islanders already know that there are only two possible eye colors. If the islanders do not have this common knowledge, then only the n=1 step of the induction works. To see this, assume that the islanders do not know that there are only two possible eye colors. Let n be the number of islanders with blue eyes. If n=1, the person with blue eyes will see no others with blue eyes and will thus commit suicide. However, if n>1, then each islander will see at least one other person with blue eyes. A blue-eyed islander who observes n-1 other blue-eyed islanders may not conclude that their eyes are blue after n-1 days because the possibility that their eyes are green has not been ruled out. It would be illogical for the islander to assume that if there are any green-eyed islanders, then there must be more than one.
Thus, we must assume that the islanders know a priori that there are only two possible eye colors in order for the second argument to work. However, even here there is a difficulty and we must make the second assumption that the islanders know that no person has one blue eye and one brown eye. For if the islanders do not know this fact, then the argument given above applies again by substituting “one blue eye and one brown eye” for “green-eyed.”
So, in order for the second argument to work, the islanders must already have the common knowledge that (1) there are only two possible eye colors, and (2) no islander has one blue eye and one brown eye. With these two assumptions, we may now see why the foreigner’s statement is required in order to implement the mass suicide. Before the foreigner’s statement, the proof of the proposition fails when n=1 because the only islander with blue eyes has no way of knowing this fact. Thus, while the induction step of the proof of the proposition always works, the initial step requires the foreigner’s statement. As the islanders are highly logical, they do not accept the proposition until they hear the foreigner’s statement.
Thus, argument 2 is invalid unless the islanders’ society allows some discussion of eye color. It seems unlikely that a society that forbids individual knowledge of ones eye color would permit other discussions of eye color. So, I’m inclined to favor the conclusion of argument 1, that the foreigner’s statement will have no effect on the islanders, but not its justification. I think that the proper justification for argument 1 is that the islanders will not have (1) and (2) as common knowledge and hence cannot provide a proof to the proposition.
6 February, 2008 at 11:04 am
Jian
I think this discussion is getting foolish with details while the mathematics is ignored. There are only two maths involved:
1. Is the induction valid?
2. Is “common knowledge” legitimate here?
The rest is un-important, and the formulation of the original puzzle may not be the best (getting rid of the brown eyeds altogether may be better), but it is clear enough. I hope better mathematicians or Prof. Tao himself will give us the final enlightenment.
6 February, 2008 at 11:13 am
t8m8r
Even if there can be more than two colors, n=2 works because nobody committed suicide on day 1 means that every blue eyed person sees at least one other blue eyed person, and if n=2 every blue eyed person will see one and only one blue eyed person, and every other colored person will see 2 blue eyed person. So blue eyed people can determine themselves easily.
As for the other amusing variants of the puzzle, I think the foreigner should choose one blue eyed person and announce that he is blue eyed in front of all the islanders. Then that man will commit suicide but the other blue eyed islanders will be saved.
http://www.math.ucla.edu/~tao/blue_variant.html
6 February, 2008 at 12:09 pm
t8m8r
Dear Jian,
How do you know everyone commented here is “worse mathematicians”?
6 February, 2008 at 12:28 pm
PhilGibbs
I have been trying to think of ways to avoid objections such as you need to state in the puzzle that “everybody knows that everyboday knows that everybody knows that everybody is logical”, etc. and that “everybody believes the foreigner and everybody knows that everybody believes the foreigner etc.
Perhaps it would be sufficient to say something like this…
… By the end of his stay on the Island everybody had come to trust everything the foreigner said which was fair enough because in fact he did always tell the truth. Then he made a speech saying “I am happy to see that everybody is here to hear me today, and that you have all come to trust everything I say, and that you are all totally logical, and that you have all carefully observed the colour of everybody elses eyes. How unusual it is to see another blue-eyed person like myself in this region of the world.”
Then we would know that everybody knew that everybody knew that everybody was logical etc. Or at least we would know that everybody believed that everybody believed etc. I think belief is sufficient to make the blue-eyes commit suicide on the hundredth day :-)
Am I making any sense?
6 February, 2008 at 12:53 pm
t8m8r