Blue-eyes logic puzzle

Factual Questions
1

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 ( :wink: if you know where this comes from) but I think the puzzle is either poorly-written or just not that interesting.

2

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.

3

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

4

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.

5

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

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

6

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.

7

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.

8

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.

9

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.

10

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.

11

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.

12

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.

13

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.

14

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.

15

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

16

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.

17

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.

18

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.

19

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.

20

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