Math Problem #3 (Logic)

let's say all 1,000 islanders know each other and know the eye color of each other. so the blue eyed people will know there are 900 brown eyed people, 99 blue eyed people, and 1 brown or blue eyed person, whereas the brown eyed people know there are 100 blue eyed people, 899 brown eyed people, and 1 blue or brown eyed person.

nm I still fail to see how blue eyed people will realize they have blue eyes. the most information they have is that there are 99 blue eyed people on the island and that he or she might be blue eyed. since they're forbidden to discuss the topic, I don't know how they come to realize they are blue eyed because they do not know whether the statistic for blue eyed people is 99 or 100.

The foreigner has an effect. Yes, if there's more than 1 blue-eyed person, then everyone knows that there's at least one blue-eyed person on the island. But with the foreigner, everyone knows that everyone else knows that there's at least one blue-eyed person, and everyone knows that everyone else knows THAT, and so on ad-infinitum. You can't achieve this situation without the foreigner. For example, suppose that there's 2 blue-eyed people on the island. Then everyone knows that there's at least one blue-eyed person on the island. But they don't know whether everyone else will know that. A blue-eyed person won't know whether the other blue-eyed person knows that there's at least one blue-eyed person. If he or she knew that the other one knew, then they'd both be committing suicide. But he or she doesn't and so nobody commits suicide.

http://groups.google.com/group/rec.puzzles/browse_frm/thread/97481189aa166c2c
This explains what additional information the foreigner brings to the island.

Everyone already knows that there is at least one blue-eyed person on the island; the extra knowledge is that everyone knows that everyone knows that everyone knows-- infinitely many cycles-- that there is at least one blue-eyed person on the island.

I think the answer is wrong. It's a neat piece of deduction, but all the foreigner told them is that there's at least 1 blue eyed person there, which, if they are perfectly logical, all of them already know. It seems like you have to add something to the puzzle, like make that gathering the first time any blue eyed person has seen another, or something.

also if everyone knows that there's only blue and brown eyes on the island, then the brown eyed people would all have to kill themselves the day after the blue-eyed people did.

I think the problem with this puzzle is the fact that we naturally want to evaluate what the tribe members know as a collective. Instead we should look at an individual tribe member and figure out everything that one person knows and extrapolate that to the rest.

Let's start with 5 tribe members: A, B, C, D, and E.

A, B, C, and D have blue eyes.
E has brown eyes.

Now let me tell you a story about D. D probably thinks he's brown eyed, cause he doesn't want to die, but thats not terribly important.

D looks around and sees 3 blue eyed people: A, B, and C. Now D looks at his buddy C thinks to himself, "Man sucks for C being blue eyed in this situation. Poor C can only see A and B. He must think there's only 2 blue eyed people!"

Now D is laughing to himself thinking, "C probably thinks that B can only see A. After all C thinks he's brown eyed so C must think that B thinks that he is brown eyed too and that A is the only blue eyed person."

We know that if there are only 1 blue eyed people, that the blue eyed person will realize that the foreigner is talking about him and commit suicide the next day.

Now D is has a sudden realization. "A is obviously not going to commit suicide tomorrow. But if C thinks that B thinks that A is the only blue eyed person, C is going to think that B and A are both going to commit suicide on the second day!!"

We know that if there are 2 blue eyed people, they both only see one other blue eyed person and assume that the other is going to commit suicide. When they both fail to commit suicide the next day, they are both going to realize that there are in fact 2 blue eyed people and not one. And since they each can only see one other blue eyed person, the other blue eyed person must be themself. Of course since they both know what eye color they are, they will both commit suicide on day 2.

Now D is thinking, "Wow, when poor C sees that both B and A don't die on day 2, C will realize that there are in fact 3 blue eyed people and he is one of them!"

If there are 3 blue eyed people, each of them only sees 2 blue eyed people. Each person will assume the "2 blue eyed" scenario and expect the other 2 to die on day 2. However when that fails to happen (nobody will die cause they're all waiting for everyone else) all 3 will realize on that day that there are in fact 3 blue eyed people. And since they can only see 2, they must be blue eyed themself. Of course since all 3 of them know what eye color they are, all 3 will commit suicide on day 3.

D thinks, "Poor C is going to die on day 3 and he doesn't even know it yet."

But suddenly, D wonders, "Wait... what if C doesn't die on day three?"

As we know, D is assuming the "3 blue eyed" scenario because he can only see 3 blue eyed people. When nobody dies on day 3, he's going to realize what we already know. D is in fact blue eyed himself!

Now take D's train of logic and apply it to A, B, and C. Because all 4 of them see and think the same thing. All 4 of them will commit suicide on day 4.


Late in the evening on day 4, E breathes a sigh of relief. Luckily A, B, C, and D killed themselves at noon today. If one had died today, it would mean that he was in fact blue eyed as well. E of course knows now his eye color is NOT blue. But that isn't necessarily grounds for suicide. All he can do now is contemplate his future alone on the island (before he kills himself out of depression...)

An easy counter example to your argument: if there is exactly 1 person with blue eyes, then he himself does not know he has blue eyes. If the foreigner comes and says there are blue eyes on the island, then he would know that he himself is the only one with blue eyes since he knows everyone else has brown eyes.

Except that they don't know there's only blue+brown eyes. Each person knows there are exactly 100 blue eyes, and 899 brown eyes and he himself. When the blue eyes all commit suicide after the foreigner comes, he now knows that there are 899 brown eyes, and himself, who does not have blue eyes, but that's not enough for him to commit suicide

This is incorrect, because you base this argument on the assumption that A sees nothing, B only sees A, C only sees A and B, etc. In the problem, they can see everybody. Therefore:

A knows there are 3 blue-eyed people and 1 brown-eyed person
B knows there are 3 blue-eyed people and 1 brown-eyed person
C knows there are 3 blue-eyed people and 1 brown-eyed person
D knows there are 3 blue-eyed people and 1 brown-eyed person
E knows there are 4 blue-eyed people

The only scenario where something happens is when there is only one blue-eyed person.

The main problem with the obvious answer is that it assumes that the foreigner did not unveil any knowledge what so ever. Imagine an island with only two blue eyed people A and B. A knows that there is at least one blue eyed person because he sees B. However, A does not know that B knows that there is at least one blue eyed person because he cannot see that B sees his eyes. So when A notices that B does not commit suicide the noon after the 1st day, he must realize that B did not commit suicide because he saw another pair of eyes (which could only be his own). A similar argument can be done for person B. Hence, A and B commit suicide after two days.

If there are three blue eyed people A, B, and C, then A knows that B knows that there is at least one blue eyed person. However, A does not know that B knows that C knows that there is at least one blue eyed person.

Let a fact be 1st order knowledge among a group of people if everyone in the group knows it.
A fact is 2nd order knowledge among a group if there is 1st order knowledge and everyone knows there is 1st order knowledge.
Recursively, a fact is nth order knowledge among a group if there is n-1th order knowledge of the fact and everyone in the group knows that there is n-1th order knowledge. Let common knowledge be knowledge that exists to all orders.
In the original scenario, the statement "There is at least one blue eyed person on the island" is 99th order knowledge among the blue eyed people. What the foreigner's statement does is turn that knowledge into common knowledge. Everyone heard the foreigner and everyone noticed that everyone else heard and so on. This subtle change in knowledge is the flaw with the argument supporting "nothing happens".

No, no the scenario that I suggested is being told from D's point of view. Put yourself in his shoes and you'll understand. This problem goes beyond each persons knowledge of other people's eye colors. You have to take into consideration what each person thinks each other person knows.

Assuming that "brown eyed" means "NOT blue eyed"

D thinks that:
1) C can only see 2 blue eyed people. D thinks that he himself is brown eyed.
2) C thinks that B can only see one blue eyed person. D thinks C thinks that C himself is brown eyed
3) C thinks that B thinks that A cannot see any blue eyed persons. D thinks C thinks B thinks that B himself is brown eyed.

So essentially all that the scenario is, is a simulation going on in D's head. It's what he thinks other people are thinking. And because all the tribes people are "highly logical", D's train of logic can be applied to each A, B, and C as well.

****Additionally

Let me show why if there are 2 blue eyed people, 2 people still die on day 2.

A and B are blue eyed. A sees only B, and B sees only A. Each assumes that the foreigner is referring to the other and waits to watch the other commit suicide on noon of day 1. Because both are waiting for the other, no one dies on day 1.

A sees that B didn't die and realizes B wasn't the only blue eyed person, there must be another. And since A can see only one blue eyed person, the other blue eyed person must be A himself. And vice versa for B. So on day 2, knowing now what their eye colors are, both A and B commit suicide.

Lemme know if you need me to explain 3+ blue eyed. But its pretty self explanatory after you understand how it works with more than 1.

SourCheeks has the right idea but I wouldn't say that person D thinks that he is brown eyed (non-blue to be more precise). It's more like he keeps non-blue and blue as his possible eye colors (because of his limited knowledge) and waits to see if the other blue eyed people commit suicide on the right day. Despite this minor technicality, I think SourCheeks got the gist of it.