[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 people wishing to comment on that puzzle use this fresh post instead. -T]
This is one of my favorite logic puzzles, because of the presence of two highly plausible, but contradictory, solutions to the puzzle. Resolving this apparent contradiction requires very clear thinking about the nature of knowledge; but I won’t spoil the resolution here, and will simply describe the logic puzzle and its two putative solutions. (Readers, though, are welcome to discuss solutions in the comments.)
– The logic puzzle –
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).
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?
Note 1: 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.
Note 2: Bear in mind that this is a logic puzzle, rather than a description of a real-world scenario. The puzzle is not to determine whether the scenario is plausible (indeed, it is extremely implausible) or whether one can find a legalistic loophole in the wording of the scenario that allows for some sort of degenerate solution; instead, the puzzle is to determine (holding to the spirit of the puzzle, and not just to the letter) which of the solutions given below (if any) are correct, and if one solution is valid, to correctly explain why the other solution is invalid. (One could also resolve the logic puzzle by showing that the assumptions of the puzzle are logically inconsistent or not well-defined. However, merely demonstrating that the assumptions of the puzzle are highly unlikely, as opposed to logically impossible to satisfy, is not sufficient to resolve the puzzle.)
Note 3: An essentially equivalent version of the logic puzzle is also given at the xkcd web site. Many other versions of this puzzle can be found in many places; I myself heard of the puzzle as a child, though I don’t recall the precise source.
Below the fold are the two putative solutions to the logic puzzle. If you have not seen the puzzle before, I recommend you try to solve it first before reading either solution.
– Solution 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).
– Solution 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 
As the above two solutions give contradictory conclusions, at most one of them is correct. Which one (if any) is the correct solution, and what is the precise reason that the other solution is invalid?
229 comments
Comments feed for this article
7 April, 2011 at 10:08 am
Xamuel
Another variation of this is the Muddy Children Puzzle, which Fagin, Halpern, Moses and Vardi chose for the introduction or first chapter (can’t remember which) of their book “Reasoning About Knowledge”.
You forgot to mention one thing: you seem to be implicitly assuming the islanders aren’t deaf… oh, and they all know that they’re all not deaf, and so on… or at the very least, that the deaf ones can read lips…
7 April, 2011 at 10:23 am
Terence Tao
Yes, this is the type of “legalistic loophole” I mention in Note 2. With these sorts of logic puzzles, there is always the implied assumption of “idealised conditions” (no deafness, colour-blindness, or other physical disabilities, no pirates to come and randomly abduct half the population on Day 17, no unexpected breakdown of causality or other laws of physics, and so forth). It is a trivial matter to “break” the logic puzzle using non-idealised conditions, but this is not the most interesting aspect to the puzzle.
7 April, 2011 at 10:50 am
Nicole Krieger
Wouldn’t the brown-eyed people then kill themselves, too, once they saw that all the blue-eyed people were dead? Wouldn’t they also know that all the blue-eyed people would kill themselves, and so once they were gone wouldn’t they figure out they had brown eyes?
7 April, 2011 at 11:02 am
Amic
No, because each one could consider to be the only one to have green eyes for example.
7 April, 2011 at 11:05 am
Nicole Krieger
It’s not a boolean?
4 May, 2011 at 10:25 pm
Anonymous
If it were boolean, then there would be no need of a foreigner, they would all commit suicide on their own.
7 April, 2011 at 11:06 am
Greg
There is nothing that says there are necessarily only two eye colors. Therefore, none of the brown-eyed people would necessarily know that they didn’t have, say, green eyes.
7 April, 2011 at 11:12 am
bretbenesh
Nicole: the brown-eyed people would definitely commit suicide if they knew that there were only two possible eye-colors: blue and brown (effectively, “blue” and “not blue”). However, each of the brown-eyed people would think: “All of the blue-eyed people just killed themselves; all of the remaining people have brown eyes, but it is possible that I have brown eyes OR green eyes (but definitely not blue eyes). ” EVERY brown-eyed person will think this, so none of them will commit suicide since they still have at least two possibilities for their eye color.
7 April, 2011 at 11:14 am
bretbenesh
Sorry for the redundancy—Greg’s and Amic’s answers did not show up until I posted.
7 April, 2011 at 11:19 am
Nicole Krieger
Or hazel or violet or whatever.
7 April, 2011 at 11:42 am
Nick
You’re correct: the brown eyed individuals would, in fact, also kill themselves at a later date. After all the blue-eyed individuals had killed them selves on day 100 (when the traveler makes his comment on day 0), there would be left exactly 900 brown-eyed people. The same exact logic that applied to the blue-eyed people now applies to the brown-eyed people. Any brown-eyed individual, looking around, would see 899 brown-eyed people. When these people didn’t commit suicide on day 899, he would have to conclude that he also had brown eyes. Therefore, the remaining population would commit suicide on day 900. The brown eyed individuals do not need to assume that there are only two eye colors for this to occur. Indeed, each population of individuals with a unique eye color will kill themselves off working from smaller populations (rarest eye color) up through larger populations (more common eye colors) for any number of colors. And again, as others have pointed out, this gradual genocide would happen without any interference from the traveler (i.e. if he had never shown up). We simply take this as a convenient date to start thinking about this thought experiment. This is the correct manner through which the two different scenarios should be reconciled.
8 April, 2011 at 8:53 am
mixedmath
There is an error in this argument when you imply that there is no need for there to be only two eye colors. Suppose for ease that there are 3 people on the island: one has blue eyes, one has brown, and one green. Then at first, none knows their own eye color. But as soon as the unfortunately honest traveler says there is a blue-eyed man, the blue-eyed man will kill himself.
Yet now the brown and green eyed men will still have no idea what their eye colors are. The brown-eyed man sees the other green, but does not know whether there are brown-eyed people on the island (or any other color, for that matter). Similarly, the green-eyed man does not know if there are any green-eyed men on the island. If the traveler were to come back and say, I see green eyes, then that color would also eventually kill itself. Finally, I note that this generalizes to larger numbers without error.
7 April, 2011 at 11:00 am
Nicole Krieger
… and why would the brown-eyed people not also be thinking the same thing the blue-eyed ones were, and kill themselves by accident thinking they were the other blue-eyed person? Wouldn’t they be subject to the same train of thought?
7 April, 2011 at 11:08 am
Anonymous
No, because each non-blue-eyed person counts the full set of blue-eyed people, while each blue-eyed counts one less.
7 April, 2011 at 11:13 am
Nicole Krieger
So the blue eyed people are killing themselves a day earlier than the brown-eyed person would have, that makes sense.
7 April, 2011 at 11:06 am
X9
For a better example use this explanation; in a prison a crazy ruler has set up a riddle- he has trapped all prisoners (all of them smart logicians) in boxes. The boxes are located in a circle. Each box is soundproof. From a window in the box each prisoner can see the color of all boxes but not of his own box. There is no way of communication between boxes as the windows are constructed in such a way that you can see out but not in. There is a one-way speaker system in all boxes. In every cell an explanation is given; guess or deduct the correct color of your own for freedom or the wrong color for extermination. Also the rules of the game are explained on a wall poster in each cell. One day a new box is added and the information is given over the speaker system that the arriver can see another blue box (like himself) etc. In such a way the puzzle can be constructed in a way that is both correct to normal life and understandable in real-life logic. There also must be a way for the prisoners to know if other prisoners have made a logic assumption.
The answer will depend a bit on how the puzzle is constructed.
7 April, 2011 at 11:26 am
X9
To better understand; reduce the number of prisoners to 10 (this will not effect the outcome). As easily seen, if the puzzle is corrected in a certain way, the individual prisoner will know his color by the last day (given knowledge they all think the same way and to the rules of logic deduction).
You can also reduce the number of prisoners to 5 or 3. Remember to include the option of any color. The color of the speaker/guru (if used) will not be relevant if the wording is not ‘same color as my own’. In such a way the outcome of puzzle will depend on how it is constructed (it can be constructed in a solvable way an also to be unsolvable only by a slight variation in word use). Good luck.
7 April, 2011 at 11:14 am
Greg
It might be worth pointing out that the announcement, in the n=2 case, does add new information (I am ignoring the n=1 case since it seems to have some special structure).
When n=2, each blue-eyed person knows that there is at least 1 other, but they do not know whether the other knows that there is at least 1 other. The announcement, being public knowledge, then ensures that it is commonly known that there is at least one person with blue eyes. That is, the announcement does add new information when n=2, contrary to the first proposed solution.
How this scales to larger n is still unclear to me, however.
7 April, 2011 at 11:19 am
DT
For n = 3, the third guy will think that the other two will figure it out in 2 days and then kill themselves, and this is exactly what the other two will think. But then after two days when they find out that the other two have not killed themselves, they’ll figure out that there has to be a third person with blue eyes, and voila! It scales exactly this way for all higher n.
7 April, 2011 at 11:27 am
Greg
While I trust the induction, it is still slightly questionable to me. In the n > 2 cases, the announcement adds no new information it would seem. Everyone sees that there is someone with blue eyes, and everyone sees that everyone sees that there is someone with blue eyes, etc. So the information that was new in n=2 is no longer new in any n > 2. Would this mean that any situation where n > 2 is inherently unstable (and should have already collapsed)?
7 April, 2011 at 11:31 am
DT
True!
7 April, 2011 at 11:53 am
Greg
Given my correction to myself, I now don’t think that the situation is inherently unstable, but that there is new information provided by the announcement that was not previously present. Thus, the inductive proof is the correct solution.
7 April, 2011 at 11:37 am
Greg
Ah, I found a problem with what I wrote. If n=3, it is indeed the case that everyone sees that there is a blue-eyed person, and everyone sees that everyone sees that there is a blue-eyed person, but this does not entail that everyone knows that everyone sees that everyone sees a blue-eyed person.
For, each of the blue-eyed people is left with two hypotheticals: “If I have blue eyes, then everyone knows that everyone sees that everyone sees a blue-eyed person”, but also “If I have non-blue eyes, then I don’t know that everyone knows that everyone sees a blue-eyed person” (this second one is due to the fact that one of the two visible blue-eyed people would see only one other blue-eyed person and things would be back in the n=2 case).
7 April, 2011 at 12:20 pm
DT
True, again! So the traveller does act as a trigger.
7 April, 2011 at 4:17 pm
Lukasz
When considering what everyone thinks as a whole it’s a little confusing for me, I prefer to see it from recursive point of view of just one of them, even though it amounts to the same thing.
If n=2, person 2 is looking at person 1 and thinking (a) “If I’m not blue, then person 1 will kill himself today, otherwise I’m blue and we’ll both kill ourselves tomorrow”.
If n=3, person 3 is looking at person 2 and thinking (b) “If I’m not blue, then person 2 is thinking (a) and they will die tomorrow. If I am blue then person 2 is thinking (b) and we’ll all have to kill ourselves in two days”.
If n=4, person 4 is looking at person 3 and thinking (c) “If I’m not blue, then person 3 is thinking (b) and they will die in two days. If I am blue then Person 3 is thinking (c) and we’ll all have to kill ourselves in three days”.
Of course for n=3, not just person 3 is thinking (c) but all people 1 to 3, but we only need to consider 1 of them. Same idea for n=3.
… and death by induction it shall be.
7 April, 2011 at 11:16 am
DT
No. After n days, since all the blue-eyed people would have killed themselves, the brown eyes people will know that *all* the blue-eyed people are dead (since they all know that the blue-eyed people were highly logical, and wouldn’t kill themselves unless they were absolutely sure of their eye colours.)
7 April, 2011 at 11:21 am
DT
This one was for Nicole.
7 April, 2011 at 11:20 am
Anonymous
The first solution is correct. The foreigner never says how many people he saw with blue eyes, and none of the islanders are aware of the statistic of how many people have blue eyes. So they would not know n people should have blue eyes, and would not necessarily deduce their eye color when they count n-1 blue eyes.
7 April, 2011 at 11:26 am
DT
In my opinion, the second one is correct. They won’t do anything instantaneously after the announcement. But, from the point of view of a blue-eyed person (say), it’ll be clear that 99 days are enough for the other 99 blue-eyed people (that he can see) to figure out their own eye-colors. After 99 days, when he sees all of 99 blue-eyed people still alive, he’ll figure out that he has blue eyes too.
This is assuming, of course, that they still remember the announcement after 99 days. (Note 2.)
8 April, 2011 at 7:37 am
DLS
If n=2, the statement “Everybody knows that someone has blue eyes” is initially true. If n=3, the statement “Everybody knows that everybody knows that someone has blue eyes” is true (but this is not true if n=2). More generally, the statement “(everybody knows that)^k someone has blue eyes” is true for k=n-1 and not for k=n. However, after the public announcement, the statement is true for all n. This is essentially equivalent to the induction but captures exactly the knowledge that is conveyed by the speech.
10 April, 2011 at 7:41 am
Nicole Krieger
Exactly, so the moment they began existing would be the start of the process, well before the visitor shows up.
7 February, 2012 at 10:12 am
Lenoxus
It can’t, because prior to the input of outside information, there is no reason whatsoever for a lone blue-eyed person to kill himself. Once the visitor speaks, there is such a reason, and the process starts.
30 June, 2011 at 5:45 pm
hugo
This is the subject that we should be talking about, because after all it is the interesting part
7 April, 2011 at 11:21 am
Nicole Krieger
I’ve got to say, I’m not sure I would describe people who killed themselves when they know their eye color as “highly logical”!
This is a very tragic puzzle…
7 April, 2011 at 11:29 am
DT
It’s a sacred ritual for the tribes people. For many of the atheists, the belief in God is absolutely absurd, irrational and illogical, yet Albert Einstein was a firm theist. Humans are fascinating creatures.
This makes me sound like ET, not DT. :P
7 April, 2011 at 11:48 pm
Anonymous
No he wasn’t. He believed in Spinozas god at most, a god who wound up the universe at the beginning of time and then let it run, not any kind of personal god, the kind most atheists would call silly. Even Dawkins has grudgingly admitted a case can be made for Einsteins and Spinozas god.
9 April, 2011 at 2:07 am
DT
Hehe. Yeah, I know now. What I posted was because of some stupid thing a youtube video had led me to believe. I am reading “The World As I See It” by Einstein, and what you say is indeed correct.
7 April, 2011 at 5:26 pm
Stas
It’s better to replace people with robots/cyborgs/androids who are programmed to be behave as described.
7 April, 2011 at 11:31 am
Ravi Kunjwal
I don’t think any logical conclusion in the nature of solution 2 follows: solution 2 assumes a knowledge of n, the number of blue-eyed folks in the tribe. any individual in the tribe knows (or can, in principle, know):
1) there are 1000 people in the tribe, including him,
2) if this individual is blue-eyed he knows that of the other 999 folks
- 99 are blue-eyed and 900 are brown-eyed,
and if he is brown-eyed, he knows that
- 100 are blue-eyed and 899 are brown-eyed
3) Of course, this individual doesn’t know his own eye-colour.
4) So when the foreigner makes a reference to “another blue-eyed person”, it could mean any of the other 99 or 100 folks.
5) But then each individual in the tribe reasons in exactly this fashion. Not one of them has any a priori information about his own eye-colour.
Life will go on as usual – the foreigner hasn’t really told them anything new. Each one of them already knows that there is at least one “another blue-eyed person”.
The induction that solution 2 proposes assumes a priori knowledge of the number of blue-eyed guys. Of course, if there were only one blue-eyed guy, he would have to commit suicide, since he knows there is no other blue-eyed guy in the tribe. If there are at least 2 blue-eyed guys, neither of them would have to commit suicide after two days. Each of them only knows that there is at least one blue-eyed guy and at most two, but there is no way to decide what the total number of blue-eyed guys is. Similarly if there are n blue-eyed guys, each of them knows that there are at least n-1 blue-eyed guys and at most n, but there is no way to decide which, unlike when n=1, where it is clearly established that the blue-eyed guy is blue-eyed because no one else is. The argument by induction is fallacious.
7 April, 2011 at 11:34 am
DT
Read Greg’s reply above. He raises an excellent point. The situation seems like it’s always unstable. So if the other had not been trying to figure out their eye colours before the announcement, life will go on as usual. Otherwise, they would have killed each other a long time ago.
7 April, 2011 at 11:32 am
Nicole Krieger
Wait a second, back up. The whole n=1 situation never occurs to begin with, because everyone already knows for a fact that n is either 99 or 100. So no one is sitting around thinking “What if it is just me and some other person”. So the induction falls apart because we know that situation is impossible from the start.
7 April, 2011 at 11:37 am
DT
I think the induction is alright. n = 1 is just a case to begin with, but we see that even for higher n, it would stand.
n = 1 – Easy
n = 2 – B1 thinks B2 will kill himself tonight, and B2 will think the same thing about B1. When the next day they see each other again, they’ll figure out that n has to be greater than 1. But everyone else they see is brown-eyed! So they kill themselves.
Similarly for higher n.
7 April, 2011 at 10:18 pm
Nicole Krieger
But we know that the n=1 case doesn’t exist to begin with. Everyone knows there are at least 98 other people with blue eyes. So n=1 through 97 are impossible, and you can’t base anything on it to begin with.
This is causing quite a debate in our household now, with my husband being in favor of the tragedy.
What would really be evil is if some guy came to the village and said, “How nice to see another grey-eyed person”.
8 April, 2011 at 9:02 am
mixedmath
I was thinking of this possibility myself! Then everyone dies. The power of a (grey) lie.
7 April, 2011 at 11:34 am
Nicole Krieger
Oh, I see Ravi just came to the same conclusion.
7 April, 2011 at 11:46 am
X9
Ok, here’s the correct (or best) version;
In a room there are 10 Fields Medal winners. All are fully functioning and none has caught Alzheimer’s yet. They all were hats of different colors but can not tell the color of their own hat. Communication leads to disqualification in the contest and there is a prize of 1million$ for first correct answer (no, Grigory Perelman is not competing). Every two minutes a bell rings that indicates possibility for an answer. At first no one makes an attempt of answering but then Randall Munroe shows up (as surprise guest) wearing a green hat stating- ‘one of your hats is blue’ etc.
Here comes the questions; for what distribution of hat colors will the problem be solved (and in what time)? And for what distributions will it not be solved? Again good luck.
7 April, 2011 at 12:05 pm
Filipe
Dear 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 1:00 pm
Ankur
Let BEP = blue-eyed person. My conclusion is that solution 2 is flawed.
The mere number of BEPs in the system does not determine whether they commit suicide or not on a given day. This also depends on what their knowledge is on the particular day. Your proposition in solution 2 therefore needs to be more explicit, e.g., as follows.
If there are n BEPs who know, on day n that there are n BEPs, they commit suicide on day n.
Now let us go through your proof. Case trivial for n=1. Assume it is true for n-1 and consider n. A BEP x knows that there are at least n-1 BEPs. x also knows that another BEP (y) knows that there are at least n-2 BEPs – x can be sure of only those BEPs that both him and y can see. So x conjectures “if there are at least n-1 BEPs and on day n-1, all know that there are n-1 BEPs, they would commit suicide.” After n-1 days. no one commits suicide. At this stage all that x can conclude is that *either* the another BEP y does not know that there are n-1 BEPs *or* that there are indeed n BEPs in the system. Your proof skips the former case. I don’t see how x can conclude that y does know that there are n-1 BEPs in the system.
You are implicitly assuming that because a BEP x knows that there are at least n-1 BEPs in the system, that all other BEPs also know that there are n-1 BEPs in the system. This “symmetry” argument is valid for an external observer, not for the BEP x.
7 April, 2011 at 1:20 pm
Greg
But doesn’t BEP y know, being the logical BEP that s/he is, that since no one killed themselves after n-2 days, that there must be at least n-1 BEPs?
7 April, 2011 at 1:43 pm
Ankur
Let us see what information BEP x has about BEP y’s knowledge. BEP x knows that BEP y knows there are at least n-2 BEPs in the system. Now if these n-2 did not commit suicide, then BEP x knows that BEP y knows that either these n-2 BEPs do not know that there there are n-2 BEPs or (BEP x knows that BEP y knows) that there are indeed n-1 BEPs.
Again we run into the same problem.
7 April, 2011 at 1:49 pm
Ankur
Greg, see Prof Tao’s latest buzz.
8 April, 2011 at 8:52 am
Ankur
I take this back. I have not used the foreigner’s intervention. The above argument can be extended further to eventually come to a stage where no BEP can be sure that everyone knows that there is at least one BEP.
Austin’s comment here: http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/#comment-51447
shows that the foreigner’s comment supplies every BEP with this information. Thus the induction goes through.
7 April, 2011 at 1:20 pm
DT
After the announcement, for:
n = 1
Trivial
n = 2
– B1 and B2 both know that N(BEP)>= 1
7 April, 2011 at 1:24 pm
DT
- If the equality was to hold, that is, if there was only one BEP, B1 or B2 would know. But after one day when they are both alive, they figure that there has to be one more.
– Since they can see that everyone else has brown eyes, it’s easy to figure out that it is them
n = 3
– From B3′s point of view, if n = 2, then B1 and B2 would be dead by day 3
– Since they are not, there has to be one more BEP, and since he can see that everyone else is Brown, he figures out that it is him.
n = 4
– From B4′s point of view, if n = 3,……
This can be extended for any n, I guess. So the induction seems to be correct.
7 April, 2011 at 10:21 pm
Nicole Krieger
Except they aren’t all neatly numbered BEP 1 through 100. There is no one in the tribe who will think, “Hey, there’s only one person I can see with blue eyes so if he doesn’t kill himself, I’d better,” because they can ALL see 99 blue eyes, and they know that those people all see at least 98 people.
So if we arbitrarily assign one guy number 2, he can see that BEP1 has blue eyes, but he also sees BEP3, BEP4, BEP5 through BEP 99 all have blue eyes, too. And he knows number one can see those guys.
7 April, 2011 at 1:46 pm
Ankur
But Bi does not know that Bj knows that N(BEP) >=1. Bi only knows that Bj knows that N(BEP) >=0.
7 April, 2011 at 3:32 pm
Hao
(I’m slowly coming around to the second solution)
But to answer your (implied) question: “But Bi does not know that Bj knows that N(BEP) >=1. Bi only knows that Bj knows that N(BEP) >=0.”
That is precisely the point. The information given by the foreigner now informs Bi that Bj knows that N(BEP) >= 1.
8 April, 2011 at 8:47 am
Ankur
Thanks. That’s right.
7 April, 2011 at 1:40 pm
Literalman
Consider two slightly different propositions:
P1. 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. (This is the original proposition).
P2. Suppose that the tribe had n blue-eyed people for some positive integer n. Then no longer than n days after the traveller’s address, all n blue-eyed people will have committed suicide.
Isn’t the supplied proof a proof of P2 rather than P1?
7 April, 2011 at 1:48 pm
Terence Tao
Yes, this is a good point! It is in fact a moderately challenging exercise to show that, assuming a “blank slate” initial state in which the islanders initially know nothing about eye colour beyond what they can see from direct observation (and making the idealised assumption that there are no other causes of death or incapacitation among the islanders), that one can strengthen the proof of P2 to a proof of P1. (The key here is to introduce the concept of a possible world from modal logic; basically, if one can imagine a self-consistent world in which X is false but which is compatible with all current knowledge about the world, then one cannot know for certain that X is true.)
[This illustrates the more general principle, by the way, that lower bounds are often substantially harder to establish than upper bounds, when it comes to estimating the time at which a certain piece of knowledge becomes available.]
10 April, 2011 at 6:33 am
Literalman
Sometimes, though, it’s the upper bounds that are difficult. For instance, it would be mass murder if you were to have been the visitor to the island and said: “if RH is true, then I see at least one BEP”. But what would the moral standing for you to say: “if P=NP, then I see at least one BEP”. Of course, that would be far reckless than “if P!=NP, then I see at least one BEP” :-)
10 April, 2011 at 8:39 am
Literalman
Oops…meant to write that it would be more reckless to say “if P!=NP, then I see at least one BEP”!
15 April, 2011 at 3:44 pm
Quoting a comment from 2010 clarifying the P1 vs P2 question
[from 24 June 2010 of the old thread. Reposting because the link-to-comment URL provided by WordPress doesn't actually point to that comment and it would be difficult to locate the content otherwise.]
“The induction argument gives an upper bound for the number of days by which those with blue eyes can determine their eye color. However, it does not explicitly rule out the possibility of more efficient reasoning that reaches the same conclusion on an earlier day.
Formalizing the argument in (e.g.) modal logic would bound the reasoning power of the islanders and thus permit solid conclusions about what deductions CANNOT happen within N days, for each N. But this would require a completeness proof, i.e., a clear and convincing argument that whatever logical formalism is used correctly captures all possible “information” and “conclusions” available to the logicians on the island.
Possibly Aumann’s approach is clearly general enough to encompass this, but again, it may contain hidden assumptions as to what the islanders can and cannot reason about.
To see the difficulty, think about what if the visitor had made a higher-order statement such as “in the first draft of my speech, there were comments that, had I made them, would have certainly caused suicides within 100 days; but luckily, I noticed this in time to strike the comments from the speech I am now making!”. One needs a way of capturing not only the logic that the islanders can perform in a given logical system but a way of seeing that the system analyzed is as strong as possible. ”
[the proof of completeness would be closely related to the "possible world" semantics that Terry mentioned. I don't know how it would work for higher order modal logics or if these are in fact complete. Aumann refers to Robert Aumann's paper on "agreeing to disagree" where he establishes a semantics for reasoning about common knowledge.]
7 April, 2011 at 2:01 pm
Hao
I will reword the proposition slightly: “Suppose that the tribe has EXACTLY n blue-eyed people for some positive integer n. Then n days after the traveller’s address, all n blue-eyed people commit suicide.”
The proposition is true for n = 1 (base case).
For induction, we need to show that proposition being true for (n=i) implies the proposition being true for (n=i+1). However, if the proposition is true for (n=i), it cannot be true for (n=i+1), because the tribe has a constant number of blue-eyed people.
The alternative form of the proposition without “exactly” (Suppose that the tribe has at least n blue-eyed people for some positive integer n. Then n days after the traveller’s address, all n blue-eyed people commit suicide.) fails because it isn’t true for n=1.
7 April, 2011 at 2:10 pm
Austin
Here is the precise reason Solution 1 is wrong.
The foreigner’s faux pas DOES tell each tribesman something he did not know: namely, that everybody knows that everybody knows that everybody knows that (…) that everybody knows that someone has blue eyes.
That statement should include 99 repetitions of the phrase “that everybody knows”.
7 April, 2011 at 2:12 pm
Austin
(In fact, the foreigner doesn’t just make this statement known to everyone — he makes it true!)
7 April, 2011 at 2:40 pm
Austin
No, I take my second comment back (I stand by the first).
7 April, 2011 at 3:20 pm
Manuel
That’s exact.
7 April, 2011 at 4:31 pm
Brian
99 instances (98 repetitions), yes?
8 April, 2011 at 8:55 am
Ankur
Shouldn’t it be infinitely many repetitions? The repetitions count the “levels of knowing”, in other words, knowing an increasing hierarchy of things. I don’t think the number of repetitions should depend on the number of BEP.
13 May, 2011 at 12:58 pm
Anonymous
The number of levels of knowing does depend on the number of BEPs. Consider n=1: brown eyed person B knows that there exists a blue eyed person (person A), but he does not know if everyone knows it: in fact, the blue eyed person does not know, but if B were blue eyed, then A would know that there existed a blue eyed person. Now n=2: BrEP1 knows that there is a BEP, and knows that everyone knows, but cannot deduce whether everyone knows that everyone knows that everyone knows, since he does not know his own eye color.
7 April, 2011 at 2:45 pm
Dr. Sextistics
This sounds a lot like Curry’s Paradox.
7 April, 2011 at 4:31 pm
rebelJinnee
Question: have the islanders been co-existing more than 100 days before the stranger’s arrival on the island?
=========================
Additional information for solution 2:
— from a brown-eyed person’s perspective —
How does a brown-eyed person reason when n is 2?
S/he sees that there are n blue-eyed persons and reasons as follows
“If I am brown-eyed, then there are n blue-eyed people on this island, and so they will all commit suicide n days after the traveler’s address; if no such suicides take place on the nth day, then I must be blue-eyed (n + 1 blue-eyed persons) and must therefore commit suicide on the n+1th day”
Or more succintly, reasoned a brown-eyed person,
“I know I am blue-eyed if no suicides take place on the nth day”
— from a blue-eyed person’s perspective —
A blue-eyed person will arrive at the conclusion that h/er eye color is blue when no suicides take place on the n-1th day.
example: let n = 2 and b1 & b2 be the 2 blue-eyed persons.
b1 sees b2′s blue eyes and reasons: “b2 didn’t commit suicide after 1 day because b2 saw a blue-eyed person and that blue-eyed person must be me (b1) since I can see everyone’s eye color is brown except for b2′s” (if b2 didn’t see another blue-eyed person, b2 would have committed suicide
on n-1th day after the foreigner’s revelation)..
7 April, 2011 at 4:44 pm
rebelJinnee
Another way of looking at solution 2:
———————— from an islander’s perspective ————————
Let I be one of the 1000 islanders (not the foreigner).
If I sees m blue-eyed persons, I will wait until the mth day to see if suicides
take place: if they do, I lives; otherwise, I commits suicide on the m+1th day.
7 April, 2011 at 5:25 pm
DSchwab
Terry,
Isn’t it possible for the islanders to avoid the outcome of solution 2 by simply agreeing not to commit suicide for the subsequent 1000 days? (Or any number > 100, but every islander knows the total population, so that’s a natural choice.) This way they erase the trigger, there is no information gained when there are no suicides on day 99, and nobody learns their eye color. (Presumably they had to do this following the invention of their religion or they’d have had the same issue and would be dead already.) I suppose you could argue that this is “talking about” the eye color issue, but perhaps a logical actor with a desire to live would develop this strategy independently and assume that all others have as well. Also, note that this only works if there is more than one blue eyed person.
17 June, 2011 at 5:05 am
Marcelo Cantos
That’s against their religion.
7 April, 2011 at 6:01 pm
keith
I feel the validity of the proposition, during the process of induction, has not been proved right yet. Therefore people there could not know this proposition itself, which means they could not know “and so they will all commit suicide n-1 days after the traveler’s address”.
7 April, 2011 at 6:12 pm
Josh Brown Kramer
There is a very general version of this puzzle in “Mathematical Mind Benders” by Peter Winkler. There are only two eye colors, and the visitor can say ANYTHING nontrivial about the number of blue eyes, TRUE or FALSE, and everyone still ends up dead.
7 April, 2011 at 9:16 pm
Deniz
On the 100th day, if blue-eyed people fail to commit suicide, the next day, all brown-eyed people will commit suicide, thinking they’re blue eyed.
7 April, 2011 at 9:21 pm
Peli Grietzer
Unless I’m confused, I think the following demonstrates the significance of the foreigner’s announcement:
In a simplified case with three blue eyed islanders (let’s call them B1, B2, B3), prior to the foreigner’s anouncement B1 believe that if B1 does not have blue eyes then there are only two blue eyed islanders, one of whom is B2 who (in that scenario) believes that if B2 does not have blue eyes then there is only one blue eyed islander, B3, who (in that scenario) believes that if B3 does not have blue eyes then there are *no* blue eyed islanders. Thus, B1 believes that if B1 does not have blue eyes, then B2 believes that if B2 does not have blue eyes then B3 will commit suicide *upon learning from the foreigner that there is at least one blue eyed islander*. Now, on the morning of the second day after the announcement B1 can reason: if B1 does not have blue eyes and B3 did not commit suicide on the first day, then B2 now learns that B3 knows of a blue eyed islander that’s not B3 and (in that scenario) B2 will conclude that B2 has blue eyes and commit suicide at noon. When noon of the second day comes and B2 does not commit suicide, B1 learns that B1 has blue eyes. B1 then commits suicide. (The same applies to B2 and B3.)
8 April, 2011 at 1:49 am
Stijn
The fact that the visitor discusses the topic introduces a starting point, where everyone will reflect on the problem at the same time. This starts the induction process. Broaching the topic was taboo; the visitor changes this and by doing so synchronises the population.
8 April, 2011 at 3:13 am
Bryce
Putting in the perspective of what an islander knows helps show the induction for me:
If I am an islander and I see n blue eyed people there are two cases:
I am also blue eyed, therefore the n blue eyed people I see also see n blue eyed people.
I am not blue eyed, therefore the n blue eyed people I see only see n-1 blue eyed people.
Expanding on the “I am not blue eyed” case:
The n blue eyed people see n-1 blue eyed people, so they know that there is either n blue eyed people, or there is n-1 blue eyed people who see n-2 blue eyed people.
So, this means this is a proof by contradiction with induction, which is why I’ve had so much trouble making intuitive sense of it, even though I completely believe the induction.
8 April, 2011 at 3:45 am
Ravi Kunjwal
Ok, I retract my earlier comment. Solution 2 works. If, say, N=2, then each blue-eyed guy waits for one day, secure in the knowledge that there is at least one other blue-eyed guy who must kill himself if he is the only one blue-eyed, because he knows the fact that there is at least one blue-eyed guy in the tribe. But the other guy doesn’t. The only reason the other blue-eyed guy won’t kill himself, the first guy reasons, is because he knows at least one other guy who has blue eyes. Now all the other tribesmen have brown eyes, the other guy has blue eyes, so he himself must be blue-eyed to explain why the other blue-eyed guy did not kill himself. The other blue-eyed guy reasons exactly like this. Both of them kill themselves on the 2nd day.
The fact that everyone knows that everyone else knows there is at least one blue-eyed guy (“common knowledge”) is the key to see why the argument by induction works. At first glance, it wasn’t clear to me why it worked. After reading the wiki article on “common knowledge” it became clear that I was ignoring the fact that the blue-eyed guys – being logical – would reason why the other blue-eyed guys did not commit suicide, taking into account the fact that they share “common knowledge” – that everyone knows that there is at least one other blue-eyed guy.
8 April, 2011 at 9:01 am
Ankur
Yes indeed. See my comment to my comment here: http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/#comment-51484
8 April, 2011 at 6:53 am
Akashnil Dutta
Solution 2 is correct.
Proof:
Whatever be the thought process of each person, his actions is defined by an algorithm f of the following form:
f:O->A where O is the set of all observations till some day and A is the set of actions, {commit suicide today, don’t}. A sample element of O would be “The address by the foreigner was made 3 days ago, and I see no suicides till now, I have always seen the following eye colors, 100 blue, 899 brown” etc.
Now each person, being completely logical, will make the following analysis:
Since everyone is completely logical, everyone follows a logical algorithm. Let the set of all logical algorithms be F*
any F in F* should have the following property P:
For all x in O, F(x)=suicide iff the following statement is true: “If everyone follows some algorithm in F* (not necessarily same), there is a unique eye color possible for the person committing suicide (or not) for which x is a consistent observation”.
Now, consider the first day. It is clear that F(x)=suicide iff x does not include a blue.
Inductively, if x is a second-day observation, F(x) can also be completely determined for all possible second-day observations and so forth. Hence indeed F is unique, and F* has only one element.
Now, everyone being completely logical will conclude that there exists this unique algorithm satisfying property P and act according to it.
At first glance, it may appear that the algorithm given is solution 1 (never commit suicide in any cases), also satisfies P. But, on closer look, it is not a complete algorithm, it does not say what should be the action corresponding to “no blue eyes seen on day of address by foreigner”. Nor can it be extended to include trivial cases of n=1 to satisfy P completely, because there exist an unique F satisfying P, as proved earlier.
8 April, 2011 at 7:16 am
n00b
Solution 2 looks ok, but I am not able to understand how the foreigner’s comment can act as trigger?
8 April, 2011 at 8:55 am
Nicole Krieger
Wouldn’t they have all committed suicide before the guy even shows up?
The guy plants the idea “Everyone else knows there is a blue eyed person, and they know that everybody else knows that, too”, but isn’t the idea already in everyone’s head before he even shows up?
8 April, 2011 at 9:12 am
Ankur
No. No BEP knows that every BEP knows that there is at least one BEP. The foreigner’s comment provides this information. See Austin’s comment and my comments aboves.
9 April, 2011 at 7:43 am
Nicole Krieger
Yes they do, because they see that Alice sees at least 98 BEPS, Bob sees at least 98 BEPS, Carol sees at least 98 BEPS, Dan sees at least 98 BEPS… they know that every blue eyed person knows that there are at least 98 BEPS… not just 1!
9 April, 2011 at 9:22 am
Ankur
But they don’t know that Alice knows that Bob sees 98 BEPs.
17 April, 2011 at 4:42 am
Joseph
yes they do. Or rather they know that Alice knows that Bob sees at least 97 BEP, that is to say they (lets call them Sharon) know that Alice does not know her own eye color but that she can see some number of BEP’s greater than 1 and that the forigner could have been talking about any one of those persons. ALL the islanders already know that there are at least 99 and no more than 100 BEP’s on the island, the forigner does not add any new information by stating that there is at lesat one. No one seems to address this issue directly in these comments, they just jump on the induction train, but that is the whole problem, the islanders already know that there ISN’T some n of BEP’s where n is an integer, there is some n where n is either 99 or 100, and you cant get there from here.
8 April, 2011 at 9:02 am
Nicole Krieger
Though I’m still optimistic… I mean, say I’m the 100th person. I assume I’m brown eyed, look around and think, “Alice thinks there are only 98 people, and that Bob thinks there are only 97 people and that Bob thinks Carol thinks there are only 96 people. But I know that Bob doesn’t think there are only 97 people, because I can see that Alice has blue eyes, so I know he thinks that there are 98 people with blue eyes, and that Carol also thinks that, so there for NO ONE thinks there are only 2 people, thus I have no idea what color my eyes are”.
Hopefully the visitor is a missionary who has come to convert them to some religion not involving ritual suicide. Though of course the idea that knowledge=death is hardly exclusive to the suicidal eye color tribe.
Also, I think we can eliminate other eye colors as a possibility, because in a tribe of 1000 they must be so inbred that any other recessive eyecolors would have shown up a bit more often.
8 April, 2011 at 10:35 am
Anonymous
“It is probably the n=3 case (three blue-eyed people) which causes the first major conceptual difficulty, in which common knowledge separates from both first-order and second-order knowledge. As pointed out above, in this case the three blue-eyed people all know that there is at least one blue-eyed person, and they know that everyone else knows this also… but they don’t know that everyone else knows that everyone else knows this, until the foreigner speaks. The remarkable thing about the puzzle, to me, is how such a subtle and seemingly academic change in the knowledge environment eventually propagates to have a concrete and dramatic effect.” By Tao, Feb 8,2008.
Why “they don’t know that everyone else knows that everyone else knows this”?
8 April, 2011 at 10:50 am
Literalman
Re: Why “they don’t know that everyone else knows that everyone else knows this”?
Answer: they don’t know that everyone else knows … that everyone else knows until he speaks because it’s not true until he speaks.
9 April, 2011 at 7:40 am
Nicole Krieger
It is true, they can see 99 blue eyed folks and they know that everyone else sees at least 98 blue-eyed folks and that the other people all know that the other people can see more than 1 blue-eyed person. The thought is already in their mind.
8 April, 2011 at 2:23 pm
mixedmath
Consider the logic necessary for 3 blue-eyed people: one blue might suppose that he does not have blue eyes (I will refer to this as the exterior supposition). Then he might look at a second blue guy, and think – what if he supposes that he does not have blue eyes (the interior supposition)? Then the second blue guy might, in this hypothetical (recall that this is all the first guy’s thought process), ask about the 3rd blue guy – the 3rd guy would be the only one with blue eyes. So on the second day, when the 2nd guy sees the 3rd alive, his thought process would lead to a contradiction, so now he knows that he has blue eyes. On the third day, the first guy’s thought process lead to a contradiction, and so he knows that he has blue eyes.
This is symmetric, and so all three blues arrive at the same conclusion and are dead by the 4th day. So it is necessary that ‘they know that everyone else knows that everyone else knows’ that someone has blue eyes. Otherwise, there is nothing wrong with that last person (in the hypothetical) to assume he actually has brown eyes too.
8 April, 2011 at 11:21 am
none
You mean I can show an islander some source code and ask whether the program halts, and if the answer is “yes” they can tell me that right away, but if it’s “no” then they might have to say “I don’t know”? Of course that’s illogical all by itself, for well-known reasons ;-).
8 April, 2011 at 12:36 pm
Anonymous
The problem here occurs in the form “If X, then Y”.
If Y is an unprovable statement, there is no statement X in that system such that X is equivalent to the implication (X → Y).
8 April, 2011 at 2:55 pm
Blue Eyes and Brown Eyes « mixedmath
[...] bring it up now because it has raised a lot of ruckus at Terry Tao’s blog. It doesn’t seem so peculiar to me, but the literally hundreds of comments at Terry’s [...]
9 April, 2011 at 2:29 am
Geoff Robinson
I didn’t read all of the above, just a few. Apologies to anyone who already
said what I said. Isn’t the answer that nothng would happen in that scenario.
The fault seems to be in the induction hypothesis. If there
were 3 islanders to start with, there are two potential scenarios.
Two or three of them have blue eyes, in which case the outsider tells none
of them anything they didn’t know before-they all knew there
was at least one blue-eyed islander.
Or only one of them has blue eyes. In that case, the outsider has told
the person with blue eyes something he didn’t know before, but has
not told the other two anything new. In this (catastrophic) scenario,
the blue eyed person will commit suicide. As to what happens
the following day, I’m not sure the problem is so well-defined.
If they all know that there are only two possible colours,
then the other two should commit suicide (at least if their
brains are wired the same way as mine)- they should be
able to figure out that if only one person has disappeared,
the rest of them have non-blue eyes. So if they know there
is only one other colour available, they can figure out their
own eye colour, and then must kill themselves.
But as the problem is stated, it is not clear to me that they have
any reason to know there is only one colour than blue
available. A given islander might have green eyes for all he knows.
So, back to the original question. Nothing happens. The reuslt generalizes:
if there are n islanders, and only one is blue eyed, he will kill himself.
If there is more than one blue eyed islander, no one will
kill themselves. The start of the “induction” is atypical and misleading, and
this is why the second argument is fallacious.
9 April, 2011 at 3:45 am
boobs
The starting point is impossible. The scenario of solution 2 would have been played out already (when the law was first declared), killing everyone. Since the starting point is false, you can assign any truth value to situation 1 and 2.
9 April, 2011 at 8:11 am
Geoff Robinson
I don’t follow what you mean. Just because the law
is declared, that didn’t tell anybody for sure what colour their
own eyes were. Only when extra information comes from
an outsider is there the possibility that anyone knows
for sure what colour their own eyes are. And then
a person can only know for sure that (s)he has blue eyes
if there is no-one else visible to them who has blue eyes,
and the outsider has told them that there is someone
somewhere with blue eyes.
9 April, 2011 at 11:02 am
Geoff Robinson
In my original post, I should have said “nothing happens which was
not going to happen anyway”, and left everything else out.
The blue-eyed islanders will all eventually commit suicide, but not necessarily on day 100 after the foreigner’s announcement.
But maybe the problem is slightly ill-posed.
The islanders need to have a common starting point from
which they start counting. Once they have that, they will all
commit suicide, given that composition of the tribe.
It may be the intention of the poser of the question to mean
that the foreigner has now given them a point from
which to start counting in common which they did not have
before, in which case the foreigner becomes an agent of the
collective suicide. But if, like “boobs”, one inteprets the passing of the
law as a common point from which to start counting,
then one knows that 99 or less days have passed since
that time, or else there would be no blue-eyed islanders
left at that point in any case. But then the pronouncement
by the foreigner has made no difference to what would
happen. Maybe this is why the problem is slighly thorny.
If the foreigner has given anything to the islanders they
didn’t have before, it is a common frame of reference to
start counting. Once they have that, then they are doomed.
But is it really clear that they couldn’t have had a common point
from which to start counting before the foregner arrived?
9 April, 2011 at 1:11 pm
mixedmath
Even if there were only two people on the island, both with blue eyes, the additional information from the traveller is necessary for them to kill themselves.
Otherwise, at every point they look around and wonder – hmm, I wonder what eye color I have? They have no certainty of any fact to what they think others think they know.
9 April, 2011 at 2:14 pm
Geoff Robinson
I see what you are saying, and you may (finally) have straightened me out about this. Given the information from the outsider, Person 2 thinks:”If my eyes are not blue, then Person 1 must kill his/her self. But person 1 did not kill his/her self on day 1, therefore my eyes must also be blue.”
So, if there is only one blue eyed person on the island at the beginning,
that person gets new information from the foreigner, which
they must act on. But the fact that no-one acts on day 1 tells
everybody that there are at least two blue eyed people.
But then if there are exactly two blue eyed people, they must
both act on day 2, as they both initially know there are
either one or two blue-eyed people, and after day one, they know
it must be two , etc. So the induction argument is correct after all.
I hope this is the end of it for me.
9 April, 2011 at 2:42 pm
mixedmath
@Geoff Robinson 9 April 2011 at 2:14
Exactly right!
-David Lowry
9 April, 2011 at 5:35 am
Rob Blake
Assume that each islander realizes the trap the foreigner has placed them in. Assume further that at least one of them is altruistic enough to value the life of his tribe more than himself. He goes to the village center at high noon to commit suicide despite not knowing his eye color. The other tribesman cannot perfectly know why the martyr has committed suicide. Perhaps he knows his eye color, perhaps he does not. Does this break the induction?
If more than two people decide to adopt this martyr strategy, only the first to arrive at the town’s center need go through with the ritual. The second can simply watch, secretly relieved that they will be able to live another day.
9 April, 2011 at 1:02 pm
Sper
@ Rob Blake: Your comment seems to disregard the second note.
9 April, 2011 at 11:09 pm
Fun with common knowledge « The Leisure of the Theory Class
[...] another game theory puzzle, one that is always fun to come across, especially on Terence Tao’s blog. In the version I know the islanders are less devoted to their religion and more jealous of their [...]
10 April, 2011 at 11:57 am
MCF
Online LaTeX Equation Editor:
http://www.codecogs.com/latex/eqneditor.php
10 April, 2011 at 1:01 pm
Jason T. Miller
The second solution seems mostly correct, at least “in the spirit of things.”
The first solution, on the other hand, is a complete non-starter, because the proposition “the traveller’s comments do not tell the tribe anything that they do not already know” does not follow _at all_ from the fact that “everyone in the tribe can already see that there are several blue-eyed people in their tribe.”
First, if the “the tribe” were a hive mind, they’d all have offed themselves at the first opportunity upon accepting their hokey religion. So we instead consider
Proposition A: “For all tribespeople P, there does not exist a fact F such that (a) P does not know the truth value of F before the traveller begins his comments, and (b) P knows the truth value of F immediately after the same.”
This certainly lacks the “intuitive appeal” of the original formulation, but it seems like a “safer” expression of the idea that P “learns something” from the traveller’s speech. Note also that, by “knows,” I mean “could potentially infer from known data.” The circularity in this statement is quite intentional — the puzzle should clearly not be approached as an epistemology exam, the point is that tribespeople, religious as they may be, do not, by hypothesis, “believe” things. Instead, they are in possession of a certain collection of “true facts” at any given time, and any claims as to their actions must follow deductively from these “facts” and “the rules.”
Suppose, then, that proposition A is true, let P be a tribesperson, and assume no facts exist satisfying both (a) and (b) for P. First, this means P is indubitably prescient, at least with respect to the traveller’s comments, otherwise he’ll necessarily learn _something_, at the very least that (a) and (b) hold for no facts other than the fact that (a) and (b) hold for no other facts. If this sounds confusing, it should, but it seems to follow quite directly from any reasonable interpretation of “high logicality.”
In other words, anything P knows immediately afterwards, he knew beforehand, so he cannot _possibly_ learn anything between “immediately before” and “immediately after.” Modulo formalization, this seems to be the only way to exclude various sorts of “higher-order knowledge” without forbidding the very sorts of conclusions we _must_ allow tribespeople to draw from traveller’s comments for a sensible, nontrivial interpretation of the puzzle.
Since this must be true of all tribespeople, the traveller’s actual comments seem to be largely superfluous. But this is not the case, whence _indubitable_ prescience: everyone must, in fact, know that what they know is/was/will be the case, i.e., that they will learn nothing, including that they have learned nothing, that they know they cannot possibly learn anything.
And so on. Yet somehow, solution 1 obtains this from the fact that “everyone in the tribe can already see that there are several blue-eyed people in their tribe.” Yet I can only think of a one-word “proof”: obvious.
11 April, 2011 at 1:36 am
Geoff Robinson
While I understand the logical structure, and apparent inevitability,
of solution two, I have some issues with the language of the problem.
The second solution effectively credits all the islanders with the
ability to extrapolate back to a scenario when one islander would
have had no choice, and then reconstruct the logically inevitable consequences of that initial lack of choice. I suppose my question is : “is it entirely clear from the pharasing of the problem that this the only logical choice available to them? Do they have to extrapolate back all the way to a time when there is no choice?”
I would find the following tightening of the first solution
a little more difficult to refute: “Nothing happens. Each islander is logical
enough to realise that their own eye colour might be unique on the island,
and, as things stand at that time, the traveller has given none of them any reason to change that belief”. One can dress up the language further by saying that each islander thinks :”It is indeed fortunate that that traveller did not have the same colour eyes as me, or I would have had no choice but to kill myself. As it stands, I don’t need to do anything, and my 999 logically
minded friends will see that for themselves too”. One could say that some of the islanders are opting to do nothing on the basis of a false premise, but
they don’t know for sure that it’s false, and no one has given them any reason to revise that premise.
Try this with 6 islanders, three brown eyed, and three blue eyed,
at the time of the time of the traveller’s arrival. Each one thinks
“My eye colour could be unique here for all I know, and as far as
anyone else knows, their eye colour could be unique on the island too.
I happen to know that they are all mistaken in that belief, but they
do not know that, and nothing the traveller says has corrected their
belief.” Where then is the need to start extrapolating backwards?
Each islander knows only that if their eye-colour is unique among
islanders, it is neither blue nor brown, because each can see at
least two blue eyed people and at least two brown-eyed people.
11 April, 2011 at 2:17 am
Matthew
It is a brilliant puzzle and solution;
i’m not trying to disprove the puzzle, because in good faith it holds; but, I would like to point out something obvious anyway; it’s an island, so they are next to the ocean and water is reflective
also, one cannot live without water
/that is all\
11 April, 2011 at 3:47 am
Matthew
http://en.wikipedia.org/wiki/Common_knowledge_(logic)#Example
11 April, 2011 at 4:28 am
Matthew
http://boards.4chan.org/sci/res/2868576#2869058
“Anyway, the reason they kill themselves despite having already known at least one other blue-eyed person exists there is because the mentioning of their eye colour itself is the issue. Regarding the group as a whole, he has declared the existence of a blue eyed person, something that has never actually happened before in their tribe. It is forbidden to mention and therefore all of the blue-eyed tribespeople are condemned at once.”
a nice moralistic summation, logic aside.
also, remind me not to join that religion (I’ll be the visitor if I must)
too much thinking all around; sleeping time
11 April, 2011 at 4:32 pm
Pete
There are two relevant things (knowledge) that result from the outsider’s statement:
1) the color blue is special in the islanders’ thoughts
2) the islanders all start considering it at the same time.
Thing 2 is the indirect and hard to spot thing. (Stijn mentioned it above.) It effectively synchronizes the islanders’ thoughts. The structure of the problem suggests that one label the days with the inductive index n, and the outsider’s faux pas forces every islander to count n=1 on the same day.
Thing 1 is necessary as well, otherwise the islanders wouldn’t know to which eye color they should relate the counter n. But once the outsider says “blue”, all islanders know there are either 99, 100, or 101 blue-eyed islanders.
Having both things, the islanders can relate the passage of n suicide-free days to the number of blue-eyed islanders, and the proof by induction applies.
Had the synchronization not occurred, then no knowledge could be gained from the passage of days. This would be the case for an outsider simply saying the same thing but only to individuals and on different days. This would also describe the state of the tribe before the faux pas.
Had the eye color not been mentioned, the islanders wouldn’t know which color to count, and there would be nothing to which the passage of days would relate. It’s contrived, but imagine some sort of mass amnesia affecting all islanders. If they all regain their cultural memories on the same day, and they know it, then their counters would synchronize. But there is no danger, because there is no color for them to count.
13 April, 2011 at 12:06 am
Pseudonym
The knowledge which is imparted by the foreigner’s statement is subtle, but important. What the islanders don’t know prior to the statement is what the other islanders do and don’t know about each others’ knowledge.
Everyone on the island knows that there is at least one person with blue eyes. Everyone on the island knows that everyone knows that there is at least one person with blue eyes. Everyone on the island knows that everyone knows that everyone knows that there is at least one person with blue eyes…
…and so on, but only up to a point. Everyone knows up to 99 levels of knowledge about knowledge, but no further. By telling everyone that there is at least one blue eyed person on the island, this pushes the bound of knowledge about knowledge as far as you need to go, because everyone heard that statement, and everyone knows that everyone heard that statement, and so on.
13 April, 2011 at 12:54 am
Geoff Robinson
I find this puzzle really uncomfortable. I think I now realise why at a personal level, which may not apply for others: for me, I think it is that the
problem highlights the difference between “reasonable” behaviour,
and “strictly logical” behaviour, and the sometimes blurred boundaries
between them in “normal” experience (ignoring the question of whether
committing suicide for those reasons is reasonable).
The following verbalization enabled me to reconcile some of the issues for myself. Assuming that the island was in equilibrium beforehand, the traveller’s announcement has made a difference, but it can be seen as a negative one. Before the announcement, they are logically entitled to be certain that no other islander knows their own eye colour. After the announcement, they are not. Once the
equilibrium is broken, there is only one way for it to be restored:
each blue eyed-islander must commit suicide, and then the
population that remains will be back in equilibrium ( but with one
less eye-colour).
Continuing this perspective, each islander might as well regard
the blue-eyed population (s)he can see as a single organism
(which is, I suppose, what the second solution effectively does).
I also found it helpful to think in terms of minutes, rather than days
(though I know it makes no logical difference). Suppose that
the rule is that each islander must commit public suicide within
one minute of discovering their own eye colour, and suppose further
that each islander has an alarm clock (better be digital!).
Each islander can then think: ” I can treat the blue-eyed population
I see as a single entity- I just need to recalibrate what I mean by
a minute. I see n blue eyed people, so I can treat n “old” minutes
as one “new” minute. Then I will effectively be in the situation of
deciding whether there are one or two blue-eyed islanders.
I’ll set my alarm one “new” minute ahead. If the blue-eyed population
I see has not disappeared when the alarm goes off, then I’m
in the “two blue eyed islander situation”, and must commit suicide myself.”
(If the islander can see no blue-eyed population to start with,
they must commit suicide anyway, given the announcement).
14 April, 2011 at 5:46 am
Geoff Robinson
I really hope that this is my last comment on this problem. I am sure
that I am not alone in that hope. One flippant
remark is that to find the purely logical solution to the question, it
helps to “become part of the problem, not part of the solution”
(where have I heard that before?). Imagine that through some quirk of
fate you have forgotten your own eye colour, and been sent to the island
to recuperate. Then credit the other islanders with being able to reason
the same way you can.
Another (perhaps obvious to many) comment is that, once one moves away from the “idealized” problem, there is a quantitative element to the distinction between what is reasonable and what is logical. Everyone would ( I think) agree that if there was only one blue-eyed islander, then it would be both unreasonable and illogical for that islander not to act on the information
imparted by the traveller. However, suppose that, instead of an island,
you translate the problem to a city of 300000 inhabitants, of whom
100000 are blue-eyed. It might be illogical for all the islanders to
ignore the traveller’s announcement, but it would be entirely unreasonable
for any of them to bother to start counting days (assuming they had
anything like a normal human lifespan) , since in any case any one of them would die before they could ascertain their own eye colour
(I know this contravenes note two, and I know that if you start to go down this route, you have to start modelling for the fact that some of the population will die of natural causes in the meantime, etc, which would
probably become intractibly difficult. However, it does illustrate a point).
14 April, 2011 at 9:45 am
Ilkhom
Agree. This is becoming a question of policy – do they really want to know something, if they are going to die after learning it?
14 April, 2011 at 1:02 pm
mixedmath
Going down this line of thinking ruins the logical appeal of the puzzle. It seems to give people enough trouble without layering additional levels of difficulty on top of the problem.
David
15 April, 2011 at 3:25 am
Geoff Robinson
If you were responding to my comment you are certainly right. I do
understand that one is looking at a totally different problem, but I was
trying to reconcile the (for me) counterintuitive nature of the logical answer
by analysing the difference between what is reasonable and what is absolutely logical. One thing the comments on this post show is that different people’s intuition is telling them very different things. For the
mathematician (or mathematics student) it should perhaps not be
too difficult to adopt the maxim ” forget intuition, and trust rigorous
logical argument”. On the other hand, when trying to use mathematics
and isolating the essential properties of the situation you are trying to model, it is important to understand the limitations imposed on the
model you are using by the “simplifying” assumptions made, and perhaps
be prepared to amend the mathematical model to better reflect the
problem you are using it for.
13 April, 2011 at 1:09 am
mircea
Did anybody tell the tribe that there can be only 2 eye colours?
13 April, 2011 at 2:58 am
Ilkhom
A hypothesis:
The tourist taught them that their island is closer to India, than Sweden.
And I personally never seen blue-eyed Indian.
And that changed one subtle assumption.
Is it right way of thinking?
13 April, 2011 at 3:05 am
Ilkhom
the outcome is like in the answer, but for different reason
13 April, 2011 at 3:05 am
Ilkhom
like in the answer 2, I meant
13 April, 2011 at 3:51 am
lkozma
Solution 2 is correct, Solution 1 is wrong because there is always transfer of information in the stranger’s speech.
Suppose there was only 1 blue-eyed person:
[before]: Not everyone knows there exist blue eyed people
(the blue eyed person doesn’t know it)
[after]: Everyone knows there exist blue eyed people.
Suppose there are 2 blue-eyed persons:
[before]: Everyone knows there are blue eyed persons.
Not everyone knows that everyone knows that there are blue eyed persons
(the 2 blue eyed don’t know).
If Alice and Bob are blue eyed, Alice knows Bob is blue eyed,
but thinks that Bob thinks nobody has blue eyes.
[after]: Everyone knows and knows that everyone knows etc.
Suppose there are 3 blue-eyed persons:
[before]: Everyone knows there are blue eyed people.
Everyone knows everyone knows there are blue eyed people.
Not everyone knows everyone knows everyone knows there are blue eyed people.
This last statement changes after the speech.
Similarly for any n:
[before]: (everyone knows)*(n-1) there are blue eyed people.
[after]: everyone knows everything.
13 April, 2011 at 4:19 am
Ilkhom
No, not always.
If I say that your nickname is lkozma, the amount of information transfered is zero.
13 April, 2011 at 3:57 am
lkozma
Incidentally, this is why dictatorships don’t allow gatherings of people (or free broadcast media). Everyone knows the regime is bad but not everyone knows that everyone knows etc. When the whole hierarchy collapses, revolutions break out.
13 April, 2011 at 4:37 am
Peter Whittaker
The puzzle can be understood by thinking about it in terms of quantum mechanics and colllapsing wave functions, with the collapse leading to an event. In this case, the wave function describes eye colour, and the event is suicide. Sure, it’s silly, but that’s not important; the event could be self-exile, putting on a t-shirt that announces one’s eye colour, etc.
Every islander knows the colour of every other islander’s eyes, but not their own. This means that each islander’s “eye colour information wave function” is not yet collapsed.
In other words, from their own perspective, each islander doesn’t even have an eye colour! They’re not “blue” or “brown” or “green”, or anything else: Each individual’s colour is “?”.
Every islander has exactly the same knowledge as all the other islanders – they all have the same information. No one acts, because no one has sufficient information to act – they each know their eye colour to be “?”. New information is required to collapse that function, to pin “?” to a specific colour.
The stranger’s pronouncement is the new information that causes functions to start collapsing. But they don’t collapse right away unless there is only one blue-eyed person on the island.
If there is 1 person, they know their eye colour to be blue, and so they act on that information.
If there are 2 or more people, and one has blue eyes, that person immediately knows their own eye colour, and they act.
If there are 2 or more people, and two have blue eyes, each one continues to know their own colour as “?” until the next day, when the other does not act. This tells each of the two blue-eyed people that the other blue-eyed person knew of a blue-eyed person and didn’t act – in other words, the other blue-eyed person didn’t have enough information to act, because they could not know their own eye colour until the time for the action passed.
Once the time passes for the “other guy” to act – to kill himself – the observer who has blue eyes and doesn’t know it now knows there is at least one other person with blue eyes, and by looking at everyone else now knows that it must be himself.
So the next day, they both act.
With three blue-eyed, it takes two days of non-action observed by someone who sees two blue-eyed people for that person to realize their must be one more person with blue eyes, and that it must be them.
Just keeping days for each person with blue-eyes.
The stranger’s words are the trigger that starts wave functions collapsing, but it is only sufficient information in the special case where only one person has blue eyes.
When more than one person has blue eyes, additional information is required for each blue-eyed person to realize their own eye colour, and that additional information is the continued non-action on the part of all of the other blue-eyed people.
Once all the blue-eyed people take their collective action, the island returns to the state wherein everyone’s knowledge of their eye colour is “?”. They may all see brown, but they don’t have enough information to make any conclusions about their personal eye colour.
13 April, 2011 at 5:13 am
Ilkhom
No. Incorrect.
A priori, probability of having blue or brown eyes is 1/2.
Now imagine we have three islanders, each has blue eyes,
then would think [even after the tourist mentioned he saw blue eyes in the crowd] “Ah, Ok, yeah I know we have people with blue eyes, but everybody still believes that he or she may have any of the colors, so nobody still really sure about colors, therefore no suicides”.
But after the tourist speech, probability of having blue eyes is not 1/2 anymore.
13 April, 2011 at 5:31 am
Peter Whittaker
Your a priori probability is wrong. It is a) not a priori at all, but based on a particular known probability distribution, and b) irrelevant and c) irrelevant – it is irrelevant for two reasons.
It is irrelevant because b) no one takes action on probability on this island, but on certainty – they only act when they know something, and because c) blue and brown aren’t the only possibilities: I could see one person with blue and 999 with brown, and see that person with blue kill themselves tomorrow at noon, and I still would not know that my eyes were green.
13 April, 2011 at 6:25 am
Peter Whittaker
A more general statement of the puzzle….
The puzzle can be stated generally as follows:
There exists a system S in which there are N agents.
Each agent has a property, P, which has a value, Pv.
Discussion of P is forbidden. (Call this rule R1 for later reference.)
If an agent should discover their Pv, they must take an action, A, after time T.
Each agent can see that there are N values of P, that is, Pv1, Pv2, Pv3… PvN
Each agent is ignorant of their Pv, and has no reason to believe it is the same as any observed Pv. This means that there may – or may not – be N+1 values of P, that is, the Pv1, Pv2, Pv3… PvN observed values and their own PvN+1, which may or may be the same as one of the Pv1, Pv2, Pv3… PvN observed values.
Given these conditions, there is insufficient information for any agent to know their Pv, so no agent takes action A. As far as they are each concerned, the value of their property is Pv?
An outsider arrives, one not bound by rule R1 or one capable of breaking rule R1.
The outsider announces that they see the value PvX. The outsider does not indicate how many agents have PvX, merely that some do.
Any agent that cannot see any PvX immediately knows they are the only one with PvX. They are therefore compelled to take action A after time T.
Any agent A that sees one and only one other agent with PvX expects that other agent to take A after T.
When T passes and the other agent does not act, the agent expecting A must conclude that they themself also have PvX, because the only thing that would stop the other agent from acting is uncertainty about their own Pv, and they would only be uncertain if they also saw one other with PvX and were expecting that one other to act. Therefore, each must conclude that there are exactly two agents with value PvX, the one they can observe, and themself.
Therefore, after a second time T, they both take A.
Add another agent with PvX, and repeat with three agents with PvX: After the first time T, each agent with PvX expects nothing, because they can observe two agents with PvX and they know neither has enough information to act. After a second time T, each agent with PvX expects the other two to act, but they do not, which means there must be one more agent with PvX, one that each agent cannot observe – themself.
Therefore, after a third time T, all three take A.
Add another agent with PvX, and repeat….
The reason for dramatic action A (suicide, self-exile), etc., is simply to restore the system S to its initial state: the agents who know their Pv must be removed from the system to return all agents to the original level of ignorance, of uncertainty.
Once all agents with PvX are removed, the original description of S, above, applies with N reduced by 1. The exact number of agents in S, the exact number of agents removed by A after the outsider’s disturbance, and the exact value of N are all irrelevant.
20 April, 2011 at 3:00 pm
UK
Thanks! I couldnt figure out the solution for quite some time because I couldnt formulate the problem rigorously in my mind. But your reformulation helped me see the solution clearly.
13 April, 2011 at 1:59 pm
JPP
(Sorry if I’m making a dumb comment or saying something someone already said).
This problem reminds me something I read as a child:
“James Bond is captured. On Sunday, his gaolers tell him that he will be put to death a morning at dawn. The precise day will no be revealed in advance so that the visit of the executioner will be a complete surprise for him. But in any case, he’ll be dead on the next Sunday at dusk.” The paradox is now the following: Commander Bond can think “If I’m still alive on Saturday (after dawn), I’m doomed to be killed the next day. But this wouldn’t come as a surprise so this hypothesis is absurd and they can’t kill me on Sunday. So if I’m alive on Friday, I’ll be killed on Saturday, but this wouldn’t come as a surprise and so on.” By this brilliant induction, our glorious spy safely concludes that the gaolers can’t logically kill him and he will escape this pickle, as usual. The visit of the executioner on Wednesday then comes as a complete (and rather unpleasant) surprise. How to solve this paradox?
I have an odd feeling that this problem and the blue-eyed islander one are kind of related. Am I wrong? What can you say about Bond’s one?
13 April, 2011 at 5:04 pm
Peter Whittaker
Is the problem with the Bond puzzle the layering of hypotheticals? IF I’m alive on Friday, I won’t be killed Saturday, and IF I’m alive….
But IF he is killed Monday, then the whole thing falls apart. I don’t see a contradiction, I just see a conclusion reached on shaky conjecture.
The blue eyed problem is framed in such a way (very strict rules known and followed by all) that there is no conjecture, no probability, just fact, solid information, the others did not commit the act, therefore… and conclusions drawn from that information.
Think of it another way: Bond is reasoning based on potential future events and what those might mean. The islanders are based on past events and what those must mean, given that the rules are always followed. The past events are the stranger’s announcement and the fact that each morning an unexpected number of people have not committed the act.
14 April, 2011 at 8:32 am
Terence Tao
Ah, yes, the unexpected hanging paradox. There are some similarities between the two puzzles, in that one has to work with chains of higher-order knowledge statements (Bond-on-Monday knows that if he is not killed on Monday, then Bond-on-Tuesday knows that …), though now the deductive chain is working backwards in time rather than forwards.
To me, though, the resolution of the unexpected hanging paradox is the fact that once there are two or more days involved, there is an implicit assumption that Bond knows the consistency of his own knowledge (or more precisely, of the consistency of his future knowledge). For instance, suppose that the execution is either at Monday-dawn or Tuesday-dawn, and consider the state of Bond’s knowledge at Sunday-dusk (just before Monday-dawn) and Monday-dusk (between Monday-dawn and Tuesday-dawn). Let me abbreviate these states of knowledge as Bond-Sunday and Bond-Monday respectively.
Bond-Sunday knows that if there is no execution at Monday-dawn, then Bond-Monday will know the following facts:
1. There was no execution at Monday-dawn.
2. Bond-Monday knows that there was no execution at Monday-dawn.
3. The execution is either at Monday-dawn or Tuesday-dawn.
4. Bond-Monday knows that the execution is either at Monday-dawn or Tuesday-dawn.
5. On the date of the execution, Bond will be completely surprised by the event.
These five facts are inconsistent with each other, and hence Bond-Monday’s knowledge would be inconsistent. However, in order for Bond-Sunday to then deduce (via reductio ad absurdum) that there is an execution at Monday-dawn, he must first know that Bond-Monday’s knowledge is consistent. But this itself will lead to an inconsistency in Bond-Sunday’s knowledge, by similar arguments to above (and so forth back in time, if we consider more than two days).
So we see that the unexpected hanging paradox is in fact closely related to Godel’s second incompleteness theorem, which roughly speaking prevents any reasonable and consistent formal system from knowing its own consistency. This connection is discussed in detail in this recent Notices article of Kritchman and Raz.
Note that the blue-eyed islander puzzle is unaffected by this issue, because at no point does any islander need to know that any other islander’s knowledge is consistent (or any iteration thereof). Instead, they need to know that the other islander’s knowledge is logical (i.e. closed under the rules of deductive logic), which is a different property.
14 April, 2011 at 9:29 am
Ilkhom
But does your post mean that solution is already given?
I am still dissatisfied with it then, I see it relies on the intention of tribespeople to know about their eye-color. It is unclear, if when they are given an opportunity to figure out their own eye-color they want it to be pursued.
19 April, 2011 at 11:51 am
Pace Nielsen
“Note that the blue-eyed islander puzzle is unaffected by this issue, because at no point does any islander need to know that any other islander’s knowledge is consistent (or any iteration thereof).”
So, just to see if I got this: we, the puzzle solvers, may assume that the people in the puzzle are consistent to come to our solution, but the people in the puzzle itself cannot make such an assumption.
19 April, 2011 at 11:59 am
Pace Nielsen
Or to put it another way:
Suppose that in the puzzle there are exactly two eye-colors: blue and brown, and all the islanders know this fact (and know the others know this fact, etc…)
When all the blue-eyed islanders kill themselves, does it necessarily follow that the brown-eyed islanders must kill themselves the next day? For if they do not have to assume that their fellow islanders have consistent knowledge, then could they not conclude that it is possible that those blue-eyed islanders killed themselves early because of their inconsistent knowledge?
(Note: I’m also not sure that knowledge acts like an axiomatic system in all the relevant ways to speak of formal consistency…)
4 May, 2011 at 10:39 pm
Alexey-Voropaev
Would you please answer also:
Is this issue related somehow with Theorem of Poincaré about three bodies?
Sorry for my English : (
13 April, 2011 at 10:58 pm
Ilkhom
Answer 1 is right.
[it is wrong only in degenerate cases of 1 2 or 3 people]
The religion prevents them from discussing the topic.
Cases with than 4(?) or so people require implicit communication through observing the events of suicide. But as it is mentioned above any communication is prohibited,and the lack of suicide has no disambiguative power.
16 April, 2011 at 12:53 pm
Big Red Bits » Reasoning about Knowledge
[...] to Petra in Jordan together with Vasilis Syrgkanis and in the road we kept discussing about the Blue-Eyed Islanders Puzzle, posted by Terry Tao on his blog. It is a nice puzzle because it allows us to reflect on how to [...]
16 April, 2011 at 4:17 pm
moonshadow
One free thinker in the bunch would realize that there is money to be made in starting a new religion. He would renounce the existing religion based on a revelation from “God”. He, or more likely She, would have “visions” to guide the people to a realization that they should not only know their eye color but embrase it. For a nominal fee they would meet each week and hear the Prophet speak. They would go out to their friends and share the good news that they did not have to die. They could know the color of their own eyes and live!!! PRAISE THE PROPHET!!!!!!!!!
17 April, 2011 at 5:16 am
Joseph
I keep seeing comments, here, on xkcd, on the wikipedia page, that say “imagine if there was x islanders” but there’s not, there are 1000, and it is common knowledge that there are 1000, and comments like, “imagine there are 2 (or 3 or 4) blue eyed people, but all the islanders KNOW there are NOT 2 or 3 or 4, they all KNOW that there are EITHER 99 OR 100 OR 101 (That is every one of them sees either 900 or 899 brown eyed people and 99 or 100 blue eyed people, and each knows that they may have blue eyes). I cannot understand how they begin their induction before day 99, as they all know that no one is going to commit suicide on day 1 or 2 or 3 etc because there is no way to infer their own eye color on any of those days. on day 99, there is no preceding case, is has NOT been demonstrated that there is NOT 98 blue eyed people on the island by the lack of suicides, that fact was already established, and KNOWN TO ALL.
smart people seem to believe that induction is possible and that solution 2 is correct, but I have not seen any explanation that isn’t manifestly “hand-waving”. Is anyone aware of a PEDAGOGICALLY SOUND explanation of this puzzle?
Also the common knowledge page on Wikipedia pulls the same trick with the knowledge that the foreigner adds; they say “imagine the number of tribesmen is n” BUT ITS NOT! its 1000! does anyone know of a PEDAGOGICALLY SOUND that is without hand-waving or appeal to “multi-modal logic” that can explain why induction should be possible in a case where is is already KNOWN that there are more than 50 people on the island who have blue eyes?
I am deeply suspicious of people who assert wildly unintuitive things about seemingly simple scenarios and then to prove them have to resort to talking about theoretical frameworks only a tiny percentage of the worlds population could possibly be familiar with.
18 April, 2011 at 9:48 pm
Tollens
“on day 99, there is no preceding case, is has NOT been demonstrated that there is NOT 98 blue eyed people on the island by the lack of suicides, that fact was already established, and KNOWN TO ALL.”
Here is the last step in the induction: If no one commits suicide on day 99 then there were could not have been 99 blue eyed people (this was not known beforehand). Hence there must be 100 blue eyed people and on day 100 all the blue eyed people commit suicide.
I suggest reading Lkozma’s comment which makes the solution much more intuitive.
18 April, 2011 at 10:14 pm
Anonymous
I am impressed by the longevity of the enthusiasm on this puzzle. I guess I should check back once a while for new interesting comments.
19 April, 2011 at 11:47 am
megatron
Hi,
From an engineering point of view (EE or CS), let’s imagine the island/w the islanders is the system under test. The foreign visitor is the external excitation signal.
Say the purpose is to input a signal (foreigner’s action) to kill every blue eyed islander.
solution 1: the foreigner can point to each blue eyed islander and tell him/her that he/she is blue-eyed
solution 2: the foreigner can count and say that there are 100 blue-eyed islanders
In addition, if the input signal is deceiving, for example, the foreigner says that there are 99 blue-eyed islander. the blue eyed islander will count 99. and the brown eyed count 100 and knows that it’s a false claim. so nobody dies.
But what if the foreigner says 101 blue eyed. then blue eyed won’t die. but all brown eyed will die next day, thinking that they are blue-eyed.
To kill 100 blue-eyed islander, all these takes precise counting, which it’s computationally expensive.
what is amazing for me is that for such a system, there exists simple “algorithms” to achieve the goal:
1. foreigner just say: “how unusual it is to see another blue-eyed person …”
or
2. (deceiving information) foreigner just say: it’s amazing to see a red-eyed person (which kills every islander)
Can some theorists generalize this phenomena?
19 April, 2011 at 11:55 pm
Varjabedian
Dear prof. Tao,
The foreigner gives a starting day to apply solution 2, for me that’s the information missing.
23 April, 2011 at 12:32 am
AnusInFabula
I think there is two possible way:
1)
If every islander knows the statistics he can count the number of islander which
have blue and brown eyes and than understand wich one is his own eye colour and suicide him.
The tribe could not exists.
2)
If every islander doesn’t know the statistics the foreigner’s assertion does not influence in any way the life of islanders cause we have this logic-scheme:
A islander’s reality: there are over 800 people blue-eyed in this place
B foreigner’s assertion: there are some person blue-eyed in this place
Deduce with assumption A,B that my eye colour is X has not logical reasons, cause A is equivalent B.
If someone commits suicide for this is the same case if i know that (Exists x€R such that x=1) come somebody and tell me (Exists x€R such that x=1) i deduce y=1.
There’s no way.
25 April, 2011 at 11:48 pm
Ajay Ravi
Here’s the proof similar to solution 2 which clearly shows that traveller announcing the presence of blue-eyed person provides new information that forces all n blue-eyed people to commit suicide.
The proof is structured into numbered propositions, with proposition N=n providing the proof for n blue-eyed people:
Proposition 1: if n=1 AND traveller announced there is a blue-eyed person, then the blue eyed person commites suidicde after 1 day
Proof: the blue-eyed person realises he is the only one with blue eyes and commites suicide the next day.
Proposition 2: if n=2 AND traveller announced there is a blue-eyed person then the blue eyed people commit suidicde after 2 days.
Proof:
All blue-eyed persons reason in this way:
if I am not blue-eyed then there is 1 blue-eyed person on the island, and since traveller announced there is a blue-eyed person, the lone blue-eyed person will apply Proposition 1 to commit suicide after 1 day.
Therefore if there is no suicide after 1 day, I must also be blue and I will have to commit suicide after 2 days.
Proposition 3: if n=3 AND traveller announced there is a blue-eyed person then the blue eyed people commit suicide after 3 days.
proof:
All blue-eyed persons reason in this way:
if I am not blue-eyed then there are 2 blue-eyed people on the island, and since traveller announced there is a blue-eyed person, the 2 blue-eyed people will apply Proposition 2 to commit suicide after 2 days.
Therefore if there are no suicides after 2 days, I must also be blue and I will have to commit suicide after 3 days
…
proposition N: if n=N AND traveller announced there is a blue-eyed person then the blue eyed people commit suicide after N days.
proof:
All blue-eyed persons reason in this way:
if I am not blue-eyed then there are N-1 blue-eyed people on the island, and since traveller announced there is a blue-eyed person, the N-1 blue-eyed people will apply proposition N-1 to commit suicide after N-1 days.
Therefore if there are no suicides after N-1 days, I must also be blue and I will have to commit suicide after N days
29 April, 2011 at 9:53 am
ETzortzakis
Solution 1 is wrong!
proof:if there are n blue eyed persons(BEPs) A_1,A_2,…,A_n
-for n=1 it’s obvious that traveler’s statement adds new info.Then starts what we call 1-sub game,which is A_1 realizing his own eye color and committing suicide on the same day.
-for n=2 then traveler’s statement again adds new info,
indeed A_1 knows that there is at least one BEP but he doesn’t know that A_2 has this knowledge.But now(after foreigner’s remark),he knows that A_2 also knows this.So now A_1 is thinking that if his own eye color is brown then A_2 plays the 1-sub game which will conclude with A_2 committing suicide on the 1st day.So if on the 2nd day A_2 is alive then no 1-sub game ever happen so he realizes that his own eye color is blue and thus commits suicide on the 2nd day.Symmetrically A_2 does the same.
-n=3 A_1 knows that there is at least one BEP.
A_1 knows that A_2 and A_3 know that there is at least one BEP.
BUT A_1 doesn’t know if A_2 knows that A_3 is aware of the fact that there is at least one BEP!
We can see clearly now where Solution 1 fails,the comment gives the tribe meta-knowledge(or meta-meta-knowledge) aka knowledge on others knowledge.So A_1 is thinking if i have brown eyes then the other 2 with their new knowledge play a 2-sub game so they will commit suicide on the 2nd day,else i am BEP and we all commit suicide on the 3rd day.
The rest of the induction is clear from n=3,
this faux pas gives A_1 the knowledge that A_2 has the knowledge that…that A_n-1 has the knowledge that A_n has the knowledge that there is at least one BEP in the tribe.
30 April, 2011 at 11:32 am
Dale
Most blue-eyed people will not know how many blue-eyed people are on the island. (Do you know how many blue-eyed people live in your neighborhood?) Being highly logical, when they recognize the iteration, they will have ggod reason not to know the number. Some will committ suicide on the 100th day (they had counted), but everyone else (brown or blue eyed) will continue to not count the number of blue-eyed people.
30 April, 2011 at 11:47 am
Dale
Actually, we could call this the “Sargent Schulz” solution (for fans of Hogan’s Heroes)
30 April, 2011 at 12:21 pm
G. Siamantas
The first solution seems to be the correct one.
The second solution requires that at least one of the n-1 blue eyed islanders know his/her eye color, that it is not true.
This easily demonstrated when n=2.
Both blue eyed residents don’t know their eye color, their decisions are mutually exclusive.
After the first day they will both wait indefinetely because they both know that they don’t know their eye colors.
If one of them knew that the other knows his eye color only then he would commit suicide the other day.
The only guy that will be probably forced to commit suicide will be the traveller because he talks too much…
30 April, 2011 at 7:01 pm
al
I was struggling with why the foreigner triggers everything, until I read the Wikipedia article on common knowledge and the light dawned.
As far as any single islander knows, all the other islanders are blind (or otherwise ignorant of the eye colours of other people).
On the day the foreigner makes his speech, each islander discovers that every islander knows that at least one islander has blue eyes. After the first non-suicide day, each islander discovers that every other islander knows that at least two islanders have blue eyes and so on and so on.
Without this knowledge of what the other islanders know, then each islander cannot assume that all the blue-eyed islanders would kill themselves on the right day.
PS Many of Nicole Krieger’s comments are amusing.
5 May, 2011 at 6:04 am
G. Siamantas
In this variant of the muddy children puzzle the information provided by the traveller does not add any more information to the knowledge that every blue eyed tribesman has. They all already know that there are 99 other blue eyed islanders. The solution to THIS puzzle is proposition 1.
The only way that the words of the traveller can trigger a sequence of suicides in the islander community is if they have in mind the solution of other versions of this puzzle, as most people does in these comments.
In order for proposition 2 to be true there should be added in the description of the puzzle the element of synchronicity in the islander’s thoughts, i.e. all the islanders reason in complete synchronization. This is NOT stated in the given puzzle description. This is usually given in the descriptions of other variants of the puzzle.
A general comment on all variants of the puzzle: in order for the solution to be the suicide of all islanders or for all children to say that they have mud in their foreheads etc. All islanders, children etc must think inductively on n (in mathematical terms) and this is normally not the case in normal people’s thinking.
5 May, 2011 at 10:43 am
al
I would say this is covered by “all the islanders are highly logical” and Note 1 and Note 2.
There are millions of possible caveats you could exploit to avoid conclusion 2.
30 June, 2011 at 6:22 pm
hugo
The foreigner does not act as a trigger, we just assume he will cause the same thinking in all the tribepeople, wich is to count. And they all assume in their world they will all do it.
So thats the fact they “know” everybody will start to think that makes each one of them to star worring about themselves.
Im sorry for my bad english, im portuguese
6 May, 2011 at 12:21 am
jqanderson
Has anyone mentioned that this is game theory 101? The answer hinges on the concept of common knowledge, and there are a number of ways to formalize it. Ask your econ professor or consult any graduate-level game theory handbook for precise statements.
7 May, 2011 at 6:24 am
Phanindra
I think this puzzle can be solved if one understands the “depth” of knowledge. Here is my go at a solution:
Let 1) “k” denote the string “knows that”
2) “e” denote the string “there is a blue eyed person in the tribe”
to avoid writing the phrases repeatedly.
I looked at a much simpler case to start off with. Assume that there are only three people in the tribe all of them blue
eyed. Name them a,b,c.
At the beginning of time (in this problem) one can say that the following are true:
1) d k e
2) d k (f k e)
where d belongs to {a,b,c} and f belongs to {a,b,c}. However, at the next level of “depth”, the following statements are
false:
1) d k (f k (g k e))
where d belongs to {a,b,c}, f belongs to {a,b,c} and g belongs to {a,b,c}.
Note that if any of the above false statements become true somehow (here, with the passage of time and observing whether
people are comitting suicides or not) then it could be shown that d knows his/her eye colour (where d belongs to {a,b,c}).
The words of the traveller make these statements true at the beginning of day three. Even though at the first day his words
do not help the tribe at all, they become handy after sometime. Unfortunately, at the height of their knowledge, they choose
to kill themsevles !
7 May, 2011 at 6:37 am
Phanindra
A minor mistake in the above: for the false statements, d != f != g. Some of the rest are trivial and the others are not that important.
10 May, 2011 at 12:14 pm
FV
1. If everybody knew that there are only two colors they would know immediately about Solution 2, i.e. that eventually they would know their eye colors, so they could commit suicide immediately if they felt like it.
2. Nicole Krieger mentioned a possibility of evil foreigner with grey eyes. Another possibility is of an islander too scared to commit suicide, in which case the following day everybody would have to commit suicide.
10 May, 2011 at 12:42 pm
FV
3. Of course, as someone mentioned above, if they knew that there are “exactly two colors” then by the same Solution 2 they would all commit suicide even without the foreigner.
However, what if they all knew that there are “at most two colors”? Then the first induction step would not work since the only blue eyed person would not have killed himself since he could assume that he also has brown eyes. However, in the case of “at most two colors” and 100/900 breakdown they know immediately that there are “exactly two colors”. Isn’t that paradoxical?
10 May, 2011 at 1:42 pm
FV
Oh, I see! Announcing whether there are “at most two colors” or “exactly two colors” reveals different “common” information, even though to each individual it is exactly the same! Nice!
10 May, 2011 at 3:47 pm
SJO
Actually, all the islanders will completely know the statistics of the population. In a large population of 1000 people, excluding themselves, everyone can compute a distribution based on their observations, and those distributions would be identical.
12 May, 2011 at 5:13 pm
Tad Boniecki
Please put me out of my agony! I have read through the blue eyes puzzle a few times, as well as the answers on the Net. It doesn’t make sense to me. The solutions start with the case where there is one blue-eyed islander, who then leaves on hearing the blue eyes statement. They then move on to the case of two blue-eyed islanders hearing the same statement.
The problem is that the announcement that there is an islander with blue eyes is made *only once*, so it cannot be used in 100 separate cases. Sure, if there were only one blue-eyed islander then he would leave on hearing the statement, but we start with 100 blue-eyed islanders, not one. I think the inductive logic fails because it assumes that the statement about someone having blue eyes is made every day.
Come to think of it, even if the statement about blue eyes were to be made every day, that still would not help. The solution is only valid if we can get from the case of 100 to 99 blue-eyed islanders.
Let’s strip the puzzle back to essentials. Suppose the scenario is that there are only two islanders, both with blue eyes, and that the outside person says, “I see someone with eyes.” Can we get from two islanders to one in this simplest version of the puzzle? I think not, because the statement about there being a blue-eyed person is never made to just one islander. Because it is never said to just one islander, we cannot work back to this case from the case where there are two islanders.
Another problem is that the announcement of there being a blue-eyed islander does not tell anyone anything. Every one of the islanders can already see a blue-eyed islander, so apart from saying it out loud, the statement can have no effect, as no information is being given. If each islander thought this thought, rather than hearing it said out loud, then it would have the same effect. If the inductive proof were valid then all the islanders would have left 100 days after arriving at the island, whether or not anyone made the statement out loud.
In conclusion, the statement, “There is a blue-eyed person” can *only *have an effect if there is just one blue-eyed person to hear it. This never happens, as the statement is only made once to the initial group of 100. So, theorem one is false because the case of one person hearing the statement never happens.
Thanks
Tad
13 May, 2011 at 8:08 am
Terence Tao
The key point here is that the “real” world in the puzzle – i.e. the world of what actually is true in the puzzle (i.e. the world in which there are 100 blue-eyed islanders) – is not the only world that one has to analyse; various “purely hypothetical” worlds, in which there are other numbers of blue-eyed islanders, also influence the behaviour of the islanders. The reason for this is that while you know that such worlds are purely hypothetical, the islanders do not, and so must also take those worlds into consideration. (More subtly, there are worlds which each islander knows are purely hypothetical, but they do not know that the other islanders know to be hypothetical – such as the world in which there are only 98 blue-eyed islanders instead of 100. Somewhat surprisingly, these worlds need to be taken into consideration also. And so forth.)
A familiar everyday example of this phenomenon (at least at the first-order level) comes from the game of poker. A player may, in reality, hold a lousy hand, but may be able to successfully bluff other players into thinking that he or she in fact holds a very high-ranking hand. The hypothetical world in which this player holds a good hand is not the real world, but the other players do not know that fact – and as a consequence, this bluff can significantly alter their behaviour. Higher order versions of this phenomenon can occur when a bluffing player has to try to gauge if another player has “bought” his or her bluff and has a genuinely strong hand, or does not believe the bluff and is counterbluffing. Only one of these alternatives can be the truth, but the mere possibility of the other alternative can still cause a real change in the player’s behaviour.
In a similar way, in an island in which there are two blue-eyed islanders, the hypothetical world in which there is only one blue-eyed islander is a possible world to each of the two blue-eyed islanders, and can only be ruled out one day after the foreigner speaks.
In an island in which there are three blue-eyed islanders, the hypothetical world in which there is only two blue-eyed islanders is a possible world to each of the three blue-eyed islanders, and can only be ruled out two days after the foreigner speaks. And so forth.
The only hypothetical worlds which can be completely eliminated from one’s analysis are those worlds that are commonly known to not be possible. In particular, once the foreigner speaks in full view of all the islanders, it becomes common knowledge that there is at least one blue-eyed islander, and so the world in which there are no blue-eyed islanders can be ruled out completely from that point onwards.
To understand the puzzle properly, one has to “get inside the head” of an islander, and see things from the islander’s point of view, taking into account that the islander may not know everything that you, as an external observer, know. (In particular, hypothetical worlds which you know to be impossible, can become possible once one adopts an islander’s perspective.) Furthermore, one has to iterate this process, getting inside the head of an islander as he or she in turn gets inside the head of another islander, and so forth. (In fact, this process has to be iterated 100 times in order to fully resolve this particular puzzle!)
15 May, 2012 at 3:40 pm
Jeremy
The hypothetical worlds part is where it seems the logical argument parts ways with the real world.
It has to be known to these logical people that whatever the real number of blue-eyed people is (let’s call it N), blue-eyed people see N-1 blue-eyed people and the rest see N blue-eyed people. So it is Common Knowledge that everyone has first-hand evidence of at least N-1 blue-eyed people.
That this is Common Knowledge follows as a consequence of the GIVEN that all the islanders are completely logical AND THAT THAT IS COMMON KNOWLEDGE, that they can all see everyone else’s eye color, and are ignorant only of their own eye color.
So every tribe member can be absolutely sure that whatever number n of blue-eyed people they see, no other tribe member could possibly conclude there are fewer than n-1 blue-eyed people, and this, too, would be Common Knowledge. Furthermore, since n >= N-1, no other tribe member could possibly conclude any other tribe member concludes there are less than N-2 blue-eyed people.
Stated differently, ever tribe member is certain that their first-hand evidence of n blue-eyed people requires the world to be such that N >= n, and everyone else has first hand evidence of at least n-1 blue-eyed people and N-1 blue-eyed people. Thus even though I may conclude that another islander thinks there is one fewer blue-eyed person than I do, I cannot transitively think that that islander thinks that another islander would think there could be even one fewer. This is because I know the world is such that if I am seeing N-1 blue-eyed people, I have blue eyes and no one else is seeing fewer blue-eyed people and alternatively, if I am seeing all N blue-eyed people, I do not have blue eyes so no other person would not suspect I see fewer blue-eyed people than they do.
So it must be Common Knowledge that there are at least N-2 blue-eyed people. That is, it is Common Knowledge that every islander will, from first-hand observation and reasoning, conclude the lower bound of every other islanders estimate is >= N-2.
The key here is that it is Common Knowledge that any islander would have first-hand knowledge of at least N-1 people with blue-eyes. (Or perhaps the key is that the blue-eyed islanders are interchangeable.) In a hypothetical world with 3 blue-eyed islanders, there is no hypothetical world with no blue-eyed islanders. All the blue eyed islanders see 2 other blue-eyed islanders and cannot imagine a world where a blue-eyed islander does not see a blue-eyed islander (and of course all the rest see 3 blue-eyed islanders), so it is not a possibility for any islander to conclude there are no blue-eyed islanders.
15 May, 2012 at 4:10 pm
Jeremy
Of course, knowing that there are at least n-1 or N-2 blue-eyed people doesn’t tell me whether or not I have blue eyes. I will only know I have blue eyes when I know N > n. I will only know that when I know the n blue-eyed people I see also think that N > n. So what the foreigner does is start the clock ticking. Today we know n > 0. Tomorrow, when nobody does anything, we know n > 1, and the next day we know n > 2, and so on. In our world with 100 blue-eyed islanders, everyone knows that everyone knows there are at least 98 and everyone can see there are at least 99, but only on day 100 do those people who see 99 know that they are one of the 100 blue-eyed people and not a non-blue-eyed person amongst 99 blue-eyed people.
15 May, 2011 at 5:06 pm
Tad Boniecki
Sorry to be a nuisance, but I am as confused as before. You wrote about hypothetical worlds and that the islanders have to take these into account. Fine. But I still don’t see how the saying out loud of “I see blue eyes” can have any effect, given that each of the islanders can think this without the benefit of outside help. Each islander also knows that every other islander knows this, and so on.
Secondly, I can’t follow the proof of the case where n=1 because the statement about blue eyes is only made once, to 1000 islanders, never to just one or two. It cannot be hypothesised because it simply does not happen within the framework of the puzzle.
What am I missing??
Thanks
Tad
16 May, 2011 at 7:49 am
Terence Tao
You are getting close to the key point in the puzzle, which is that the “and so on” in your first paragraph is actually false. (This is easiest to see in the case when there are 2 blue-eyed islanders.)
In the inductive argument, n is the number of blue-eyed islanders, not the number of islanders in total, which is indeed commonly known to be 1000. In contrast, n, while actually equal to 100, is not commonly known to equal 100, and can hypothetically be anything from 0 to 1000 once one works in a sufficiently highly nested knowledge framework.
16 May, 2011 at 8:06 am
FV
Tad,
The point is that by saying “I see blue eyes” he does reveal information they previously did not know, it’s just not an obvious information. Suppose that there are two blue-eyed people, A and B and a lot of browned eyed people. Each of them knows that there is a blue-eyed person. But A does not know whether B knows that there is a blue-eyed person. When A looks at B, he thinks: “Well, I and everyone else except B knows that there is a blue eyed person. But does B know that there is a blue-eyed person? I don’t know… It really depends on whether I have blue eyes or not.” After the foreigner’s announcement A thinks “Now B knows for sure that someone has blue eyes. If I have blue eyes then B will think it’s me and not kill himself on the first day. But if I have not blue eyes, B will know that it must be him and kill himself on the first day.” So the foreigner reveals information, not about what each of them already knows about other’s eye color, but about what each of them knows about what others know.
Try the same with three blue eyed people – A, B and C. A knows that B knows that someone else has blue eyes, namely, C. But when A looks at B and thinks: “Does B know that C knows that someone else has blue eyes?”, the answer is that A is not sure since it depends on his eye color, but foreigner’s announcement changes this.
16 May, 2011 at 8:29 am
lkozma
You can also check my first comment above, where I explained what is the information transmitted by the foreigner’s speech:
http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/#comment-51675
16 May, 2011 at 8:16 am
FV
Dear Terry,
Wouldn’t it be fun to have an undergraduate class (or even graduate class for law majors!) consisting completely of logic puzzles like this one? This one alone would take at least one class. Is there a good book with 20-30 different logic puzzles such that each would fill one class? Could you make a list of as many non-trivial puzzles as you know, and ask others to contribute. Also, it would be fun to think of ways of using these types of puzzles to force others to reveal information they are hiding, i.e. logic based interrogation techniques! Better than water-boarding! If you find this idea interesting, I can not think of a better way to turn it into a collaborative project than your blog! Thanks, Terry!
16 May, 2011 at 12:29 pm
farzin
I think the problem is in the nature of the question when n=1 and n>1.
These problems are different when n=1 and n>1 since when n=1 everybody knows there exists blue and brown colours except the blue eyed guy but when n>1 every body knows that two colours exist so the information in the problem is not same when n=1 and n>1. I think the induction logic does not work here since we have two different type of problems.
16 May, 2011 at 2:33 pm
farzin
In other words, the information provided by the foreigner changes the problem if n=1 or n=2 since if n>2 everybody already knows that blue and brown exist. Therefore the right induction for n>2 is that for n=1 every body knows blue and brown exist and so on.
At the end by the solution 2 we see that based on the assumptions of the problem it is not possible to have a community of people with blue eyes for n>2 even without having a foreigner!!!.
17 May, 2011 at 10:12 am
gcy
Approaching the problem by recursive postulation (for the lack of a better word) – modeling a possible scenario within a possible scenario, and so on – is more sensible than inducting on 1, 2, 3,…, n-1, n, though both are essentially the same.
But the former approach may be more convenient to help resolve the above paradox, because it allows the information ‘there is at least one blue eye’ to perpetuate across all scenarios hypothesized by the islanders, in the manner of ‘A thinks B thinks C… an so on’ – let’s just call that 1st, 2nd, 3rd, … k-th order postulation. Whereas in reality, every islander can casually conclude that everyone else must see at least one blue-eyed (which is of equivalent logic to the foreigner’s statement) – this observation is bound to the ‘reality framework’ for which it is based on, and does not prevail when an islander ‘gets inside the head of another’ to postulate an alternate scenario, and so on. Without the foreigner’s information, this exercise will not yield a definite outcome because at the 99th-order postulation, the possibility that n=0 (there can be no blue-eyed) cannot be eliminated (by the way, every postulation is verifiable by dichotomy logic – if not k-1 islanders, it must be k – such that it provides new information back up the postulation chain).
Hence, the islanders will not be able to figure out anything unless the given the foreigner’s statement as the ‘baseline truth’, such that the thought experiments can lead to a definite conclusion on the 99th / 100-th day.
17 May, 2011 at 11:51 pm
James
Terry’s explanations are fantastic on a mathematical level and also on a language level. The hypothetical worlds situation is explained beautifully. Indeed I do agree with outcome 2 and when I “saw the light” I felt smarter! The “sufficiently highly nested knowledge framework” is also a nice phrase.
Is there, though, a similarly nice and intuitive way of describing why the blue eyed guys would not kill themselves earlier?
I know that some poster earlier talked about 100 days being an upper bound. Is it easy to explain why 100 would also be a lower bound or do we not have enough information?
Also, can we apply the following straightforward argument or is it too “hand wavy”? Argument: Because of symmetry the blue eyed people must all commit suicide at the same time.
From then, could we then rule out the possibility of this happening on any day before the 100th day? Thus making 100 a lower bound also.
Finally, can you keep posting interesting problems like this on a regularly? I imagine after solving/ understanding 10-20 problems like this, we might feel better able to tackle problems in general.
7 February, 2012 at 9:49 am
Lenoxus
Here’s an answer to why they cannot die any sooner than Day 100.
Suppose that each of the blue-eyes thinks “Well, I see 99 blues, so there are either 99 or 100. Since this is a version of the puzzle where we are “trying” to deduce our own color as soon as possible, then I will commit to killing myself on Day 2 if and only if no one has done so on Day 1, that is, tomorrow.”
The problem is that if there really were only 99 blues, then they would each have to think something like the same thing: “I see 98, so I will kill myself on Day 2 if no one does on Day 1.” The 100 blues would have already known this about the hypothetical 99 blues. Therefore, they would have to modify their “strategy” accordingly: “If there are really 99 blues, then they will wait to see if the 98 that they each see kill themselves on Day 1. When that doesn’t happen, those 99 blues will kill themselves on Day 2. And IF that doesn’t happen, then I’ll know there are 100 blues total, and we’ll all kill ourselves on Day 3.”
But it can’t possibly stop there! Why, exactly, would a hypothetical 98 blues kill themselves immediately on Day 1? There can’t be any particular reason. The hypothetical 99 know that a hypothetical 98 would also wait a day, so these 99 wouldn’t kill themselves until Day 3 at the earliest. Except, of course, that this in turn relies on a hypothetical 97 blues immediately deducing their own color from the foreigner’s statement and killing themselves on Day 1…
As I hope you can tell, this just keeps going and going. It stops once we reach a hypothetical single blue-eyed islander. Unlike all the various combinations of hypothetical islanders before him, this guy would kill himself on Day 1. So the rest of the islanders’ thought process must build up from there.
On Day 1, it becomes common knowledge that there is more than 1 blue, on Day 2 that there are more than 2, and so forth. On Day 99, each of the 100 blues sees that the other 99 did not kill themselves, and so all 100 prepare to do so the next day.
17 May, 2011 at 11:57 pm
Tad Boniecki
I have finally understood the answer. Enlightenment came when I read the clear explanation on wikipedia:
http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29#Example
This may help other people.
Tad
19 May, 2011 at 9:11 pm
Epistemic logic, temporal epistemic logic, and the blue-eyed islander puzzle lower bound « What’s new
[...] recently reposted my favourite logic puzzle, namely the blue-eyed islander puzzle. I am fond of this puzzle because [...]
20 May, 2011 at 12:34 am
Oskari
I’m absolutely bewildered by this puzzle, not because it would be hard to solve, but because of the use of deductive reasoning in absolutely wron realm of things. This is a question of inferring the properties of your model of the world from the observations you make. The link between the model world (a world described by random variables) and the real world is the observations we make of the real world. This cloudy hazy curtain of observations always separates the two. Deductive logics is completely confined in the model world, and can be used ONLY to narrow down the support of the random variables of the model world (based on previously assumed knowledge of the world).
The solution 1 is correct, with only one exception of n=1 (in which case they all kill themselves by the day two).
The reasoning is as follows:
Villagers state of knowledge of his eye’s colour is a random variable with support: Colour=[blue,brown]. Before the new observation provided by the foreigner, the state of blue eyed villager’s random variable “colour”=[(n-1)/N,(N-N-1)/N], where n is the number blue eyed villagers and N is the total number of villagers. Should there be any “observation” that will have only one solution (giving 100% of the probability mass two either of the two states), the person will kill himself. This “elimination” of possible states (or narrowing the support) can be done with deductive reasoning.
When the foreigner provides the new observation, the only two states of the random variable “colour” of interest in this puzzle are: colour=[1,0] or colour=[0,1].
If n=1, then the blue eyed person concludes with deductive reasoning that the only random variable state that fits the observation is colour=[1,0], and therefore he kills himself. And after that the rest conclude, they must have brown eyes, so they kill themselfs as well.
If n>1, then deductive reasoning is not able to eliminate (give zero probability) to either state, and therefore will not cause any consequences. The end of story. If you want to calculate the probabilities, use the bayes theory, which also gives you the way to join the information from two or more observations:
p(colour|observations) = p(observations|colour)*p(colour)/p(observations).
20 May, 2011 at 2:03 am
Oskari
I see Terence has talked about bayes before:
https://profiles.google.com/114134834346472219368/posts/G5DnA8EL7D3/In-classical-logic-one-can-represent-ones#114134834346472219368/posts/G5DnA8EL7D3
21 May, 2011 at 10:32 am
A small segue of subject | Great & Amazing Content Site
[...] if we discard the blue-eyed men on the island, and look at real human markets, we would expect to see a collective rationality not finite, but [...]
26 May, 2011 at 1:08 pm
Anon
Consider the modified scenario, where the foreigner instead remarks: “There are *exactly* two distinct eye-colours on this island.” What happens then? If I’m not mistaken, on day 100 all the blue-eyed islanders kill themselves, and then the following day everyone else kills themselves.
On the other hand, if the foreigner says: “There are *at most* two distinct eye-colours on this island”, then everyone learns they have either blue or brown eyes, but without the tragic ending.. how odd!
27 May, 2011 at 7:38 am
Terence Tao
If the foreigner says “there are exactly two distinct eye colours”, but does not name what they are, then nobody commits suicide (assuming there are no other sources of information, of course), because the fact that the two eye colours are blue and brown is not common knowledge. (For instance, if there are two blue-eyed islanders A, B and two brown-eyed islanders C, D, then A knows that B knows that there are two eye colours, but it is not the case that A knows that B knows what those two eye colours are, and that one of them is brown, but it is not the case that A knows that B knows what the other eye colour is.)
27 May, 2011 at 12:18 pm
Anon
Ah, quite right.. well that’s even more odd, because in this case the islanders are actually learning something new about their own eye colours directly from the foreigner (that their eyes are either blue or brown).. in the original scenario where he remarks that someone has blue eyes, the islanders learn nothing about their own eyes directly from him. But you’re right, even the n=1 part of the induction no longer works.
17 June, 2011 at 3:53 am
Marcelo Cantos
But does this uncertainty extend to a larger population? Surely each islander among the 1000 can readily infer that everyone sees at least brown and blue eyes, and that everyone else has made the same inference.
16 January, 2012 at 11:37 pm
Anonymous
Right, in the modified puzzle when
the foreigner says “there are exactly two distinct eye colours”, but does not name what they are, then nobody commits suicide – even in the formerly “fool proof” cases of n=0 and n=1 (of blue-eyed and 900 brown-eyed). It is also interesting to note that if, in the original puzzle, “because of some accident,” e.g. pre-suicide overdrinking, the 100 blue eyed will not commit suicide on the 100th day, the next 101th day, all 900 brown-eyed must commit suicide – because the inductive nested logical calculations are done by everybody (and the brown-eyed people all think that there 100 blue-eyed people, for sure, – but maybe 101 ).
17 June, 2011 at 3:59 am
Marcelo Cantos
I don’t follow the second scenario. Everyone already knows that there are at least two eye-colours (and that everyone else knows this too, and that everyone knows that everyone knows, …). With this knowledge, the assertion that there are at most two colours is identical to the assertion that there are exactly two colours.
27 May, 2011 at 3:52 am
dimitris stathopoulos
day 1: nobody dies because nobody knows his/her eye colour
day 2: each person count the other 99 or 100 (depending on his eye colour) blue eyed persons
day 3: you cant say to the other the colour of eyes he has so you ask how many he found with blue eyes
day 4: those who found 99 realise that they have blue eyes and they commit suicide!
THE END!
27 May, 2011 at 4:00 am
dimitris stathopoulos
also:
those who found 100 also die because the know that they have brown eyes!
funny
31 May, 2011 at 10:02 pm
Anonymous
I will use the xkcd example where people get to leave on a nightly ferry.
Guru says “there’s at least one person with blue eyes”
With this, I don’t see any flaws in the following logic:
For 1 blue-eyed person (A):
A leaves the instant the 1st Ferry arrives, because he only sees one other person (the Guru) who clearly does not have blue eyes.
—
For 2 blue-eyed people:
There’s 2 possibilities for A in A’s mind. A has blue eyes or non-blue eyes.
If A has non-blue eyes, B will leave on the first ferry.
B DOESN’T leave on the first ferry.
A knows the other possibility must be true, that A has blue eyes. They both leave on the 2nd ferry.
—
For 3 blue-eyed people:
There’s 2 possibilities for A again and as always… A has blue eyes or non-blue eyes.
If A has non-blue eyes, A might as well be a brown-eyed person. B and C would ignore A and behave as though B and C are the only blue eyed people. We agreed that 2 blue eyed people leave on the 2nd ferry. The 2nd ferry comes by and no one leaves. A must have blue eyes.
They all leave on the 3rd ferry.
—
For 4 blue-eyed people:
A has non-blue eyes or blue eyes.
If A has non-blue eyes, A might as well be a brown-eyed person. B, C, and D would ignore A and behave as though B, C, and D are the only blue eyed people. we agreed that 3 blue eyed people leave on the 3rd ferry. The 3rd ferry comes by and no one leaves. A must have blue eyes.
They all leave on the 4th ferry.
—
I don’t see how this could possibly be wrong.
Now we try the other way…
Suppose there is no Guru:
For 1 blue-eyed person:
No way of discerning own eye color.
—
For 2 blue-eyed people:
Yes, both people know that there is at least one blue-eyed person, but A doesn’t know B knows, and B doesn’t know A knows.
For all A knows, A has non-blue eyes, and it is as though B is alone on the island.
—
For 3 blue-eyed people:
For all A knows, A has non-blue eyes.
If this is the case, this is what B’s vision would look like:
A = non-blue (worst case)
B = (I don’t know because I’m A pretending I’m B)
C = blue
Now have A’s theoretical B pretend he’s C:
A = non-blue (worst case)
B = non-blue (worst case)
C = (I don’t know because I’m A pretending I’m B pretending I’m C)
As far as A knows, B has no way of knowing whether or not C knows anyone has blue eyes.
A can’t know if B knows C knows.
—
For 4 blue-eyed people:
For all A knows, A has non-blue eyes.
If this is the case, here’s B’s vision:
A = non-blue
B = (idk)
C = blue
D = blue
Now have A’s B pretend he’s C.
A = non-blue
B = non-blue
C = (idk)
D = blue
Now have A’s B’s C pretend he’s D.
A = non-blue
B = non-blue
C = non-blue
D = (idk)
A’s B’s C can’t count on D.
I like this idea… but why do you need 3rd order knowledge? Isn’t the below actually true?
A=non-blue
B=(idk)
C=blue
D=blue
A knows B knows C knows (C at least sees D)
A knows B knows A knows (A sees both C and D)
A knows B knows D knows (D at least sees C)
A can comfortably obtain that Everyone knows everyone knows everyone knows that there is at least one blue-eyed person. Isn’t that enough?
Are my inductions without the Guru wrong? Could someone explain why you need 3rd order knowledge or show me my error in the 4 blue-eyed people no Guru step?
7 June, 2011 at 12:14 am
Chen Wei
the visitor’s words is meaningless, because everyone already knew that at least one native people are blue-eyed. So, what’s the fuction of the visitor’s announcement.
7 June, 2011 at 6:57 pm
cocacola1123
I have some opinions about this puzzle, I am not sure it’s right, just for discussion:
1. The 2 solutions are all right. Because it is unreasonable that the foreigner trigger this incident. Actually I believe a reasonable trigger (beginning condition) is as follow: the islanders immediately reach a common knowledge that “all islanders know that at least 98 blue eyes are exist”. (brown eyes will make the common knowledge 99, but it is contained in the condition of “at least 98”, however, such difference make the brown eyes wait for all blue eyes commit suicide, then they will die one day later)
2. 1st day, no one died, so the common knowledge rises to 99;
2nd day, no one died, so the common knowledge rises to 100;
3rd day, all blue eye commit suicide;
4th day, all brown eye commit suicide;
3. Conclusion: there is m brown, n blue. In 3rd day , min(m, n) will commit suicide. In 4th day , max(m, n) will commit suicide. If m=n, they all commit suicide in 3rd day.
12 June, 2011 at 10:03 pm
Anonymous
As a nudge for people who are skeptical that the foreigner has introduced information to the system, consider that the situation would be different (and no villagers would die) if the foreigner made his comment individually to each villager.
12 June, 2011 at 10:04 pm
Anonymous
That is, individually and privately.
20 June, 2011 at 1:38 pm
Winston W. L. Ho
Shang1 nao3 jing1 ah! (crack my brain) The person who came up with this puzzle is a genius. My understanding to hopefully ‘unify’ the two solutions goes like this:
We can use a simplification (offered by Jim http://higherlogics.blogspot.com/2008/02/blue-eyed-islander-puzzle-analysis.html ) of considering a small group of 4 people wearing hats. N people wear blue hats and 4-N people wear brown hats. Every minute, if anybody deduces the color of the hat he is wearing, he has to declare it. At a certain point in time, an outsider pops in and says ‘I see at least 1 blue hat.’
If N=2, the statement that the outsider said has already been known by all the four people, long before the outsider came. So how did the people deduce the color of their hats? Why didn’t they do so earlier?
The answer I think is because the outsider provided the origin time. This allows the people to deduce the color of their own hat based on counting each passing minute. The declaration has to occur at fixed time instants.
I don’t understand the mathematics of the wikipedia entry on common knowledge, but I offer my simple common sense explanation. How does this relate to the common knowledge?
20 July, 2011 at 2:22 pm
jlflorez
My opinion is that foreigner statement break the uncertainty when one guy is seeing that nobody has blue eyes, then he is the BEP, and by induction you reach the ritual suicide in the day n.
11 August, 2011 at 2:47 am
JoshuaR
No new information is given. All islanders already know there is at least one blue-eyed person on the island.
But they need the foreigner and if you look at this problem BACKWARDS from what others have explained, you realize a key difference.
I am blue. I do not know this. I look around and see 99. Suppose I am not blue. Then a blue person sees 98. Now that person doesn’t know he is blue. Since I don’t know that I am blue, and to his mind he doesn’t know that he is blue, I might assume that HE would think that there might only be 97 blues, if I am not blue. And so on and so on until we get to the “he might think that he might think that he might think… that he is the only blue or that there are no blues.” And so he cannot kill himself until someone states for certain there is at least one blue.
In real terms, each individual will guess there are 99-100 or 100-101 blues, but none will know where they stand on that totem pole. If one guessed he were on the high end, say a brown saw 100 blues, then he might guess he is number 101, or that there are 100 only. But if he puts himself in #100s shoes, he will say, “if I am brown, #100 will think to himself that he is either #100 or not blue.” And so on. It all matters what they can guess that another knows.
As soon as the foreigner comes in, when you get to “he might think that he might think… that he is blue,” the countdown starts.
11 August, 2011 at 2:51 am
JoshuaR
No new information is given. All islanders already know there is at least one blue-eyed person on the island.
But they need the foreigner and if you look at this problem BACKWARDS from what others have explained, you realize a key difference.
I am blue. I do not know this. I look around and see 99. Suppose I am not blue. Then a blue person sees 98. Now that person doesn’t know he is blue. Since I don’t know that I am blue, and to his mind he doesn’t know that he is blue, I might assume that HE would think that there might only be 97 blues, if I am not blue. And so on and so on until we get to the “he might think that he might think that he might think… that he is the only blue or that there are no blues.” And so he cannot kill himself until someone states for certain there is at least one blue.
In real terms, each individual will guess there are 99-100 or 100-101 blues, but none will know where they stand on that totem pole. If one guessed he were on the high end, say a brown saw 100 blues, then he might guess he is number 101, or that there are 100 only. But if he puts himself in #100s shoes, he will say, “if I am brown, #100 will think to himself that he is either #100 or not blue.” And so on. It all matters what they can guess that another knows.
As soon as the foreigner comes in, when you get to “he might think that he might think… that he is blue,” the countdown starts.
…
Edited because I forgot to say, but of course within minutes of reading the induction solution starting from 1, I was sure that was simple and that was it… until I really started to think about it the other way, that the foreigner didn’t really add new information, that it didn’t matter what would happen IF there were only 1 blue because that situation is impossible because there are certainly at minimum 99 blues to every person on the island… But then if you look at it in such a way as to say, “I know this but he may not know that if I am in fact this…” you realize that the induction method does indeed work.
23 August, 2011 at 5:27 am
Henry
All blue eyed people see 99 other blue eyed people and that everyone else (900) are brown eyed. So they all know only 2 alternatives exist: 99 and 100 are the only alternatives. They also know everyone of the blue eyed people know of at least 98 are logical and honest so day one equal to 98.
Day 2 then is 99 and no one dies. On day 3 (set to 100 blue eyes) the whole village commits suicide under the mistaken (for 900 of them) belief they have blue eyes.
The reason is that the brown eyed people had different information then blue eyed people they would set the alternatives at 100 or 101. So day 1 was set as 99, day 2 was 100 and day 3 included them.
Even when everyone else showed up at noon (they would assume the brown eyed people had figured out they were brown eyed) based on all blue eyed people (themselves included) lining up in the square.
So the Foreigner doomed 900 people to commit suicide by flawed logic.
23 August, 2011 at 8:43 am
Henry
I have an additional clarification before someone else brings it up. The logic of the 100 days of waiting. Each other person could only see -1 blue eyed people. This math works but does not make sense logically. Each blue eyed person knows that there are at least 99 people and at most 100.
Even if the other people only see 98 no one can see <98. This is common to the whole group so there is no need to start at 0 as no one can see less than 98 blues. I does not matter what the subjective count is or what someone else might think they think someone else thinks.
The absolute (objective) answer can only be 99 or 100 for everyone. All 999 other people see at least (98- blue eyes for blue eyed people and 99 for brown eyed people) if I am not blue eyed.
They see 99 and 100 if I am blue eyed.
So we start at the largest impossible answer of 97. We all know no one will kill themselves now as no one can see just 97 blue eyes. So at the next noon (Day 1) we advance to 98, Day 2 is 99, Day 3 is 100. No one dies on day one or two so I go kill myself on day 3.
What I don’t know (if I have blue eyes) is that the brown eyed people started at 98 because they know that everyone must see at least 99. They know the absolute (objective) answer is 100 or 101. For them Day 1 is 99, day 2 is 100 and now on day 3 they think the answer is 101 blue eyed people (including themselves) so everyone dies on day 3.
3 January, 2012 at 3:37 am
Sean Eberhard
I don’t think this argument works: I think that the blue-eyed people really do kill themselves on day 100. The problem depends delicately on what each person knows, what each person knows each other person knows, what each person knows each other person knows each other person knows, and so forth.
Imagine for instance that Adam is a blue-eyed person. Adam sees 99 (other) blue-eyed people, and therefore knows that there are exactly 99 or 100 blue-eyed people in total. Adam may then reason as follows: “Suppose there are 99 blue-eyed people. Consider one of the blue-eyed people I see, Bob say. Bob sees 98 other blue-eyed people, and therefore knows that there are either 98 or 99 blue-eyed people in total. Bob may then reason as follows: ‘Suppose there are 98 blue-eyed people. Consider one of the blue-eyed people I see, Carla say. Carla sees 97 other blue-eyed people, and therefore knows that there are either 97 or 98 blue-eyed people in total.’”
Reasoning like this can get you all the way down from 100 to 1. The point is: each person may know himself that there are 99 or 100 blue-eyed people, but each other person only knows that each other person knows there are at least 98 blue-eyed people, and worse each person knows only that each person knows only that there are at least 97 blue-eyed people, and so on.
I hope that made sense.
15 November, 2011 at 9:25 am
Yale Dikes
figured out a solution that works; it uses only one inductive point at a time, a stable one, that is shared by all members of the party. And gets the blues gone in two days if they are equal to or less than the size of the other group. The …others may take longer, the others being the larger party. Either the next day, or after the others leave switch to the higher commonly viewed number.
Take 100 bs and 101 gs.
The method goes as follows The {b’s}* will see 99 the {G’s} will see 100 b’s but {G’s} will know that the b’s see 99 blues ( as the b’s they see can’t see themselves), they don’t know their own color, The {g’s} will likewise know that all the b’s they see will only have a shared view of 99 of the commonly viewed bs . The {b’s} will see 101 g’s and know they only have a shared view of 100. The lower number, call it lower commonly viewed number , is used by both as the starting point to avoid the inductive latter ; thus the starting point for both is 99. ( trigger point for both 98 blues or 98 greens) . It is not met. All stay. Day two: number goes to 100, b’s all see 99, and leave. Day three, either greens know there are two values and leave or the number is raised to to 101 and they leave.
The method goes as follows The {b’s}* will see 99 the {G’s} will see 100 b’s but {G’s} will know that the b’s see 99 blues ( as the b’s they see can’t see themselves), they don’t know their own color, The {g’s} will likewise know that all the b’s they see will only have a shared view of 99 of the commonly viewed bs . The {b’s} will see 101 g’s and know they only have a shared view of 100. The lower number, call it lower commonly viewed number , is used by both as the starting point to avoid the inductive latter ; thus the starting point for both is 99. ( trigger point for both 98 blues or 98 greens) . It is not met. All stay. Day two: number goes to 100, b’s all see 99, and leave. Day three, either greens know there are two values and leave or the number is raised to to 101 and they leave.
15 November, 2011 at 9:29 am
Yale Dikes
There are some, like suicide guy above, who think distribution like 99/ 100 create a problem for the inductive method used to solve the problem. Essentially, if there is a distribution of 99 blues and 100 browns poor browns all see 99 and what do they do?
They wait.
Remember the starting point, 98 leave iff 97) . no blue or brown leaves. Then 99 (leave iff 98). The blues leave. The hapless browns are spared. Than they leave via elimination if they know there are only two values, or by raising the induction point to 100 the next day. They never have to face the choice the apparent paradox purports.
15 November, 2011 at 12:27 pm
Yale Dikes
Damn, screwed up with an illegitimate move. The induction points are different I inadvertently scewed it.
15 November, 2011 at 12:35 pm
Yale Dikes
Same applies to Henry where the number that a brown eyes will see is 100 meaning the possiblities would be 100 or 101, and the same reasoning would generate the number of off 99, and he would illegitimately want to leave with the blues on day 3.
Shhez. That the trick. Finding a stable induction point ( for blues and greens) other than 1. It seems that the traditional way might be the only way to accomplish this.
15 November, 2011 at 12:39 pm
Yale Dikes
Same applies to Henry’s solution : For green’s the possibilties are 100 or 101, so his method will generate 99 for them, not the 98 it does for blues.
15 November, 2011 at 12:41 pm
Yale Dikes
The only stable induction point seems to be 1. Even though they all know there is more that they all know , they can’t use it to pick a unique number. That’s the rub.
20 November, 2011 at 8:27 pm
Blue Eyes: The Hardest Logic Puzzle in the World « Guzman's Weblog
[...] Tao’s The blue-eyed islanders puzzle – repost Share this:TwitterFacebookLike this:LikeBe the first to like this post. [...]
24 December, 2011 at 12:59 am
David Ho
Hello prof Tao,
I really enjoyed going through your Diversions page. I have tried several puzzles and solved them. I thought the blue-eyed islanders puzzle wasn’t very difficult. The easiest way for me to solve these is to try simpler cases and induct upwards. So, I just thought of a room of 4 people, 3 with brown eyes and 1 with blue. Then I tried with 2 brown eyed people and 2 blue eyed people. It was easy to induct upwards from there.
The one puzzle that has me a bit unsure is the white/black sand mixture problem. I have sent you an email about it because the solution wasn’t listed on your webpage. I have also scoured Google and haven’t found a reasonable answer. I’ve even posted it on a puzzle forum and it has caused some controversy. I approached it several different ways and examined each conclusion. First, I tried using an exaggerated approach to make the solution more obvious. So, instead of one teaspoon, I transferred the whole bucket of white sand into black and mixed. This obviously leads to an equal mixture of impurities. I then tried a simplified model using small cubes as sand particles. This assumed even distribution in the mixture. In this case, I had to make some pretty big leaps in logic by making some assumptions that might not necessarily happen in the real world. Finally, I tried to solve it using algebraic techniques. This was a bit tricky, for me anyways, on the second transfer of mixed sand. It seems that the mixtures are still equal.
So, will you tell me if I’m right? Is the sand mixture equal in impurities? I can finally sleep at night once I know the right answer. :-) Thanks.
2 January, 2012 at 2:44 pm
David Ho
Nevermind. I figured it out. The solution should look something like this:
Let X,Y = white sand, black sand bucket, and t = teaspoon and 0 <= t <= 1. So, removing one teaspoon from Y to X:
Y-tY ; X + tY
Removing a teaspoon from X + tY to Y – tY we eventually get:
t/(t+1) * X + t/(t+1) * Y in one bucket and 1/(t+1) * Y + t/(t+1) * X in the other. What this shows is that the amount of impurity X in one bucket is equal to the amount of impurity Y in the other and vice versa. This solution also shows that by taking no teaspoon (t=0) the results collapse to what we expect: X in one bucket with no Y and vice versa. It also shows that if we take t=1 (mixing the entire bucket into another and then splitting it back), we have a completely equal mixture in both buckets as expected; i.e., 0.5X + 0.5Y and vice versa.
3 January, 2012 at 3:11 am
Sean Eberhard
A zero-algebra way of seeing this solution is to observe that each bucket has the same starting as ending volume. Therefore the amount of black sand in the white sand bucket must be the same as the amount of white sand in the black sand bucket.
14 January, 2012 at 3:30 pm
Tessa
Take in account that I am young;
If the foreigner said his statement directly to an islander, the islander would think he had blue eyes and therefore kill himself. But, if no one knows what color eyes they have after the one dies, they can’t very well kill themselves. So, if one islander told another that they have blue eyes, each would kill himself for knowing and sharing that information. And it seems that in the end they either all would die, or they all would live.
Now if the islander said his statement not directly towards one islander, no one would kill themselves unless another told them what color eyes the other had, resulting in more than one islanders dying.
And then there’s the chance the islanders didn’t speak the foreigner’s language (whatever that might be, if not English), then the islanders would move on about their lives. But how would an islander know what color another’s eyes were if they didn’t understand the foreigner?
Ultimately, there could be any number of outcomes to this puzzle, and I could carry with those but I’d probably end up confusing myself.
18 January, 2012 at 7:07 pm
Tyrocomp
OK, I’ve been racking my brain about this for a few days, and I actually think the first solution is correct. The inductive solution seems to assume that even if n>2 that the islanders will induct based on someone following the reasoning of n=1. I don’t think this happens except in the (rather obvious) cases of n=1 and n=2.
Take the case of 100 BEP, each of them numbered BEP1, BEP2 and so on.
BEP1 thinks there could be 99 BEP’s (because that is what he sees) and he assumes that he is not a BEP. He then thinks from the perspective of BEP2. BEP2 would then think that there are 98 BEP’s because BEP1 is not a BEP, and in BEP2′s thoughts neither is he.
Then we move onto BEP3. The problem is, from anybody’s perspective (and while we are in this little world BEP1 has created in his head) BEP3 sees 98 BEP’s. He doesn’t automatically assume that there are 97 BEP’s In BEP1′s world, It is a fact that there are 99 BEP’s visible, and any of those 99 are going to see 98 BEP’s.
The inductive solution seems to say
1. BEP1 assumes he is not blue eyed, and sees 99 others
2. Given the above BEP2 assumes he is not blue eyed, and sees 98 others
3. Given the above BEP3 assumes he is not blue eyed and sees 97 others
This is not true. 3 contradicts what BEP1 will assume is a patently known fact by all BEP’s, and therefore you cannot continue the induction process.
20 January, 2012 at 4:35 am
Aadil Aman
In this post I saw that People are confused for the third color say “green”. Even if there exist a third color, Say the foreigner realizes later that he did a mistake.
But if he will say, “Ah! I am sorry. That was my mistake I wanted to say that Its good to see a green eyed person on this island!”
Saying this, he will be responsible for everyone’s death as Everyone will think that he/she is a green eyed person! So the the next day all the people will commit suicide and the story will end!
One more thing, this problem has a kind of “Circular” Logic, as the persons may think the same way or the persons may think in a different way, So their is an Ambiguity here!
21 January, 2012 at 11:06 am
X. Ying
The key point of this story is about Common Knowledge. The backward induction is based on Common Knowledge. The foreigner tells every body that these is at least one blue eye in this tribe. This becomes a Common Knowledge in this island. So backward induction works. Solution 2 is correct. Each person watching doesn’t get a Common Knowledge but a 99 level mutual knowledge in this case. This knowledge is not sufficient to support 100 level backward induction. So solution 1 is wrong.
The more details please see my blog. But you must know chinese.:-)
http://blog.wenxuecity.com/myblog/49240/201201/19041.html
http://blog.wenxuecity.com/myblog/49240/201201/19044.html
http://blog.wenxuecity.com/myblog/49240/201201/19052.html
Otherewise you can read following article. But you must know mathematics.
http://plato.stanford.edu/entries/common-knowledge/
25 January, 2012 at 1:26 am
Tyrocomp
Well, then why wasn’t it common knowledge before? Whats the difference between the following scenarios?
1. I hear a foreigner say there is at least 1 blue eyed person. Everybody heard this. Therefore this is now common knowledge
2. I see 99 blue eyed people. Each of them sees at least 98 blue eyed people, and I know that. Everybody knows that that N=98 or 99. Since 98 and 99 are greater than 1, it is now common knowledge tha there is at least 1 blue eyed person.
In both cases, I know that all other members of the island possess the same knowledge – that there is at least 1 blue eyed person (in the second place the common knowledge is actually a step further in that there are at least 98 blue eyed people).
25 January, 2012 at 9:11 am
Barry Cipra
Tyrocomp, this difference is most easily explained by starting with 3 people, say Alice, Bob, and me. If I see that Alice and Bob both have blue eyes, then I know there’s at least one blue-eyed person, and, as you pointed out, I know that Alice and Bob also know that there’s at least one blue-eyed person (because they see each other’s blue eyes). I also know that Alice and Bob both know that I know there’s at least one blue-eyed person (because Alice knows I can see Bob’s blue eyes, and Bob knows I can see Alice’s). What I *don’t* know is that Alice knows that Bob knows there’s at least one blue-eyed person, and vice versa. That’s because for all I know my eyes are brown, in which case Alice, not knowing her own eye color, wouldn’t know whether Bob sees anyone with blue eyes (and likewise for Bob). But if an outsider makes a public announcement, then I *do* know that Alice and Bob both know that the other one knows there’s at least one pair of blue eyes, and the logical process can go from there.
In sum, for 3 people, the outsider’s announcement ensures that everyone knows that everyone knows that everyone knows there’s at least one blue-eyed person. For 4 people, the announcement adds one more level of the “everyone knows that” phrase. In general, if you have N blue-eyed people, then you need N levels of “everyone knows that” nesting in order for the logic to play out, but without the outsider’s announcement, you’ve only got N-1 levels.
12 February, 2012 at 9:44 am
Florian.Biermann@gmx.de
Was the argument expressed by Nicole Krieger above finally refuted? I agree with her that the inductive argument is problematic here. It assumes that IF there was just one blue-eyed person on the island (n = 1), the visitor’s statement would make that person commit suicide on day one. That is definitely true. However, with n = 100, everybody knows that n is at least 99 (because everybody can see 99 blue eyed people). As n >= 99 is mutual knowledge, from the fact that nobody committed suicide on day one no islander can deduce anything, because only under COUNTERFACTUAL circumstances, i.e. if n = 1, somebody would have committed suicide on day one. This means that with n >= 99 being mutual knowledge, under no possible state of the world somebody would have killed himself on day 1. Now we apply induction: Nobody will kill himself on day 1 under any possible state of the world, therefore the fact that day one passed without anyone committing suicide does not give any additional information to a villager who is unsure whether the state is n = 1 or n = 2, even if such a villager would exist. In particular, it does not tell him that n = 2 is the true state of the world. This goes on for 98 days. So with n >= 99 being mutual knowledge, it is impossible that under any possible state of the world somebody would have committed suicide until day 98. So the fact that indeed nobody has committed suicide until day 98 does not give any information to any villager about the true state of the world. Now day 99 begins. As a villager, I just know that the n = 99 or n = 100. The fact that 98 days have passed without anyone committing suicide does not add to my knowledge. Hence as a villager, I do not commit suicide at day 99, regardless what is the true state of the world. Now day 100 begins. Again, under no possible state of the world, somebody would have killed himself up to day 99. So again, I can deduce nothing from the fact that 99 days have passed without anyone committing suicide and I am again left with the two possible states of the world n = 99 and n = 100, prescribing me to stay alive.
One cannot start an inductive argument with a basis which is known to be NOT TRUE. “Assume n = 1…” WAIT! n CANNOT be 1 if we assume n >= 99 to be mutual knowledge.
12 February, 2012 at 6:02 pm
bert
There’s one thing that bugs me here, and any help understanding this is appreciated.
When thinking of this as a kind of game, the strategy of committing suicide on the n-th day if you see n-1 people with blue eyes, that is clearly a correct and working strategy for the players to collectively solve the question of who has blue eyes. It’s also the fastest and simplest stratey.
What the foreigner brings to the table is that he gets all the players to agree on two things: when to start counting days, and the eye color they will try to figure out. He’s not so much giving any information about who has which eye color, he’s just starting the game.
If there are 1 or 2 islanders with blue eyes, it’s clear to me that the conclusion is inevitable and that they will know for sure. But for 3 or more players, it gets fuzzy for me. I can see how they can solve the puzzle if they all use this strategy, but I don’t see how they know that this is the strategy that everyone must be using, or that everyone agrees to even play the game at all?
12 February, 2012 at 6:06 pm
bert
Something feels wrong to me about the proof by induction, but I can’t quite put my finger on it (probably because there is nothing wrong with it). It seems like it’s inducing over two things simultaneously, the number of blue eyed islanders, and the number of days. It’s as if we skip from day n-1 with n-1 blue eyed islanders, to day n with n blue eyed islanders, without considering day n-1,n-2,.. with n blue eyed islanders?
17 March, 2012 at 1:13 am
Ahno
Wow, a way to kill all logical bastards on the island indifferently to their eye color. :)
18 March, 2012 at 8:16 am
Ahno
Also actually I only see one mess in this solution and that is adding days as variable. Because someone thinking of something is not time related thing. That is why there probably be an avalanche effect at some random point of time.
By the way if try to resolve this “information poisoning” case when there are up to 4 blue-eyed (B) and up to 3 brown-eyed (R) islanders it’s funny and shows how the logic works in intuitive way:
1x B: I see no one else B but me -> suicide;
2x B: If he didn’t kill himself then I am B too -> double suicide;
3x B: If there were only 2 of them they should kill themselves from previous logic but they are not then it’s 3 of us -> mass suicide;
4x B:
1 step:
1,2,3,4 B: oh there are 3 or 4 blue eyed, wait and see;
2 step:
Random B: no one takes action then there are not 3 but 4 blue eyed because it’s evident for those 3 if its actually 3 B from previous logic -> own suicide -> those 3 see evident thing -> mass suicide
etc >_<
11 April, 2012 at 1:55 pm
JO
Ok, I just came upon this puzzle yesterday and read most of the comments above.
From what I can see there is a problem with the puzzle to begin with.
First of all If there are 4 or more people with blue eyes to begin with they won’t need some one to tell them that at least one person has blue eyes. they will have figured it out on their own and commited suicide long before someone told them. This puzzle only seems to work with 3 or less blue eyed people.
Br = Brown eyes. His point of view doesn’t matter.
(Bl) = Blue eyer point of veiw. He/she doesn’t know if he is blue or brown.
‘Bl’ = (Bl) know that at least one other person’s point of view is what matters, because all the others you know have blue eyes and each of them are thinking of the other blue eyers assuming the (Bl) thinks that he/she has brown eyes.
Bl = all the other blue eyers.
Beyond this it doesn’t matter, because you know for a fact that all the other blue eyers are thinking only one of two things 1. (Bl) has blue eyes or 2. (Bl) has brown eyes.
1 blue eyer needs some one to tell them that their is one to figure it out. System is stable before the statement is made.
Br / (Bl)
2 blue eyers need some one to tell them that their is at least one of them to figure it out, because they can only see one of them and figure that he/she doesn’t know it.
System is stable before the statement is made.
Br / (Bl) / ‘Bl’
3 blue eyers need some one to tell them that their is at least one of them because even seeing two other can figure on each one not knowing about themselves and knowing one other doesn’t know, but can at least see one. Which each may think that the others think their is only one, assuming that him/herself is not blue eyed.
System is stable before the statement is made.
Br / (Bl) / ‘Bl’ / Bl
4 Blue eyers don’t need anybody to tell them. they already know. Each one sees that their are 3 others and know that at each one of them doesn’t know his/her own, but can see at least 2 others. It is known by all that all the others know that their are blue eyed people.
System is unstable before statement is made. they all commit suicide from the get go.
Br / (Bl) / ‘Bl’ / Bl / Bl
5 on up is all the same. Just more blue eyers that can see each other.
I tried to explain this best I could. Let me know what you think.
30 May, 2012 at 4:30 pm
Lenoxus
Obviously, prior to the visitor’s statement, the deduction process won’t work with just 1 blue-eyed person and 199 browns. That one blue will never know if her eyes are brown, blue, green, or other.
Because of this, it doesn’t work with 2 blues and 198 browns, either. This is because from the perspective of each of those 2 blues, it is exactly the same as if the other blue was the only blue. This is the key thing to grok.
Now, if it doesn’t work with 2, then it won’t work with 3 — because from the perspective of each of those 3, it is exactly the same as if the other 2 blues were the only blues. Those 3 have no way of knowing themselves to be blue and not brown. From their point of view, it’s the same as in the previous paragraph.
If it doesn’t work with 3, then it won’t work with 4 — because from the perspective of each of those 4, it is exactly the same as if the other 3 blues were the only 3 blues. How would the 4 blues know that they were 4 in total? Why wouldn’t they each think “I might be one of 197 browns”?
If it doesn’t work with 4, it won’t work with 5 — for the same reasons as above.
At no point can anyone deduce their own eye color, because they have no reason to expect anyone else to deduce their own color based on people not leaving, which is what the whole puzzle is all about.
Once we add the visitor’s statement, however, it all works.
A lone blue would have to leave on Day 1. (She knows that there are either zero or one blues, but the visitor’s statement excluded the zero, so therefore there is 1 blue — himself.)
Because a lone blue would have left on Day 1, then 2 blues (if there are exactly 2) would deduce that there must be 2 blues, and leave on Day 2.
If there are 3 blues, then they, each knowing that the other 2 “ought to” have left on Day 2, will leave on Day 3.
If there are 4 blues, then they will each see the situation the same as if there were only 3, and will thus “expect” those 3 to leave on Day 3. When that doesn’t happen, they conclude the only other possibility — that there are 4 blues and not 3 — and leave on Day 4.
Etc.
29 May, 2012 at 7:49 am
Does P contain languages decided solely by incomprehensible TMs? | MoVn - Linux Ubuntu Center
[...] obstructs my own understanding of a broad class of problems that includes Terry Tao’s Blue-Eyed Islanders Puzzle, Dick Lipton and Ken Regan’s Urn-Choice Game, and their hybridization in the context of [...]