The blue-eyed islanders puzzle

Pro. Tao,

I really can’t figure out the “blue eyed islanders” puzzle, and there is no post option in that web page, so I can only ask you here:

What is the correct answer?

I tent to think the Induction is invalid.

The second argument is flawed. The people will never know if there are 101, 100, 99 blue eye people in the tribe, as they wouldn’t know there own eye colour. The person would have to give the number of blue eyed people for the second argument to work, because then the brown eyed people will know they have brown eyes.

Prof. Tao,

Sorry for having led this web page into the discussion (since it is originally under “career advice”). However, this is what I think:

Mathemacality has a limit as applied to reality. Mathematical induction starts with K=1, but the reality is GIVEN K=100, which does not arrive as a sequence from K=1. So the sequencial reasoning isn’t valid here. The blue-eyed islanders could comprehan their reallity with our induction only when they want to (that is, if they are mathematical souls), but they don’t have too (which does not necessarily violate logic). In fact one could argue that, since induction is not necessary therefore following it is not logical, therefore there will be no effect for the islanders. Or if they are indeed mathematical souls, then I go with Philipp: They will all commit suicide even if the outsider never came. Or K= 100 is an impossible situation to be a reality (so the puzzle contradicts itself).

However, my intuition goes with the limitation of mathematical reasoning. I am reminded another puzzle, though not the same, but also about the mathematical handling of information:

(supposedly a real story, I might not get the time right) During WW2, a city (in Poland?) made an anouncement: A military exercise would be conducted some day in the following week, yet in order to get the residents of the city used to unprepared situations during the war time, the specific day of the exercise would not be given so that it would come as an suprise. A mathematician (name I forgot) immediately reasoned:

The exercise can not take place in Sunday (the last day of the week), since if so, by Saturday night, people will know (therefore not a suprise). But then it can’t be Saturday either since if so by Friday night people will know that it will happen on Saturday since the possibility of Sunday is already ruled out. But then, Friday, Thursday, Wednesday, Tuesday, Monday are not valid days either. Therefore the exercise can never happen!

The exercise still took place on Wednesday, as nobody had induced, therefore still a suprise as promised.

Dear Philip,

In the situation you are considering that is no visitor visits island, if there is only one blue eyed person, how would he know he is blue eyed. Quoting you “If there was only one blue-eyed islander, (s)he would have committed suicide” I think its not true in the scenario you are considering.

I believe rather the visitor is indeed adding some information.

The version I know has only the blue-eyed people killing themselves (why do these puzzles always involve so much death, anyways?). The follow-up question is then to ask what is the new information. It’s easiest to figure out that question by studying the case where only two people have blue eyes.

For the answer, here’s an old thread from rec.puzzles.

Thanks Tao 8)

The ever exceeding tower of truths about knowledges has to be flatted to be common knowledge. The function of the visitor.

Now I can reason about other Islanders believes.

Great puzzle 8)

This was always a great puzzle. The key to understanding it, as a few have pointed out, is to understand that the puzzle assumes a logical foundation not found in the real world. It’s a model for firm mathematical reasoning and as such operates under a very strict set of rules. A bunch of real world people like you and I on an island would not kill ourselves, but these robot-like entities would, because they’re following strict logical rules as defined by the field of formal logic and the specifications of the problem.

Under such a formal system, the inductive reasoning is sound, and the basis case of n == 1 is ABSOLUTELY REQUIRED. Mathematical induction is nothing without both a proper basis and inductive rule. And remember folks, this is a math/logic problem, not a reflection of any real world behavior.

The induction breaks at the point where the foreigner names the number of blue-eyed people on the island.

If, in this case, he says “how nice to see another blue-eyed person”, then if that blue-eyed person cannot see anyone else with blue eyes, he must commit suicide. However, if there are two blue-eyed people, all they have been told is that there is *another* blue-eyed person on the island… which they already knew, because they can see them. (Everyone with brown eyes can see two blue-eyed people, but cannot tell them so.) So nothing changes.

Had he said “a hundred blue-eyed people”, then whilst everyone would could see 100 blue-eyed people could breathe a sigh of relief, everyone who could see only 99 blue-eyed people would pretty much have to kill themselves at the earliest possible opportunity. (The remainder of the islanders would have to die the day after, of course – because if everyone around you has one of only two eye colours, including your immediate family, it is illogical to hope you were some kind of genetic throwback with a unique eye colour! Add the possibility of green eyes, though, and the rest of the islanders could survive.)

And of course, if he had slipped up and said “101 blue-eyed people”, every *brown*-eyed person would have had to kill themselves the next day, because they could only see 100 blue-eyed people; whilst the blue-eyed people would have been highly amused at the silly foreigner until the next lunchtime, when the horrible truth dawned on them that they now knew they all had blue eyes…

BUT if he’d said “102 blue-eyed people”, an entire island would have been chortling merrily about silly foreigners who had no manners and couldn’t count.

C’est la vie. Let’s hope they never invent mirrors, or drink from streams.

Mneh. I was right, but for the wrong reason.

My initial conclusion neglected nth-order effects, of course, as is obvious to anyone. However, as several other people have written, if we allow for nth-order effects, the islanders would have had to kill themselves spontaneously – specifically speaking, each islander would have had to kill themselves M+1 days after the two conditions (all islanders know the rule; M people with eye colour X still alive after M days) are met.

Clearly they haven’t – which either means they’re already on a countdown, or we can discount nth-order effects altogether. Either way, the foreigner’s faux pas adds no existing knowledge, and therefore has no effect.

“All the tribespeople are highly logical and highly devout, and they all know that each other is also highly logical and highly devout.”

Which means they only have first-order knowledge of each others’ reasoning abilities. Nobody is certain that everyone else knows they’re highly logical and highly devout, so the inductive case is broken.

Part b of this puzzle: The visitor waits until 12:01 the next day, then announces he was only kidding. What effect, if any, will this have on the visitor’s life? :)

Sunglasses.

Hrm… I simply don’t follow the reasoning in the induction. Peeling it apart:

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

Why do they realize? If none of them are told their eye color from birth, and the speaker has only indicated that some member of the tribe has blue eyes, no individual in the tribe has a way of knowing whom it is, unless the speaker deliberately points them out. If N were the total number of members of the tribe and not the total number of blue eyed people, this would make sense, but as is it doesn’t.

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

Why would they reason that? It’s as if you’re saying: 1. N people have blue eyes. 2. I don’t have blue eyes. 3. There must be N-1 people with blue eyes. This doesn’t make any logical sense. Are you sure you’re not confusing N being people with blue eyes versus total tribe members?

“, and so they will all commit suicide n-1 days after the traveler’s address’.”

This seems pulled out of a hat. If we take the rule of the culture/religion seriously, they have to kill themselves the day after they find out. Why would they wait for N-1 days? Or any number of days? Unless for some reason they didn’t know until that time — but whether or not they realize something yet only comes below…

… I can’t even get any farther through it. Am I seriously missing something or is the problem’s wording just totally mangled?

The basis is incorrect.

“Proof: We induct on n. When n=1, the single blue-eyed person realizes that the traveler is referring to him or her”

When n = 2, the two blue-eyed people think that the traveler is referring to the other blue eyed person.

Only in the situation that there is one blue eyed person does any state change occur, otherwise, no new information is being given to the islanders.

Phillip, I think you are over complicating things with your mathematical inuendo. It’s not impressing me. Other people might be blown away with it and think, “he must be right.”

So let’s say you have 2 blue eyed people, then how after 2 days would they kill themselves? If you had 3? Why would they kill themselves after 3 days.

Let me put myself in the shoes of a blue eyed person. I don’t know my eye color, but I see 2 people with blue eyes. How do I know I have blue eyes. He didn’t give a number. I am not going to tell those 2 their eye color and no one is going to tell me mine. So why would I just kill myself without knowing?

Now, let’s assume I am a brown eyed person. I see 3 people with blue eyes. After 3 days… would I kill myself? Do I have blue eyes too? see, that is the unknown and the visitor gives no indication as to the number of blue eyed people. Common knowledge says that what the visitor claimed is what people already knew. So therefore, argument 1 is correct because he didn’t tell the people anything knew. Also, since he is not of their religion, he doesn’t have to kill himself. Worse case scenario would be that the villagers expect him to commit suicide but if he is not part of their religion, then there should be no effect.

Hi from Adelaide, Terry. You’re quite well known back in your hometown!

There are two faults with the puzzle.

1) It tells you, but assumes that the islanders know, the exact numbers of people with eye colours.

2) The statement was clearly “how unusual it is to see another blue-eyed person like myself in this region of the world”, but Argument 2 is based on the assumption that at least 1 person (to start induction) worked out their own eye colour from that statement.

The puzzle would have been more interesting if it didn’t have these various interpretations, but then perhaps there wouldn’t be as much discussion and interest due to the lack of ambiguity!

I personally believe there would be an argument 3) based on the exact wording of the puzzle… which is that 100 days after the speech, nobody has committed suicide.

The following argument works for me.

Case 1: There is only one blue eyed person (A).
Day 1: A thinks there are 0 or 1 blue-eyed persons. Foreigner says atleast
1. So he immediately deduces it must be himself.

Case 2: Two blue eyed (A,B)
Day 1: A thinks B thinks there must be 0/1/2 blue-eyed. Foreigner speaks.
Day 2: 0/1 case covered by Case 1. So it must be 2, A sees that B is one
blue-eyed and the other one must be himself.

Case 3: Three blue eyed (A,B,C)
Day 1: A thinks B thinks C thinks there must be 0/1/2/3 blue-eyed. Foreigner speaks.
Day 2: 0/1 case covered by Case 1. Remaining 2/3.
Day 3: 2 covered by Case 2. So there must be 3 blue-eyed. A sees two
other blue eyed. So the other one must be himself.

And so on.
I think this is the same as induction , which somehow was not very intuitive to me.

According to the rule of the game “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.”
If it weren’t for the rule saying “the following day”, on the 100th day, as the 100 blue-eyed people go to the village square to commit suicide, the 900 brown-eyed ones, seeing the blue-eyed ones walking there, would then know there were only 100 blue-eyed people in the world, and so would go there too at the same time on the 100th day to also commit suicide. But then because no villager would know whether each of the others was there for being blue-eyed or for being brown-eyed, they’d all turn around and walk away, and so equilibrium would be kept.
The rule dividing something continuous, time, into something discrete, 24-hr periods from noon to noon, is as much responsible for the suicides, 100 on the 100th day and 900 on the 101st day, as is the maths of knowledge discovery. The statement of the foreigner provides the first “tick” through this discrete medium.

This is not a puzzle. There is nothing to figure out. This is merely a test of reading comprehension. The “puzzle” clearly states that the islanders are not allowed to discuss eye color. The foreigner makes a general statement, not a specific statement. He mentions he sees a blue eye person, he doesn’t say he sees 100 blue eye people.

The rules of the religion (again, reading comprehension) state that if a, “tribesman discovers his or her own eye color” they are to commit suicide. The foreigners comment is not directed at any specific person, so no one has any reason to think that they have blue eyes. They can all clearly see other tribesmen with blue eyes, so they can safely assume that the speaker was referring to them and then instantly forget about the whole thing.

Anything else is speculation and is not based upon the information provided. For any of the previously mentioned contrived theories to be anywhere near plausible, we have to assume a number of things that are not mentioned in the original statement, such as intelligence and reasoning ability of the tribesmen, mathematical knowledge, curiosity, memory (100 days is a long time), and even the average lifespan or even if they are nomadic and intermingle with other tribes, etc.

This is not a mathematical problem, this is an English problem and quite a few of you have failed at reading comprehension.

Hello, a lot of people seem to be arguing with the assumptions of the question! The point is not whether those assumptions would apply to any real-world situation, but what follows from those assumptions.

The knowledge that is required to make things go is not that every islander knows that there is someone with blue eyes on the island, but that for any configuration of the n blue eyed islanders that are present, A1 knows that A2 knows that … An knows that there is at least one person with blue eyes. The latter is much more in terms of information.

> although the islanders are not initially aware of these statistics

So why shouldn’t a brown-eyed islander assume he/she has green eyes?

Wouldn’t EVERYONE commit suicide? After all, if the blue eyes eventually equal zero, then a logical person would know this, and realise there eye colour must be brown…

Isn’t Faith the only genuine form of common knowledge in humanity supposedly?

Isn’t form of common knowledge the mathematical form for meditation? It is my experience too: Faith is only a fancy word for trust: When one completely (in our language: “Commonly”) trusts the universe, trusts its elements Commonly, one sees the universe as a through entirety.

The meditating individual is already aware to the fullness of the blue-eyedness of the universe, but lacks self-awareness (reality confirmation). Then the visitor’s reality confirming message touches in: n = 1 ! (In Zen Buddhsim, it could take form in sound, imagery, line of poetry, thought, suddent trivial happening etc.). Infinity is thus reached (induction).

The individual then suddenly becomes aware to his own blue-eyedness. The individual becomes enlightened.

It actually makes better sense to understand our original puzzle the above way (even logicaly) with favorable enlightenment but ritual suicide as the consequences. Isn’t it consistent with our actual life experience in many situations too: We are already seeing it in full, but just lacking that final piece of reality to set in, and so we get stuck (like in a love relation)? Our conciousness system is in fact highly unstable towards enlightenment, like the Daoist sages say: The Dao is simple and the road to it flat, the foolish miss it, the clever overlook it.

John,

“knowledge” could be understood as interaction. (For instance, one could say two objects have knowledge about each other through gravitation). With agency I meant human agency.

If some1 doesnt sees any logic about my argument..do let me knw ;)

There exists a Stanford web paper 1997 discussing a variant of the Richard Borcherds [5 February, 2008 at 9:19 pm] variant of this problem by John McCarthy et al [or Nikos Drakos, Leeds], translated by Yasuko Kitajima using Kripke-structured semantics.

Often, to be logical is to be irrational.

I have a question: why do we need an outsider?

Does it make a difference if an islander breaks the custom and declares: some of you have blue eyes?
Does it make a difference if the one who declares it has brown eyes or blue eyes (he himself can’t know which).

Imagine: there are 10 people with blue eyes, 90 with brown eyes.

One of them breaks the silence and says: some of you have blue eyes. After that, all respect the traditions again.

Is the introduction of the outsider mathematically necessary or is it just so that in the example the islanders don’t have to violate their tradition?

regards,
peter

Dear John,

thanks for your answer, I thought so too, but this common knowledge problem did quite upset my intuition so I didn’t know if maybe I missed something.

Regards,
Peter

I really don’t get why anybody would kill themselves in this case!

Gives this bit of information:
“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).”

We have to believe that:
* all the blue eyed islanders believe there are either 99 or 100 blue eyed islanders.
* all the brown eyed islanders believe there are either 100 or 101 blue eyed islanders.

The visitors comment doesn’t come as a surprise to anyone as it is common knowledge that there are blue eyed people on the island.

“(and they all know that they all know that each other is highly logical and devout, and so forth).”
Given this information we can reason that everybody understands that none of the others know what eye color they have.
Since the total number of blue eyed islanders isn’t given to anybody but an outsider, the islanders will not react because none of the blue eyed islanders commit suicide as they know none of the blue eyed islanders would know that they are blue eyed.

The proof for argument number 2 goes like this:
“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.”

This makes sense as the one blue eyed person would not know of the existence of other another blue eyed person before it is mentioned by the visitor.

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

Correct

“and so they will all commit suicide n-1 days after the traveler’s address”.”

This does not make sense to me. Each islanders knows that, like themselves, none of the other islanders know what eye color they have and therefore do not have any reason to kill themselves! The same argument is valid even though nobody has committed suicide after n-1 days! Everybody still knows that none of the other islanders know their eye color and all believe the travelers comment could just as well have been to any of the blue eyed islanders as to him/herself.

“But when n-1 days pass, none of the blue-eyed people do so (because at that stage they have no evidence that they themselves are blue-eyed). After nobody commits suicide on the day, each of the blue eyed people then realizes that they themselves must have blue eyes, and will then commit suicide on the day.”
To me this doesn’t make any more sense than the statement above. The fact that nobody commits suicide when the n-1 days have passed still doesn’t mean that you have blue eyes as each blue eyed islanders knows of n-1 other blue eyed islanders the comment could have been directed to.

Let us say that n-1 blue eyed islanders commit suicide after n-1 days. That would still not give the last blue eyed islander a reason to kill himself! He would still not know whether or not the comment was directed to him unless the visitor says it once more after all the other blue eyed islanders have killed themselves.

I am therefore in favor of argument number 1. Nothing happens.

Alright, John and Saad, I get it now.
Thanks for the thorough explanation.

I’m brown-eyed. I see 2 blue-eyed people. They don’t commit suicide. Why don’t I deduce I have blue eyes?

Charles,

Because the 2 blue-eyed people you see both commit suicide 2 days after the stranger’s address. As I said in my answer above, that confirms that there were only 2 blue-eyed people on the island. Remember, the pattern is that if there are N blue-eyed people, N days after the stranger’s address, they’ll all commit suicide.

If the religion forbids them to know their own eye colour, and they are all highly devout, why would they engage in logical games to discover their eye colour? A highly logical highly devout islander would surely realise the peril of engaging in that line of reasoning which might allow them to discover their eye colour and therefore reason alternately saying:
“Everybody can see people with blue eyes, so this stranger has told us nothing new.” and subsequently put the other way of reasoning out of mind.

Is it truly ‘illogical’ to reason in that way?

Peter

Saad / Guest – All the stranger said was that he sees people with blue eyes. He didn’t say how many. There could be 1 or there could be 1000. If all I see are brown eyes I know I have blue eyes. But if I have brown eyes and I see the blue eyed person (or 2 or 10 or 900) I still don’t know that I have brown eyes.

I just don’t get that leap of logic that says “2 (or 10 or 900) people died, and I saw 2 people with blue eyes, that means I can’t have blue eyes”. Why not?

Anyway, once I think I know my own eye color I have to kill myself anyway, so at the end of this it’s Easter Island. :-p

The second argument is flawed. The people will never know if there are 101, 100, 99 blue eye people in the tribe, as they wouldn’t know there own eye colour.

I agree. Plus, there’s no new information here. The foreigner merely acknowledges that there are people of blue eye colour on the island, and this is a fact previously established by the islanders through observation.

On the other hand, if each of the tribesmen were dumb enough to hold a census of eye colours and compare results, they will be able to determine the colour of their own. All it will require is for two persons of opposite colour to compare notes, the one with the lower count is blue. Since we know that everyone on the island is both logical and honourable, this will under no circumstances happen.

One way to think about it is that the foreigner’s comment, plus induction, plus the passing days creates new information.

Before the foreigner comes, every blue eyed person knows that there are at least 99 blue eyed people (since they can see them) and there may be 100 (if they themselves on blue-eyed). Likewise, every brown eyed person knows that there are at least 100 blue eyed people and maybe 101.

Since these are logical people, they would come up with and follow the inductive reasoning behind the second argument. At the end of the first day, since no one kills themselves, all the people would know that there are at least 2 blue eyed people on the island. By the end of the 99th day, since no one has killed themselves, the blue eyed people would all know that there are 100 blue eyed people and, seeing only 99 others, would know that they have blue eyes and commit suicide.

No one kills themselves. The reason is that they can’t agree on the time by which they wait for others to figure out the solution.

Say we have two blue eyed people. They are both very logical so they instantly grasp the inductive nature of the problem. So the first guy says “Hey, I will wait one day for the other blue eyed guy to figure it out. If he does, we are both dead”

the second guy thinks “Hey, I will wait five seconds for the other blue eyed guy to figure it out. If he does, we are both dead”

Then they both realize that they cannot logically predict how long they are both are going to wait to have the other guy figure it out. Logically, and instantly, they conclude that there is no way to agree on a time period to figure it out. They go about their daily lives.

This may have been said already (I have not read all comments), but the intuitive difficulty I have with the puzzle is understanding what new information the stranger provides. There can be no suicide if he provides no new information.

1 blue-eyed person (BP):
Beforehand the single BP does not know the island has BP.
Afterwards he does. So new information.

2 BP:
Beforehand every islander knows that the island has BP, but each BP does not know that the other BP knows that there are BP on the island. Or more simply, everyone knows there are BP on the island, but not everyone knows that everyone knows there are BP on the island.
Afterwards, everyone knows that everyone knows there are BP on the island, so new information.

3 BP:
Now everyone can see at least 2BP. So everyone knows that everyone knows there are BP on the island. But each BP can only see two other BP, and they do not know whether each of the BP that they see can see one or two other BP. If a BP can only see one other BP, then as with the 2 BP case, they don’t know whether that BP knows whether there are BP on the island. Therefore, each of the 3BP do not know whether the two other BPs know whether everyone knows there are BP on the island. Or more simply, everyone knows that everyone knows there are BP on the island, but not everyone knows that everyone knows that everyone knows there are BP on the island.
Afterwards, everyone knows that everyone knows that everyone knows there are BP on the island. So new information.

4BP: etc

So to break it down, you have the following theorem:

Let P0 be the proposition that there are blue-eyed people on the island, and let Pk be the proposition that everyone knows Pk-1. If there are n blue-eyed people on the island, then n days after Pn becomes true, all blue-eyed people will commit suicide.

Pn-1 is true before the stranger makes his faux pas, but Pn is false beforehand. Afterwards, Pn is true (as is Pn+1, Pn+2 etc but we don’t need those). That’s why the BP don’t commit suicide until the stranger speaks.

This is so hard to think about because we (or at least I) have absolutely no intuition about the difference between Pn and Pn+1 when n is bigger than 2.

No, EVERYONE would kill themselves on the 100th day.

EVERYONE would see on the 99th day that no one killed themselves.

EVERYONE, since they don’t know the color of their own eyes, would assume that *they* were the 100th.

And EVERYONE would die on the 100th day.

If you’re making the assumptions that lead to the second conclusion, then the real answer is the whole tribe is dead, on day 100. There’s no other conclusion.

david:

no, the brown eyed people know there are 100 blue eyed people, because they count all of them, the blue eyed people only know that there are 99 blue eyed people, so when day 100 rolls around with no death toll everyone who thought there was only 99 blue eyed people realize that there must be 100, and since they were wrong in their earlier count, that they must be one of the blue eyed people, thus they take their own lives.

The obvious answer is that the foreigner would commit suicide the next day. But the whole island would die anyway due to some flu or illness previously unseen on the island that the foreigner unknowingly brought with him.

Answer: Everyone Dies.

The foreigner is irrelevant. The instant all of the islanders gather together they will have the information necessary, and know that everyone else has the information necessary, to trigger the string of suicides. Therefore if they suicide hypothesis is accepted by the islanders, they would consider it suicidal to gather every single islander together, and would refuse to all be gathered together. If they were, they would immediately kill the foreigner for attempted murder and run away before they finished counting, and refuse to speak of the event. Since they wouldn’t know for certain that all of them had finished counting, none of them would have to commit suicide.

I only read the first few comments but am going to post this anyway. Hopefully I won’t sound like (or turn out to be) an idiot. Here’s my idea:

(i) Say there is 1 blue-eyed person (‘BEP’) on the island. The traveler’s statement will tell this person they are blue-eyed (because that person sees no other BEP) and that person will kill themselves.

(ii) Say there are 2 BEP on the island. Each will know there is 1 BEP, 998 brown-eyed people, and themselves (eye colour unknown). Each will be able to determine their own eye colour from the actions of the other BEP. On the appropriate day, if the other BEP were to kill themselves, the person would have to have brown eyes (as the dead BEP would not have seen any other BEP). If the person were *not* to kill themselves, however, that would mean the person has blue eyes, as the other person would have been waiting for the same determination. Next day both will have to kill themselves.

(iii) Say there are 3 BEP on the island. The idea is to extend this pattern to the 3rd BEP: each BEP knows that there are 2 BEP, 997 brown-eyed people, and themselves (eye colour unknown). Each BEP could then determine their own eye colour from the actions of the other 2 BEP: if they were to have brown eyes, the 2 BEP would be stuck in the same situation as above, and would end up killing themselves. When the other 2 BEP do not kill themselves at the appointed time, however, the person knows they must *not* be brown-eyed, and thus must kill themselves. Each BEP has this perspective, and so all BEP must kill themselves on the next day.

But in (iii) is where I think a mistake is made. If there are 3 or more BEP, such as in (iii), then each BEP knows something they do not in (i) or (ii), which is that every BEP (regardless of their own eye colour) knows that there is at least one other BEP. So only with 3 or more BEP in the group is it common knowledge – i.e. known to every member of the group – that *every other member of the group knows* that there is at least 1 BEP. This is different from the idea that “everybody knows there is at least 1 BEP”, which would be true in (ii).

So in both (iii) and the problem’s stated 100 BEP case, the traveler’s statement actually does not change the tribespeople’s situation, i.e. it does not give any person new information about the number of BEP. Each already knows that there is at least 1 BEP, *and* each already knows that everyone else already knows there is at least 1 BEP. Nobody starts questioning; that is, the chain of reasoning that results in many (probably grisly) demises cannot begin under these circumstances because the reasoning in (i) – and (ii) – is not consistent with this knowledge.

wow! interestin puzzle man!

Its counter intuitive but I believe its correct:

A. If there is 1 blue-eyed he will obviously deduct that he has blue eyes after the foreigner’s comment: 1 suicide on day 1.

B. If there are 2 blue-eyed, each will deduct from the others hesitation (A does not occur) that there must be one more hence they will each know they have it: 2 suicides on day 2.

C. If there are 3 blue-eyed, each will deduct from the other 2’s hesitation (B does not occur) that there must be another: 3 suicides on day 3.

And so on..

thanks to all of you for arguing any of this…proof and mysteries are made in, and from, the questions no one can answer, or ask (as the case may be). It’s been fun and enlightening reading them all.

ciao

kiki

“But in (iii) is where I think a mistake is made. If there are 3 or more BEP, such as in (iii), then each BEP knows something they do not in (i) or (ii), which is that every BEP (regardless of their own eye colour) knows that there is at least one other BEP. So only with 3 or more BEP in the group is it common knowledge – i.e. known to every member of the group – that *every other member of the group knows* that there is at least 1 BEP. This is different from the idea that “everybody knows there is at least 1 BEP”, which would be true in (ii).

So in both (iii) and the problem’s stated 100 BEP case, the traveler’s statement actually does not change the tribespeople’s situation, i.e. it does not give any person new information about the number of BEP. Each already knows that there is at least 1 BEP, *and* each already knows that everyone else already knows there is at least 1 BEP. Nobody starts questioning; that is, the chain of reasoning that results in many (probably grisly) demises cannot begin under these circumstances because the reasoning in (i) – and (ii) – is not consistent with this knowledge.”

Suppose instead of saying “at least one of you has blue eyes”, the visitor said “I like football”. Then in the case where there are three blue eyed people A, B and C, A knows that B knows that there is at least one person with blue eyes. But he does not know that A knows that B knows that C knows there is at least one blue eyed person or BEP. I find the best phrase to use is “for all A knows”. For all A knows, it is the case that B is thinking “for all I know, C is thinking “for all I know, there is noone with blue eyes on the island””. To write out A’s thought’s in full:

“For all I know, B is thinking “for all I know, C is thinking “for all I know, there is noone with blue eyes on the island”””.

It doesn’t take much imagination to imagine what the thoughts of A will be for the case where there are 4 or more BEP on the island. Naturally the thoughts of B, C, D and so on will be the same.

The way to imagine it is put yourself in the position of a blue eyed islander, and think thoughts of nested “for all I know”s. Then you will realise that the visitor does provide new knowledge when he says “at least one of you has blue eyes”. He provides new nth order knowledge, where n is the number of blue eyed people.

i thought i’d write this out at length to ensure no ambiguity about the necessity of the foreiner’s input.

before any information is given to the islanders:

if there is 1 blue-eye person on the island then he does not know there are blue-eyed people and so will never commit suicide.

if there are 2 blue-eyed people on the island then they each know there are blue-eyed people on the island but do not know if the other person does, as they do not know if they themselves are blue-eyed. for this reason it gives no new information when no-one commits suicide.

if there are 3 blue-eyed people on the island then each in turn will think the following (statement 1): “those two blue-eyed people each know there are blue-eyed people on the island, however, assuming my eyes are not blue, they do not know that the other person knows there are blue-eyed peole on the island, and so no-one commits suicide and this gives no new information. if my eyes were blue then those people would think exactly as i have and so once again no-one commits suicide and this gives no new information.”

and for completeness, so that it is clearly justifiable to extend to an arbitrarily large number of blue-eyed peole N,

if there are 4 blue eyed people on the island then each in turn will think the following: “those three blue-eyed people each know there are blue-eyed people on the island, however, assuming that my eyes are not blue, each one of them will think as in statement 1 because they do not know their own eye-colour. if my eyes were blue then those people would think exactly as i have and so once again no-one commits suicide and this gives no new information.

thus without any information being given to the islanders each blue-eyed person can form a chain of such reasoning, and no suicide occurs. the act of the foreigner saying there is a blue-eyed person doesn’t appear to give any information, however it does confirm to everyone that everyone knows there are blue-eyed people on the island, something which is necessary for the inductive reasoning to occur.

Red.

The second prisoner knows there is at least one red hat on himself and the third prisoner from the first prisoner’s statement. so, if he sees a white hat on the third prisoner, he would deduce that his own hat must be red. But he can’t decide in fact. From which the third prisoner concludes that his hat must be red.

I love the idea of setting prisoners free but massive suicide!

To bypass the discussions of religion and suicide, etc. consider this formulation of the problem, which is one that can be tried at home:

* Sit 10 people (or any number greater than 2) at a circular table
* Deal a shuffled deck of cards, one card per person, face down on the table
* Each person lifts up their card, face out, so that everyone can see it but themselves
* Give the instructions:
1) Look around and count the number of Red cards you see
2) The game is over when when all of the Red cards are laid face up on the table
3) If you hear a count one greater than the number of Red cards you see, lay your card face up on the table
* Someone starts counting out loud

If the instructions are followed, all of the Red cards, and only the Red cards will be turned up at the count N, where N is the number of Red cards.

Makes for a neat parlor trick!

This also makes me think that the absolutely only purpose of the foreigner in the original problem is to “start the count”. His statement adds no knowledge, third order or otherwise.

This puzzle is as stupid as the endless banter it has created.

Well, they ask him politely (at spear point on the edge of a volcano) to commit (Hoot Gibson*.)
This being the only logically worked out answer given all the conditions.

*Or maybe they were a ‘Clutch Cargo’ cult.
This being your snarky obscure reference.

This may be nonsense but:

The tribe lives in a delicate balance where each member knows every eye color but their own.

So, for each islander, there is both common knowledge yet one unknown.

The stranger, however, brings common knowledge but NO ADDITIONAL UNKNOWN. Thereby tipping the scale and setting off the chain reaction.

Total bs im sure.

Hi Terence,

This version of the problem has become an example of the social phenomenon of cognitive distortion known as emotional reasoning.

Readers may want to ask themselves how a different set of utilities or outcomes would effect this problem with otherwise the same parameters?

For example, instead of punishing the blue eyes, reward them with a trip to the stranger’s homeland;
or if all blue eyes donate a blood sample for testing, then reward the entire tribe with a hospital or other community facility.

Considering the study from the University of Copenhagen in my comment on 7 February, 2008 at 7:18 pm, another interesting problem may be to calculate other possible eye color combinations that may be hidden from the stranger; see Eye color genetics.

More accurately: everyone knows for sure that everyone knows for sure that everyone knows for sure that …. that everyone knows that there are some blue eyed people on the island.

John Armstrong, I think you only need meta-knowledge to the n-th degree where n is the number of blue-eyed islanders. I attempted to argue this in my comment above

I may be wrong, but I think the key to understanding the puzzle and to understanding why the puzzle is so difficult to understand is to note that the information provided by the stranger ensures everyone on the island has meta-level “n” knowledge, whereas before he speaks they only have meta-level “n-1” knowledge. Meta-level “n” knowledge is necessary and sufficient for suicide on the n-th day.

Actually I should say, exactly average intellect

Here’s a variation to think about once you’ve solved the original. What difference is there, if any, if one of the tribespeople happens to go to the bathroom during the foreigner’s speech? Having not heard the foreigner’s comment, this tribesperson doesn’t see any cause for alarm, but what about all the others? Does the color of this person’s eyes make a difference?

By the way, persons who figure out the first puzzle can state the answer but please do NOT tell why. This childish puzzle once defeated a friend of mine who was a very talented mathematician. When he learnt the answer, he could only smile…

Dear Anonymous,

In order not to spoil the puzzle for others, I won’t tell if your answer is right or wrong…

Puzzle 2 looks easy and conventional, but it is quite fun and difficult (at least for me). Don’t give up.

How about this approach:

The question is why the foreigner’s speech would ever trigger ANYTHING at all, since he, in fact, discloses NO new information to the public. Their common knowledge seems not have changed after they listened to him, as they were already well aware of the fact, that some of them are blue-eyed.

Suppose, however, that there was only one person with blue eyes. Then, the foreigner’s speech would indeed bring news to him, so it will trigger his reaction. If there were two blue-eyed person, each of them would think that the speech did bring new information to the other, and after they realized it did not – this would trigger their reaction.

Therefore, we have a chained predicate of a kind “I think that you think that he thinks etc…. that this information is news to him” – and the very fact that the predicate turns out to be false constitutes this “new bit of information” that triggers the consequences.

No one will commit suicide because he doesn’t say how many there are nor is he saying it to anyone in general… how is this a math problem?

Yes

Wouldn’t it also be possible that the blue persons kill themselves on the second day. I mean they now this hole procedure, so they can swap the days in between.

I think no one will die.
1. The stranger tells them, that there IS another (means one) blue-eyed person.
2. The villagers do NOT talk about the eye color.
3. The villagers do NOT know the exact ratio of blue and brown eyed people.
Every blue-eyed villager knows 900 brown-eyed and 99 blue-eyed villager and every brown-eyed villager knows 899 brown-eyed and 100 blue-eyed villager.
As I menioned, there is no communication about the eye color and thus the stranger adds no new information.
If there is only one blue-eyed villager, the situation is different, because he sees 999 brown-eyed mates. So he can reason – without any further information – that he must have blue eyes.

I haven’t read all comments, but no where in the original puzzle does it state the tribe consists of (only) two eye colors. If a third color is added (e.g., green) all bets are off ;)

my first idea was that the tribe must be irritated because the STRANGER does know his own eye colour, but didnt commit suicide. this could have no effect on the tribe because they accept that there are other religions beneath theirs. or they will kill the stranger or they will not believe in their god any longer. blablubb…. hope, you got the point, my english is not so good :p

To all ignorami:
TRY to read the puzzle or keep quiet…

To Todd – the ignoramus!

The plural can be ignorami as well:

http://www.merriam-webster.com/cgi-bin/dictionary?book=Dictionary&va=ignoramus

Simple Mind…

To John Armstrong:
1) It is very tactless to comment about
people’s grammatical mistakes, real or imaginary.
2) It is laughably ridiculous to claim that you know better than Merriam-Webster how to form a plural.
3) Your preference for OED just displays your snobbishness: this is America, not England.
4) Your comment about “people […] trying to sound smarter than they are ”
exactly applies to you.

browned-eyed-girl –
“John Armstrong, I think you only need meta-knowledge to the n-th degree where n is the number of blue-eyed islanders. I attempted to argue this in my comment above”

I really don’t see how the meta-knowledge is necessary at all. Refer to my playing cards formulation above. As long as you know that everyone understands the rules (logical) and will follow them (devout), you know with 100% certainty that on day N+1 (where N is the number of Blue Eyes *you* see) that you absolutely have blue eyes *IF* the Blue Eyed People you see did not suicide on day N.

All that is necessary is a Time 0 and a ticking clock. In this problem the foreigner provides the Time 0, but no meta-knowledge is necessary.

just wanted to add, that both arguments are correct then.

Actually, words like “color” (Br. “colour”) derive ultimately from Latin, where the ‘u’ isn’t in there. You can look it up if you like. But either spelling is acceptable.

See ‘The Software Foundry’ on WordPress:
~ Eros
~ Philia – Philial/the Love of Friendship (1 to 3 years) – This is the most broad and ambiguous of the greek loves
[hence Philadelphia]
~ Agape
~ Storgē

“More generally, the problem is that there is no common knowledge of existence of a blue-eyed islander before the foreigner speaks.”

Isn’t this only true in the case of # of blues = 1?

Thanks for reminding me of the logical definition (which I’d read and already forgot to reference by the time I finished the thread). Still, in the case of 2+ blue-eyed islanders, taking the proposition p as “the existence of blue-eyed islanders,” is it not that case that even before the foreigner speaks, each islander knows p, and knows that each knows p, and so on? I don’t see what “order” of this knowledge the foreigner adds… ah… but in thinking it through I see the proof. What the foreigner does provide is a common starting point for this chain of logic to begin. They establish common knowledge not just about the existence of blue-eyed islanders, but also that everyone must begin working through the consequences of that truth as of the time of the announcement.

I believe the phrasing of p is important though. If p is the “existence of blue-eyed people,” I argue that was common knowledge before the foreigner’s announcement in any case with 2+ blue-eyed residents. Everyone could have seen a blue-eyed person, every person would know that everyone could see one, everyone would know everyone else knows that, etc. The p that matters is “existence of blue-eyed people AND announced to all at time t by the foreigner.”

Without loss of generality for 2+ blues, consider the case of 5 blue-eyed people. Before the announcement, everyone already knew blue-eyed people existed and knew there were either 4, 5, or possibly 6 of them. But they had no common frame of reference about when to expect the other 4 or 5 should appear for their ritual. Once the foreigner’s announcement was made, each of the non-blue eyed persons would expect the 5 blues to go through the process, culminating on the 5th day. Each of the blues would do the same, and realize on that 5th fateful day that they must be the 5th.

The information the foreigner contributes is to augment the common knowledge with a common starting point for applying their logic.

In any case, thank you for offering a very captivating logic problem. JP

ihilien,

It’s not a matter of “keeping their mouths shut.” As professor Tao stated above:

[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.]

Given this, the events unfold the way they do. Also, it’s just a puzzle. Asking why people would willingly be in a suicide cult is missing the point.

OJ,

There IS new information given to the people: common knowledge of the statement that there are blue-eyed people on the island. I think you’re having trouble understanding common knowledge and how it applies to this example. I don’t think I can explain it better and more succinctly than Professor Tao did in his post above (23 February, 2008 at 4:23 pm).

“Dear Randy & Trebuchet: As I stated before on 8 Feb 2:02 pm, in the absence of the foreigner there is insufficient information available for any islander to determine their own eye colour; this can be seen by considering the base case of the inductive step (one blue-eyed islander).”

If this is the case, how can the Playing Card formulation possibly work? No information is exchanged about card color and yet it works with 100% accuracy as long as not every card is black (which is not the case in our problem).

Or put another way: if the foreigner instead said (after having learned the ‘rules’ of the religion) “OK everyone, kill yourself as soon as you know your eye color, starting now”, the end result would be exactly the same. Me, as a blue-eyed person, would have 100% certain knowledge of my eye color on day 100, as long as I know that everyone else can reason as well I (logical) and will follow the rules (devout).

All that is necessary (hence the foreigner) is a clock to start.

Again, if one imagines all islanders were AI robots (who can only reason logically, and infallibly and only so), then one won’t have any difficulties in accepting the induction. In fact, it will be quite natural. Most difficulties in accepting the induction are implicitly in the artificial nature of the set up of the puzzle. I had that difficulty at the beginning.

Or one could imagine it as a games played among computers. It is in fact quite straight forward a solution.

The assumption that everybody is logical and devout, and that that is common knowledge, is, however, not strong enough. Everybody would not have to be mere logicians, but also logicians totally committed to Kripke logic, or modal logic, or whatever this type of logic is called. That is not what real people do, since if they are logical at all, they better be bayesian logicians as there are only very few things totally beyond a doubt 100% certain in our world.
And, of course, the world in which the tribe lives can’t be our world, but needs to be a perfect platonic mathematical world. In our world, thanks in part to quantum mechanics, there are always uncertainties. How would the tribespeople be certain that everybody understood the stranger correctly? Perhaps somebody erronously thought the stranger was talking about brown eyes. “Blue” and “brown” do not sound terribly different. And if there is the smallest chance of doubt, the induction fails.

Secondly, the story doesn’t tell why these perfectly logical tribespeople follow this religion. That’s because on this island, there also lives a demon (named ‘the eye of Kripke’). That demon is a perfect modal logician, and if he determines that someone could have learned his own eye color, and didn’t kill himself, he will torment that person for eternity and will not allow them a chance to commit suicide again.

Here is what I don’t understand (and it only applies for 3+ blue-eyed residents, 1 and 2 being cases where the conclusion is clear): The islanders don’t have common knowledge until the foreigner’s remark. Yet the foreigner’s remark adds no new information, since everyone already knows that blue-eyed islanders exist, that everyone else can see this, that everyone knows that everyone else can see this, and so on. Aside from my previous idea about a common reference point in time, I can’t grasp what the remark adds that wasn’t there before. And if it adds nothing, the conclusions should have played out long before the foreigner.

If the foreigner had said, “I can’t believe 100 of you have blue eyes just like me,” I see what common knowledge is created. But they didn’t, and it’s apparently not the common reference point in time that matters. If that’s the case, would the outcome be the same if the foreigner gave their speech on multiple nights to subsets that covered everyone on the island?

For those still can’t see how new information is added in by the foreigner’s speech, consider the two statements below. First, let’s name the blue eyeds B1, B2 … B100.

Statement A: B1 knows that B2 knows that B3 knows … … B99 knows that there are blue eyeds.

Statement B: B1 knows that B2 knows that B3 knows … … B99 knows that B100 knows that there are blue eyeds.

Before the foreigner makes the speech, only statement A is true. After the foreigner makes the speech, statement B is true. The key to see this is that, as B1 speculates he sees 99 blues. As B2 speculates IN B1’S SPECULATION he sees only 98 THEORETICAL blue eyeds (ie. blue eyeds for sure) due to the fact that B1 does not know his own eye color. Similarly, B3 in B2’s speculation which is in B1’s speculation sees only 97 theoretical blue eyeds. … … Hence, B99 in B98’s speculation which is in B97’s speculation …. … which is in B2’s speculation which is in B1’s speculation sees 1 theoretical blue eyed. Finally B100 in B99’s speculation which is in B98’s speculation … … which is in B1’s speculation sees NO theoretical blue eyed. Then the foreigner makes his speech. Now, B100 in B99’s speculation … … which is in B1’s speculation knows that there are blue eyeds, ie. he now sees theoretical blue eyeds.

One can think this through when there are only 3 blue eyeds first to see how this works. Then try 4, 5 to see how this holds true for higher numbers.

Hope this helps.

“For a very similar reason, if the traveler does not mention eye colour at all, then no information is communicated and no suicides begin at any time.”

Ok, let me correct the Playing Card analogy so that it matches the problem.

Formulation 1: Gather 10 people who know and understand this problem, sit them at the table, deal the cards and have them hold them face out. The 11th person walks into the room and says “One of these cards is red” and then starts counting. On the Nth count (where N is the number of red cards) all red cards will be turned up simultaneously.

Formulation 2: Gather 10 people who know and understand this problem, sit them at the table, deal the cards and have them hold them face out. The 11th person walks into the room and says “Begin” and starts counting. On the Nth count (where N is the number of red cards) all red cards will be turned up simultaneously.

In cases where at least three red cards have been dealt (to match the Blue Eyed Islander problem), I am understanding that you are saying that in Formulation 1, the players will accurately turn up the red cards every time and in Formulation 2, the players will NOT always accurately turn up the red cards every time. Is this correct?

Just trying to turn this problem into something that can be empirically tested to prove whether the statements we are making are indeed true.

Suppose that there are zero blue-eyes and the foreigner is joking. The next day all of the brown-eyes commit suicide?

Dear Terrence,
I have a small question, but in order to ask it, I would first modify your statement at 9:51 Feb 26th as “everyone (who is blue-eyed) on the island already knows that there are 99 blue-eyed persons on the island, and assumes that these 99 know that there are 98 blue-eyed persons (that is assuming himself brown-eyed), and also assumes that these 99 assume that those 98 persons know that there are 97 blue-eyed persons, and so on. At every stage there is an assumption, and to the end of the sequence, 2 persons see that there is 1 blue-eyed person, and assume that this person doesn’t see any blue-eyed person”. So normally this sequence ends peacefully. Only when the traveler addresses the tribe does the assumption fail at the last step, which leads to other assumptions being false too. Now my question is: what if the first blue-eyed person in the hierarchy assumes that he is blue-eyed instead?

I’m not sure I understand correctly, but just to check:
Is the key point here that the tribe-people all obtain the common knowledge that the tribe contains at least one blue eyed person at the same time?

i.e. suppose instead of a stranger coming to the island, and making the unfortunate statement in front of the whole tribe, s/he told:
– half the tribe on Monday
– half the tribe on Tuesday
– both halves of the tribe know they were told, but don’t know when they were told
would the result be the same?

Or alternatively, suppose the tribe has a special ceremony where they all gather round in a big circle, and each tribesperson takes turns going around the circle looking into every other tribes-person’s eyes, and furthermore, everyone in the tribe sees everyone in the tribe doing so, would this have the same outcome as in the initial formulation?

ok. now my brain hurts.

Dear Prof. Tao,
I think the induction method (argument 2) does not work simply because the n=1 case
is not admissible logically. Indeed, imagine a single blue eyed tribesman
among other 999 islanders with brown eyes.
He (or she) knows about the religious prohibition of knowing his own eyes
color. But the prohibition itself logically implies that there are more than one
(two) eye colors present. And since the blue eyed person knows for sure
that the rest 999 of the islanders are brown eyed, he (she) concludes inevitably
that his (her) eyes must be blue! So in the n=1 case the blue eyed person has to commit
a suicide at the moment he (she) learns about the religious commandment to do so,
without any reference to the foreigner. For this reason, the visiting foreigner would never find the island in the n=1 situation and the induction sequence cannot start.
At the same time, there seems to be absolutely no logical inconsistency in the argument 1, which seems to be the actual solution
Regards

which I believe is the actual solution to the problem

I’m reading your solving mathematical problems book and I think I can apply some of the things I learned to this problem.
(Hope I learned well)

On page 14 on your book you analize a problem like this: “The first sneaky thing to be done is to guess the answer. Circumstancial evidence (this problem is from a mathematics competition) suggests that this is not a trial-and error question”.

In this problem I would say “I will first try to guess the answer. This is a mathematician’s blog, suggests that the answer is not simply argument 1, as argument 2 seems more sophisticated.”

Then on your strategies chapter you say “modify the problem slightly”.
In this sense I would first consider only 1 blue eyed. When the foreigner says what he saids, the only blue eyed gains knowledge on his eyes and comits suicide the next day. If they where two blue-eyes, when the next day no-one suicides, they both gain knowledge and suicide the 2th day.
And so on if they where 100 blue eyed they would suicide the 100th day. So it look’s better this than argument 1.

A question, though, would be: do the tribe know that there are in total only 2 eye colors (blue and brown)? because one would pherhaps think they could have green or black eyes, and as they are not sure, they don’t gain knowledge.

One thing more, if they know there are only two eye colors, after all the blue eyes suicides, all the brown eyed gains knowledge and suicides the next day.

Sorry if this was already asked before, I didn’t read all the comments.

Am I on the good road?

I am now even more sure argument 2 is the valid one.

Supose we arbitrary choose a sequence of the blue-eyed residents. Lets call it a_n, a_(n-1), …, a_1.
(In this case n=100 blue-eyed people)

lema 1:
every blue-eyed person knows this: at least there are (n-1) blue eyed people (because she sees them), and at most (n).
lema 2:
every other-color-eyed person knows this: at least there are (n) blue eyed people, and at most (n+1).

When the foreigner says what he says, every person thinks like this:
if I’m not blue-eyed, the foreigner didn’t say anything about my eye color, so I will surely not have to commit suicide.
But if I am blue-eyed, what I know is this: (I’m a_n, and the number in brackts [] means how many blue-eyed people at least each a_i knows there are)

a_n [b-1], a_(n-1) [b-2], …, a_1 [0]

that means a_n knows a_(n-1) knows … etc … that a_1 may not know if there are blue-eyed people on the island.

but when day (n-1) arrives, using lema 1, noone suicides because they all know there are at least (n-1) blue eyed people, so there still is a chance that they have other-colored eyes.

lema 3:
But this means that there have to be more than (n-1) blue eyed people, because everyone knows that everyone knows … etc, that each other is also highly logical, so she realizes everyone other blue-eyed has deduced the same thing like her, that is basically the proof of induction of argument 2.

lema 4:
using lema 1 and lema 3 we know that the number of blue eyed has to be exactly (n), so each a_i realizes she’s got blue-eyes, and the next day (day n), all a_i suicide.

I think if we asume argument 1 we can arrive at a contradiction, because if all the blue eyed are higly logical and knows every other are … etc, they should be able to deduce lema 1 and lema 3, and from their combination lema 4, thus they should suicide.

I hope this makes at least a bit of sense :)

I see an analogy between this problem and what in computer science is called a deadlock: example when n process have n recurses (1 proces – 1 recurse) and each other needs a recurse of some other but noone is going to drop the recurses it has, so all the proceesses are hanged. (it’s somewhat cyclic)
If someone puts an aditional recurse the deadlock can disapear and the process continue operation.
In this case the aditional recurse would be the information the foreigner tell them so solving the deadlock that no blue-eyed people knows wich is her own eye color.

An even more interesting problem: The visitor states that there are [any-specific-number] eye colors in the tribe.
Everyone eventually dies, multiple eye colors will suicide on the same day if equal numbers of people have those eye colors, and the largest group will suicide either on the same day as another equal size group or immediately after the second largest group.

S={k | k blue-eyed persons commit suicide, after k days}
1) 1 in S. (Actually true~)
2) k in S -> k+1 in S (?) No!!! this is fault.
its contraposion : k+1 not in S -> k not in S
at 99th days, 99 persons did not commit suicide, therefore At 98th days, 98 persons did not commit suicide.
And 97 is same…, 96 same…,…
At last, at first day(after 1 day) 1 person did not commit suicide!
it’s the opposite of condition 1)…

Argument 2) means that k not in S, then k+1 in S. The induction argument is not correct

(Sorry, forgive my poor english. )

I see the possible objection to my solution: since these islanders are logical, they will, seeing only blue and brown eyes, conclude that these are the only two possible colors.

I would beg to differ – that’s why we have words like ‘exception’ and ‘outlier.’ The islanders, being logical, would be aware of the possibility that their own eye color was different from that of the others. An islander could hypothesize that it is LIKELY that their eye color must be one of blue or brown, but for them to conclude absolutely that: “all eyes that I have seen are either blue or brown. therefore all eyes are either blue or brown” would not be logical.

An islander must commit suicide the next day upon knowing their eye color.

Knowing, to a logical person, means knowing absolutely, with logic. Not knowing with a feeling of some probability.

Faced with the choice of committing suicide, or making a conclusion based on probability (but not on logic) a logical thinker would make the winning choice: reject probability, follow logic, and do not commit suicide.

(A joke)

This surely proves, finally, the inconsistency of ZF set theory and logic; so all of us mathematicians might as well commit suicide now.

Dear Professor Tao,

Maybe most people find this logical puzzle “unbelievable” because it’s necessary for a mass suicide that the existence of blue eyed islanders is known.

But let’s have a little look at the induction argument:

The induction is based on the idea that each islander knows the following law:

L(n-1): If there are exactly n-1 islanders with blue eyes they’ll all kill themselves n-1 days after hearing about the existence of blue-eyed islanders.

If we assume this assertion as a logical law then it must also be known by the highly logical thinking islanders.

The logical law must not be broken, so if a islander sees exactly n-1 blue eyed islanders which don’t commit mass suicide the n-1-th day, there cannot be just n-1 islanders with blue eyes but the islander has to have blue eyes, too. Otherwise the law L(n-1) would be broken.

The information of the stranger is needed, because then we can deduct the “starting law” L(1), which starts the “motor” which’ll end in the mass suicide.

Maybe for “normal” humans it’s just hard to imagine that there is a inductive list of logical laws which behave as follows:

A: “If the events A(1), A(2),…, A(n) don’t occur then A(n+1) has to occur.”
This is a deduction which interacts with the logical laws L(n):
L: “If there are n blue-eyed islanders they’ll commit suicide after n days.”

It’s hard to understand, that the aspects A and L of the solution of this problem “play ping-pong”. I had some problems with solving this problem when I started studying maths (some university give pupils a chance to take a part of the studies during schooltime) but with many patience I could get the “ping-pong”-solution.

It’s a nice problem and I’m glad that you help other people to get to know such interesting problems like this.

One of your (17 year old) fans ;)

P.S. Please excuse my bad English – I didn’t have English-class in school for two years.

Very interesting. And I have a question – what content of the foreigner’s speech will trigger suicides?

For example, instead of saying “how unusual it is to see another blue-eyed person like myself in this region of the world”, the foreigener says
i) there are two different eye-colored people on this island. or
ii) there are various eye-colored people on this island. or
iii) do you know how many blue eye-colored people on this island?
….

What will be the respective outcomes?

The 100 blue will not suicide because 3 blue would not suicide. No suicide on day 2 is consistent with both two blue (and a brown) .. and 3 blue. It doesn’t discriminate anyone’s eye color.

If 3 blue .. each sees 2 blue.
For none is it the case there is 1 blue that will know and suicide.
Therefore .. no conclusion can be drawn from no one suiciding.

it is interesting that in the case of 2 blue .. if suicide is immediate no knowledge is obtained from the stranger’s info. Each sees a blue .. each knows if the other sees brown they will suicide .. each will know they are brown when the other leaps. But both are blue .. so neither will leap to a false conclusion.

Sequenced suicide adds information only in the case of 2 blue.

Fortunately .. the volcano that was still spewing red hot lava in the time of the blue-eyed missionary’s previous departure .. is now extinct so the worst that can happen is a few scraped knees and such.

I feel that zgrav put his finger on WHY this puzzle is counterintuitive.

It is that, somehow, we intuit that mathematical induction breaks down on iteration of an apparently well-defined function, when that function involves knowledge. That is, the sequence:
x,
knowledge-of x,
f(knowledge-of x),
knowledge-of f(knowledge-of x),
f(knowledge-of(f(knowledge-of(…x…))))
undergoes a fuzzy phase change in truth value for some depth of nesting.

Furthermore, non-identical people differ as to where that level of nesting appear, and we do not know the distribution.

This is inconsistent with unbounded rationality, but entirely plausible under bounded rationality. It is hard, however, to axiomatize satisficing, so this problem will not go away any time soon.

There is some experimental evidence that the level of nesting is close to that magic number 7 plus or minus 2, for ordinary adults, when dealing with exceptions to exceptions to exceptions to… for dealing with items on an assembly line. EXCEPT for programmers, who experimentally deal with an unbounded level of nesting, having abstracted that procedural approach to exception-handling.

I disagree with Phillip. I think that the newcomer does give away unknown information by telling everyone that there are some blue eyed people. By saying this, he makes the information “common knowledge”. Thus the island will continue living on forever if left to themselves. The reason is thus: I claim that an islander just looking around and seeing another blue eyed person only gives them a “first order” knowledge of who has blue eyes. Take for example the case of two blue and several brown eyed people. Everyone can see another blue eyed person, However, from the point of view of one of those blue eyed people, I have no way of knowing that the other blue eyed person can make the same claim (I see no more blue-eyed people). Only as problem solvers of this riddle do we know this information, but it is not necessarily known to the islanders. Take the case of three blue eyed people, the rest brown. Every blue eyed person can see that there are other blue eyed people. Further, they know that their friends who they can see have blue eyes, also make the same conclusion, since there is one other blue eyed person who they each can see. So they know that he knows there is a blue eyed person on the island. But that’s as far as we can go, since there are no more blue eyed people that they can see! A similar situation results from considering what a brown eyed person would conclude. My point is that I believe that Dr. Tao’s induction is flawless, but the claim that the islanders would have already known the information given by the newcomer is misguided (as I am sure he is aware.) The key is to distinguish between information that we (as problem solvers) know, and information that each inhabitant of the island knows.

that is just silly, what kind of religion would prevent you from knowing your own eye color? What if you go swimming and see your reflection in the water?

The problem with this puzzle’s solution is that it assumes everyone sees everyone at the same time.

You cannot say for certainty that the suicide/departure will happen in k+1 days time because, even though the islanders have perfect knowledge of each others’ eye color (once seen), they likely haven’t already seen all of them.

Now, if they’ve seen everyones eye color, then they’ll all leave/kill themselves on the second day.

That first day Tom will think “well, there goes Bob and Joe and Carl — it was nice knowing them.” But when Bob and Joe and Carl don’t off themselves in the morning, Tom will realize that he is also blue eyed (everyone else being brown eyed) and join the merry immolation throng in the morning.

But the brown eyed ones do kill themselves also :). Not because the foreigner didn’t say anything about them but because “they all knew that everyone knew there are brown eyed people”.This is the trigger that makes every brown eyed or blue eyed person to kill themselves.

What a great puzzle!

I think the resolution is that the first proposed solution is false; the foreigner DOES give the islanders new information. The inductive argument is correct, but we must still explain how the islanders survive before the foreigner arrives!

The way I figured this out, and the easiest way to understand it I think, is to consider the simplest cases. Let be the number of blue-eyed islanders.

If , then each islander sees zero or one blue-eyed islanders, but since he or she doesn’t know , no conclusions are drawn.

If , then while each islander already knows that there are blue-eyed islanders, he or she does NOT know that all the other islanders know this. If we call the two blue-eyed islanders Alvin and Barry, then Alvin knows that Barry has blue eyes, but he does not know whether Barry knows about any blue-eyed islanders, since Barry is the only blue-eyed person Alvin sees, and he doesn’t know his own eye color. Thus, the fact that Barry does not kill himself the day before doesn’t mean anything to Alvin. However, once the foreigner comes along, Alvin suddenly knows that Barry knows that there are blue-eyed islanders, and we can use the inductive argument as presented: Alvin now knows that Barry would have killed himself after one day unless Alvin had blue eyes, and thus both kill themselves on day two.

This works for all . For , Alvin knows that Barry knows that there are blue-eyed islanders, but he DOESN’T know that Barry knows that Cathy knows this! Without this information, he cannot know his own eye color, despite the information that no one killed themselves in the preceding days. In general, the foreigner provides the th step in the chain of reasoning.

I still see no response to my indicating the meta-meta-problem which is an obstruction to the use of induction in the meta-problem. One implicitly or explicitly has a Temporal Epistemic logic, whose axioms deal with the passage of time and inferences on sequences of events (including null evens, of the “dog that did not bark in the night” variety). The axioms also deal with the beliefs and the belief-revision algorithm of the agents (islanders). For induction to work as naively assumed, one needs to have unbounded introspection, with an axiom P^(KP) ==> KKP, that is, if proposition P is true, and you know that proposition P is true, then you know that you know that proposition P is true. Given a finite number of agents, and a countable set of propositions at all times in the belief set of each, then one needs to deal with the combinatorial complexity of the recursion of every agent modeling every other agent’s belief set and its dynamics, in a way that Felix Klein [Indra’s Pearls: The Vision of Felix Klein is a geometry book written by David Mumford, Caroline Series and David Wright] noted bears resemblance to Indian metaphysics. Francis Harold Cook describes the metaphor of Indra’s net from the perspective of the Huayan school in the book Hua-Yen Buddhism: The Jewel Net of Indra:
“Far away in the heavenly abode of the great god Indra, there is a wonderful net which has been hung by some cunning artificer in such a manner that it stretches out infinitely in all directions. In accordance with the extravagant tastes of deities, the artificer has hung a single glittering jewel in each “eye” of the net, and since the net itself is infinite in dimension, the jewels are infinite in number. There hang the jewels, glittering like stars in the first magnitude, a wonderful sight to behold. If we now arbitrarily select one of these jewels for inspection and look closely at it, we will discover that in its polished surface there are reflected all the other jewels in the net, infinite in number. Not only that, but each of the jewels reflected in this one jewel is also reflecting all the other jewels, so that there is an infinite reflecting process occurring.”

The only thing that happens to the tribe is that they “lose trust in the visitor”. He had won their trust and then they learned that he knew his own eye color and was still alive which is contray to their belief. They know nothing more about their own eye color then before the visitor came to the island. Unless, we were given the information that he looked at only one person or was looking directly at one person when he spoke about his eye color, we cannot assume that anyone deduced they had discovered their eye color. One can project that they demanded he commit suicide in order to pay tribute to their religion, but that would be more drama than fact.

I did not have time to read through all the comments to see if this has been already mentioned, but this is very similar to the muddy children puzzle and other logic puzzles (http://en.wikipedia.org/wiki/Induction_puzzles). It can be modelled using multi-agent epistemic logic to show that n blue eyed people would commit suicide after n days, assuming of course that they are all perfect logicians themselves. (which is stated in the puzzle, and of course means that they would immediately know the answer to this puzzle also)

What really would happen is: He’d be mobbed and killed immediately before he could identify the identity of any specific islander. The logical islanders would immediately perceive that he is a threat to public safety whose careless statements could require many islanders to commit suicide. Acting almost as one, they would silence him immediately and permanently.

Can anyone answer the following question?

Let’s assume that 14 days have passed after the foreigner’s remark.

Now he adresses the tribe again:

“Two weeks ago I told you that I saw at least one blue eyed person. Meanwhile I can say that there are indeed many more.”

“I tried to count them, but stopped counting at 20, because I noticed there are so many more. I can say that I am now sure that more or less half of the population have blue eyes, even if I don’t know the exact number.”

The foreigner obviously gives additional information, but thereby disturbes the running clock. Should the tribespersons continue with their schedule, i. e. there are at least 14 persons? Or should they now assume that there are at least 20 persons? After all anyone can verify that the foreigner is also right with his remark that more or less half of the population has blue eyes.

Obviously the foreigner changes to fuzzy logic now: There are 20 persons for sure, but since he has seen “many more”, there are at least 22 (if we assume “many” means at least two) – but the probability that there are only 22 is “practically zero”. In fact, anyone can verify immediately that there are more than 22.

What will happen?

Let us assume there are n blue eyed people on the island.

Argument 1 is flawed because it fails for n = 1 in which case the information given by the foreigner is of value.

Coming to Argument 2:

Each of the blue eyed tribal has a doubt that there are either n-1 or n blue eyed people. Now this doubt has also become a common knowledge among all the blue eyed islanders. Let us call this doubt d.

Argument 2 would work for only one value of n that is 1.
For Argument 2 to work for n = 1 it requires the information given by the foreigner.
And for any other value n > 1 Argument 2 would not work even with the information given by the foreigner in the puzzle statement as it fails to dispel the doubt d of the tribals.

If the foreigner says that there are atleast k blue eyed people where k < n noone would commit suicide at all because it fails to dispel the doubt d of the tribals.

Now for Argument 2 to work as mentioned it requires the exact number n to be specified by the foreigner. And in this situation where the foreigner specifies the exact number of blue eyed people the puzzle becomes identical to the article specified in wikipedia about common knowledge.

Argument 2 tempts one to think it would work for any n. But what is that instance of n, noone in the island knows so it fails to dispel the doubt d ..so it is flawed.

Listen up meatbags.

I’ve asked Professor Farnsworth to fire up his brand spanking new invention the Calcuanator 5000 (with extra spank) and get to the bottom of this. Results: no new information regarding eye color provided by the foreigner. I was about to tell you all this, but then that do-gooder Ethan “Bubblegum” Tate showed up, acting all smug in his fancy white lab coat. Anyways, Bubblegum says “It’s not about new eye color information baby, the razzamatazz is all in the reference point.” Bubblegum also says the brown eyed peeps keep on keeping on, they all thinking they the only one got green eyes.

Now to find me some inorganic nookie . . . or something to steal.

The common knowledge is not the color of eyes, it is the unanimously agreed upon mark in time where all start counting days. The mark in time is the day the the announcer makes the announcement. All islanders have the same common knowledge then. If each islander was told in secret the same announcement with the following twist “I saw blue eyes on the island and I told and will be telling the rest of the people on different days”, then in case of two islander with blue eys, none will commit suicide either because they would not have a common mark in time to make a conclusion when the other did not commit suicide.

Sorry if I am repeating anyone’s words; I only read the first 20 or so comments.

I don’t know if the following was already mentioned. However, here is why the foreigner does indeed bring new information.
Let P=’There are blue-eyed islanders.’
Say there are in fact n blue-eyed islanders .
In case of n=1,2, P is no common knowledge.
In case of n=3: knows P, and knows that knows P, but does not know that knows that knows P.
In case of n=4, doesn’t know that knows that knows that knows P…
This shows that P is no common knowledge before the foreigner’s address. The justification of argument 1 is false.
Again sorry for repeating, if I did.

Even better they will all reach the conclusion that their religion is not
logical and so mass-convert by not committing the ritual suicide. The visitor would then later be friendly welcomed by enlightened (and logic-scientific) islanders not ridden by superstition.

The link explains this puzzle in detail

http://www.rawkam.com/?p=978

Cool problem, when do we get the solution? :)

I think that the second proof is rigth. If the traveler doesn’t make that statement, the 100 blue eyes don’t suicide after 100 days because… 100 days from WHEN?

The traveler gives them an important piece of information, gives them a starting point for their rationale. And in my oppinion, the main reason why induction works in this case is because not only each islander can make the induction argument, but they know that each other islander can make exactly the same argument in exactly the same day (without the statement of the visitor this is not the case).

In shorter words the visitor gave them the following piece of information, which is critical for the induction: you can all start reasoning now.

@Yale

What starts the argument is not the knowledge that there is at least a blue eyed person on the island, and that everyone knows it. What starts the argument is the fact that everyons STARTS reasoning at the same time, and that they know it.

To over simplify the problem, the traveler statement tell them the following:
“If there is only one blue eyed person on the Island he will suicide tomorrow”. This is implied in his statement, is a completelly new piece of information, and without it the induction is not possible ;)

Professor Tao,

There are various nice problems similar to this. A few are posted here

The only information that the foreigner gave was that “lets start counting from today”. So, he helped synchronized local variable for every person to a global variable. That implicit conclusion was what made the difference. In the second argument, you assume everyone starts counting from that day.

@aquazorcarson: No. Asking the question is not equivalent to telling the answer. That’s exactly the point in this puzzle.
Saying “there are blue-eyed people” makes the fact common knowledge for the attendant people. Asking the question does not – so nothing would happen.

Suppose there are just five people: Alice, Bob, Charlie, Diane, Elaine. It so happens they are all blue. (-eyed, not sad.) In such a situation, none will commit suicide, because each will think: “My eyes might be brown, green, or red.”

Now, Alice knows that Elaine is blue, and Alice knows that Diane knows that Elaine is blue — but Alice doesn’t know if Bob knows if Charlie knows if Diane knows if Elaine knows that there is at least one blue on the island. She really, really doesn’t! Alice would only know that if she knew her own eye color (which she can’t), or if she thought that someone else know their own eye color (which she knows they can’t).

What the foreigner’s comment does is cut that bridge short. Now it is the case for any person X that she knows that any person Y knows that there is at least one blue, and further for any possible nesting thereof. So the count begins…

Except it still seems weird to me that there would be that wait. Surely everyone already knows that no one will die on day 1 — and therefore the absence of deaths on day 1 is not new information! Right? If someone did kill themselves, then every islander would correctly think “Wow, he screwed up.” (Which is, of course, impossible for these islanders to do — so would the survivors’ heads explode?) Hmm. I’m alllmost getting how it works…

====

Now, I’m not sure if this quite needs to be a stated part of the problem, but perhaps the most counterintuitive thing is that these weirdo Vulcan islanders do consider it horribly wrong to discuss eye color, but simultaneously can’t help themselves from thinking about it, even when doing so carries the risk of death. They don’t shy away from it in their minds the way that actual people operating under taboos tend to, especially if the taboo is specifically about knowledge itself.

However, the nature of the problem doesn’t require that dying (or just leaving the island) is something an islander wants to avoid — indeed, great pains have to be taken about just how dead-set the islanders are on following the law. They can even have the incentive to die/leave, and it still works exactly as well.

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

Or have I changed the problem?

Nevermind, I get it now.

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

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

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