The first argument is true; the second has the logical flaw. The flaw is assuming that induction can continue despite additional pre-knowledge available when there are greater numbers of blue-eyed people.
The statement will have no effect when the number of blue-eyed people is 3 or more:
When the number of blue-eyed people is 0, the foreigner is lying, and if the tribe believes him, everyone commits ritual suicide.
When the number of blue-eyed people is 1, the blue-eyed person did not know there were any blue-eyed people in the tribe. Knowledge is added by the statement, and the blue-eyed person commits ritual suicide.
When the number of blue-eyed people is 2, the blue-eyed people knew that there was a blue-eyed person but did not know that the blue-eyed person knew that the tribe had any blue-eyed people. Knowledge is added by the statement, and the blue-eyed people commit ritual suicide.
When the number of blue-eyed people is 3 or more, the blue-eyed people knew that there were blue-eyed people and knew that the blue-eyed people knew that there were blue-eyed people. No knowledge is added by the statement, and no one commits ritual suicide.
No.
There is nothing wrong with the induction and the second argument is the correct one. This is a well known puzzle that became very popular on Terrence Tao's blog (http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islan...) - where you can also find the solution (and various wrong attempts) in the comments.
With 3 blue-eyed people:
Everybody knows that there are other people with blue eyes.
Everybody knows that everybody knows that there are other people with blue eyes.
However, prior to the visitor's statement, nobody knows that everybody knows that everybody knows that there are other people with blue eyes.
Because, consider the case where there are 3 blue eyed people named A,B,C.
A knows that B knows that C has blue eyes.
However A cannot possibly know that B knows that C knows that somebody has blue-eyes, because that somebody can either be B - in which case B has no way of knowing that, and therefore no way of knowing that C knows that, A - in which case A has no way of knowing that , and therefore no way of knowing that B knows that C knows that, or C, in which case C has no way of knowing that, and therefore B has no way of knowing that C knows that.
Following the visitor's comment - A does know that, and eventually everybody kills himself.
I think you've got it wrong. The information added is that a blue eyed person has been positively identified. In the three person case, each blue eyed person can see two people and is internally modeling their logic about the two person scenario. Once the logic for a two person scenario falls through, they can infer that there are not two people with blue eyes.
The brown eyed people are however modeling an N+1 person case.
> When the number of blue-eyed people is 1, the blue-eyed person did not know there were any blue-eyed people in the tribe. Knowledge is added by the statement.
Wouldn't the blue-eyed person think either:
a) The visitor is lying, and wonder why everyone else doesn't think they are blue-eyed, thus committing suicide?
b) Since they know no one else is blue-eyed, deduce that they are the sole blue-eyed person and commit suicide?
> When the number of blue-eyed people is 2, the blue-eyed people knew that there was a blue-eyed person but did not know that the blue-eyed person knew that the tribe had any blue-eyed people. Knowledge is added by the statement.
Wouldn't these two people wonder why the other blue-eyed person isn't committing suicide, and deduce that they too must also be blue-eyed?
I read an essay once remarking that the ancient Greeks really wanted to square the circle (you can think of the problem as being to construct a line of length pi using only a reference line of length 1 and a compass and straightedge).
Despite not knowing that this couldn't be done, no reference survives to any Greek claiming that it could.
Today, we know perfectly well that the problem is impossible. But we get dozens of papers a year claiming to have solved it. The essay reflected that something has gone wrong in our culture.
Please don't contribute to that problem by spouting off about problems you don't understand.
If n=3, then each of the blue-eyed people know that there are blue-eyed people and know that the other blue-eyed people know. However, they don't know that all the blue-eyed people know that the blue-eyed people know. This is the piece of information that is learned by the statement given.
In general, if there are N blue-eyed people, then it is the Nth abstraction of "he knows that I know that he knows that I know that..." that is learned by the statement.
the error is in sloppy induction. The inductive step attempts to assume the lesser n condition by mapping it onto itself (which is a fallacious situation).
I think the foreigners statement is ambiguous enough to render the proof in argument 2 incorrect. "... another blue-eyed person", to me, implies a singular person in the tribe has blue eyes. All of tribespeople will see multiple tribespeople with blue eyes, and therefore assume the foreigners statement was wrong, rendering no effect.
It's not so much that the statement was ambiguous or wrong -- it's that the statement gave no one in the tribe more information than was previously available to him/her.
Everyone in the tribe already observes at least 99 members with blue eyes, and everyone knows that everyone else observes at least 99 members with blue eyes, so the statement should have no effect.
> Now suppose inductively that n is larger than 1. Each blue-eyed person will reason as follows: “If I am not blue-eyed, then there will only be n-1 blue-eyed people on this island, and so they will all commit suicide n-1 days after the traveler’s address”.
Why should not a brown-eyed person reason as follows as well? It is at this stage that an implicit "counting" of the blue-eyed population creeps into the flawed proof.
EDIT: I misidentified the place where the flaw comes in. Will repost a better explanation.
They would. The traveller has accidentally doomed them all.
edit: this is based on an unfounded assumption because of the wording of the problem - they may only know they don't have blue eyes. But when I read "100 have blue eyes and 900 have brown" it makes it sound binary and I assumed that's knowledge the tribes people have as well, i.e. we have only either blue or brown eyes.
If there are 100 blue eyed people, each of them will kill themselves on day 99 (because they can only see 99 other blue-eyed people). However, the brown eyed people will wait until day 100.
On day 100, a brown eyed person won't know that he is brown eyed, only that he is not blue eyed, so he could have green eyes, purple eyes, etc.
Taking the 'dramatic effect' argument further: if all the blue-eyed people kill themselves, would the brown-eyed people all simultaneously know they have brown eyes and also have to kill themselves?
This is the missing element from most explanations I see of this problem. We all look at the n cases from the POV of a blue-eyed person. An outside observer with brown eyes has the same level of information available to him, so it seems to me just as likely that after the first day, each person, regardless of eye color, could reason that nobody left the previous day, so the visitor must have been referring to me. So either eventually everyone dies, or they all realize the paradox and forgo the ritual.
And do the islanders know that there are 100 blue-eyed people? Remember... they don't talk about eye state.
Each Blue-eyed person may think that there's 99 people with blue eyes and still not know their own state. So basing any logic on the fact that there is 100 people with blue eyes makes sense to an outside observer, but to the blue-eyed people they can't use this fact in any logical conclusion.
The traveler has no effect.
The logical flaw is that with n > 2 blue eyed people, everybody knows that there is at least 1 blue eyed person AND everybody knows that everybody ELSE knows that there is at least 1 blue eyed person.
The traveler's comments would only have an effect with n<=2 blue eyed people. With n = 1, he'd instantly know. With n = 2, the 2nd blue eyed person would recognize that the first person now has the information and if he doesn't commit suicide on the first night, then the 2nd blue eyed person knows the 1st blue had the information before, meaning he saw somebody else, and then they both die on night 2. n > 2, the info is already out that blue-eyed ppl exist and the count has already started.
So, what the visitor is providing is really the coordination, the point at which you can measure 100 or 99 days. But doesn't this setup require that there have always been 100 blue eyed people since forever? Any birth or death or all the islanders being crated at once would serve equally well as a timer. It seems like this problem only works because the blue-eyed islanders all know that there are 99 other islanders with blue eyes, but there was no moment in time where they learned it. And since that is so contrary to our expectations, it's what ends up making the whole scenario seem so unintuitive.
No, the key is that the foreigner's statement establishes common knowledge at some point in time. What happened before that point in time is irrelevant.
> the blue-eyed islanders all know that there are 99 other islanders with blue eyes
That's true, but what they don't know (until the 2nd) day) is that all the other blue-eyed islanders know that all the other blue-eyed islanders know that there are 99 other blue-eyed islanders. On the 3rd day they will realize that all the other blue-eyed islanders know that all the other blue eyed islanders know that all the other blue eyed islanders know that... and so on. Then on the 100th day there are 100 iterations of recursive knowledge, and all the blue-eyed islanders realize they themselves must have blue eyes.
UPDATE: note that it is crucial that all the islanders are together when the foreigner makes his statement. If he goes to each islander individually and says "some of you have blue eyes" then it doesn't work. What matters is not the statement, but that all the islanders witness all the other islanders hearing the statement.
> If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness.
Emphasis mine, of course.
You can think of this clause as specifying the clock speed (one cycle per day) of the logical machine that is the island.
There's an infuriating variant, which I have as yet been unable to solve:
An infinite sequence of people have either blue or brown eyes. They must shout out a guess as to their own colour of eyes, simultaneously. Is there a way for them to do it so that only finitely many of them guess incorrectly?
Personally, I'm convinced the blue-eyed people die on the hundredth day if they haven't earlier - I am not convinced there is no shorter path to the information (though I certainly don't know of one).
1- Nothing says that there were 1000 islanders on the day the alien made his speech. Some may have discovered they eye color and died before.
2- Compare:
“how unusual it is to see another blue-eyed person like myself in this region of the world”
with:
“how unusual it is to see other blue-eyed persons like myself in this region of the world”
To me, it is clear that the entire tribe the day the stranger makes his speech consists of N brown-eyed, and one single remaining blue-eyed.
They immediately understand the same thing, and all commit suicide the next noon.
This is a lovely way to teach induction and proofs as part of a class. I personally prefer the dragon version of this problem. An elegant solution is provided here.
Shouldn't it be better if people had to commit suicide in their own houses? I mean if there are 2 people with blue eyes and on the second day they see each other at the town square about to commit seppuko they'd figure perhaps the other is the only one with blue eyes. Or this whole thing went over my head.
Ok, I'm pretty sure I'm being moronic and missing something, but does the foreigner give the tribe any more information? Does the tribe already know how many blue eyed and brown eyed people there are?
If they already knew how many of each, then they would all be dead, as any of them would see that the numbers add up only if he was in a specific group.
The problem statement specifies that the population of the island all reason with perfect logic. Compare that to the reasoning displayed by my babysitter's son once:
Me: I saw my parents wrapping a Christmas present, but on Christmas
when I received that present, it was labeled "from Santa".
Him: Santa Claus is real.
Good luck finding a suitable population to experiment on. ;)
[+] [-] Mindless2112|12 years ago|reply
The first argument is true; the second has the logical flaw. The flaw is assuming that induction can continue despite additional pre-knowledge available when there are greater numbers of blue-eyed people.
The statement will have no effect when the number of blue-eyed people is 3 or more:
When the number of blue-eyed people is 0, the foreigner is lying, and if the tribe believes him, everyone commits ritual suicide.
When the number of blue-eyed people is 1, the blue-eyed person did not know there were any blue-eyed people in the tribe. Knowledge is added by the statement, and the blue-eyed person commits ritual suicide.
When the number of blue-eyed people is 2, the blue-eyed people knew that there was a blue-eyed person but did not know that the blue-eyed person knew that the tribe had any blue-eyed people. Knowledge is added by the statement, and the blue-eyed people commit ritual suicide.
When the number of blue-eyed people is 3 or more, the blue-eyed people knew that there were blue-eyed people and knew that the blue-eyed people knew that there were blue-eyed people. No knowledge is added by the statement, and no one commits ritual suicide.
Edit: clarity.
[+] [-] pavelrub|12 years ago|reply
With 3 blue-eyed people: Everybody knows that there are other people with blue eyes. Everybody knows that everybody knows that there are other people with blue eyes. However, prior to the visitor's statement, nobody knows that everybody knows that everybody knows that there are other people with blue eyes.
Because, consider the case where there are 3 blue eyed people named A,B,C. A knows that B knows that C has blue eyes. However A cannot possibly know that B knows that C knows that somebody has blue-eyes, because that somebody can either be B - in which case B has no way of knowing that, and therefore no way of knowing that C knows that, A - in which case A has no way of knowing that , and therefore no way of knowing that B knows that C knows that, or C, in which case C has no way of knowing that, and therefore B has no way of knowing that C knows that.
Following the visitor's comment - A does know that, and eventually everybody kills himself.
Formally this new information is knows as "common knowledge": http://en.wikipedia.org/wiki/Common_knowledge_(logic)
[+] [-] DannoHung|12 years ago|reply
The brown eyed people are however modeling an N+1 person case.
[+] [-] jader201|12 years ago|reply
> When the number of blue-eyed people is 1, the blue-eyed person did not know there were any blue-eyed people in the tribe. Knowledge is added by the statement.
Wouldn't the blue-eyed person think either:
a) The visitor is lying, and wonder why everyone else doesn't think they are blue-eyed, thus committing suicide?
b) Since they know no one else is blue-eyed, deduce that they are the sole blue-eyed person and commit suicide?
> When the number of blue-eyed people is 2, the blue-eyed people knew that there was a blue-eyed person but did not know that the blue-eyed person knew that the tribe had any blue-eyed people. Knowledge is added by the statement.
Wouldn't these two people wonder why the other blue-eyed person isn't committing suicide, and deduce that they too must also be blue-eyed?
[+] [-] thaumasiotes|12 years ago|reply
Despite not knowing that this couldn't be done, no reference survives to any Greek claiming that it could.
Today, we know perfectly well that the problem is impossible. But we get dozens of papers a year claiming to have solved it. The essay reflected that something has gone wrong in our culture.
Please don't contribute to that problem by spouting off about problems you don't understand.
[+] [-] MereInterest|12 years ago|reply
In general, if there are N blue-eyed people, then it is the Nth abstraction of "he knows that I know that he knows that I know that..." that is learned by the statement.
[+] [-] dnautics|12 years ago|reply
[+] [-] DanielStraight|12 years ago|reply
http://xkcd.com/solution.html (Though you might want to click his link to the problem description first since his is a variation.)
[+] [-] md224|12 years ago|reply
http://en.wikipedia.org/wiki/Common_knowledge_(logic)
http://plato.stanford.edu/entries/common-knowledge/
[+] [-] elwell|12 years ago|reply
[+] [-] hornd|12 years ago|reply
[+] [-] Mindless2112|12 years ago|reply
Everyone in the tribe already observes at least 99 members with blue eyes, and everyone knows that everyone else observes at least 99 members with blue eyes, so the statement should have no effect.
Edit: split to separate comment.
[+] [-] unknown|12 years ago|reply
[deleted]
[+] [-] dnautics|12 years ago|reply
Why should not a brown-eyed person reason as follows as well? It is at this stage that an implicit "counting" of the blue-eyed population creeps into the flawed proof.
EDIT: I misidentified the place where the flaw comes in. Will repost a better explanation.
[+] [-] tbrake|12 years ago|reply
edit: this is based on an unfounded assumption because of the wording of the problem - they may only know they don't have blue eyes. But when I read "100 have blue eyes and 900 have brown" it makes it sound binary and I assumed that's knowledge the tribes people have as well, i.e. we have only either blue or brown eyes.
[+] [-] IanDrake|12 years ago|reply
So, every brown eyed person was one day away from leaving when all the blue eyed people spontaneously left.
However, now everyone left knows they have brown eyes.
Update: To herge's point they probably don't know there are only two possibilities.
[+] [-] herge|12 years ago|reply
On day 100, a brown eyed person won't know that he is brown eyed, only that he is not blue eyed, so he could have green eyes, purple eyes, etc.
[+] [-] aolol|12 years ago|reply
[+] [-] thaumasiotes|12 years ago|reply
[+] [-] Jehar|12 years ago|reply
[+] [-] axus|12 years ago|reply
[+] [-] benjohnson|12 years ago|reply
Each Blue-eyed person may think that there's 99 people with blue eyes and still not know their own state. So basing any logic on the fact that there is 100 people with blue eyes makes sense to an outside observer, but to the blue-eyed people they can't use this fact in any logical conclusion.
[+] [-] vytasgd|12 years ago|reply
The traveler's comments would only have an effect with n<=2 blue eyed people. With n = 1, he'd instantly know. With n = 2, the 2nd blue eyed person would recognize that the first person now has the information and if he doesn't commit suicide on the first night, then the 2nd blue eyed person knows the 1st blue had the information before, meaning he saw somebody else, and then they both die on night 2. n > 2, the info is already out that blue-eyed ppl exist and the count has already started.
[+] [-] Symmetry|12 years ago|reply
[+] [-] lisper|12 years ago|reply
> the blue-eyed islanders all know that there are 99 other islanders with blue eyes
That's true, but what they don't know (until the 2nd) day) is that all the other blue-eyed islanders know that all the other blue-eyed islanders know that there are 99 other blue-eyed islanders. On the 3rd day they will realize that all the other blue-eyed islanders know that all the other blue eyed islanders know that all the other blue eyed islanders know that... and so on. Then on the 100th day there are 100 iterations of recursive knowledge, and all the blue-eyed islanders realize they themselves must have blue eyes.
UPDATE: note that it is crucial that all the islanders are together when the foreigner makes his statement. If he goes to each islander individually and says "some of you have blue eyes" then it doesn't work. What matters is not the statement, but that all the islanders witness all the other islanders hearing the statement.
[+] [-] thaumasiotes|12 years ago|reply
> If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness.
Emphasis mine, of course.
You can think of this clause as specifying the clock speed (one cycle per day) of the logical machine that is the island.
[+] [-] Smaug123|12 years ago|reply
An infinite sequence of people have either blue or brown eyes. They must shout out a guess as to their own colour of eyes, simultaneously. Is there a way for them to do it so that only finitely many of them guess incorrectly?
[+] [-] pavelrub|12 years ago|reply
This is a variant of the hat puzzle, and the solution requires some set-theory.
[+] [-] anonymoushn|12 years ago|reply
[+] [-] miguelrochefort|12 years ago|reply
[+] [-] dllthomas|12 years ago|reply
[+] [-] informatimago|12 years ago|reply
2- Compare: “how unusual it is to see another blue-eyed person like myself in this region of the world” with: “how unusual it is to see other blue-eyed persons like myself in this region of the world”
To me, it is clear that the entire tribe the day the stranger makes his speech consists of N brown-eyed, and one single remaining blue-eyed.
They immediately understand the same thing, and all commit suicide the next noon.
[+] [-] konceptz|12 years ago|reply
https://www.physics.harvard.edu/uploads/files/undergrad/prob...
[+] [-] lazyant|12 years ago|reply
[+] [-] spongerbakula|12 years ago|reply
[+] [-] miahi|12 years ago|reply
[+] [-] unknown|12 years ago|reply
[deleted]
[+] [-] unknown|12 years ago|reply
[deleted]
[+] [-] DannoHung|12 years ago|reply
[+] [-] elwell|12 years ago|reply
[+] [-] thaumasiotes|12 years ago|reply