My write-up of the "Blue Eyes" solution (SPOILER A

[zokyo]

Hey, I came up with an answer that was different to the official one. Here Tis.

All of the people with blue eyes would get off the island on whatever night the guru says "I see someone with blue eyes." Everyone with blue eyes would form a group, pushing away all of the others who didn't have blue eyes. It would be logical for them to do this once they heard the guru mention the blue eyes, whereas they couldn't form groups before he mentioned blue eyes because no one would know the colour of the eyes of the group they were trying to form. Suggesting Blue eyes would be the clue for the blue eyed people to form a group. Once he says "I see some one with blue eyes", everyone else would stare at some one with blue eyes. If you looked around to see someone staring at you, you would know that you had blue eyes. I know this is due to an assumption made by everyone on the island but a more efficiently logical person would make the assumption that the others on the island were logical enough to at least attempt such a method, although I guess it comes down to whether or not they all knew that the others were all such great logicians, and it would seem that they did. It says that they can't communicate, but looking at a person constitutes communication in my book, so I think there's still a semantic flaw in the official answer. The official answer is also based on a collective assumption made by all of the logicians on the island.

If you can think of a way to contradict this answer please let me know

[quintopia]

please delete the thread you made so's a mod doesn't have to.

the reason your answer is wrong is simply that this is a logic puzzle, not a real world situation with real people. no one has to look at anyone else when the guru says anything, because they can always see everyone else already (without or without looking) and already have a mental count of the number of blue-eyed people. moreover, there is no reason anyone can think that everyone else will simultaneously come up with the pushing away strategy, since there is no communication and they are not clones, so pushing away communicates nothing.

[Oculus Vespertilionis]

please delete the thread you made so's a mod doesn't have to.

the reason your answer is wrong is simply that this is a logic puzzle, not a real world situation with real people. no one has to look at anyone else when the guru says anything, because they can always see everyone else already (without or without looking) and already have a mental count of the number of blue-eyed people. moreover, there is no reason anyone can think that everyone else will simultaneously come up with the pushing away strategy, since there is no communication and they are not clones, so pushing away communicates nothing.

This is true. But if it does communicate something, then the problem itself prohibits it.
Either way, this seems to be another example of the idea that perfectly logical people will act so as to communicate eye color, but the problem is set up to avoid this possibility.
-OcV

[Wildcard]

My goodness. This seems to be a never-ending thread because every once in a while, someone reads the first post, none of the responses, and then since they don't really understand the solution, they're SURE that it can't be right and they're SURE that they've come up with objections that no one else has before! So rather than reading any responses (which would immediately prove them wrong) they go ahead and repost one of the same 5 or so types of arguments that have been posted and reposted since the first couple pages.

Sorry, just had to get the disgust out of my system. Better now.

Someone brought up Lacan (I think is the name) in the last couple pages, and previous versions of this puzzle, which I found very interesting. It reminded me of a puzzle I read long ago which is a much simpler one, but is in fact based on the same type of logic as Blue Eyes and Lacan's puzzle. It's not an exact verbatim quote, but all important details are correct and it's very close to verbatim (from memory):
-----------
A school bus emerges from a dusty tunnel and the teacher notices that three boys (John, Jack and Tim) have smudges on their foreheads. She decides to find out which of the boys is cleverest.

She tells the three boys to look at each other, then "Raise your hand if you see someone with a smudged forehead." All three boys immediately raise their hands. "Now, when you know for certain whether your own forehead is smudged or not, lower your hand." The three boys puzzle in silence for a minute, then Jack smiles and slowly lowers his hand. "I know that my forehead is smudged," he announces.

HOW DOES HE KNOW?
-----------

And the solution reads more or less as follows:

---------------
Jack reasons like this: "Either my forehead is smudged or it is not. Let us assume for a moment that it is not. Then I raise my hand because I see smudges on John and Tim, Tim raises his hand because he sees John, and John raises his hand because he sees Tim. But if my forehead were not smudged, Tim would see John raise his hand and know that he sees a smudge; he would know that John couldn't see a smudge on my forehead and so would know that his own forehead was smudged. John would know that Tim must see the smudge on John's forehead. However, both boys are still confused. Therefore, my own forehead must be smudged."
--------------

There are some notable differences here, as well as some similarities: First, and most notably (in my opinion), the participants are not all equally logical or intelligent. Indeed, in the puzzle itself it is stated that the teacher wants to find out which boy is cleverest.

Obviously there are also less people (3 instead of 100).

The logic style, however, is similar: observing a lack of action within some specified or unspecified time frame on the part of other people, and thus deducing things about *their* ability to infer based on data they can observe (one's own forehead, or one's eye color.)

Interesting....

(That was from "The Arrow Book of Brain Teasers" by Martin Gardner, if I recall correctly. The book is, I believe, buried somewhere in my attic or the like.)

[Dan-o-Myte!]

Here's my issue with the "solution" to this problem.

It's like trying to shovel snow with a rake.

The shoveler takes the rake in hand and rigorously scrapes it along his sidewalk; sees the snow blocking the walkway but is certain he shoveled correctly and so heads back inside confidant that the chore is done. Then whenever someone comes to complain about the snow on the walk they carefully inspect the rake for any flaws or damage and, not finding any, says "See, this is correct. I know it can be hard to understand but it's all done correctly."

The problem lies within the nested hypotheticals (x100). The "Everyone knows everyone knows everyone knows..." does not go 100 levels deep, it can only go three. I know, I know...it's been shown over and over how it can and must go all the way...but this is the rake.

When it is examined in the form of a chain: What A knows B knows C knows D knows... it appears to go 100 levels deep down to the potential of someone not seeing anyone with blue eyes. But the semantics are where the facts are getting confused. A is not the same as everyone, B is not the same as everyone, C is not the same as everyone.

What we need is not a chain, but a net. A chain needs to go 100 levels deep to include all participants; a net only needs to go three deep: What everyone [A, B, C, D...] know everyone else[[B,C,D...], [A,C,D...], [A,B,D...], [A,B,C...]...respectively] knows everyone knows. Perhaps someone more mathematically inclined could chart it better. Done in this way, when the net is extended to encompass what everyones potential knowledge of all others could be, we are still left with a hypothetical situation in keeping with the known facts: Everyone knows everyone else can see 98 minimum and can conclude no one else could possibly imagine one who observes fewer than 97.

[phlip]

The "Everyone knows everyone knows everyone knows..." does not go 100 levels deep, it can only go three.

Why not? It's certainly meaningful to talk about "I know what A knows what B knows" to more than 3 levels... I'll refer again to my previous example about coinflips:

To demonstrate the difference... consider a coin toss. I flip a coin, and look at it... but don't show you. Say it's heads.
Now, I know it's heads, and you don't. You know that I know the coin's value.. but you don't know that I know it's heads, specifically.
Now consider that when I take a look at it, you're able to steal a glance at it, but I don't notice.
Now, you do know that I know it's heads. But I don't know that you know that I know it's heads.
And we can add another level if I catch you stealing a look, but don't say anything, and you think you've gotten away with it... then I know that you know that I know it's heads, but you don't know that I know that you know that I know it's heads.
And we could keep this chain up as long as we like, by making even more contrived situations where I notice that you noticed that I noticed that you're cheating, but I don't think you've noticed that, or whatever.
We can also make an infinitely long chain... say, if I actually explicitly show you the value on the coin. So it's obvious to both of us that it's heads... and the fact that it's obvious is also obvious, and the fact that that is obvious is also obvious, ad infinitum. So I know that you know that I know that you know that it's heads, with any number of "know"s nested around it. The technical term for this state is "common knowledge"... everyone knows it, everyone knows that everyone knows it, to any level of knowledge about knowledge.

When it is examined in the form of a chain: What A knows B knows C knows D knows... it appears to go 100 levels deep down to the potential of someone not seeing anyone with blue eyes. But the semantics are where the facts are getting confused. A is not the same as everyone, B is not the same as everyone, C is not the same as everyone.

But A doesn't have to be the same as everyone, it's just an arbitrary object.

To take the example from that Wikipedia page, it's like saying "if you pick any arbitrary integer, and double it, you get an even number. Therefore, all integers give even numbers when doubled." This is a valid argument, and is a pretty standard way of proving a universal statement.

So the same applies here. For any arbitrary people A, B and C, A knows that B knows that C knows that there are at least n-3 blue eyed people on the island. Therefore, because they were arbitrary, everyone knows that everyone knows that everyone knows that there are at least n-3 blue-eyed people on the island.

What everyone [A, B, C, D...] know everyone else[[B,C,D...], [A,C,D...], [A,B,D...], [A,B,C...]...respectively] knows everyone knows.

Sure, at least to start with, that's the other way of proving a universal statement - enumerate every single possibility. But why do you stop after two levels? There's no reason to.

To use your notation, everyone [A,B,C,D,...] knows that everyone else [[B,C,D,...], [A,C,D,...], [A,B,D,...], [A,B,C,...], ...] knows that everyone else [[[C,D,...], [B,D,...], [B,C,...], ...], [[C,D,...], [A,D,...], [A,C,...], ...], [[B,D,...], [A,D,...], [A,B,...], ...], [[B,C,...], [A,C,...], [A,B,...], ...], ...] knows...
And here we see the problem with this approach - it's not incorrect, but it gets very unwieldy, very quickly.


Finally: a thought to leave you with. You're saying that, if I asked you, as an outside observer, "what's the highest number of blue-eyed people that everyone can guarantee that everyone can guarantee that everyone can guarantee exists, based on their respective knowledge, to any arbitrary depth of guarantees?" then your answer would be two less than the number of blue-eyed people on the island (you said 98 in your post, for the puzzle's 100). So let's say there's 99 blue-eyed people... your answer would be 97, yes?
Now, let's say that instead of being an outside observer, you're on the island, as a brown-eyed person. Clearly this won't change your result, as the limiting cases are the ones about what blue-eyed people know about what blue-eyed people know (the knowledge of blue-eyed people about blue-eyed people is the same in the 100-blue-eyes-and-100-brown-eyes case as it is in the 100-blue-eyes-and-10-brown-eyes case). So your answer would still be 97.
Now, let's say that instead of being a brown-eyed person, you actually have blue eyes. Since everything you can actually see is identical in both cases, your answer must be the same, 97. Your knowledge hasn't changed... other people's knowledge changes based on your eye colour changing, but you don't know that other people's knowledge has changed. So your answer must still be 97. But know it's three less than the number of people on the island.
And since you're saying 97, and you're just an arbitrary blue-eyed person, the same can be said for every blue-eyed person... so the highest number anyone can guarantee is an answer to that question is 97. But that just adds another level of "...everyone can guarantee that..." to the question, which contradicts the fact that the question specifically states "to any arbitrary depth of guarantees", and we'd already claimed that, to any arbitrary depth of guarantees, the answer would be 98 at worst.
So your answer leads to a contradiction.

[Dan-o-Myte!]

Sure, at least to start with, that's the other way of proving a universal statement - enumerate every single possibility. But why do you stop after two levels? There's no reason to.

I stop after two levels because at that point all possible situations are covered. Going further the chain becomes recursive. An arbitrary blue eye, A, can see 99 and therefore knows B can see 98 but could think C might see 97. But to say A sees 99 and knows B sees 98 who thinks C sees 97 who thinks D sees 96 doesn't follow because A knows C sees B's eyes, and knows B knows D sees C's eyes. There are only two levels on unknowns: what A knows and what B might think. Because they are arbitrary entities they are mathematically identical. I know I can see 99, so I know you can see 98; but then I am you, so I know he can see 98; but then I am he so I know she can see 98. Once A goes from thinking about B to thinking about what B thinks about C, A becomes B. It doesn't continue down the line, but just bounces back and forth. The chain becomes recursive, so while you can follow it to infinity you go nowhere.

To demonstrate the difference... consider a coin toss. I flip a coin, and look at it... but don't show you. Say it's heads.
Now, I know it's heads, and you don't. You know that I know the coin's value.. but you don't know that I know it's heads, specifically.
Now consider that when I take a look at it, you're able to steal a glance at it, but I don't notice.
Now, you do know that I know it's heads. But I don't know that you know that I know it's heads.
And we can add another level if I catch you stealing a look, but don't say anything, and you think you've gotten away with it... then I know that you know that I know it's heads, but you don't know that I know that you know that I know it's heads.
And we could keep this chain up as long as we like, by making even more contrived situations where I notice that you noticed that I noticed that you're cheating, but I don't think you've noticed that, or whatever.
We can also make an infinitely long chain... say, if I actually explicitly show you the value on the coin. So it's obvious to both of us that it's heads... and the fact that it's obvious is also obvious, and the fact that that is obvious is also obvious, ad infinitum. So I know that you know that I know that you know that it's heads, with any number of "know"s nested around it. The technical term for this state is "common knowledge"... everyone knows it, everyone knows that everyone knows it, to any level of knowledge about knowledge.

We can continue this I know you know I know it's obvious business forever, sure, because nowhere along this line do we encounter anything in contradiction with the facts. Can A think B think C think D sees 96? No, because this A's knowledge that C sees 98, and A's knowledge that B knows that C and D can see 98.
With the cheating example, assuming we are both perfect observers, I can cheat and you can notice I cheated and I can notice you noticing. But if I didn't cheat in the first place, you cannot notice me cheating, so I cannot notice you noticing. Either I cheated or I didn't. With the blue eyes, there are either 101 or 100 of them. There are either 100 or 99 of them. They could speculate one level away, but with only one unknown they can't speculate further. There are not 500, or 52, or 1, or 0, or -8.

And since you're saying 97, and you're just an arbitrary blue-eyed person, the same can be said for every blue-eyed person... so the highest number anyone can guarantee is an answer to that question is 97. But that just adds another level of "...everyone can guarantee that..." to the question, which contradicts the fact that the question specifically states "to any arbitrary depth of guarantees", and we'd already claimed that, to any arbitrary depth of guarantees, the answer would be 98 at worst.
So your answer leads to a contradiction.

Not quite. I'm saying anyone can guarantee anyone sees at least 98, but given that hypothetical but possible scenario they could speculate, not guarantee, another could see at least 97. The break between the speculation and the guarantee is key. With one level of uncertainty (one unknown color), you can speculate one level away from the certain, but you cannot speculate upon the speculation without changing the possible conditions. By changing the conditions (possible # of blue eyes), you cannot use information based upon the initial conditions. The guru did not say "I see some with blue eyes" to a crowd containing a solitary blue eyed person, she said it to a mob of 100.

[lordatog]

Can A think B think C think D sees 96? No, because this A's knowledge that C sees 98, and A's knowledge that B knows that C and D can see 98.

This simply isn't true. A knows that B, C, and D can see at least 98, A knows that B knows that C and D each see at least 97, and A knows that B knows that C knows that D can see at least 96. Yes, A knows that B knows that D can actually see at least 97, and A knows that C knows that D can see at least 97, but A doesn't know that B knows that C knows that D see can at least 97. These distinctions are critical. Normal human reasoning essentially never goes this deep into hypotheticals, so it's understandable that this is hard to follow intuitively, but just because it's unintuitive doesn't make it wrong.

Edit: Fixed quote bracket

[douglasm]

Sigh.

Ignore the nested hypotheticals thing for now. It is most definitely correct, but you seem to have trouble understanding how and why. Let's try an alternate approach.

Under what circumstance would a person leave on day 1, the first opportunity? This should be quite obvious. It will happen if there is only one blue-eyed person on the island.
Under what circumstance would a person leave on day 2? The only information he has different from the previous case is that no one left on day 1. Thus, for someone to leave on day 2 he must have been uncertain about whether there were 1 or 2 blue-eyed people on the island and there must in fact be more than 1 blue-eyed person on the island. This will happen when a person is blue-eyed and there are two blue-eyed people on the island.
Under what circumstance would a person leave on day 3? The only information he has different from the previous case is that no one left on day 2. Thus, for someone to leave on day 2 he must have been uncertain about whether there were 2 or 3 blue-eyed people on the island and there must in fact be more than 2 blue-eyed people on the island. This will happen when a person is blue-eyed and there are three blue-eyed people on the island.
Under what circumstance would a person leave on day 4? The only information he has different from the previous case is that no one left on day 3. Thus, for someone to leave on day 3 he must have been uncertain about whether there were 3 or 4 blue-eyed people on the island and there must in fact be more than 3 blue-eyed people on the island. This will happen when a person is blue-eyed and there are four blue-eyed people on the island.
<repeat a bunch more times>
Under what circumstance would a person leave on day 100? The only information he has different from the previous case is that no one left on day 99. Thus, for someone to leave on day 99 he must have been uncertain about whether there were 99 or 100 blue-eyed people on the island and there must in fact be more than 99 blue-eyed people on the island. This will happen when a person is blue-eyed and there are one hundred blue-eyed people on the island.

Where is the error in the above logic? Yes, this uses hypotheticals, but they are iterative rather than recursive and should be easier to understand.

[Dan-o-Myte!]

This silly thing won't stop rattling around in my brain-meats. I've been thinking about the "common knowledge" argument, and I must say I've come around. I do indeed believe it is appropriate to apply it the way the champions of the solution have been doing. However I still stand by my assertion that it is incorrect. Here's why:

I see one big old glaring error staring us in the face that seems to obvious to have ever been missed. I don't recall seeing it pointed out anywhere in the last 18 pages but I admit some of that kinda became a blur so I might have missed it. In trying to be as concise as possible, as well as not muddying the waters with too many numbers most of us have been using only 1 number as the minimum eg: A sees 99 knows B sees 98 knows C sees 97... but somewhere along the line it gets forgotten that this is the minimum number x might be seeing, and been treated as the number x sees.

See, from a brown eyeds perspective, he sees 100 blue eyeds. He knows one of them sees not 99, but 99 or 100. Therefore he knows the next sees not 98, but 98, 99, or 100. And so on down the line until we get to the last. The final person is known to be known etc... to see 0, 1, 2, 3, 4, 5, ... 99, or 100. Not 0. What he is known to be known, etc.. to see does not grant any additional information, because it becomes less, not more, accurate the further down the line you go. So the fact that he might see any number from 0 to 100 is irrelevant. The only thing that matters is how many he does see, 99.

[douglasm]

The ridiculously long string of "knows that X knows that..." is not needed or used to establish a minimum, only to establish a reason for why the Guru's statement has an effect.

There are three critical things that matter here:
1) How many blue eyes a person actually sees establishes a maximum.
2) The Guru's statement establishes a minimum.
3) The passing of time and discrete opportunities to leave the island progressively increases the minimum.

The huge nested hypothetical chain of knowledge is only used to establish point 3, and it is not the only way to establish that point.

When the minimum and maximum meet, all the blue-eyed people determine their own eye color and leave. All the brown-eyed people still have a minimum and maximum that differ by 1 at that point, so they still don't know.

[Dan-o-Myte!]

Ok first of all I want to say I think I've gained some clarity over people's thought processes (my own included) so let me see if I can more precisely show where my sticking points are.

I've read and agree with the iterative progression from day one to day 100, but my understanding is that without the guru's statement the base case cannot be established so what would happen on day 1 and therefore each following day is uncertain, correct? So that given a situation with a single blue eye the guru's statement gives him the information he needs to leave on day 1.

I agree the number of blue eyes establishes the maximum, #seen +1.

I believe the brown eyes are irrelevant to the logic processes to solve the problem and can safely be left out altogether. Is this correct?

I do not see how the guru's statement can establish a minimum without using a huge nested hypothetical chain. I believe this would be required to solve the problem with iterative logic. If you can show me this how this is accomplished or give the page number of a post explaining it I would appreciate it.

If the huge hypothetical chain is used I understand how the guru's statement re-introduces information lost during the chain's construction, but I fail to see how the blue-eyes are any better off at the end of this chain than they were at the start. It seems to me that all they gained is greater uncertainty as to how many one could see.

Anyway I realize I started out as somewhat argumentative and it must be frustrating come here and not see your point after 18 pages of explanations, but try to understand I've read them too (if I'm honest I skipped a couple in the middle, so if there's a particularly brilliant rundown on pages 14 or 15 feel free to lynch me) and I'm unconvinced. It probably didn't help much that they were not in the same order I've been thinking about things. I'm sure everyone can agree that on the surface it seems preposterous that someone could give vital information by stating the obvious. Hopefully this can give us a better starting place to try to iron out the wrinkles, in whichever direction, and I appreciate the discussion.

Edit: After re-reading the solution page and some of the earlier forum entries I must concede that I am an ass. The solution is absolutely correct.
I can't say why but the key came to me by envisioning (envoicing?) the evil smart guy from the princess bride explain part of it to me. He says "You know that I know ... that you know there are at least 0. BUT: Do I know that you ... at least 0 and know that I know there are at least 1? ... Yes I do! How? The guru told me so! Ha ha ha ha ha ha ha ha..."

I know it can happen after 100 days. I think somehow it may be done in fewer, but I have no proof for that so therefore must default to the 100 I know works. I guess I might poke around through the old messages some more to look for more concrete proof that it must take 100. Anyway thanks and apologies to those who discussed it with me.

[douglasm]

Edit: And he edits the post before I finish typing. I'll add a proof of why 100 days is the minimum.

To prove that it can't be done in less than 100 days, consider it from the other direction. If the blue-eyed people leave on day X, why would they do so? The possibility of 99 blue-eyed people must have been eliminated within the past 24 hours. The guru's statement obviously doesn't do that in that short amount of time, so it has to have been eliminated some other way. The only other possible way is that if there were only 99 blue-eyed people they would have left on day X-1. Now, why would 99 blue-eyed people leave on day X-1? It must be either because of the guru's statement or because 98 people would have left on day X-2. Now, why would 98 blue-eyed people leave on day X-2? And so on.

You eventually get down to a lone blue-eyed person would leave on day X-99. It's not possible for anyone to leave before day 1, so the earliest possible date for the hypothetical loner to leave is day 1 and X cannot therefore be less than 100.

Original post preserved in spoiler:

Spoiler:

I've read and agree with the iterative progression from day one to day 100, but my understanding is that without the guru's statement the base case cannot be established so what would happen on day 1 and therefore each following day is uncertain, correct? So that given a situation with a single blue eye the guru's statement gives him the information he needs to leave on day 1.

Correct. This is why the guru's statement is important. The guru's statement does occur, however, so the base case is valid and so is the entire rest of the chain, so the end result is also valid.

I believe the brown eyes are irrelevant to the logic processes to solve the problem and can safely be left out altogether. Is this correct?

Not quite. For a complete solution you have to give a reason why the brown-eyed people would not (incorrectly) conclude that they have blue eyes. This is generally a pretty trivial thing you can tack on at the end, though, and they can otherwise be ignored.

I do not see how the guru's statement can establish a minimum without using a huge nested hypothetical chain. I believe this would be required to solve the problem with iterative logic. If you can show me this how this is accomplished or give the page number of a post explaining it I would appreciate it.

The guru's statement is quite simple and explicit, and exactly equivalent to "minimum blue-eyes = 1".

If the huge hypothetical chain is used I understand how the guru's statement re-introduces information lost during the chain's construction, but I fail to see how the blue-eyes are any better off at the end of this chain than they were at the start. It seems to me that all they gained is greater uncertainty as to how many one could see.

The huge hypothetical chain ends with "knows that there are at least 0 blue-eyed people on the island." The construction of this chain of hypotheticals does not in any way change what the people know. It is strictly an alternative way of expressing certain knowledge that they already have, and this particular way of expressing it happens to have an obvious interaction with the guru's statement. Specifically, the guru's announcement changes the end of the chain to "knows that there is at least 1 blue-eyed person on the island."

The huge nested chain of hypotheticals is essentially equivalent to someone going backwards through the iterative approach I outlined. Someone thinks "If I did not have blue eyes, when would the 99 blue-eyed people I see leave? Hmm, let's consider it from that guy's perspective. I've already assumed for the purpose of analysis that my eyes our brown, so he looks around and sees 98 blue-eyed people. He does the same thing I'm doing, assumes for the purpose of analysis that his eyes are brown, and considers it from the perspective of this other guy. I'm assuming my eyes are brown, in my imagination of that guy he's assuming his eyes are brown (even though they aren't), and in my imagination of his imagination he's thinking that this other guy looks around and sees 97 blue-eyed people..." Keep going and you eventually get to someone who, in your imagination of A's imagination of B's imaginations of C's imagination..., sees no blue eyes. Without the guru's statement, you get to this point and shrug, having figured out nothing useful. With the guru's statement, you figure out that this recursively imagined guy realizes his eye color and leaves. Then you figure out that the guy one layer of recursion below him would leave the next day, and extend it down the chain until you get to "if my eyes are not blue, all the blue-eyed people will leave on day 99". When they don't, you conclude that your eyes are blue and you leave on day 100.

You may have already read me trying to explain it this way before, but it's worth reiterating. If two statements say "A knows that B knows that...X knows Y" with a different number of repetitions of "knows that" in the middle, they are significantly different, and the one with more repetitions is the stronger statement. Something is common knowledge if you can insert an infinite number of "knows that"s into it and it will still be true. The product of logical deductions can be common knowledge if and only if either all facts used to derive it are common knowledge or you directly prove the infinite repetitions criterion.

At the beginning, every blue-eyed person on the island knows the following piece of information that, despite being known by all of them, are not common knowledge. You can insert a large number (100) of repetitions of "knows that" into a sentence about them and it will remain true, but not an infinite number.
1) There are either 99 or 100 blue-eyed people on the island, depending on the person's own eye color.

They also know the following pieces of information that are common knowledge:
a) All the islanders are perfect logicians
b) All the islanders can leave only by proving their own eye color
c) All the islanders will leave as soon as possible
d) The schedule of ferry departures
e) The observation and noncommunication abilities of all islanders

The guru's announcement adds the following piece of information to the pool of common knowledge:
f) There is at least 1 blue-eyed person on the island.

Item f is, of course, no news to anyone. Its introduction to the status of common knowledge, however, is.

Using only the information that is common knowledge, it is easily possible to deduce after one day that there are at least 2 blue-eyed people on the island. This fact becomes common knowledge at that time. Again, everyone knew it already but it was not previously common knowledge.

Using only common knowledge, everyone can easily deduce that after two days there are at least 3 blue-eyed people on the island. This fact becomes common knowledge at that time. And so on and so forth, until day 100 where the fact that there are at least 100 blue-eyed people on the island becomes common knowledge. At that moment, all blue-eyed people can combine this common knowledge fact with their own personal knowledge and conclude that they have blue eyes. This conclusion is personal knowledge, not common knowledge, but that doesn't matter because personal knowledge of your own eye color is sufficient to leave the island.

[maetharim]

Ok, first thing I would like to say is that I love XKCD and everything that you do; this is my first post so I wanted to say that right off. I work at a nationwide chain that shall remain nameless (but rhymes with "quest why") and this site is perhaps the number one reason for decline in productivity on the sales floor. I mean that in a good way. Anyway, regarding the "blue eyes" puzzle, one possible solution I can see that is different from the given one is this.

There is nothing in the write-up that says that a) the ferry has no driver, and I posit that it must because there must be some way for the ferry to ascertain the veracity of each person's claim that he/she knows his/her eye color and that b) the ferryman/woman is human and bound by human limitations and that c) the ferry always comes from the same direction to reach the island and that d) it only takes the span of one night for the ferry to reach the island and then return to the mainland and that e) the ferry is the only way to leave the island and that f) the humans in the puzzle are moral beings.

Considering all of the above, I posit that an acceptable, logical solution is for a person on the island train their body to allow them to swim the distance from the island to the mainland which should be an achievable human feat being that people can swim such (comparatively) vast distances as the English Channel.

Perhaps another acceptable, logical solution is for a person to overpower the ferryperson and commandeer the ferry themselves; thus allowing everyone to leave the island.

Now I admit that my first solution may not be workable since there is no indication of what kind of ferry is being used; I'm assuming a raft/barge type thing while a motorized ferry would cover more distance than a human would be able to do in one evening. This solution can also be easily defeated by asserting that the ferry is the only way to leave the island (sharks perhaps, or underwater raptors!)

The second solution I find to be much more plausible as nowhere do we have an indication of the morality of the individuals involved; only that they embrace logic and will follow any logical deduction to its immediate conclusion. There isn't even any need to outright murder the ferryperson, only incapacitate him or her so that the ferry may be used by the natives. The ferryperson could even be on the ferry, bound and gagged perhaps, on the trip to shore.

I apologize in advance if any or all of these ideas have already been suggested and proven wrong but I am coming into this discussion late and with no desire to read 16+ pages of posts.

I submit myself to the approval of my peers. XKCD is god.

[itaibn]

Two problems with your solution:
1. These guys spent wasted their life getting perfect logical enlightenment. They have no physical strength at all.
2. They actually quite like the island. They only leave because they logically must.

[maetharim]

Two problems with your solution:
1. These guys spent wasted their life getting perfect logical enlightenment. They have no physical strength at all.
2. They actually quite like the island. They only leave because they logically must.

Hmmm, I agree that those would be both quite reasonable obstacles for my solutions, but I fail to see the presence of those arguments in the formation of the problem.

[skeptical scientist]

Okay, if you want to be pedantic and look at exactly what it says in the statement of the problem, let's be pedantic.

Hmmm, I agree that those would be both quite reasonable obstacles for my solutions, but I fail to see the presence of those arguments in the formation of the problem.

No, but the idea that they want to leave is also quite absent. What it does say is, "Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay." It doesn't matter whether they want to leave, or whether they could leave without knowing their eye color, only that they stay if they don't know their eye color, and leave (that night) if they do. So your "solution", which contradicts this basic fact, is not a solution at all.

[maetharim]

Okay, if you want to be pedantic and look at exactly what it says in the statement of the problem, let's be pedantic.

Hmmm, I agree that those would be both quite reasonable obstacles for my solutions, but I fail to see the presence of those arguments in the formation of the problem.

No, but the idea that they want to leave is also quite absent. What it does say is, "Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay." It doesn't matter whether they want to leave, or whether they could leave without knowing their eye color, only that they stay if they don't know their eye color, and leave (that night) if they do. So your "solution", which contradicts this basic fact, is not a solution at all.

Ahh true, true; a good point. I would then ask the person who posed the riddle if there is actual desire on the part of the subjects to leave the island or if the ferry just acts like some sort of magnet and draws to it anyone who knows they're own eye-color, which seems somewhat odd.

[skeptical scientist]

Who cares, it's a riddle! Why does the knight want to pass through every square on a chess board exactly once?

[Dan-o-Myte!]

Using only common knowledge, everyone can easily deduce that after two days there are at least 3 blue-eyed people on the island. This fact becomes common knowledge at that time. And so on and so forth, until day 100 where the fact that there are at least 100 blue-eyed people on the island becomes common knowledge. At that moment, all blue-eyed people can combine this common knowledge fact with their own personal knowledge and conclude that they have blue eyes. This conclusion is personal knowledge, not common knowledge, but that doesn't matter because personal knowledge of your own eye color is sufficient to leave the island.

Yes this makes sense, I believe I understand. I think I just got my wires get crossed again, I'll attempt to paraphrase :
Once the common knowledge has been wound, so to speak, it is not then unwound with the new data but must be kept intact to keep the base case established. This line of thought is then concluded and we move on to the iterative progression which takes real time. Then each day the common knowledge chain can grow one level shallower while still keeping the base case intact, up until the day where the common knowledge becomes completely unwound and has the same minimum requirement as the personal knowledge, on day 100.

[halitus87]

Hi a uni mate sent me this
and i thought about it for a while and this is what i came up with
i havent looked at the solution provided yet, ill do that im a minute.

but Illd like some feed back on my solution
(sorry for the rough English, im an engineering student)

I say
Every one leaves at once except the guru
Based on the following

- the guru can not know her own colour because the has no way getting any information on it
- the answer is not no one leaves
- if one person figures out his own eye colour every one else with that eye colour must also know ( for what ever unknown logic that they KNOW) because they are all perfectly logical
there for all people of the same eye colour must leave at the same time.
- the guru doesn't actually help any one, as there are more than 2 blue eye people every person can see at least 1 blue eyed person.
- now because guru is useless, every one else has the exact same knowledge and is perfectly logical

OK SO.

They are all just as logical and have the same info.
if one person figures it out they all do (Sept guru, poor girl)

some one HAD to figure their colour out some how (becuase some one has to leave)
It doesn't matter how (its not in the question)

therefore they all leave on the first day after the guru talks
except the guru

I think I did it

Phillip

[phlip]

- the guru doesn't actually help any one, as there are more than 2 blue eye people every person can see at least 1 blue eyed person.

A large part of the counter-intuitiveness of the solution is that this is actually not the case.

Have a read through the official solution, and (at least the first few pages of) this thread. There's a lot there that explains why the guru's statement isn't absent of information.

[Kingreaper]

To help hint, without giving it all away if you haven't read the rest of the thread: Imagine a situation where there's only one blue-eyed person; will (s)he leave before the announcement?

Now imagine two blue-eyed people. Will they leave before the announcement? If not, why not? Will they leave immediately afterwards?

[graatz]

I'm sure you all love it when someone new stumbles upon a three year old post and decides to contribute his $0.02, but I find myself unable to resist.

Answering xkcd's questions on the solutions page:

1. What is the quantified piece of information that the Guru provides that each person did not already have?
All of this talk of stratified hypotheses and meta-knowledge is way too convoluted. It's clearly illogical to think that someone honestly thinks that someone thinks, etc. (times 97 or so), that there might only be 0 or 1 people with blue eyes on the island, in light of the fact that everyone knows that everyone else can see no fewer than 98 blue eyes. Instead, what the Guru is providing is the impetus for everyone to start thinking of his own eyes as blue or not-blue, as opposed to blue, brown, green, hazel, pink, yellow, etc. With this in place, each islander can now consider how the islanders would react based on whether or not his own eyes were blue.

2. Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?
Islanders don't need to consider these as actual possibilities, but rather acknowledge them as an inductive starting place. The logical islanders know that if there are actually n blue-eyed people, they will deduce it on the nth night. They know this because of induction from the trivial case.

Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?
The only way for n islanders to conclude their own eye color is blue is to wait through the hypothetical cases for n-1 nights. Although every islander can conclude that every other islander knows there are no fewer than 98 blue-eyed people, their inability to communicate with each other precludes the possibility of agreeing to use this as the "first night" case.

This is the best way I have of looking at it. A lot of people answer Q1 that the new information is that everyone now knows that everyone knows that there is at least one blue-eyed person, but that's simply not true. Every islander can conclude that every other islander knows that there are no fewer than 98 blue-eyed islanders. For that matter, everyone can conclude that everyone else knows there are no fewer than 98 brown-eyed islanders. However, no one knows that there are no red-eyed islanders, nor can anyone conclude that some islanders might not have that knowledge. So it isn't knowledge about the other islanders' knowledge that is being provided by the Guru.

[Random832]

:evil: I'm sure you all love it when someone new stumbles upon a three year old post and decides to contribute his $0.02, but I find myself unable to resist.

Answering xkcd's questions on the solutions page:

1. What is the quantified piece of information that the Guru provides that each person did not already have?
All of this talk of stratified hypotheses and meta-knowledge is way too convoluted. It's clearly illogical to think that someone honestly thinks that someone thinks, etc. (times 97 or so), that there might only be 0 or 1 people with blue eyes on the island, in light of the fact that everyone knows that everyone else can see no fewer than 98 blue eyes.

For any arbitrarily chosen Person A and Person B whose eyes are in fact blue:
Person A does not know that person B knows that anyone on the island can see 98 (or, rather, 196 - but there's an implicit "people with") blue eyes.

A: sees 99, thinks B might see 99 or might only see 98
B: if we assume (as A must consider a possibility) that B sees 98, thinks A (or C or whomever) might only see 97.

It's longer to write, but no less valid, to take this all the way to 1 or 0.

[Yakk]

All of this talk of stratified hypotheses and meta-knowledge is way too convoluted. It's clearly illogical to think that someone honestly thinks that someone thinks, etc. (times 97 or so), that there might only be 0 or 1 people with blue eyes on the island, in light of the fact that everyone knows that everyone else can see no fewer than 98 blue eyes. Instead, what the Guru is providing is the impetus for everyone to start thinking of his own eyes as blue or not-blue, as opposed to blue, brown, green, hazel, pink, yellow, etc. With this in place, each islander can now consider how the islanders would react based on whether or not his own eyes were blue.

97 levels of abtraction are unreasonable in a practial person.

These aren't practical people. They are perfect logicians. They don't behave like practical people.

Every islander can conclude that every other islander knows that there are no fewer than 98 blue-eyed islanders.

The 4 person island.

We pick an islander who sees 3 blue eyed people. Call this person W.

Case A has 4 blue eyed people, and case B has 3 blue eyed people. The islander doesn't know which.

The Islander does know that the other islanders see either 2 or 3 blue eyed people.

Case A: the other Islanders see 3 blue eyed people.
Case B: the other Islanders see 2 blue eyed people.

In case B (which this Islander cannot rule out), what does this Islander know about what the other Islanders know?

Well, they are blue eyed; and they see 2 or 3 blue eyed people. Let's have Islander W pick another islander to model -- Islander X -- and determine what W knows about X's perception.

W knows X sees 2 or 3 blue eyed people. W will make assumption B for now (we can work on assumption A later).

So W knows that X sees 2 blue eyed people. W then imagines X picking one of those blue eyed people, and asking "what do I know about how many blue eyed people this guy sees"? Call the blue eyed person W is imagining X is imaginging Y.

W imagines X imagines Y can see 1 or 2 blue eyed people (because W imagines X doesn't know if X has blue eyes).

Now, W knows that Y sees at least 2 blue eyed people; but W cannot determine if X can determine that Y sees at least 2 blue eyed people!

So W has to imagine X imaginging Y seeing only 1 blue eyed person, even though W knows that Y isn't seeing only 1 blue eyed person!

And when W imagines X imaginging Y, Y ends up imaginging what the blue eyed person Y sees is seeing (call this guy Z) -- the Y that is being imagined by the W being imagined by W that is!

And even though W knows that Z cannot be seeing 0 blue eyed people, the Z being imagined by the Y being imagined by the X being imagined by the W doesn't know this.

You would claim that W clearly knows everyone can see 2 blue eyed people. But imagine that W isn't blue eyed (there are only 3 on the island). Now W thinks about the behaviour of X. X only sees 2 blue eyed people (but as far as W knows, it could be 3). X's behaviour depends on what X sees, and not on what W sees; so W's model of X's behavoiur has to include the possibility that X only sees 2 blue eyed people.

Now imagine we had X on the island, and X sees 2 blue eyed people. Is it right for X to presume that everyone can see 2 blue eyed people? When W is modeling the behaviour of X, this is the perception that W is modeling.

But you already knew this, because you read the entire thread before posting.

[graatz]

And even though W knows that Z cannot be seeing 0 blue eyed people, the Z being imagined by the Y being imagined by the X being imagined by the W doesn't know this.

See, way too much thinking

Ultimately, A cannot model B modeling C modeling D as ... Y modeling a situation where Z could be seeing zero blue-eyed islanders, because A knows that B knows that C knows that Z can see more than one person with blue eyes, so they can't validly (logically) model a case where that is a valid hypothesis that Z would make. It only really works for small numbers of actual blue-eyed islanders, because there has to be a case where however many steps A is away from Z, A could still rationally assume that the person under him could actually conceive of Z thinking that. On the 100 blue-eyed island, the thought that an "imagined" Y could imagine Z as seeing zero blue eyes is patently absurd. For any Z islander that Y would honestly conceive of, he knows that Z is seeing several blue-eyed islander. And not only would the "imagined" Y know it, so would the "imagined" X all the way back to the actual A.

For that matter, the islanders could be imagining what other islanders are thinking about the count of brown eyes, the count of green eyes, and the count of red eyes before the Guru speaks. Because of the number of blue and brown eyes, everyone knows that everyone knows that at least one islander has brown eyes, and that each of them knows that at least one islander has blue eyes. The Guru adds no quantitative data to every islander's knowledge base. The Guru only sets the stage to start thinking of your own eyes as specifically blue or not blue, concentrating the stream of hypothetical "what is everyone else thinking" in terms of blue eyes as opposed to any other color.

Believe me, I understand the induction process that concludes that n blue-eyed islanders will leave on the nth night, which involves each of them contemplating the event that one person sees zero other blue-eyed islander and working up to the actual number.

[Random832]

And even though W knows that Z cannot be seeing 0 blue eyed people, the Z being imagined by the Y being imagined by the X being imagined by the W doesn't know this.

Hmm... Eva or TTGL?

Which works better as a tagline, "This is the Z that exists in Y's mind" or "Don't believe in Z! Believe in Y who believes in Z!"

It only really works for small numbers of actual blue-eyed islanders, because there has to be a case where however many steps A is away from Z, A could still rationally assume that the person under him could actually conceive of Z thinking that.

You see, you're only saying this because you aren't a perfect logician. Because it's actually such a ridiculously illogical thing to say that half the people on this thread wouldn't accept it despite also not being perfect logicians. There is no number of steps at which it magically goes from working to non-working. You just kind of waved your hands and said there is, because you didn't think of it.

[graatz]

You see, you're only saying this because you aren't a perfect logician.

I think at this point we are confusing what it means to be perfectly logical. In effect, you are claiming that a perfect logician would hold it plausible that someone is assuming something that they both know is not true, but is conceivably true based on further hypothesis about what a third and fourth person could hypothesize as true, although they also both know it not to be true.

On the other hand, I'm claiming that the perfect logician knows the difference between what Y actually knows and what a Y modeled by X modeled by W could be thinking is true. My perfect logician knows that the only way for each person to seriously begin to consider the color of his own eyes, he needs to know that all islanders are considering the case of the same eye color, which is impetus that the Guru provides them.

All of this imagined Y who can imagine Z imagining that he might be the only blue-eyed person on the island is akin to the judge who tells the prisoner that he will be executed some day next week that will come as a surprise to him. 'Well,' the prisoner thinks, 'I can't be executed on Friday, because by the time Thursday comes around it will no longer be a surprise to me.' But then the prisoner starts thinking about it more: 'The judge knows he can't surprise me on Friday, and knows that I'll know that. Because of this, I can rule out Thursday, too, as Friday is off the table, and the same logic would apply to Thursday, too.' In fact, using inductive reasoning, the prisoner concludes that he can't ever be executed, for knowing what he knows, and knowing what the judge will know he knows, no day could ever come as a surprise. Much to the prisoner's surprise, however, he was executed on Tuesday.

[Random832]

On the other hand, I'm claiming that the perfect logician knows the difference between what Y actually knows and what a Y modeled by X modeled by W could be thinking is true. My perfect logician knows that the only way for each person to seriously begin to consider the color of his own eyes, he needs to know that all islanders are considering the case of the same eye color, which is impetus that the Guru provides them.

There's no reason they can't already be considering every case simultaneously. The problem is that _none_ of the cases are any good without someone saying, in public (so that there is no doubt at any level that everyone knows it), that some particular eye color exists.

[Klotz]

Can somebody explain to me what information the Guru gives, if everyone can already see someone with blue eyes?

[lordatog]

The information the Guru gives is due to the fact that the claim is made in public. Everyone can see that everyone is there to hear it, and everyone can see that everyone can see that everyone is there to hear it, and everyone can see that everyone can see that everyone can see that everyone is there to hear it, and so on, infinitely deep.

Suppose for a second that there are only two people on the island with blue eyes. Now, everyone on the island knows that there is at least one person with blue eyes, so you might suppose that the Guru's claim is useless. However, consider blue-eyed person A. He can see one person with blue eyes (blue-eyed person B), and thinks "I know that there is at least one person on the island with blue eyes, but I don't know if B knows that. My eyes may or may not be blue, and if they aren't, then B cannot see anyone with blue eyes." So, even though everyone on the island already knew what the Guru had to say, A did not know that B knew it (and B did not know that A knew it). Because the Guru's claim was made in public, though, A can see that B is there to hear it, and now knows that B knows that there is someone with blue eyes on the island.

With three people, it's more complicated, but works in the same way. A knows that there are blue-eyed people on the island. A knows that B knows that there are blue-eyed people on the island (because they can both see C). A knows that C knows that there are blue-eyed people on the island (because they can both see B). A does NOT know, however, whether B knows that C knows that there are blue-eyed people on the island. He thinks "My eyes may or may not be blue. If they are not, then person B will think 'My eyes may or may not be blue. If they are not, then C cannot see anyone with blue eyes'". Now, A knows that C can see someone with blue eyes, but he doesn't know if B knows that. This distinction is critical. Once the guru has spoken, though, A can see that B can see that C is there to hear it, and now knows that B knows that C knows that there is someone with blue eyes on the island.

For any number of blue eyed people, the chain of knowledge is one step too short for people to leave on their own. If there are 26 blue eyes, then A knows that B knows that C knows that... that X knows that Y can see someone with blue eyes, but you can't extend that to Z. A does not know whether B knows that C knows that... X knows that Y knows that Z can see someone with blue eyes. After the guru has spoken, however, the chain can be extended, because when the claim was made, everyone was there and paying attention, and A saw that B was there to see that C was there to see that... Y was there to see that Z heard the claim.

This is very unintuitive, largely because humans simply don't think like this. We understand "I know that you know that he knows ____" a few levels deep, but if you try to go beyond that your brain just gives up. The islanders, however, are not human - they are perfect logicians, and no human could ever be a perfect logician.

[Macbi]

Can somebody explain to me what information the Guru gives, if everyone can already see someone with blue eyes?

The Guru tells everyone that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone can see someone with blue eyes. Which they didn't know before.

[Nitrodon]

The Guru tells everyone that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone can see someone with blue eyes. Which they didn't know before.

They don't learn that until the end of the first day. Until then, everyone merely knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that there is at least one person with blue eyes.

[DrSir]

The information the Guru gives is due to the fact that the claim is made in public. Everyone can see that everyone is there to hear it, and everyone can see that everyone can see that everyone is there to hear it, and everyone can see that everyone can see that everyone can see that everyone is there to hear it, and so on, infinitely deep.

Suppose for a second that there are only two people on the island with blue eyes. Now, everyone on the island knows that there is at least one person with blue eyes, so you might suppose that the Guru's claim is useless. However, consider blue-eyed person A. He can see one person with blue eyes (blue-eyed person B), and thinks "I know that there is at least one person on the island with blue eyes, but I don't know if B knows that. My eyes may or may not be blue, and if they aren't, then B cannot see anyone with blue eyes." So, even though everyone on the island already knew what the Guru had to say, A did not know that B knew it (and B did not know that A knew it). Because the Guru's claim was made in public, though, A can see that B is there to hear it, and now knows that B knows that there is someone with blue eyes on the island.

With three people, it's more complicated, but works in the same way. A knows that there are blue-eyed people on the island. A knows that B knows that there are blue-eyed people on the island (because they can both see C). A knows that C knows that there are blue-eyed people on the island (because they can both see B). A does NOT know, however, whether B knows that C knows that there are blue-eyed people on the island. He thinks "My eyes may or may not be blue. If they are not, then person B will think 'My eyes may or may not be blue. If they are not, then C cannot see anyone with blue eyes'". Now, A knows that C can see someone with blue eyes, but he doesn't know if B knows that. This distinction is critical. Once the guru has spoken, though, A can see that B can see that C is there to hear it, and now knows that B knows that C knows that there is someone with blue eyes on the island.

For any number of blue eyed people, the chain of knowledge is one step too short for people to leave on their own. If there are 26 blue eyes, then A knows that B knows that C knows that... that X knows that Y can see someone with blue eyes, but you can't extend that to Z. A does not know whether B knows that C knows that... X knows that Y knows that Z can see someone with blue eyes. After the guru has spoken, however, the chain can be extended, because when the claim was made, everyone was there and paying attention, and A saw that B was there to see that C was there to see that... Y was there to see that Z heard the claim.

This is very unintuitive, largely because humans simply don't think like this. We understand "I know that you know that he knows ____" a few levels deep, but if you try to go beyond that your brain just gives up. The islanders, however, are not human - they are perfect logicians, and no human could ever be a perfect logician.

But if you see at least two people with blue eyes, then everyone must be able to see someone with blue eyes. This is where humans diverge from super-logical processors ;P

[BlackSails]

[quote="DrSir"

But if you see at least two people with blue eyes, then everyone must be able to see someone with blue eyes. This is where humans diverge from super-logical processors ;P[/quote]

No, that fact is obvious to the islanders as well.

[Phrozt]

Would kind of suck if someone with blue eyes died...

[ashort4]

The solution provided by xkcd is actually incorrect. The solution operates on the reasoning that each of the x number of blue-eyed people see x-1 blue-eyed people, and can assume that they don't have blue-eyes, so they can imagine that each of the x-1 they see individually sees x-2. In other words, if there are 3 blue-eyed people, each sees 2, and can assume that both of the 2 only see 1. If there are 5, each sees 4, which makes it possible that each of the 4 only see three, and each of the three they would assume to only see 2. Each blue eyed person watches the whole process from the perspective of a brown-eyed person until they collectively realize they are the final blue-eyed person. This works fine exactly up to the point where he developed the solution, but no further. The maximum number of blue-eyed people that this style of reasoning works for is 5.

If there was only 1 blue-eyed person, he would know his eyes were blue, because he sees 0 blue-eyed people; he could leave the first night. If there were only 2 blue-eyed people, each would only see 1 blue-eyed person, who they could assume sees 0 blue-eyed people, and the presence of the other blue-eyed person the next morning would prove that they see 1 blue eyed person also, so each one also must have blue eyes. If there were 3 blue-eyed people, each would only see 2 blue-eyed people, who they would imagine to see only 1 blue-eyed person. On the first morning, they would still see 2 blue-eyed people, and they would realize that if these were the only blue-eyed people, they would both realize it that day and leave that night. When they were still there the next morning, each would realize they were the third blue-eyed person, and they would all leave that night. If there were 4 b.e.p, they would each see only 3, and tentatively think that each of the 3 only saw 2. The first morning they each still see 3 b.e.p, but if each of these 3 only sees 2, then the next morning each of the three would realize they are blue-eyed when the two they see haven't left, and they'll leave the third night. When they don't leave that night, each realizes they must each see 3 blue-eyed people also, and they can conclude that they themselves are the 4th blue eyed person. If there were 5 b.e.p, they would each see only 4, and imagine that each of the 4 only sees 3. Basically, they would be watching the previous scenario (with 4 b.e.p.) from the perspective of a brown eyed person, until they reached the 4th morning and all 4 were still present, and when they would each realize they were the fifth and last.

The problem comes at six blue-eyed people: 6 see 5 who apparently see only 4, who could possibly each see only 3. In other words, b.e.p #1 sees 5 b.e.p from the perspective of a brown eyed person, unaware that he has blue eyes. Each of the 5 he sees apparently only see 4 from the perspective of another self-assumed-to-be-a-brown-eyed person who actually has blue-eyes, and each of the 4 they see possibly only sees 3. They know this to be possible for each successive blue-eyed person to imagine, but they also each know there are actually 5 blue-eyed people in front of them. When each can see at least 5 each morning, they realize there is no way for the 5 to deduce how many there are. At the very least, to the 6th blue eyed person, each of the 4 blue-eyed persons known to the 5th must see 4 other blue-eyed people. If there WERE only 4, each of the 4 would see only 3, who they would imagine to see only 2, and the process could continue as usual. But all known blue-eyed people KNOW there are actually at least 4, so their reasoning cannot function based on the assumption that if there were 2 they would leave the second night, and if there were 3 they would leave the third night. Their collective understanding of the fact that there are 5 even though each of the 5 could possibly only be conscious of 4 undoes the reasoning of the solution. The solution absolutely hinges on the possibility that each of the blue-eyed people could possibly see ONLY 2 others; this is the crucial first step in the reasoning process. With 6 blue-eyed people, let alone 100, they cannot possibly reduce their reasoning to allow for each to only see 2, so the deduction falls apart. Each night effectively becomes the first night, because no new information is gained over time- each blue-eyed person is left with the possibility that they have green, brown, orange, or any colored eyes, and they cannot decide.

The true solution is that the guru provides no new information, and no one leaves. I'm almost appalled that the plethora of logicians here and elsewhere haven't followed the reasoning out past step 5, but there it is. Apparently the puzzle really is the hardest in the world, so hard that the accepted solution isn't even right. The solution provided is enticing, but the assumption that because it works for 1, 2, 3, 4, or 5 blue eyed people, it works for ANY number, is false.

[phlip]

Would kind of suck if someone with blue eyes died...

Well, let's see...

Spoiler:

If there was one blue-eyed person, and they died before they left, then obviously, noone would leave.

If there were two blue-eyed people, and one of them died before night one, then the other person wouldn't be able to get any information. But if they die on day 2, then the other person already knows they didn't leave on night 1, so the still-alive one will still leave on night 2.

If there are three blue-eyed people, and one of them died before night one, then noone leaves, but if one dies on night two, then each of the living ones knows that the two-person case still works, so when they don't leave on night two, they still learn about their own eye colour and leave on night 3.

And it continues like this.

I think it generalises too... as long as strictly fewer than n blue-eyed people have died before night n, for all n, the survivors will still leave at the appropriate time.

[edit]
I wrote most of this before ashort4's post, but just got distracted before submitting it...

Maybe I'll read through all that and answer it eventually, or maybe someone else can take it this time...

But I will, however, say this:
You claim that the solution works for 5 people, but doesn't work for 6. That is, if there are 5 people, they will leave on day 5, but if there are 6 people, they will never leave.

But consider: you're on the island, and can see 5 blue-eyed people. The announcement happens, 5 days come and go, and those 5 blue-eyed people have not left the island. Clearly, if your eyes weren't blue, they would have left, because, as you said, the 5-person case works. But they haven't left. Why can't you deduce that your eyes must be blue, and leave on day 6?

[ashort4]

Um, for the exact reason I described. Why don't you actually read it before trying to argue with it?

edit: Gah. I might as well try to clarify as long as I'm at it.

So- the only way 5 people are able to leave the fifth night is because they can reduce the possibly number of blue-eyed people hypothetically knowable to the other blue-eyed people to be 2 at one point. I'll try to illustrate it another way:

Blue-eyed person one: This is an arbitrary blue-eyed person, any one of the five. We'll examine the problem from his point of view. As it stands, b.e.p #1 has no reason to assume his eyes are blue. He sees four blue eyed people, and knows that each of the four must see at least three. B.e.p #1 is aware that he could have blue eyes, so he is open to the idea that the 4 he sees also see 4. If b.e.p #1 does not have blue eyes, and the four blue eyed people see only three, b.e.p #1 realizes that b.e.p #2 also has no reason to think he has blue eyes, so the 3 b.e.p that b.e.p #2 sees could possibly each see only two b.e.p. Keep in mind that we are witnessing this from blue-eyed person #1s perspective, because b.e.p #2 actually sees 4 just like #1 does.

I'll go ahead and clarify this: the first morning is when the guru speaks, the first night is the night following the guru's proclamation.

So, if b.e.p #3 sees just 2 blue eyed people, as b.e.p #2 can safely assume, then on the third morning, when the two b.e.p. that b.e.p sees are still present, b.e.p #3 would realize he was the third blue eyed person, and they would leave the third night, unless b.e.p #3 also sees three people- including b.e.p #2. B.e.p #3's presence on the fourth morning would clue b.e.p #2 into the fact that he also has blue eyes, because clearly each b.e.p he apparently witnesses (from b.e.p #1's perspective) also sees another b.e.p. They would all leave the fourth night, but they all see b.e.p #1 as well, so they finally each realize the 4 they are watching have also been watching them, and they all leave the fifth night.

Ah, great. Solved nice and tidily, for if it works for five people, it must work for any number! Simple, effort-free induction. BUT WAIT! What if there were 6 blue-eyed people watching this process? Let's examine, again from b.e.p #1's perspective.

B.e.p #1 now sees 5 b.e.p in front of him. To #1, b.e.p #2 apparently sees 4 b.e.p in front of him, which, since he also doesn't realize he has blue eyes, seem to him to each see only 3, if b.e.p#1 and 2 don't have blue eyes. They need to be able to reduce the possible number of b.e.p to 2, because the only way they can begin the deductive process is if at some point just two b.e.p seem as if they are going to leave the island on night two and shock the others by still being present on morning 3, as happens in the case above. However, when each b.e.p #3 is clearly aware of at least 3 other b.e.p, no insight is gained on the third morning- the chain of realizations leading up to the final b.e.p realizing their eye color cannot start without the 2 person event. B.e.p #3 sees at the very least 3 B.e.p, and only if b.e.p #1 disregards the 4 others that b.e.p #3 obviously can see! When it gets to the second night, b.e.p.#3 might seem to be thinking (from b.e.p #2's perspective as imagined by b.e.p #1) "The three I see will be leaving tomorrow night if I don't have blue eyes."

In reality, however, b.e.p #2 also sees #1, so he knows b.e.p. #3, 4, 5, and 6 also see #1- each is known be all to see at least 4 b.e.p. Being perfect logicians, they know that because there is no possible combination of b.e.p who could think there are only 2 b.e.p around, no new information is gained on the second morning that would lead to new information on the third morning and new information on the fourth morning, etc. The chain of revelations is broken; the islanders all know they are still trapped.

To risk being overly redundant, the only way 3 islanders would be able to leave the third night is if they each realized on the third morning that the only 2 bep they see are still on the island, and that they are the third. The only way 4 islanders would be able to leave the fourth night is if they each realized on the fourth morning that the only 3 bep they see are still on the island, and that they are the fourth. The only way 5 islanders would be able to leave the fifth night is if they each realized that on the fourth morning, the only 3 bep the other 4 might only see were still around, so the 4 would leave that night, and if 5 realized on the fifth morning that the 4 each see more than three and that they are the fifth. The only way 6 islanders would be able to leave the 6th night is if the guru said "there are 6 blue eyed people", because the 5 that they see cannot possibly deduce their own eye color, let alone the 6th. Again, this is because each of the 5 also see 5, and cannot reduce this down to a possible, revealing two. When they can't logically reduce the number of b.e.p seen by any one b.e.p to two, it is no longer a question of what night it is. For the same reason that the 100 blue eyed people can't leave on night one in the solution provided on the site, the six can't leave on night six- that is, the 100 can't leave because the logical induction xkcd imagines hasn't played out yet, and the 6 can't leave because the logical induction CAN'T play out- it has no starting point.