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

[Gelsamel]

I phrased it wrong, it's the possibility that the Guru was referring to them. If the guru was referring to them then they know they have blue eyes, otherwise they possibly have anything.

I'll buy that--and I can see where my confusion was as well, since I try to use "at least one person has blue eyes" as a reduced piece of information, which is distinct, but I think these two are equivalent with respect to the puzzle.

Edit: Still, I'm having problems seeing this as a simpler way of explaining it, maybe just cause I don't see the explanation from this angle. Could you post a sample?

A - "The Guru could be referring to me. If I was the only blue eyed person all I would see was brown eyed people, therefore the guru HAD to be referring to me, and my eyes are blue. If there is only 1 blue eyed person and it wasn't me then that person would leave on the first night because he realised he had to be the one the guru was referring too. If there are 2 blue eyed people then he won't leave because he isn't totally sure the guru is referring to him. If he isn't totally sure that the guru is referring to him then he must be seeing another blue eyed person since all I see is a blue eyed and the rest are brown and a green the only possible other person he could be seeing who is blue has to be me." etc.

However he has to know that the blue eyed people he is seeing know that they could possibly be the one, otherwise they won't go through the same logical progression 'A' above and they WON'T be 'testing' if it's them or not by observing how other blues act which would skew the results.

If the guru made 2 separate announcements to half the group each and both groups know about both announcements then counting works, however if the guru misses one person then tells that person in secret then the counting won't start because they're not sure if that last person knows and the link is broken.

I'm not real good at explaining this stuff but that's the way my mind goes through it.

[yy2bggggs]

So, after 4 days, 3 people leave for a completely different reason, on a 3 day trip, then return. What happens?

[Gelsamel]

So, after 4 days, 3 people leave for a completely different reason, on a 3 day trip, then return. What happens?

If it were possible for the people to go out of view of everyone else (in the puzzle everyone is always able to view each other) or if they were able to leave the island for a period of time for a holiday then then you can't definitely prove your eye colour.

[yy2bggggs]

So, after 4 days, 3 people leave for a completely different reason, on a 3 day trip, then return. What happens?

If it were possible for the people to go out of view of everyone else (in the puzzle everyone is always able to view each other) or if they were able to leave the island for a period of time for a holiday then then you can't definitely prove your eye colour.

The 97 blue-eyed people will leave on day 100. The remaining three will leave on day 103, and everyone else on day 104. After 4 days, you don't need all 100 blue eyed people for the 97 to conclude they have blue eyes, and for the 3, their conclusions resume they day they get back; after 97 days, they only need themselves to continue this clock.

Leaving "during the night" can be thought of as an event as well that happens every measurable night. If everyone left for seven days to different destinations, then came back, that night simply doesn't count (it's as if for that particular week, you just say people leave "during the week" rather than 'during the night").

Or at least, this is what I say.

Edit: Changed my mind. The 97 leave on day 99. The brown eyed people on day 100. Remaining three leave on day 102.

[Hangdawg]

My roommate and I disagree over the solution of this problem. He thinks I'm crazy and completely illogical for disagreeing with him, so I'll see what you guys think.

I think this solution is bunk for reasons a few people have already tried to explain.

I'll try to explain why as well:

In order for one to gain information, one has to present a hypothesis that can be tested. If one already knows his hypothesis to be false, then any following logic based upon a true hypothesis cannot be used to gain new information.

For example: If A is true then either B or C is true. If C is true, then D is true. Let's say I know D is false; therefore, B is true. Now let's say I knew from the beginning that A was false. Can I still use the logic below A and say that B is true because D is false? NO! Any "Perfect Logician" would know this.

This "solution" requires each person to make a hypothesis that he knows to be false in order to gain information. In reality, none of the "Perfect Logicians" can make the hypothesis of 1 blue-eyed person that is required to start the nightly countdown.

The "solution" only works for the case of 3 or fewer blue-eyed people.

The inductive "solution" says that since the case can be solved for 3, all the 4th person has to do is propose the hypothesis that there are only 3; but this is not the case because a hypothesis of 3 includes all the hypotheses within 3, the last of which is already known to be false, so the initial hypothesis of one can never be proposed.

The 4th person's logic must follow this pattern:

There must be either 3 or 4 and no one can see fewer than 2.
If 3, then they see 2 and they may hypothesize either 2 or 3.
But no one on the island can hypothesize that there is only one blue-eyed person because everyone must see at least 2.
Since no person on the island can hypothesize
that there is only 1 blue-eyed person on the island,
then the guru's statement does not present anyone with a valid hypothesis,
and the first night's ferry cannot be used to test the hypothesis;
therefore, no new information has been added to the system.

And all the Perfect Logicians cannot learn their eye color and so are doomed to remain forever on their island.

This puzzle may illustrate a valid mathematical theorem, but I do not agree that the mathematical theorem perfectly applies to this situation given the rules of the problem.

What do you think?

[skeptical scientist]

The fourth blue eyed person hypothesizes that there are three blue eyed people. Furthermore, he hypothesizes that one of those three hypothesizes that there are two blue eyed people. Furthermore, he hypothesizes that one of those two blue eyed people hypothesizes there is only one blue eyed person. Hence, there are hypotheticals inside hypotheticals, and in the highest order hypothetical, there is only one blue eyed person. This is not a contradiction of any known facts, as it is only a hypothetical.

If the hypothetical that there was only one blue eyed person were hypothetically true, then that person would leave on night one, so on the second day, the hypothetical person who sees only one blue eyed person knows that there are at least two, and hence he has blue eyes, so he would leave on the second night (hypothetically.) So on the third day, the hypothetical person who sees only two blue eyed people knows he has blue eyes as well, and leaves on the third night. Since this does not happen, on the fourth day, all four blue eyed people know that there are at least four blue eyed people, and all of them only see three, so all of them leave.

[Hangdawg]

This is not a contradiction of any known facts, as it is only a hypothetical.

What is the world coming to when we can claim to know things based on knowledge gained within a completely hypothetical situation?

Is knowledge gained by fictional characters in a hypothetical situation really knowledge gained?

I'll say that if the world is a pea floating in an alien's bowl of pea soup, then in about five minutes we'll all be dead, stewing in the digestive juices of the alien. What am I to do? Can I really claim to know the world is about to end because in my hypothetical situation this is true?

Let me replace these hypotheticals with logically equivalent ones:

Either 100 or 99.
If 99
Those hypothesize 99 or 98.
If 98
Those hypothesize 98 or 1+1 = 3.
If 1+1 = 3
Those hypothesize 1+1 = 3 or 2+2 = 5.
If 2+2 = 5
Hypothesize .....
If .....
Hypothesize 100 + 100 = 300
Someone tells the logicians that 100 + 100 != 300.

Does this still work? I cannot see how it does.

[yy2bggggs]

What is the world coming to when we can claim to know things based on knowledge gained within a completely hypothetical situation?

You're confusing the two distinct meanings of "hypothesize" and "hypothetical".

[bitwiseshiftleft]

What is the world coming to when we can claim to know things based on knowledge gained within a completely hypothetical situation?

The logicians are proving their eye color by contradiction. To prove a statement P this way, you assume that P is false, and then derive a contradiction. Then the rest of the proof is predicated on an entirely false, hypothetical situation, and derives a false conclusion. There isn't anything wrong with this; it's how logic has worked for millenia.

There is, however, one minor issue with the blue-eyed perfect logicians, namely Godel's Incompleteness Theorem: if someone is a perfect logician, he cannot know it, or at least cannot use it in his reasoning. For suppose the Guru had said, "You cannot prove this statement." Call this statement S. Then any islander could prove S as follows:

Either I can prove S or I can't.

Suppose I could prove S. Then S would be true, because I'm a perfect logician, and cannot make a logical error.

Suppose on the other hand that I can't prove S. Then it would also be true, because S says precisely that I can't prove it.

Either way, S is true.

But of course, proving S in this way renders it false, and perfect logicians cannot make such an error. This is a contradiction. The problem here isn't the self-reference, as statements like S can be tweaked so as not to be self-referential; rather, it's the logician assuming that he is perfect. In a technical sense, S is a reasonable statement (at least when you make it non-self-referential), and it's true, and can't be proved.

This argument sounds a lot like "this sentence is false," and for good reason: the same argument shows that statements in a logical system L cannot talk about whether other statements in L are true (but they can talk about statements in smaller logical systems being true...).

As it happens, this does not totally ruin the problem: you can tweak the "rules of the game" to make logical sense. But doing so ruins the elegance.

Edit: clarified a few things.

[phlip]

Hangdawg: Say you're on the island and you see 3 blue-eyed people. There are four, counting yourself, but you aren't to know that. Let's call these 3 people A, B and C, because imagination is for losers.
Now, as far as you know, A might only see 2 blue-eyed people. If he does, then he might think that B can only see one blue-eyed person.

It is thus completely accurate to state the following:
"I know that B can see at least 2 blue-eyed people, but I do not know if A knows this."
This can be extended to:
"I know that C can see at least 2 blue-eyed people, and I know that A knows that C can see at least 1 blue-eyed person, but I do not know if A knows that B knows that C can see any blue-eyed people."

All of this knowledge is real, not hypothetical. Indeed, nothing hypothetical has happened yet... we're merely exploring the boundaries of our knowledge, including our knowledge about what other people know.

After the guru's pronouncement, however, you do know that A knows that B knows that C knows that the Queen of England knows that the price of cheese in Yugoslavia is affecting trade routes. This knowledge is also real, and it is something we didn't know before.

After the pronouncement, come the hypotheticals. After noone leaves the first night, you say "if there was only one blue-eyed person, they would have left, therefore there is more than one blue-eyed person." Now, you knew the conclusion to this already. You even knew that A knew this. But you didn't know that A knew that B knew this. And now you do, because B must come to this conclusion, being perfectly logical. And A must also come to the conclusion, since he is perfectly logical, and knows B is also perfectly logical.

After noone leaves the second night, you say "if there was only two blue-eyed people, they would have both realised that there are at least two blue-eyed people, and both left. They did not, therefore there is at least three blue-eyed people." Again, you already knew this, but you didn't know that A knew it. Now you do.

After noone leaves the third night, you say the same thing, and realise there are at least four blue-eyed people. This is news to you, and it means your eyes must be blue. Thus you leave after 4 nights, as do the other 3 people who went through exactly the same reasoning as you did.

[Hangdawg]

Philip: I understand the inductive solution. I agreed that it works for 3, but not for 4 for reasons I explained.

So far everyone has simply explained the inductive solution over again (which I already understand) - not why my argument fails to apply to the inductive solution.

Please explain to me the flaw in my argument rather than repeating the solution.

[yy2bggggs]

So far everyone has simply explained the inductive solution over again (which I already understand)

Apparantly not. Did you even read all of the explanations?

There's nothing hypothetical about this. It's about knowledge. What is confusing you is that you can't follow the knowledge chains.

Consider 4 people: A, B, C, and D. All have blue eyes, and the only other people in the tribe are a larger group of brown eyed people.

A sees three blue eyed people. To A, it's a real possibility that there are only three blue eyed people. So let's explore what that means:

Consider 3 people: B, C, and D. All have blue eyes. A has brown eyes. This is A's knowledge of a possible, not hypothetical, world.

Now, B sees two people--C and D--with blue eyes. To B, it's a real possibility that there are only two blue eyed people. So let's explore what that means:

Consider 2 people: C and D. Both have blue eyes. A, B have brown eyes. This is A's knowledge of a possible, not hypothetical, world; the only difference is that this is A's knowledge of a world potentially, but very realistically, held to be a possible world by B. Oh, sure, we know B sees three blue eyed people really, but A does NOT know this! If you were A, you would not be able to rule out that B holds this as a possible world.

Now, C sees one person--D. D has blue eyes. To C, it's a real possibility that there is only one blue eyed person. This is A's knowledge of B's knowledge of a hypothetical world that C actually holds to be true. Oh, sure, we know C sees three blue eyed people, and we know that A knows that C sees two blue eyed people, but A does not know that B knows this!

You cannot claim this breaks at three, and you cannot claim that we're addressing your claims, unless you understand what the knowledge chain itself is. Failing this, the only way to explain this is to point to the knowledge chain. But this is not our failure, it's yours.

When A notices that D hasn't left the island after day 1, nothing can be concluded. But that's not really what happens. A, B, and C all notice each other, on all nested levels, noticing that D hasn't left. A notices specifically that B notices that C notices that D hasn't left, and can therefore rule out the possibility that B thinks C thinks there is only one blue eyed person. What A notices of C noting that D hasn't left is irrelevant, because A knows that C knows there are two people. What B notices of C noting that D hasn't left is also irrelevant, because B knows that C knows there are two blue eyed people, but A does not know this! And it is in fact relevant, therefore, that A notices B noticing C notice that D hasn't left, because now A knows that B knows that C knows there cannot be only one blue eyed person.

The nesting confuses you, but that's part of what makes this a puzzle. The nesting is very real--we just don't model nested knowledge too well, because we're not gossippy grandmothers.

[skeptical scientist]

There is, however, one minor issue with the blue-eyed perfect logicians, namely Godel's Incompleteness Theorem: if someone is a perfect logician, he cannot know it, or at least cannot use it in his reasoning.

Godel proved that Peano Arithmetic (and also set theory) are incomplete. He didn't prove that propositional logic is incomplete, and in fact propositional logic is, provably, complete. So they can know that they are perfect logicians.

(It also depends on what you mean by "perfect" and "logician", but this is clear enough for the puzzle.)

[skeptical scientist]

What is the world coming to when we can claim to know things based on knowledge gained within a completely hypothetical situation?

We can certainly get knowledge by considering hypotheticals. It is a very particular kind of knowledge. If I consider the hypothetical A, and then deduce B, I do gain knowledge - the knowledge I gain isn't the knowledge that B is true, but rather the knowledge that A implies B (and therefore if I know B is false, I can deduce that A is also false.) This is all that the logicians in the puzzle are doing - they are concluding real knowledge about implications by considering hypothetical situations, and then using their knowledge of implications together with their knowledge that the hypothetical implication is false to determine that the hypothesis was also false.

[Yakk]

The theory may be correct, but the proof is lacking. :)

You need a proof demonstrating that there is no faster method to solve this problem using different assumptions.

Lacking that proof, you cannot assume that everyone else will use this particular proof structure.

It is possible such a proof does not exist -- it might even be possible to prove such a proof doesn't exist. In that case, your logicians could not prove that someone else on the island was using a different algorithm -- the entire construct relies on knowing that everyone else uses the same proof structure.

Lacking such a proof, you cannot derive results from the behaviour of your perfect logicians islanders.

That might be an information theoretic problem.

Ie -- if there is a proof that tells everyone there are 100 people on the island after 3 days, everyone leaves after 3 days. The islander proof both relies on the non-existance of such a proof, and fails to prove that such a proof cannot exist.

Lacking the proof that such a proof cannot exist, your perfect logicians will realize they need that proof, and throw out your proof as meaningless to their problem.

And no, I don't have to provide a proof of a faster proof -- the structure of the inductive arguement provided demands that this proof be strictly fastest possible one, or the inductive arguement fails. It implicitly asserts the non-existance of proofs that provide knowledge faster.

Now, you could try "if there are K blue eyed people, by night K they will have left" -- quickly thinking about it, it works better than the default inductive hypothesis. But it definately doesn't prove that the 100 people all leave on night 100 -- it simply demonstrates they leave by night 100 or before.

[bitwiseshiftleft]

The theory may be correct, but the proof is lacking. :)

You need a proof demonstrating that there is no faster method to solve this problem using different assumptions.

OK. By induction, with n blue-eyed islanders, they will not leave before night n. Base case, n=1, trivial (that one sad guy can't leave on night 0). Induction step: with n>1 people, they clearly don't have enough information to leave on night 1. We are trying to distinguish between n and n-1, so everyone knows (by induction hypothesis) that nobody will leave before night n-1. Therefore, nobody gains any additional information on the outer level until night n-1. Since it is information on the outer level (i.e. their actual own eye color) that causes them to leave, nobody can leave until night n.

[Yakk]

The theory may be correct, but the proof is lacking. :)

You need a proof demonstrating that there is no faster method to solve this problem using different assumptions.

OK. By induction, with n blue-eyed islanders, they will not leave before night n. Base case, n=1, trivial (that one sad guy can't leave on night 0). Induction step: with n>1 people, they clearly don't have enough information to leave on night 1.

I'd like to see a proof of that. :) "Clearly" is a sign that you lack a proof! Can you prove that there is no way for the people to figure out how many blue eyed people there are without the guru's "information" injection?

We are trying to distinguish between n and n-1, so everyone knows (by induction hypothesis) that nobody will leave before night n-1.

On night n-1, your inductive hypothesis isn't fullfilled. There are n people, not n-1 people, so they could have figured out the problem and have left.

If there are n-1 people, then they couldn't have left before night n-1. But if there are n people, it might be possible for them to leave on night n-2 or n-1.

I don't think it can be pulled off (leaving earlier) -- but I can't prove you can't leave earlier.

The devil is in the details. We already have a hand-wavey arguement that this is the solution -- we need one that actually demonstrates there aren't any others.

Therefore, nobody gains any additional information on the outer level until night n-1. Since it is information on the outer level (i.e. their actual own eye color) that causes them to leave, nobody can leave until night n.

You are now talking about facts about information you didn't include in your inductive hypothesis, and I personally would find difficulty
formalizing.

Note that the brown-eyed people are trying to distinguish between n and n+1 blue eyed people. Could the brown-eyed people figure out a way to get off the island sooner than the blue-eyed people?

Doubt it myself. :)

[ringobob]

Alrite, I think I finally made the logical leap that lets me fully and completely buy this answer as correct.

Consider:

person with blue eyes:
'I see 99 people with blue eyes. If that is all of them (i.e., I am not one), then one of the blue-eyed group says:
'I see 98 people with blue eyes. If that is all of them (i.e., I am not one), then one of the blue-eyed group says:
'I see 97 people with blue eyes. If that is all of them (i.e., I am not one), then one of the blue-eyed group says:
'I see 96 people...


... 'I see 1 person with blue eyes. If that is all of them (i.e., I am not one), then that person says:
'I see no people with blue eyes. Either I have blue eyes, or no one does.'

The information that the Guru adds to the group is that that last case is now:

'I see no people with blue eyes. Therefore, I have blue eyes.'

... the other logical hurdle I ran into was this:

person with blue eyes:
'I see 99 people with blue eyes. If that is all of them (i.e., I am not one), then one of the blue-eyed group says:
'I see 98 people with blue eyes. If that is all of them (i.e., I am not one), then one of the blue-eyed group says:

... but it does not matter, because I know there are at least 99 people with blue eyes, so I know that each of them must see at least 98 people with blue eyes.

... but all that does is add an extra step into the induction:

... but it does not matter, because I know there are at least 99 people with blue eyes, so I know that each of them must see at least 98 people with blue eyes.

... and each of them, seeing at least 98 people with blue eyes, knows that each of those people must see at least 97 people with blue eyes...

... and knows that each of those people, seeing at least 97 people with blue eyes, knows that each of that group must see at least 96 people with blue eyes...

... and so on and so forth. The key is realizing that if the islander in question does not have blue eyes, then there is a blue-eyed person on the island who necessarily sees one less blue eyed person than the non-blue-eyed person does, and that person also has to assume that they may not have blue eyes, and so there may be a group that sees one less blue eyed person than they do, on down the chain.

[ringobob]

Now, you could try "if there are K blue eyed people, by night K they will have left" -- quickly thinking about it, it works better than the default inductive hypothesis. But it definately doesn't prove that the 100 people all leave on night 100 -- it simply demonstrates they leave by night 100 or before.

I intuitively feel that they either have to all leave on night K or on night 1. I don't think there can be any kind of information gained between days 2 and K-1 that would allow them to leave that they wouldn't have on day 1, and we have the proof for them leaving on day K. When I have a bit more time I'll try to figure out if I can prove that this is the case.

[Rat]

i tripped on my way to the individual comic thread and found this... the thread is way too long and confusing to read but heres my take on the solution:


all blue eyed people leave on night 100 and no earlier. brown eyed people wouldnt leave until night 101 since they see 100 blue eyed people

first question: the piece of information the guru is giving is that there are still blue eyed people on the island on the 1st through 100th day

for the second question: lets say im a blue eye. if the guru has said for 100 days straight that there is someone with blue eyes that means there are at least 100 blue eyed people. if i only see 99 blue eyed people then i have blue eyes.

for the third question: in the end the guru is basically saying "there are 100 blue eyed people on this island".. it just takes her 100 days to do so...
so, from the 1st to 100th day she is still in the process of saying "theeere aaarree ooonne huundreedd bluuuee eeyyees" which is why no one can leave until she finishes...

i didnt think the puzzle was that hard, all your crazy explanations and arguments were just hard to read...

[bitwiseshiftleft]

OK. By induction, with n blue-eyed islanders, they will not leave before night n. Base case, n=1, trivial (that one sad guy can't leave on night 0). Induction step: with n>1 people, they clearly don't have enough information to leave on night 1.

I'd like to see a proof of that. :) "Clearly" is a sign that you lack a proof! Can you prove that there is no way for the people to figure out how many blue eyed people there are without the guru's "information" injection?

I invoke information theory, specifically that fully predictable observations give no information.

The islanders do not have any information at all about their own eye color on the day they arrive, by The Rules. They can predict, therefore, that nobody will leave, and so the fact that nobody leaves gives no information.

Now, we want to say that the form and delivery of the Guru's statement gives no information either. Since the announcement is unexpected, there is no formal way to do this, but we could instead formalize in the rules of the game that the Guru will, on a certain auspicious date, tell everyone whether she sees a blue-eyed person or not; this rule does not convey information because it is not a function of eye color. Furthermore, the Guru's statement is predictable (for n>=2), and so does not convey information.

EDIT: This is a change in the rules, but it is only a clarification; such a change is (to some degree) necessary to formulate the rules in a technical manner anyway. You'll also need a change to avoid incompleteness problems, as mentioned above, but I'll try not to be that technical.

Every blue-eyed person knows that there are n or n-1 blue-eyed people, and therefore (by the induction hypothesis) that nobody will leave the island until at least the n-1st night. Therefore the fact that nobody leaves before then does not give them information. An observation that you could predict ahead of time does not give any information.

The only new information that they get, given the inductive hypothesis and the rules of the game, is whether people leave on night n-1.

Note that the brown-eyed people are trying to distinguish between n and n+1 blue eyed people. Could the brown-eyed people figure out a way to get off the island sooner than the blue-eyed people?

Doubt it myself. :)

Even so, the brown-eyed people wouldn't know whether their eyes are brown or hazel. Or green, like the Guru's eyes. Or black. Or creepy demonic red. Or some other color.

[Yakk]

Every blue-eyed person knows that there are n or n-1 blue-eyed people, and therefore (by the induction hypothesis) that nobody will leave the island until at least the n-1st night. Therefore the fact that nobody leaves before then does not give them information. An observation that you could predict ahead of time does not give any information.

Induction on the number of blue-eyed islanders does not tell you that if we have n blue eyed people they won't be able to figure out the problem before night n-1. You know lots about S(i) for i < n, and nothing about S(n) when doing the inductive proof.

You are assuming the cart. ;)

The wording on the inductive hypothesis is tricky. I keep on running into the problem of S(N) (where S() is the inductive hypothesis statement), or equivilents, creeping in if my eyes happen to be blue.

Proving the lack of information is tricky without waving hands around.

How about:

Every night the fact that nobody has left generates 1 bit of information.

If there are N blue-eyed people they each need 1 bit of information. Lacking any communication between them (how to formalize?) they need to recieve a collective total of N bits of information. Somehow the guru's statement is 1 bit of information, or they already have 1 bit of information -- thus on the Nth night they have the N bits of information needed to solve the problem collectively.

Before the Nth night, they lack the N bits of information, and information-theoretically cannot solve the problem.

Now, this isn't a proof -- it is a hand-wavey attempt at a proof by someone whose information theory is really really rusty, and wasn't really ever sharp to being with! :)

Note that the brown-eyed people are trying to distinguish between n and n+1 blue eyed people. Could the brown-eyed people figure out a way to get off the island sooner than the blue-eyed people?

Doubt it myself. :)

Even so, the brown-eyed people wouldn't know whether their eyes are brown or hazel. Or green, like the Guru's eyes. Or black. Or creepy demonic red. Or some other color.

And what if someone is colour blind?!

[phlip]

OK, here's my attempt...

xkcd's proof, as mentioned, states that if there are n blue-eyed people, they will leave on or before day n.

I'll use induction to say: if there are at least n blue-eyed people, they will not leave before day n (but may leave on it).

This is trivial for n=1, since day 1 is the first day that people could be leaving.

For n>1, each person can see at least n−1 people, so everyone knows by the inductive argument no-one will leave before day n−1. As bitwiseshiftleft said, "fully predictable observations give no information" (at least, no direct information... there's the whole metaknowledge thing going on in the background that makes xkcd's proof work, but it gives no information about the actual colours of people's eyes). So on day n−1, each person knows nothing about their own eye colour that the didn't know on day 1. It is only when noone leaves on day n−1 that they get knew information about their own eye colour, and leave on day n.

[skeptical scientist]

The theory may be correct, but the proof is lacking.

You need a proof demonstrating that there is no faster method to solve this problem using different assumptions.

OK. By induction, with n blue-eyed islanders, they will not leave before night n. Base case, n=1, trivial (that one sad guy can't leave on night 0). Induction step: with n>1 people, they clearly don't have enough information to leave on night 1.

I'd like to see a proof of that. "Clearly" is a sign that you lack a proof! Can you prove that there is no way for the people to figure out how many blue eyed people there are without the guru's "information" injection?

This is not true. Clearly sometimes means that, but sometimes it means that it really is clear. In this case, it's the latter that's true, since without the gurus statement, the logicians will observe exactly the same eye color and behavior from the other logicians regardless of their own eye color.

[Rat]

what about when the guru messes up and gets stuck on routine and says she sees someone with blue eyes on the 101st day

everyone goes on the raft the 101st night...

is it a good thing to be on the raft? itd be sad if those poor people died

and what about when everyone wakes up in the morning to find 100 blue eyed people missing.. all their friends...

and what goes through their minds when they realize at least 99 people are going to leave all at once...

i hope they go to a happy place...

[jestingrabbit]

So far I haven't found the proofs that xkcd's solution is best all that convincing. I'm not sure if this will be convincing to others but here goes.

Call the situation where there are n blue eyed people out of N people (with n<=N) S(N,n). All the n people with blue eyes must leave on some day, as there is at least one line of reasoning which implies that they leave. Moreover, they must leave on the same day by symmetry. Let D(N,n) be the day on which the best reasoning dictates the n blue eyed people leave in situation S(N,n).

A blue eyed person in S(N,n) is in the same predicament as a non-blue eyed person in S(N,n-1). If D(N,n)<=D(N,n-1) then a non-blue eyed person in S(N,n-1) will leave on D(N,n) believing that they have blue eyes. Therefore D(N,n)>D(N,n-1) and D(N,n)>=n by induction.

This implies that xkcd's solution is best (maybe).

[skeptical scientist]

So far I haven't found the proofs that xkcd's solution is best all that convincing. I'm not sure if this will be convincing to others but here goes.
...
This implies that xkcd's solution is best (maybe).

This strikes me as very clear an convincing. I can see that the lack of any argument was a problem, but the argument didn't strike me as all that hard to make, so I'm not sure why people are unconvinced. What you have just given seems to be a clear and concise way of phrasing the argument.

[phlip]

what about when the guru messes up and gets stuck on routine and says she sees someone with blue eyes on the 101st day

Hmm... this, and your previous post, seem to indicate you're misunderstanding the problem...

The guru only makes the pronouncement once... the 100 days after that, there's no pronouncement, the logicians are just stewing over the guru's message, and the fact that noone's left yet...

[ringobob]

And what if someone is colour blind?!

This is a logic puzzle, and thus, there is no logically relevant information that we are not aware of (or are not otherwise able to infer). Therefore, no one is color blind (unless it can be proved that it would not affect the answer).

Induction works to prove that, given K blue eyed people, they cannot leave before night K after the guru's announcement that she sees at least one blue eyed person.

K = 1 is trivial.

Consider K = 2:
There are 200 people on the island; 198 of them see two blue eyed people, and two of them see 1 blue eyed person. Because everyone sees at least one blue eyed person, they know that the guru may have been referring to the blue eyed person (or persons) that they see, and so there is no way for them to determine what their own eye color is. The necessary bit of info here is that there is no way for the people to communicate amongst themselves whether or not they also see a blue eyed person. The only bit of information is that there is at least one blue eyed person, and each blue eyed person sees at least one blue eyed person, so they have no information about their own eye color. The given solution tells us that they will indeed have that information on day 2, and I've shown here that there is no way for them to have that information on day 1.

Consider K = 3:
Each blue eyed person sees 2 blue eyed persons. Using the same logic as the K = 2 case, they cannot know their own eye color on day 1. At this point, the only way to gain information is through the inductive solution given. The only information gained on day 2 is that no one left on night 1. They all knew that no one would leave on night 1, because they knew that each blue eyed person would see at least one other blue eyed person, as in K = 2. So, with no new information, they cannot leave on night 2. The solution tells us they will leave on night 3.

Discreet math was a long time ago, so I can't remember how to formulate that as a proper inductive proof, but it's logically sound.

Given K blue eyed people, they must leave on night K after the guru announces that there is at least one blue eyed person.

[ringobob]

Either 100 or 99.
If 99
Those hypothesize 99 or 98.
If 98
Those hypothesize 98 or 1+1 = 3.
If 1+1 = 3
Those hypothesize 1+1 = 3 or 2+2 = 5.
If 2+2 = 5
Hypothesize .....
If .....
Hypothesize 100 + 100 = 300
Someone tells the logicians that 100 + 100 != 300.

Does this still work? I cannot see how it does.

Here's your problem: you're formatting the logic chain incorrectly. It should be this:

Either 100 or 99.
If 99
Those hypothesize 99 or 98.
Those think If 98
Those hypothesize 98 or ...

The bolded part is the important part.

Blue eyed person A sees 99 blue eyed people. He must assume that he may not be one. In that case, he knows each of those (99) blue eyed people sees 98 blue eyed people. He also knows that each of those (99) blue eyed people will be applying that very same logic themselves thusly:

"I see 98 blue eyed people. I must assume that I may not be blue eyed. In that case, each of those (98 ) blue eyed people sees 97 blue eyed people. Also, each of those (98 ) blue eyed people will be applying that very same logic themselves thusly:

"I see 97 blue eyed people...

[bitwiseshiftleft]

Every blue-eyed person knows that there are n or n-1 blue-eyed people, and therefore (by the induction hypothesis) that nobody will leave the island until at least the n-1st night. Therefore the fact that nobody leaves before then does not give them information. An observation that you could predict ahead of time does not give any information.

Induction on the number of blue-eyed islanders does not tell you that if we have n blue eyed people they won't be able to figure out the problem before night n-1. You know lots about S(i) for i < n, and nothing about S(n) when doing the inductive proof.

You are assuming the cart. ;)

You're right: I made the statement in terms of the number of blue-eyed people, and then inducted on the number of nights. The correct statement of the induction hypothesis is that on night k, if there are more than k blue-eyed people, nobody leaves. This is equivalent, but I should have been inducting on k rather than n.

Other than that, I think my proof is correct.

[Icaruse]

This has been bothering me for quite a while. I understand the reasoning behind your answer (almost entirely), however, a couple of bits have been bothering me that keep me from being satisfied and keep me from finding your proof mathematicall/logically sound:
1) Everyone is capable of the inductive modeling described with or without the guru's information. Everyone knows that everyone knows that there is at least one person with blue eyes; the guru provides absolutely nothing quantitative.
2) How does a person know whether another started his modelling the same time as him or if that person has started his modelling at all? In all logic, everyone started immediately, but when is immediately?

Personally, I believe that either all 200 people will leave 100 days after ariving on the island (in the case that they have a definitive starting point with wich to coordinate their modelling), but I accept the possibility that noone ever leaves the ilsand, if there is no definitive starting point.

The logical modelling that both the brown-eyed and the blue eyed do, can be initiated at any moment. As long as they have a time frame that they know everyone will work with, they know that if there are only 99 people with their eye color, then they will all leave on the 99th day. If they do not leave on the 99th day, then I will leave on the 100th day.

What they need is a definitive starting point, however that'd involve coordinating their effors, which they can't. In a way, this questing is incomplete. I suggest you add that there is, indeed, a "first time" that the ferry leaves the island and that everyone is present there, thus creating a logical starting point. IMO, that would make the question complete, and the answer would be that all 200 brown and blue eyed men leave on the 100th ferry trip from the island.

I appologize if this has already been mentioned and/or refuted.


Edit: After reading some pretty convincing stuff in the topic.

I supose that, in everyone being present for the guru's info, she creates a logical timeframe for a new set of logical modelling, because it is the first time everyone knows that everyone knows, etc...; however, I don't think this information is needed in the modelling, provided they have a logical starting point already. Perhaps your solution is correct if there is no starting point- if everyone has been on the island since the begining of time- but I'm not entirely convinced.

Anyway, for completelness, why I don't think the information the guru gives is needed, here is the logical thought processes that people would go through starting on the first day:

In the case that there is only 2 people with blue eyes, each of the people with blue eyes will say "if I have blue eyes, the other person won't leave because he, like me, is unsure of his eye color, but if I don't have blue eyes, he will leave imediately." Therefore, they will both leave the second day.

In the case that there are 3 people with blue eyes, each has the following two possibilities to consider:
I see two people with blue eyes. If I, in fact, do not have blue eyes, then there will be a process like above, and the two people will leave on day two. If they do not leave, they both see two people with blue eyes, so I must leave on the third day.

In the case that there are 4 people with blue eyes. Each has the following two possibilities:
case 1: I do not have blue eyes. I see 3 peopls with blue eyes. Each of them sees two people with two eyes. Each of them will consider the following two possibilities:
{
1: I don't have blue eyes, so there are only two people with blue eyes, so from the initial case, they should leave at the 2nd day.
2: If 1 isn't played out, that means I have blue eyes and will leave (on the 3rd day).\
}
case 2: None of the conditions of case 1 were played out, so I must have blue eyes. I will leave (on the 3rd day).

....

[Rat]

edit: yeah i quoted that before you edited your post... removing now to take up less room...

basically, they do need the guru to learn their eye color...

that part stays because they do.. and italics are cool...

[Icaruse]

You seem to take offense to my arguing of the answer? You think my questions invalid and yet you do not address them? I did not find it addressed in the many posts of this topic (I did scan into them, though I did not delve deeply into each individual proof), so I wished to pose it. I assure you, I neither intended to attack the author or the forum, just his solution, and did not mean to do so maliciously. I do appologize for not reading the entirity of this 110-post topic before posing my question. I did not think I would be reasonably expected to do so, but I am in the process of reading them all with full thought. If I thought myself or my logic holy, then I'd have e-mailed xkcd saying he was wrong. Instead, I posted my opinion for it to be considered and discussed. So go on and stay your personal attacks for logical ones.


Anyway, in the process of reading through the solutions, I did come across a rather convincing explination of what the guru provided. I edited it into my original post perhaps a bit too late. I still do not quite find the question, as posed, sufficient to quell my uneasyness, because I can describe a setup where, given a situation that satisfies the described one albeit, assuming a few things more, I can create a solution that comes before the posted one. In that sense, the wording of the question still seems a bit loose. If you do not agree, feel free to tell me why not.

Like I said originally, I appologize if these specific questions have already been posed and/or refuted already. I do not mean to make people reitterate.


Edit: If this is about the wording of my post, perhaps I've been taught a bit too many times to pretend like I know what I'm talking about whenever I pose a question. ^^ Anyway, I'm completely open to being completely wrong. That's all part of the process.

[phlip]

Anyway, for completelness, why I don't think the information the guru gives is needed, here is the logical thought processes that people would go through starting on the first day:

In the case that there is only 2 people with blue eyes, each of the people with blue eyes will say "if I have blue eyes, the other person won't leave because he, like me, is unsure of his eye color, but if I don't have blue eyes, he will leave imediately." Therefore, they will both leave the second day.

Why would the other person leave immediately if they see no blue-eyed people, if the guru never gave the pronouncement? For all that one person knows, they could be the one blue-eyed person, or there may be no blue-eyed people, and that person's eyes are brown, or green, or fluorescent purple, or something else.

[yy2bggggs]

Therefore, nobody gains any additional information on the outer level until night n-1.

Not quite. Information is gained each day. There's a lot more going on than you think when everyone shows up at the tribal meeting.

If people merely come to the knowledge that nobody left the island, then nothing happens. In fact, if there are only three blue eyed people, then everyone already knows that nobody will leave on the first day, after each hour. New hours ticking doesn't do anything. Days aren't special either--tribal meetings are. If a tribal meeting is cancelled, the clock tick merely doesn't happen that day.

But when people show up at the tribal meeting, something new is happening. There is an observation that is made, that gives everyone present new information. Figure out what this is, and if you give up, just reread previous posts--this was pointed out before.

[ringobob]

Not quite. Information is gained each day. There's a lot more going on than you think when everyone shows up at the tribal meeting.

If people merely come to the knowledge that nobody left the island, then nothing happens. In fact, if there are only three blue eyed people, then everyone already knows that nobody will leave on the first day, after each hour. New hours ticking doesn't do anything. Days aren't special either--tribal meetings are. If a tribal meeting is cancelled, the clock tick merely doesn't happen that day.

But when people show up at the tribal meeting, something new is happening. There is an observation that is made, that gives everyone present new information. Figure out what this is, and if you give up, just reread previous posts--this was pointed out before.

No real information is gained each day until day n... because everyone knows no one will leave until at least night n-1, because everyone with the given eye color sees exactly n-1 people, and knows they will not be able to figure out their eye color until at least day n-1. When day n comes and everyone is still there, that's the new bit of info.

[ringobob]

Rat, you should follow your own advice. You aren't properly understanding the original problem, and your answer reflects that.

Icaruse:

In the case that there is only 2 people with blue eyes, each of the people with blue eyes will say "if I have blue eyes, the other person won't leave because he, like me, is unsure of his eye color, but if I don't have blue eyes, he will leave imediately." Therefore, they will both leave the second day.

This is not true. The logical progression for two blue eyed people, without any information from the guru, is this:

I see 1 person with blue eyes. If that is all of them (i.e., I am not one), then that person says:
'I see no people with blue eyes. Either I have blue eyes, or no one does.'

... no one in that case has a definitive answer for their eye color. What the guru does is change it to this:

I see 1 person with blue eyes. If that is all of them (i.e., I am not one), then that person says:
'I see no people with blue eyes. Therefore, I have blue eyes.'

In this case, with the guru's information, a blue eyed person can hypothesize that someone would definitely know their own eye color.

The key bit of info that you're missing is that there is no set of eye colors that everyone must assume is present on the island... if no one sees any blue eyes, then they can assume that no one has blue eyes up until the point that the guru says that they see someone with blue eyes. Likewise, the brown eyed people can't assume that they all have brown eyes after the blue eyed people leave, because they may very well have red eyes, or green eyes, or any other color that isn't blue.

[damaless]

Don't get me wrong, it's not that I'm saying anyone who doesn't understand the explained answer is stupid.

It just makes me really sad that they don't teach induction in high school math.

edit: Also, something I find really interesting on a psychological level is that some people subtly let on that they think leaving the island is a good or bad thing. It's not inherent to the problem, but a few people have said something like "get to leave" or "have to leave" or whatever. It's an island where you're stuck with a bunch of really brilliant people, but you're not allowed to talk to them! In my imagination, all the blue-eyed people who leave on the 100th day are celebrating because they're getting out of a prison.

[yy2bggggs]

No real information is gained each day until day n...

Your reasoning is correct, but your conclusion is wrong. There is real information gained each day. If there wasn't, why would a day matter?

because everyone knows no one will leave until at least night n-1, because everyone with the given eye color sees exactly n-1 people, and knows they will not be able to figure out their eye color until at least day n-1.

This is correct. However, let's say that town meetings stop. But instead, the guru goes around to each person in the tribe each day, reporting on who left and who didn't. Let's further suppose this is the only thing each person knows--that the guru is coming to that person specifically, and saying who left.

Now, nobody will leave. Why? Because they get no new information. But what's more, they will not leave on day n, day 2n, day 5n, whatever.

But if tribal meetings are held daily, they will leave as described in the general solution.

You're correct in saying that they do not learn new information that nobody would leave, because they already know this. But something else is happening at the tribal meetings.