Blue-eyes logic puzzle

[smiling bandit]

This was posted in a very unusual GD thread (of which I shall not utter more, lest we be destroyed in flame and suffering when the shadows come)

A certain individual linekd to this:

http://xkcd.com/blue_eyes.html

Now, I had a slight problem upon reading this, because I don't think it can be solved. That is, it is not a resolvable problem and no one leaves.

The very short version, though go check out the link if interested...

We have an island with 100 Brown-eyed people and 100 Blue-eyed people on it. They can see each other but not communicate, and there are no mirrors, reflective pools, or other devices to see themselves in. Once you know your eye color, you can leave. If not, you can't. The Guru (who is the only person with Green eyes) says that morning, "I see one person with Blue eyes." She just says this out loud to noone in particular, but everyone hears.

The question is, who leaves and when?


...


After reading this, I have two options: I don't believe it can be resolved. No one can leave the island, or everyone leaves the same day.

Hre's my reasoning:

First, if you can't communicate how many people of each eye color you see, you can never know your own eye color. Sure, if you know there are 100 Brown-eyed people and 100-Blue eyes, it's trivial. But you can't. Your eyes might be purple with yellow stripes. Because no one can ever communicate how many total people of each eye colors there are, it must always remain a mystery. Yes, the Guru noted that at least one blue-eyed person existed, but everyone already knew that: the information adds nothing.

Second, if you can communicate how many people are of each eye color, then everyone knows they see 100 of blue or brown, and 99 of the other. Then the last person says to the Guru that there's one gree-eyed person, and the Gurur can leave as well. I assume that when they know they can leave, that person goes down to the docks, changing the numbers. If you make them leave at the rate of one a day it's annoying but the same eventual result.

xkcd claims it's a serious logic puzzle which takes some thought, but I don't see it. I could be just Blind in the Kingdom of the Seeing ( if you know where this comes from) but I think the puzzle is either poorly-written or just not that interesting.

[Frylock]

Currently clueless. The Guru's words have to be a red herring of some kind as far as I can tell--she's not informing anyone of anything they didn't already know.

[Frylock]

The solution is online of course. I'll let people google it if they want to see it.

[Frylock]

I read it. I'll just say this: I think it's worth simply spoiling it for yourself, as convincing yourself the solution works is just as interesting (maybe more) as solving the puzzle.

[Sanity Challenged]

The solution is Googlable. I will just note that your short summary of the problem leaves out 1 very important fact from the original:

They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly....Everyone on the island knows all the rules in this paragraph.

The participants have to count on each other to play perfectly.

[Zeriel]

As far as I understand it, the solution involves indirect communication. Break it down into simpler cases:

Case A: Consider the case of an island with 1 blue-eyed person and 100 brown-eyed people. When the Guru speaks, that one blue eyed person can leave that night--he can't see any blue-eyed people, so the Guru MUST be talking about him. Meanwhile, the brown-eyed people (who can each see one person with blue eyes) are following case B's logic.

Case B: Consider the case of an island with 2 blue-eyed people and 100 brown-eyed people. When the guru speaks, each blue-eyed person can see one blue-eyed person. Each can think about the other "If he doesn't leave tonight, then I have blue eyes and he doesn't know if the Guru is talking about only me. When I don't leave, he'll know he has blue eyes too (because I'm following the same logic) and we'll both leave on day two." Meanwhile, the brown-eyed people (who can each see two people with blue eyes) are following case C's logic.

Case C: Consider the case of an island with 3 blue-eyed people and 100 brown-eyed people. When the guru speaks, each blue-eyed person can see two blue-eyed people. Each will think "If I don't have blue eyes, those two will follow the process in scenario B--if they DON'T leave on day two, I must also have blue eyes. We can all leave on day 3."

--

So all 100 blue-eyed people leave on Day 100.

--

The importance of the Guru's statement is as a catalyst, as I understand it--it enables the simple scenario (1 blue-eyed, 100 brown-eyed) to proceed, and without having that initial test case you can't bootstrap the logic up to where it can deal with the actual scenario.

--

And then I googled it, and I hit pretty close to the mark. I guess all those logic puzzle books I did in high school haven't quite left me yet.

[smiling bandit]

Originally Posted by Zeriel

Each can think about the other "If he doesn't leave tonight, then I have blue eyes and he doesn't know if the Guru is talking about only me.

The problem I have with this line of reasoning is that the logic functions equally for everyone, regardless of what eye color they personally have, and counts on everyone else making the same assumptions (which are logical but not definite).

I think it works, but only if you add some statements to the problem. In this case, however, no Brown or Green-eyed person can ever leave.

[TriPolar]

Originally Posted by Sanity Challenged

The participants have to count on each other to play perfectly.

Yes, this is the key. Each islander knows the others will use the process of induction to determine whether or not they have blue eyes.

[Half Man Half Wit]

Originally Posted by smiling bandit

The problem I have with this line of reasoning is that the logic functions equally for everyone, regardless of what eye color they personally have, and counts on everyone else making the same assumptions (which are logical but not definite).

Well, they are perfect logicians, remember. So if anybody sees n blue eyed people, they know there must be either n or n + 1 blue eyed people, and in the latter case, their own eyes must be blue. So if the n people don't leave after n days, they leave with them on the n + 1st.

[Captain Amazing]

Everyone else will make the same assumptions because they are definite. If you know that at least one person on the island has blue eyes, and you know that everyone on the island other than you doesn't have blue eyes, then you know that you do. We can agree on that, right?

So, likewise, if you know that at 99 people (who aren't yourself) on the island have blue eyes, and they don't leave on day 99, you know that you have blue eyes. And you're right. Somebody with brown or green eyes will never leave, given this scenario.

[smiling bandit]

I do think there's a hidden assumption, do to the auithor's reduction of all time measures to arbitrary days:

It works if and only if you assume that all actors are simultaneous (which wasn't specified): if they can and do all act at precisely the identical time. Otherwise, You can have a situation where Brown-eyed people assume the situation has been resolved in such a manner that they are Blue-Eyed.

Originally I made a mistake due to not realizing that they all MUST leave the island immediately upon realizing they were Blue-eyed or whatever.

[Captain Amazing]

Well all actions are simultaneous in that everyone knows who's on the island (and their eye color), that everyone who leaves, leaves in the middle of the night, and that whenever someone leaves, everyone else knows the next morning.

[TerpBE]

Assume N blue eyed people:

Day 1: If you look around and see that nobody else has blue eyes, you must be the only one. You leave.

Day 2: If nobody left on day 1, it means that there are at least 2 people on the island with blue eyes. If you only see 1 other person with blue eyes, you know you must be the other one. He comes to the same conclusion, so you both leave.

Day 3: If nobody left on day 2, it means there are at least 3 people on the island with blue eyes. If you only see 2 other people with blue eyes, you know you must also have blue eyes. They come to the same conclusion, so the 3 of you leave.
....
Day N: If nobody left on day (N-1), it means there are at least N people on the island with blue eyes. If you only see (N-1) other people with blue eyes, you know you must also have blue eyes. They come to the sane conclusion, so the N of you leave.

Day N+1: All the blue eyed people left. Everyone else must have brown eyes, so they leave.

[Chessic Sense]

Here's what I had to say the first time around. In that version of the puzzle, there were only brown eyes and blue eyes, and the islanders killed themselves once they knew.

The part that you're missing is that everyone imagines 2 scenarios, but they don't know which two scenarios.

Let 1=brown and 0=blue.

The truth is 0000, but...
1. A imagines 0000 and 1000.
2. B imagines 0000 and 0100.
3. C imagines 0000 and 0010.
4. D imagines 0000 and 0001.

Now, in line 4, the third slot is 0 for sure. After all, D can see C's eyes. But C doesn't know this. C can't tell what's in D's imagination. He knows what D thinks about the A, B, and D slots but not what D thinks about the C slot.

So C thinks "I know what D thinks about A. He's 0. I know this because we can both see him. Same for B. So we know the pattern starts with 00. But I don't know what the third slot is, even though D definitely knows. So D is either thinking '0000 and 0001' or '0010 and 0011'. I just can't tell since I don't know what he sees in my own eyes. I know that the two latter cases are false because I can see 0 in his eyes, but there's no way he could know that himself. So he is thinking of one of those two pairs- Either the first set or the second set. I just don't know which."

But do you see how in all four patterns, the second slot (B) is 0? Well B doesn't know that. She thinks it could also be a 1. She's well aware that D has it narrowed down to 2. And she knows that C has D's combinations narrowed down to 4. But she doesn't know what those 4 are. They could be the 4 where the second slot (the B slot) is 0 or the 4 where the second slot is 1, but not a combination of the two.

B says to herself, "I know C has D's combinations narrowed down to 4. I just don't know which they are. They are either '0000, 0001, 0010, and 0011' if I have 0 eyes, or '0100 and 0101' or '0110 and 0111' if I have 1 eyes. If I were to know my own eye color, I would know which group of 4 that C believes possible for D to hold. But I don't, so I can at best narrow it down to 8. Of course, I know that C knows that D knows that A has 0 eyes. I know this because I know that C knows that D sees A's eyes and they're 0."

Bear in mind that B can narrow down D's choices better than 8. She can narrow down the actual possible patterns in C's mind to 4- namely, 0000, 0001, 0100 and 0101. Problem is, 2 belong to the first group of C's choices and two belong to the latter. So all it proves is that B knows that C is wrong about half his choices. It does not tell her which choices are wrong. So she can't determine any info about her own eye color. If she could, for some reason, determine which group of 4 C was actually considering for D's mind, then B would know her own eye color. But she can't, so the best she can do is 8 possible thoughts for C to hold about D's patterns.

Again, B knows that anything where the third slot is 1 is wrong, but she also knows that C is ignorant of that fact and thus can't rule it out for what C is considering possible in D's mind.

Notice that all of B's 8 choices start with 0. That's because she can see A's eyes, and she knows that C can too, and C knows that D sees A's eyes as well. But A doesn't know that! Sure, B is considering only 8 choices (4 which she knows to be false, but can't rule out that C thinks them anyway), but A can't narrow down which set of 8 those are- the one where A is 0 or the one where A is 1.

So A knows:
B is considering one of two set of options regarding C's analysis of the distributions that D considers possible. Either the set:
1) 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111 OR
2) 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

The only difference is his own eye color. Sure, B knows which one she actually is considering. And C knows which 4 he's actually considering. And D knows which 2 he's actually considering. And the narrator knows which 1 is actually true.

But A can't tell if B is considering set 1 or 2, even though we know B is considering set 1 and has discarded 2.

B can't tell which half of set 1 C is considering to be in D's mind, the first half or the second half. Of course, we know it's really the first half (0000, 0001, 0010, 0011).

C knows that it's the first half because he can see A and B and knows D can too. But he can't see himself, so he can't choose which 2 of the 4 patterns D is believing to be possible, 0000 and 0001 or 0010 and 0011.

D knows which pair it is, however. He knows it's the first pair, 0000 and 0001, that are possible. He just can't tell which 1 of the two it is.

And we, the outsiders, know which one it is - 0000.



So there you have it. I worked backwards through the logic, then forwards through it again. If anyone still can't grasp this, then I can't help you any further, I don't think. It's not an issue of how many patterns each thinks is possible, it's a matter of which patterns they think are possible.

Do not confuse the following two statements:
1. A thinks that B thinks there are 4 patterns possible.
2. A thinks that B holds 2 out of 4 possible patterns and just doesn't know which two.

Statement 1 is false and will lead to confusion. Statement 2 is true and explains the situation clearly and easily.

[Chessic Sense]

Originally Posted by TerpBE

Everyone else must have brown eyes, so they leave.

Not in this version of the riddle. Green eyes, red eyes, or even purple-striped eyes are considered possibilities.

[EdwardLost]

Originally Posted by TerpBE

Day N+1: All the blue eyed people left. Everyone else must have brown eyes, so they leave.

The brown-eyed people don't leave because they still don't know. Their eyes may be red, or green, or anything besides blue.

Never mind; scooped.

[Ximenean]

Originally Posted by smiling bandit

Yes, the Guru noted that at least one blue-eyed person existed, but everyone already knew that: the information adds nothing.

Ah, but it does. That is the subtle thing about this puzzle. With more than one blue-eyed person, it is true that everybody already knows there is at least one blue-eyes. But they don't know that everybody else knows that, and that everybody else knows that everybody else knows, and that... [repeat n times]. That is the extra information that the Guru's announcement gives them.

To give a concrete example with three blue-eyes. Take any two of them, B and C and consider B's knowledge of C's knowledge. B only knows for sure that C knows about one blue-eyes (A).
Now consider A's knowledge of B's knowledge of C's knowledge. Since A doesn't know that he himself is blue-eyed, A can't know that B knows that C knows that one or more of them is blue-eyed. As far as A knows, B might not know that C knows of any blue-eyes.

The revelation by the Guru changes that. Now A does know that, about B's knowledge of C's knowledge.

[Ludovic]

Originally Posted by Ximenean

Ah, but it does. That is the subtle thing about this puzzle. With more than one blue-eyed person, it is true that everybody already knows there is at least one blue-eyes. But they don't know that everybody else knows that, and that everybody else knows that everybody else knows, and that... [repeat n times]. That is the extra information that the Guru's announcement gives them.

Sure they do. They're perfect logicians, so they know that everyone knows that there are at least 99 blue eyed people on the island, and because they know everyone is a perfect logician, they know that everyone knows that everyone knows this, etc.

[Chessic Sense]

Originally Posted by Ludovic

they know that everyone knows that there are at least 99 blue eyed people on the island

No, they don't. That would only be the case if they knew their own eye color. They know there are 99 or 100 blues. But they think everyone else is thinking either "There are 98 or 99 blues" or "There are 99 or 100 blues". But they don't know which sentence everyone else is thinking.

Try this: We're islanders on a 200-person island. I have blue eyes. You see, including me, 50 blue eyed-people. So how many blue-eyed people are on the island? Your answer: "50 or 51." Now answer this, please: How many do I think there could be?

Notice that I didn't tell you your own eye color. I did this on purpose.

[SciFiSam]

Originally Posted by Zeriel

As far as I understand it, the solution involves indirect communication. Break it down into simpler cases:

Case A: Consider the case of an island with 1 blue-eyed person and 100 brown-eyed people. When the Guru speaks, that one blue eyed person can leave that night--he can't see any blue-eyed people, so the Guru MUST be talking about him. Meanwhile, the brown-eyed people (who can each see one person with blue eyes) are following case B's logic.

Case B: Consider the case of an island with 2 blue-eyed people and 100 brown-eyed people. When the guru speaks, each blue-eyed person can see one blue-eyed person. Each can think about the other "If he doesn't leave tonight, then I have blue eyes and he doesn't know if the Guru is talking about only me. When I don't leave, he'll know he has blue eyes too (because I'm following the same logic) and we'll both leave on day two." Meanwhile, the brown-eyed people (who can each see two people with blue eyes) are following case C's logic.

Case C: Consider the case of an island with 3 blue-eyed people and 100 brown-eyed people. When the guru speaks, each blue-eyed person can see two blue-eyed people. Each will think "If I don't have blue eyes, those two will follow the process in scenario B--if they DON'T leave on day two, I must also have blue eyes. We can all leave on day 3."

--

So all 100 blue-eyed people leave on Day 100.

--

The importance of the Guru's statement is as a catalyst, as I understand it--it enables the simple scenario (1 blue-eyed, 100 brown-eyed) to proceed, and without having that initial test case you can't bootstrap the logic up to where it can deal with the actual scenario.

--

And then I googled it, and I hit pretty close to the mark. I guess all those logic puzzle books I did in high school haven't quite left me yet.

Why the 100 days? The puzzle doesn't say that only one person can leave a day.

[Frylock]

Originally Posted by SciFiSam

Why the 100 days? The puzzle doesn't say that only one person can leave a day.

All 100 leave on the 100th day. This is because only then do any of them know that he himself (or she herself) has blue eyes--and on that day, all of them know this.

In other news:

I know how to say what new information people on the island have after the Guru speaks in the case where only two have blue eyes. (Namely, the new information is: "Now the other blue eyed guy knows that at least one person has blue eyes.") But I haven't worked out how to formulate the corresponding piece of new information in the 100-blue-eyed-people case much less the 3-blue-eyed-people case. Just keeping you posted.........

[leahcim]

Originally Posted by SciFiSam

Why the 100 days? The puzzle doesn't say that only one person can leave a day.

It's not one person leaves per day, no one leaves until the 100th day, when all 100 blue-eyed people leave. On that day every blue-eyed person simultaneously says, "I have inferred that there are at least 100 blue-eyed people on the island, and I only see 99, so the 100th must be me".

[Chronos]

I know how to say what new information people on the island have after the Guru speaks in the case where only two have blue eyes. (Namely, the new information is: "Now the other blue eyed guy knows that at least one person has blue eyes.") But I haven't worked out how to formulate the corresponding piece of new information in the 100-blue-eyed-people case much less the 3-blue-eyed-people case. Just keeping you posted.........

It's similar, but it gets pretty wordy. For 3 blue-eyed folks, it'd go something like "Now the other blues know that the other blues know that at least one person has blue eyes". For 4 blues, it'd be "Now the other blues know that the other blues know that the other blues know that at least one person has blue eyes". And so on.

Really, this problem is a poster child for the method of mathematical induction.
Proposition P(N): "For any N >= 0, if there are N blue-eyed islanders, then on night N, all blue-eyed islanders will leave"
Foundation: If N=1, then the single blue-eyed islander will know that he must be the blue-eyed guy, and leaves on night 1. Therefore, P(1) is true.
Increment: If P(N) is true, then on day N+1, every blue-eyed islander will know that there are at least N+1 blue-eyed islanders. If there are exactly N+1 blue-eyed islanders, then each will only see N, and each will know that he himself must be the N+1th. Therefore, each blue-eyed islander will leave on night N+1. Hence, if P(N) is true, then P(N+1) is true.

We've now established that P(1) is true, and that if P(N) is true, then so is P(N+1). The result follows by induction. Quite Easily Done.

[Mosier]

It's a lot simpler than all the algebra and stuff implies.

If 100 islanders have blue eyes, everyone with blue eyes sees 99 islanders with blue eyes. If, on the 99th day nobody has left the island, everyone who only sees 99 pairs of blue eyes realizes there are in fact 100 pairs of blue eyes, and now knows their own eye color. They may all leave the island at the same time.

[Mosier]

Actually, now that I think about it, the puzzle doesn't seem to work. If there are 2 people with blue eyes, and each day the guru says "I see someone with blue eyes," how do either of the two people with blue eyes know whether the guru sees the same person they saw yesterday? Saying "I see someone with blue eyes" on Tuesday doesn't give any more information than it did when you said it on Monday, because you could be seeing the same person!

[MichaelEmouse]

Originally Posted by leahcim

It's not one person leaves per day, no one leaves until the 100th day, when all 100 blue-eyed people leave. On that day every blue-eyed person simultaneously says, "I have inferred that there are at least 100 blue-eyed people on the island, and I only see 99, so the 100th must be me".

Why could a blue-eyed person think this but not a brown-eyed person?

[Indistinguishable]

Here's a similar (in fact, identical, except in wording) problem, which may be instructive:

There is a certain archipelago, consisting of 2^3 many islands, arranged into the vertices of a 3-dimensional cube. There are also bridges between islands, corresponding to the edges of this cube (so each island has 3 bridges out of it).

On each island, there is a sequence of bits, specifying its coordinates on this cube: one island is (0, 0, 0), it has three bridges to the islands (1, 0, 0), (0, 1, 0), and (0, 0, 1), each of which has two further bridges out of it corresponding to flipping further bits, and so on.

At each end of each bridge, there is an islander assigned to guard over that particular bridge. [For what it's worth, the islanders speak an odd language in which the term for "guards over a bridge on the side of it corresponding to the bit 1" is "has blue eyes" and the term for "guards over a bridge on the side of it corresponding to the bit 0" is "has non-blue eyes"]

There is a certain ritual according as to which bridges are sometimes destroyed and their guards commit suicide (or, as the islanders euphemistically refer to it, "go on a ferry ride"). Specifically, every morning, the two guards of each bridge look out at the other guards on their own island and report what they see. If they report the same pattern of live and dead guards to each other, all is well; otherwise, if they report differing patterns, they destroy their bridge and commit suicide that midnight.

The islands all exist in perfect harmony, with no bridge destructions, for many years.

But one day, The Guru comes to town, takes a look at island (0, 0, 0), and decides he doesn't care for it. He destroys the island and all the bridges out of it; that night, all the guards to those bridges commit suicide, no longer having a bridge to watch over.

What happens from that point on? In particular, what happens to island (1, 1, 1)?

Well, go ahead and work it out on paper if you like. It's easy enough. You don't have to worry about who knows what when; there's nothing about knowledge here. There's just the mechanical bridge-suicide rules, as given above. See where they take you.

[Giles]

Originally Posted by MichaelEmouse

Why could a blue-eyed person think this but not a brown-eyed person?

Because the brown-eyed person sees 100 people with blue eyes, not 99 people with blue eyes.

[MichaelEmouse]

Originally Posted by Giles

Because the brown-eyed person sees 100 people with blue eyes, not 99 people with blue eyes.

You're right, thanks.

[Zeriel]

Originally Posted by Mosier

Actually, now that I think about it, the puzzle doesn't seem to work. If there are 2 people with blue eyes, and each day the guru says "I see someone with blue eyes," how do either of the two people with blue eyes know whether the guru sees the same person they saw yesterday? Saying "I see someone with blue eyes" on Tuesday doesn't give any more information than it did when you said it on Monday, because you could be seeing the same person!

The guru only says it once, not once per day.

The guru's statement's only function is to catalyze the mathematical induction that one uses to logic their way out of it. Without the guru's statement, the 1 Blue Eyes/100 Brown Eyes version of the problem cannot be solved, and that version of the problem bootstraps the solution for N Blue-Eyed People.

[Mosier]

Assume there are 100 people with blue eyes and 100 with not-blue eyes. Blue eyed people know there are either 99 or 100 blue eyed people. Non-blue eyed people know there are either 100 or 101 blue eyed people.

Literally everyone knows that nobody can leave the island on the first, second, or third day. Indeed nobody can possibly leave the island until day 99 at minimum. So why does the problem require the islanders to wait 99 days, when literally no information is gained between day 1 and day 98?

[wellanuff]

Originally Posted by Zeriel

As far as I understand it, the solution involves indirect communication. Break it down into simpler cases:

Case A: Consider the case of an island with 1 blue-eyed person and 100 brown-eyed people. When the Guru speaks, that one blue eyed person can leave that night--he can't see any blue-eyed people, so the Guru MUST be talking about him. Meanwhile, the brown-eyed people (who can each see one person with blue eyes) are following case B's logic.

Case B: Consider the case of an island with 2 blue-eyed people and 100 brown-eyed people. When the guru speaks, each blue-eyed person can see one blue-eyed person. Each can think about the other "If he doesn't leave tonight, then I have blue eyes and he doesn't know if the Guru is talking about only me. When I don't leave, he'll know he has blue eyes too (because I'm following the same logic) and we'll both leave on day two." Meanwhile, the brown-eyed people (who can each see two people with blue eyes) are following case C's logic.

Case C: Consider the case of an island with 3 blue-eyed people and 100 brown-eyed people. When the guru speaks, each blue-eyed person can see two blue-eyed people. Each will think "If I don't have blue eyes, those two will follow the process in scenario B--if they DON'T leave on day two, I must also have blue eyes. We can all leave on day 3."

--

So all 100 blue-eyed people leave on Day 100.

Except that it seems to me in what we might call Case D with 4 people (and subsequent cases with even more people), Case B can no longer be applied and used as a basis for action in Case C, and therefore Case C could not be used in D.

In other words, with four people, when the guru speaks, each blue-eyed person can see three blue-eyed people. Each will think "If I don't have blue eyes, those three will follow the process in case C --if they DON'T leave on day three, I must also have blue eyes. We can all leave on day 4."

But this seems faulty, because the decision to not leave on day three would have been based on case C, which in turn would be based on B, but B does not apply because everyone can see that all of the others can also see multiple blue-eyed people and therefore could not make an inference about what any individual's failure to leave on the first night might mean.

[Giles]

Originally Posted by Mosier

So why does the problem require the islanders to wait 99 days, when literally no information is gained between day 1 and day 98?

Information is gained from other blue-eyed people not leaving.

[wellanuff]

Another way to approach the difficulty I have with this is, why is the following a given (as it seems to be in some of the explanations):

"n people with blue eyes will leave on day n"

I can see how this works for n = 1, 2 or 3, but not why it is true for the general case. Solutions based on this seem to be assuming something that has not been proven.

[Isamu]

What is the quantified piece of information that the Guru provides that each person did not already have?

I don't know the answer to this. The Guru only verbalized something that everyone already knew since they are all perfect logicians.

[Giles]

Originally Posted by wellanuff

I can see how this works for n = 1, 2 or 3, but not why it is true for the general case. Solutions based on this seem to be assuming something that has not been proven.

Yes, I think that's the real problem: 100 people follow exactly the same steps of logical deduction, and know that the other 99 people are thinking exactly the same way, all the time not communicating with each other. It assumes logical deduction that's just too perfect.

[matt_mcl]

Originally Posted by Giles

Information is gained from other blue-eyed people not leaving.

What information, though? That there are at least n blue-eyed people? But they already know that -- they can see them.

[Indistinguishable]

Originally Posted by matt_mcl

What information, though? That there are at least n blue-eyed people? But they already know that -- they can see them.

Information about who knows that who knows that who knows that who knows that... who knows that there at least n blue-eyed people.

You might say "Well, everyone knows that everyone knows that everyone knows that... everyone knows that there are at least n-blued eye people, from the start!".

You would be wrong.

Part of the reason I gave my archipelago rephrasing is because it seems to make clear for some people what is hard for them to see in the information/knowledge based account. The things the islanders at some particular island all know are the things which are true at every island within 1 bridge of it [since every particular islander can't tell their own eye color, so they're not sure whether they're on this island or the one across their bridge]. The things everyone at an island knows that everyone knows are the things which are true at every island within 2 bridges of it. The things everyone at an island knows that everyone knows that everyone knows are the things which are true within 3 bridges of it. Etc. [And, of course, the use of a 3-dimensional cube, with 3 bits to each island, is arbitrary; it might as well be 100]

[matt_mcl]

Okay, here's what is confusing me: I can read and mull over why the explanation above is right.

What I don't understand is why the common-sense version (the guru's statement is useless because everyone already knows there's at least one blue-eyed person) is wrong. What am I missing that I don't get the difference between the guru saying "There is at least one person with blue eyes" and being able to see that there's at least one person with blue eyes? Why does speaking the sentence out loud make a difference?

[Frylock]

Originally Posted by matt_mcl

Okay, here's what is confusing me: I can read and mull over why the explanation above is right.

What I don't understand is why the common-sense version (the guru's statement is useless because everyone already knows there's at least one blue-eyed person) is wrong. What am I missing that I don't get the difference between the guru saying "There is at least one person with blue eyes" and being able to see that there's at least one person with blue eyes? Why does speaking the sentence out loud make a difference?

If I'm one of the blue eyed guys, when the guru speaks, I now know something about what all the other blue eyed guys know.

Think about the case where there are just two blue eyed guys. Before the guru speaks, all I know is that there is at least one guy with blue eyes. I don't know that the other blue eyed guy knows that. But after the guru speaks, I do know the other blue eyed guy knows it. So my information has changed.

Maybe "my information has changed" isn't exactly the right thing to say--I haven't learned anything about how things were before the guru spoke. Rahter, the guru's speaking has changed the way things are now.

[Little Nemo]

Let's reduce the number of people to make it simpler. Let's say there are only six people besides the guru on the island: Al, Bob, Chuck, Dan, Ed, and Frank.

The guru says he sees at least one blue-eyed person.

Case #1 - Let's assume Al looks around and sees that Bob, Chuck, Dan, Ed, and Frank all have brown eyes. Al realizes he must have blue eyes. So Al gets on the boat on the first day.

Case #2 - Let's assume that Al looks around and sees that Bob has blue eyes and Chuck, Dan, Ed, and Frank have brown eyes. Al figures that if he has brown eyes that Bob is seeing all brown-eyed people. So Bob is in the position Al was in in Case #1. Bob is as smart as Al so he will figure out that he must have blue eyes. So Bob will get on the boat on the first day.

But suppose Bob doesn't get on the boat on the first day. Al will then realize that Bob must not be seeing only brown-eyed people. Bob must be seeing a blue-eyed person. And Al can see that Chuck, Dan, Ed, and Frank have brown eyes. So Al will figure out he must be the blue-eyed person Bob is seeing. So Al now knows he has blue eyes and he can get on the boat on the second day. And Bob, having the same information as Al, will also get on the boat on the second day.

Case #3 - Let's assume Al looks around and sees that Bob and Chuck have blue eyes and Dan, Ed, and Frank have brown eyes. Al figures if he has brown eyes then Chuck is seeing one other blue-eyed person, Bob. So Chuck's in the same position Bob was in in Case #2. Chuck, being smart, will figure this out and will get on the boat on the second day and so will Bob.

But if Chuck and Bob don't get on the boat on the second day, then Al will know that they must be seeing more than one other blue-eyed person. And Al can see Dan, Ed, and Frank have brown eyes. So he'll figure out he must be the other blue-eyed person. So Al will get on the boat on the third day, as will Bob and Chuck.

Case #4 - Let's assume Al looks around and sees that Bob, Chuck, and Dan have blue eyes and Ed and Frank have brown eyes. Al figures if he had brown eyes then Dan is seeing two blue-eyed people, Bob and Chuck. So Dan is in the position that Chuck was in in Case #3 and will figure it out and get in the boat on the third day, along with Bob and Chuck.

Once again, if Bob, Chuck, and Dan don't get in the boat on the third day, then Al will know there is another blue-eyed person. And once again he'll know he's the other blue-eyed person and will get in the boat on the fourth day, along with Bob, Chuck, and Dan.

Case #N - It scales up. No matter how many blue-eyed people there are, you will reach a point where all of the blue-eyed people will be able to follow a chain of logic and establish that they have blue eyes. The only person who's unaccounted for is you.

So you count up how many blue-eyed people you see and call this N. If on the Nth day, all the blue-eyed people get on the boat, you'll know that N is the total number of blue-eyed people and you have brown eyes. If the blue-eyed people you see don't get on the boat on the Nth day, you'll know there must be more than N blue-eyed people. You'll know there are N+1 blue-eyed people and you must be the +1 blue-eyed person.

[Indistinguishable]

Originally Posted by matt_mcl

Okay, here's what is confusing me: I can read and mull over why the explanation above is right.

What I don't understand is why the common-sense version (the guru's statement is useless because everyone already knows there's at least one blue-eyed person) is wrong. What am I missing that I don't get the difference between the guru saying "There is at least one person with blue eyes" and being able to see that there's at least one person with blue eyes? Why does speaking the sentence out loud make a difference?

If you are an islander, the Guru saying "There is at least one person with blue eyes" has two effects on you
A) It tells you that there is at least one person with blue eyes. Well, actually, this is no effect, because you already knew that...
B) It brings about a situation where you know that everyone else knows A). And that everyone else knows B) as well! [So everyone knows that everyone knows A). And everyone knows that everyone knows that everyone knows A). And so on, ad infinitum]. In technical jargon, it turns A) into "common knowledge", which it wasn't before. Frylock's example with two people is particularly illustrative.

Everyone who thinks the Guru's statement is uninformative is only looking at A). It's true that A) is nothing you don't already know. The value of the Guru's pronouncement is B).

It is vital for this, mind you, that the Guru makes this pronouncement publicly. If the Guru just went around whispering privately to each islander "I see at least one blue-eyed person", this would only inform each islander of A), and thus have no effect. It's the public nature of the pronouncement that allows it to bring about effect B).

In terms of the archipelago metaphor, prior to The Guru's public pronouncement, it was possible to get from the island of all blue-eyes to the island of no blue-eyes by taking N many bridges. After the Guru's public pronouncement that there is at least one blue-eyed person, the island of no blue-eyes has been bombed out of the world [at least, it's been cut off from that portion of the world compatible with this pronouncement], and the only islands left accessible all have at least one person with blue eyes. That is the pronouncement's value; to bring about that action.

[Zeriel]

Very clearly explained, Little Nemo.

The reason that you can't ever skip a day is that you don't know what anyone else is really seeing (due to your lack of information about your own eye color). Because that is true for everyone, the logical bootstrap can't skip any days.

[Isamu]

I wish they'd just start speaking to each other again. C'mon guys, forgive and forget!

[TATG]

Originally Posted by xkcd

Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.

Given that there are at least 3 blue eyes on the island, everyone knows everyone can see at least 2 blue eyes. Anyone that can see 2 blue eyes can deduce that everyone can see one blue eyes. There are at least 3 blue eyes, so everyone can deduce that everyone sees one blue eyes.

Example: Bob, Fred, Joe have blue eyes. Bob sees Joe and Fred. Bob knows that Joe sees Fred, so Bob knows that Joe knows one person has blue eyes. Mutatis mutandis for the other cases.

I don't understand what the Guru has added.

[Indistinguishable]

The Guru has added that everyone knows that everyone knows that everyone knows that there is at least one blue-eyed person. And so on.

In your case, Bob thinks he might have brown eyes. Because Bob thinks he might have brown eyes, Bob thinks Fred might see Bob with brown eyes. Bob also knows that Fred doesn't know his own eye color. So Bob thinks it might be the case that Fred thinks it might be the case that both Bob and Fred have brown eyes. Which is to say, Bob thinks it might be the case that Fred thinks it might be the case that Joe sees only brown eyes. Which is to say, Bob thinks it might be the case that Fred thinks it might be the case that Joe thinks it might be the case that everyone has brown eyes.

After the Guru makes his announcement, that no longer holds. After the announcement, Bob knows that Fred knows that Joe knows that at least one person has blue eyes.

Originally, there is a path of length 3 from island (1, 1, 1) to an island with no blue eyes. The Guru's announcement has the effect of destroying the island with no blue eyes, so that every path of length 3 out of (1, 1, 1) still lands at an island with blue eyes.

[TATG]

Originally Posted by TATG

Given that there are at least 3 blue eyes on the island, everyone knows everyone can see at least 2 blue eyes.

This isn't right; given that everyone knows that there are at least 3 blue eyes, everyone knows everyone can see at least 2 blue eyes.

But this doesn't resolve my confusion.

[TATG]

Let me try that again. The important assumption is that everone knows that everyone can see everyone but themselves.

Case: 4 blues on the island.

1) Everyone can see 3 blue eyes, because there are 4 blue eyes.
2) So everyone knows that there are at least 3 blue eyes. (by 1)
3) Everyone knows everyone can see 2 blue eyes. (by 2)
4) So everyone knows everyone knows everyone can see 1 blue eyes. (by 3)

I can't see which step is wrong.

[Indistinguishable]

Right, if everyone knows that there are at least 3 blue eyes, everyone knows everyone can see at least 2 blue eyes, and thus everyone knows that everyone knows that everyone can see at least one 1 blue eye, and thus everyone knows that everyone knows that everyone knows that there is at least 1 blue eye.

And if everyone knows there are at least 4 blue eyes, then everyone knows that everyone knows that everyone knows that everyone knows that there is at least 1 blue eye.

And in general, if everyone sees at least N blue eyes, then everyone knows (iterated N times) that there is at least 1 blue eye. But it won't be the case that everyone knows (iterated N + 1 times) that there is at least 1 blue eye.

If we start with 100 islanders, each islander sees 99 blue eyes. Everyone knows (iterated 99 times) that there is at least 1 blue eye. But, to start with, before the Guru steps in, it isn't the case that everyone knows (iterated 100 times) that there is at least 1 blue eye. The Guru's PUBLIC announcement makes that happen.

[Indistinguishable]

Originally Posted by TATG

Let me try that again. The important assumption is that everone knows that everyone can see everyone but themselves.

Case: 4 blues on the island.

1) Everyone can see 3 blue eyes, because there are 4 blue eyes.
2) So everyone knows that there are at least 3 blue eyes. (by 1)
3) Everyone knows everyone can see 2 blue eyes. (by 2)
4) So everyone knows everyone knows everyone can see 1 blue eyes. (by 3)

I can't see which step is wrong.

What you've written is correct. With 4 people, you can get to "everyone knows everyone knows everyone can see 1 blue eye". But you can't get to "Everyone knows everyone knows everyone knows everyone can see 1 blue eye".

With 5 people, you could get to that but you couldn't get to "Everyone knows that everyone knows everyone knows everyone knows everyone can see 1 blue eye".

With N people, you can get to "Everyone knows (iterated less than N times) that there is at least 1 blue eye", but you can't get to "Everyone knows (iterated N times) that there is at least 1 blue eye". Until the Guru steps in, and makes his public announcement, which has the effect of letting you get to "Everyone knows (iterated however many times you like) that there is at least 1 blue eye".

In terms of the archipelago: The distance from (1, 1, 1, 1, ...) to (0, 0, 0, 0, ...) is the number of islanders (per island). If there are N islanders, it takes N bridge-hops to get from "All blue eyes" to "No blue eyes" by bridge-hopping. But it can be done! The Guru's public announcement has the effect of making it impossible to get from "All blue eyes" to "No blue eyes" by bridge-hopping.