Blue Eyes Logic Puzzle(math.ucla.edu)
math.ucla.edu
Blue Eyes Logic Puzzle
http://www.math.ucla.edu/~tao/blue.html
18 comments
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.
Formally this new information is knows as "common knowledge": http://en.wikipedia.org/wiki/Common_knowledge_(logic)
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)
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.
The brown eyed people are however modeling an N+1 person case.
Hmm. That seems right. With 3 blue-eyed people, a blue-eyed person observing that the 2 blue-eyed people did nothing does add the additional knowledge that there are a total of 3 blue-eyed people.
So the additional knowledge added for 3 or more blue-eyed people is a lower bound on the total number of blue-eyed people (which grows over time), but it's not exactly clear to me why the foreigner's statement triggers this.
So the additional knowledge added for 3 or more blue-eyed people is a lower bound on the total number of blue-eyed people (which grows over time), but it's not exactly clear to me why the foreigner's statement triggers this.
I've been with you on this, but I think we are wrong. Here's where I'm at:
(without foreigner's statement)
1 blue eyed person- He know's nothing, nothing happens
2 blue eyed people- Each thinks the other could be the only blue but they don't know it... deadlock.
3 blue eyed people- Each thinks the other two are caught in the 2 person deadlock scenario knowing nothing.
4 blue eyed people- Each thinks the other 3 are caught in the 3 person scenario etc...
Once the foreigner adds the knowledge:
1- he'd leave the first day
2- the second would recognize the first didn't leave, they'd both leave on day 2
3- the third would recognize the first two didn't leave on day 2, etc, etc, we were wrong...bollocks.
1 blue eyed person- He know's nothing, nothing happens
2 blue eyed people- Each thinks the other could be the only blue but they don't know it... deadlock.
3 blue eyed people- Each thinks the other two are caught in the 2 person deadlock scenario knowing nothing.
4 blue eyed people- Each thinks the other 3 are caught in the 3 person scenario etc...
Once the foreigner adds the knowledge:
1- he'd leave the first day
2- the second would recognize the first didn't leave, they'd both leave on day 2
3- the third would recognize the first two didn't leave on day 2, etc, etc, we were wrong...bollocks.
I dunno, but it's interesting that if you think about it, even if he said to one person, "You have blue eyes." Only that one person would do anything.
Or, the other interesting thing is what if there were 500 and 500?
It's a very weird logic puzzle for sure.
Or, the other interesting thing is what if there were 500 and 500?
It's a very weird logic puzzle for sure.
The new information (common knowledge) is added immediately to everybody, not after 2 days. Using this information (that everybody knows that everybody knows that everybody knows...), it is then possible to decide whether you have blue eyes or not after 2 days.
I agree with you. Additionally:
> 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?
> 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?
Yes, I edited to clarify that a bit.
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.
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.
Oh please. The only things that have changed are access to such ideas and the volume of our records. He's already corrected his position. No harm in being wrong on the internet. Politeness is more important than rightness as a rule to enforce. Rightness sorts itself out among able and interested parties.
> The only things that have changed are access to such ideas and the volume of our records.
Both of those definitely changed; unlike some of the other things you say, this is not ridiculous. However, I can easily imagine finding in, say, the personal correspondence of Archimedes, a statement like "this idiot tried to show me another squaring-the-circle proof again". We do preserve personal correspondence in ancient records, and that sort of thing doesn't require a lot of access.
> No harm in being wrong on the internet.
http://www.mamapedia.com/article/mmr-vaccination
Money quote: "I have really close friends who swear that within 24 hours of the MMR their child had symptoms of autism"
> Politeness is more important than rightness as a rule to enforce.
It's better to be right. Enforcement of politeness greatly retards, and can prevent, the discovery / acknowledgement of rightness.
> Rightness sorts itself out among able and interested parties.
This can be tautologically true, depending on your definition of "able". It's very clear that rightness does not sort itself out among interested parties, and they can be harmed thereby.
Both of those definitely changed; unlike some of the other things you say, this is not ridiculous. However, I can easily imagine finding in, say, the personal correspondence of Archimedes, a statement like "this idiot tried to show me another squaring-the-circle proof again". We do preserve personal correspondence in ancient records, and that sort of thing doesn't require a lot of access.
> No harm in being wrong on the internet.
http://www.mamapedia.com/article/mmr-vaccination
Money quote: "I have really close friends who swear that within 24 hours of the MMR their child had symptoms of autism"
> Politeness is more important than rightness as a rule to enforce.
It's better to be right. Enforcement of politeness greatly retards, and can prevent, the discovery / acknowledgement of rightness.
> Rightness sorts itself out among able and interested parties.
This can be tautologically true, depending on your definition of "able". It's very clear that rightness does not sort itself out among interested parties, and they can be harmed thereby.
You missed what I think is baklava's main point: "The only things that have changed are access to such ideas and the volume of our records." Your argument that "The essay reflected that something has gone wrong in our culture" is a pretty bold statement that doesn't take into consideration the volume of and access to information we have today.
To me it seems you're contradicting yourself. What does this bold statement of yours tells you about trying to contribute to a problem one does not understand?
To me it seems you're contradicting yourself. What does this bold statement of yours tells you about trying to contribute to a problem one does not understand?
The quote you're giving me leads my response and I describe it as "not ridiculous".
"The essay reflected that ______" reports someone else's point of view, not my own. I agree that something is wrong in our culture; it cannot be shown that this represents a change from that of Classical Greece, but it can be supposed to varying levels of certainty. But if I exhort people to stop contributing to a problem of today, whether that problem originated in the recent past or the ancient past is of no relevance. We should still stop it today.
"The essay reflected that ______" reports someone else's point of view, not my own. I agree that something is wrong in our culture; it cannot be shown that this represents a change from that of Classical Greece, but it can be supposed to varying levels of certainty. But if I exhort people to stop contributing to a problem of today, whether that problem originated in the recent past or the ancient past is of no relevance. We should still stop it today.
Pardon? The parent's comment is correct.
Edit: my comment is still correct thanks to parent's 2nd edit.
Edit: my comment is still correct thanks to parent's 2nd edit.
Parent makes this very clear statement:
> The statement will have no effect when the number of blue-eyed people is 3 or more
This is wrong, and is known to be wrong. Again, if you cannot understand a problem yourself, you might at least look into it before assuming you can.
> The statement will have no effect when the number of blue-eyed people is 3 or more
This is wrong, and is known to be wrong. Again, if you cannot understand a problem yourself, you might at least look into it before assuming you can.
> Edit: my comment is still correct thanks to parent's 2nd edit.
If you're playing the retroactive-history game, let me point out that that edit had not been made when you made your comment. If party A issues a statement, I point out that it's nonsense, you say that you agree with party A, and then A recants, that doesn't make you right by virtue of the wording you used to agree with him. It makes you foolish.
If you're playing the retroactive-history game, let me point out that that edit had not been made when you made your comment. If party A issues a statement, I point out that it's nonsense, you say that you agree with party A, and then A recants, that doesn't make you right by virtue of the wording you used to agree with him. It makes you foolish.
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.
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.
"they don't know that all the blue-eyed people know that the blue-eyed people know"
Yes, they do. In the three-person case, a blue-eyed person can see two other blue-eyed people, A and B, and they know that A can see B, and vice-versa, so they know that A and B both know that there are blue-eyed people, and they know that both A and B would be able to us the same logic they used, so they also know that A and B know that A and B know that there are blue-eyed people.
Yes, they do. In the three-person case, a blue-eyed person can see two other blue-eyed people, A and B, and they know that A can see B, and vice-versa, so they know that A and B both know that there are blue-eyed people, and they know that both A and B would be able to us the same logic they used, so they also know that A and B know that A and B know that there are blue-eyed people.
Can you go into further detail about the nth abstraction of "he knows that I know..." and what effect that has on the population? The way I see it is that as soon as everybody knows that there are blue-eyed ppl and everybody knows that everybody else knows there are blue-eyed ppl the countdown begins... additionally, at that point you can already get to an infinite number of abstractions of the "he knows that I know that he.." statement because you both know that the other knows blue-eyed ppl exist, so you both know that the other knows that you know that blue-eyed ppl exist, so you both know....
At n = 3, every blue-eyed person knows everything every other blue-eyed person knows and that every blue-eyed person knows it, so you can already construct an infinitely-long chain of "I know that he knows that I know that he knows..." at that point.
(Of course, I am assuming that all the people think/reason exactly the same and that they all know that they think/reason exactly the same, which are assumptions of the original problem.)
(Of course, I am assuming that all the people think/reason exactly the same and that they all know that they think/reason exactly the same, which are assumptions of the original problem.)
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).
Randall Munroe has a much more thorough write-up on (a variation on) this puzzle:
http://xkcd.com/solution.html (Though you might want to click his link to the problem description first since his is a variation.)
http://xkcd.com/solution.html (Though you might want to click his link to the problem description first since his is a variation.)
And for an even more detailed examination of the underlying philosophical issues:
http://en.wikipedia.org/wiki/Common_knowledge_(logic)
http://plato.stanford.edu/entries/common-knowledge/
http://en.wikipedia.org/wiki/Common_knowledge_(logic)
http://plato.stanford.edu/entries/common-knowledge/
I understand the induction steps, but what I don't get is why the foreigner's statement triggers the logic induction. This quote from your first link sums it well:
I mean, what bit of information is added here?
What's most interesting about this scenario is that, for k > 1, the outsider
is only telling the island citizens what they already know: that there
are blue-eyed people among them. However, before this fact is announced,
the fact is not common knowledge.
I mean, what bit of information is added here?
What's added is the common knowledge that everyone else knows that Blue > 1 (including the foreigner), and that everyone else knows that everyone else knows that Blue > 1, etc.
Consider two blue-eyed people, Alice and Bob. Alice sees Bob's blue eyes and knows that Blue ≥ 1, and vice-versa. But Alice thinks, "What if I have brown eyes? In that case, Bob wouldn't know that Blue ≥ 1." So, everyone knows that Blue ≥ 1, but nobody knows that everyone knows that. Then the foreigner comes along and tells them that, between Alice and Bob, Blue ≥ 1. Now Alice knows that Bob knows that Blue ≥ 1, and realizes that, if Alice has non-blue eyes, Bob will use the new information that Blue ≥ 1 to conclude that he has blue eyes, and therefore commit suicide on the next day. When he doesn't, she concludes that she must have blue eyes, and commits suicide. Bob goes through the exact same logic as Alice.
Though the foreigner's statement did not tell Alice anything new about eye color distribution, it did tell her something about Bob's knowledge. The same goes for Bob, who learns about Alice's knowledge.
The logic is a bit more difficult to talk through with three people, so generalizing it further is left as an exercise ;P It comes down to "everyone knows that everyone knows that Blue ≥ 1", which the foreigner also contributes as common knowledge by making his announcement. For more blue-eyed people, recur on that statement as many times as necessary.
Consider two blue-eyed people, Alice and Bob. Alice sees Bob's blue eyes and knows that Blue ≥ 1, and vice-versa. But Alice thinks, "What if I have brown eyes? In that case, Bob wouldn't know that Blue ≥ 1." So, everyone knows that Blue ≥ 1, but nobody knows that everyone knows that. Then the foreigner comes along and tells them that, between Alice and Bob, Blue ≥ 1. Now Alice knows that Bob knows that Blue ≥ 1, and realizes that, if Alice has non-blue eyes, Bob will use the new information that Blue ≥ 1 to conclude that he has blue eyes, and therefore commit suicide on the next day. When he doesn't, she concludes that she must have blue eyes, and commits suicide. Bob goes through the exact same logic as Alice.
Though the foreigner's statement did not tell Alice anything new about eye color distribution, it did tell her something about Bob's knowledge. The same goes for Bob, who learns about Alice's knowledge.
The logic is a bit more difficult to talk through with three people, so generalizing it further is left as an exercise ;P It comes down to "everyone knows that everyone knows that Blue ≥ 1", which the foreigner also contributes as common knowledge by making his announcement. For more blue-eyed people, recur on that statement as many times as necessary.
Small clarification: For the two-person case, it's important that everyone knows that everyone knows that Blue ≥ 1. For the three-person case, it's important that everyone knows that everyone knows that everyone knows that Blue ≥ 1. (The last paragraph is a bit unclear and/or wrong.)
Also, you need "everyone knew on day X that..."
[deleted]
No information is added, it just gives all islanders a synchronized reference point to sort themselves into groups. It's the synchronization that matters, not the info itself, per se. Once they all start sorting themselves on the same day (and KNOW that all other residents are doing the same) they start the countdown to day 100.
The information that is added is that the knowledge is made common or infinite degree (ie. everyone knows that everyone knows that everyone knows......that there is someone with blue eyes)
The time which everyone made an accurate count was the new common knowledge. I believe the traveler's words added no new information, or even his presence (other than bringing everyone together). It was the gathering together, where everyone could see everyone else, and know that counts were synchronized.
I think if there were an earlier all-hands-meeting without the traveler, the counts would have been synchronized then.
So, the faux pas had no effect, but he still "caused" it by accident. So, to combine the two arguments from the main link:
The foreigner's words have no effect, because his comments do not tell the tribe anything that they do not already know. On the 100th day, the blue eyed people commit suicide, unless they die/leave/disappear first.
I think if there were an earlier all-hands-meeting without the traveler, the counts would have been synchronized then.
So, the faux pas had no effect, but he still "caused" it by accident. So, to combine the two arguments from the main link:
The foreigner's words have no effect, because his comments do not tell the tribe anything that they do not already know. On the 100th day, the blue eyed people commit suicide, unless they die/leave/disappear first.
You are wrong. The traveler's words are necessary, and you can easily see that by considering the case where the blue-eyed group consists of one person. Even when the entire island population is collected into a meeting, there is no reason for the unique blue-eyed person to suddenly intuit that he has blue eyes.
Not sure what you're refering to by "count" here. There's nothing to count. What matters is everybody coming into the knowledge that everybody knows at least one person has blue eyes. This takes a prompt about that, which is the foreigner's speech. If the foreigner doesn't cause them to start sorting themselves into blue eyes/not blue eyes groups, there's no basis for them to start deducing anything.
Counting is how they measure the days passed versus how many blue-eyed people they see. I'm sure you're right, but I have to check the assumption that seeing everyone is the same as hearing a fact about everyone.
This is hard to wrap my head around.
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.
Edit: split to separate comment.
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.
But they don't know "everyone knew on day X" so there is ambiguity about when they would be counting from, so nothing can be deduced. The foreigner's statement provides a synchronization point: clearly everyone knew at that point.
[deleted]
> 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.
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.
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.
In Randall Munroe's version of the problem, he gives the visitor red eyes to explicitly avoid this binary assumption. Obviously, the visitor's statement is slightly different because of this.
Because the blue eyed person see 99 blue eyed people and the brown eyed person sees 100 blue eyed people.
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.
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.
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.
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?
What if they had green eyes?
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.
Each blue-eyed person observes 99 other blue-eyed people in the tribe, thus reasoning that he/she has blue eyes on the 100th day. However, each brown-eyed person observes 100 blue-eyed people in the tribe, thus reasoning that he/she has blue eyes on the 101st day (however this does not happen because on the 100th day all the blue-eyed people commit ritual suicide.)
Doesn't that presuppose they know there are 100 blue eyed people in their tribe? When that information is presented to the reader, it's presented as outside knowledge.
If they knew the color counts, they would know their eye color and all would have to commit suicide. The fact that the tribe still existed means, they didn't know the totals.
For example, if I know there are 100 people with blue eyes and I can count as many without including myself, then I must have brown eyes and must kill myself.
So again, there is no possible way the tribe had any idea what the exact counts where.
As a brown eyed person, there are either 100 blue eyed people meaning I have brown eyes, or there are a 101 blue eyed people and I have blue eyes. If a census was ever taken and the exact number known everyone would have to commit suicide.
Since the visitor didn't mention an exact number then there is still no way to know if you have blue or brown eyes.
However, the tribe now knows that the visitor knows he himself has blue eyes. Will they make him follow their ritual?
Update: OK, after reading the link in the first comment, I get it.
If they knew the color counts, they would know their eye color and all would have to commit suicide. The fact that the tribe still existed means, they didn't know the totals.
For example, if I know there are 100 people with blue eyes and I can count as many without including myself, then I must have brown eyes and must kill myself.
So again, there is no possible way the tribe had any idea what the exact counts where.
As a brown eyed person, there are either 100 blue eyed people meaning I have brown eyes, or there are a 101 blue eyed people and I have blue eyes. If a census was ever taken and the exact number known everyone would have to commit suicide.
Since the visitor didn't mention an exact number then there is still no way to know if you have blue or brown eyes.
However, the tribe now knows that the visitor knows he himself has blue eyes. Will they make him follow their ritual?
Update: OK, after reading the link in the first comment, I get it.
It is not necessary for the blue-eyed people to know the total number of blue-eyed people in the tribe, they can deduce it at day 100:
* A blue-eyed person observes 99 blue-eyed people.
* On day 99, the blue-eyed people do not commit ritual
suicide.
* Thus each blue-eyed person learns that all the blue-eyed
people also observe 99 blue-eyed people.
* Thus the blue-eyed person knows that the other blue-eyed
people must observe that he/she has blue eyes.>> The fact that the tribe still existed means, they didn't know the totals.
That's the crux of it right there.
If I may also add: the outside observers remark didn't tell the tribe any information they didn't already know - that there is a blue-eyed tribe member.
That's the crux of it right there.
If I may also add: the outside observers remark didn't tell the tribe any information they didn't already know - that there is a blue-eyed tribe member.
In the case that there is at least 1 member of the tribe with blue eyes, all the people with brown eyes can see his eye color. So they satisfy the question of who the traveler is talking about with the blue eyed member.
The blue eyed member doesn't see anyone else with blue eyes.
The blue eyed member doesn't see anyone else with blue eyes.
That's a good point, but then the critical factor is that nobody knows how many people have blue eyes. More specifically, each person has to hold the possibility that n = observed persons with blue eyes + 1, which is himself.
That's why it takes n days.
Each blue eyed person can see n-1 others. If nothing happens on day n-1, they learn that they have blue eyes.
Each blue eyed person can see n-1 others. If nothing happens on day n-1, they learn that they have blue eyes.
All they know is that every blue-eyed person killed themselves. So they know they have non-blue eyes, but not which color.
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.
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.
They are perfect logicians. It is not especially generous to think they can count (that is, if there are 100 blue eyed members, they can each count the other 99).
If each blue eye can see 99 others and nothing happens on day 99, then they know what has to happen on day 100.
If each blue eye can see 99 others and nothing happens on day 99, then they know what has to happen on day 100.
But why will a non-blue eyed person not think the same then?
A non blue eyed person will see that there are 100 blue eyed people and observe them killing themselves on the 100th day. For the blue eyes, if the 99 blue eyes they can see were all of the blue eyes, they would kill themselves on day 99. So the different eye colors have different information.
As far as I can see, the brown eyes all kill themselves the next day.
As far as I can see, the brown eyes all kill themselves the next day.
They won't, because they only know that everybody else has brown eyes. They do not know if they themselves have brown/pink/green/purple eyes. They only know they don't have blue eyes.
Because they would see 100 people with blue eyes, not 99, and so wouldn't kill themselves until one day later, at which point they now know they have brown eyes, because of the suicide.
> at which point they now know they have brown eyes
.... and so have to kill themselves
.... and so have to kill themselves
The islanders don't know that there are only blue and brown eyes. For all they know, their eye color could be green, red, etc. Hence, the logic only applies for the blue-eyed people.
It would never reach that state, because every blue eyed person would have committed suicide on the 99th day.
[deleted]
[deleted]
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.
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.
> 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.
Strictly, all blue eyed people need to hear the statement, right? If someone is missing and everyone (but them) knows the missing person has brown eyes, that doesn't change the logic of those who heard.
That's right.
Which suggests some follow-on puzzles:
1. What happens if one blue-eyed person is somewhere else on the island when the foreigner makes his statement (and his absence is known to everyone)?
2. What happens if the next day a blue-eyed stranger wanders into the village, thereby establishing common knowledge that the day before there was in fact an additional blue-eyed person on the island (though no one in the village knew it at the time)?
3. What happens if the next day a blue-eyed baby is born in the village?
Which suggests some follow-on puzzles:
1. What happens if one blue-eyed person is somewhere else on the island when the foreigner makes his statement (and his absence is known to everyone)?
2. What happens if the next day a blue-eyed stranger wanders into the village, thereby establishing common knowledge that the day before there was in fact an additional blue-eyed person on the island (though no one in the village knew it at the time)?
3. What happens if the next day a blue-eyed baby is born in the village?
1. Suppose the foreigner makes his statement to a group of islanders C ("contaminated"), and the rest of the islanders P ("pure") do not hear it, and it is known to all that they didn't hear it. Call the group of blue-eyed people B. Then the intersection of C with B will kill themselves after a number of days equal to the size of that group.
2. Nothing. (I interpreted this as being without a statement by a foreigner.)
3. Nothing. (I also interpreted this one as being without a statement by a foreigner. With such a statement, it's the same problem as case 1; everyone will recognize that the baby, having not existed on Foreigner Day, can't know about nor have been mentioned in the statement.)
EDIT:
I should point out that I've assumed the foreigner's statement refers to the group he's addressing, not to the population of the island. ("At least one of you who I see before me has blue eyes".)
With a better interpretation of your problem 2:
2a. On some day, the foreigner addresses a village, saying "at least one person on the island has blue eyes". A blue-eyed stranger wanders into the village shortly after he leaves, allowing the villagers to believe that he was referring to the stranger.
In this case, there is no synchronization point, and "nothing" will still occur.
2b. A blue-eyed stranger wanders into the village the day after the foreigner leaves, allowing the villagers to believe that he was referring to the stranger.
As far as I can see, this has gone back to case 1 again. The foreigner's statement provoked a first day of blue-counting, and while it is revealed to have possibly not meant what they thought it meant, day 1 of blue-counting is sufficient for day 2. The blue-eyed villagers should kill themselves after a number of days equal to the size of their group. (The stranger, even if he settles into the village, will be unaffected.)
2. Nothing. (I interpreted this as being without a statement by a foreigner.)
3. Nothing. (I also interpreted this one as being without a statement by a foreigner. With such a statement, it's the same problem as case 1; everyone will recognize that the baby, having not existed on Foreigner Day, can't know about nor have been mentioned in the statement.)
EDIT:
I should point out that I've assumed the foreigner's statement refers to the group he's addressing, not to the population of the island. ("At least one of you who I see before me has blue eyes".)
With a better interpretation of your problem 2:
2a. On some day, the foreigner addresses a village, saying "at least one person on the island has blue eyes". A blue-eyed stranger wanders into the village shortly after he leaves, allowing the villagers to believe that he was referring to the stranger.
In this case, there is no synchronization point, and "nothing" will still occur.
2b. A blue-eyed stranger wanders into the village the day after the foreigner leaves, allowing the villagers to believe that he was referring to the stranger.
As far as I can see, this has gone back to case 1 again. The foreigner's statement provoked a first day of blue-counting, and while it is revealed to have possibly not meant what they thought it meant, day 1 of blue-counting is sufficient for day 2. The blue-eyed villagers should kill themselves after a number of days equal to the size of their group. (The stranger, even if he settles into the village, will be unaffected.)
"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."
I don't see how they know that on the second day, either, though. Before the foreigner's statement, every blue-eyes islanders knows a) that there are at least 99 blue-eyed islanders b) that all the blue-eyed islanders know that there are at least 98 blue-eyed islanders. I don't see what the foreigner's statement adds to this knowledge.
I don't see how they know that on the second day, either, though. Before the foreigner's statement, every blue-eyes islanders knows a) that there are at least 99 blue-eyed islanders b) that all the blue-eyed islanders know that there are at least 98 blue-eyed islanders. I don't see what the foreigner's statement adds to this knowledge.
You're right, my explanation is actually wrong. The idea is right, but the recursive knowledge is not gained incrementally the way I described but rather all at once at the end when they wake up on the nth day and see that everyone is still alive.
Each one reasons (recursively) that if their eyes are brown then, given that common knowledge of the existence of blue-eyed people has been established, the remaining n-1 blue-eyed people will realize their eyes are blue (and kill themselves) on the n-1'th day. Since this doesn't happen, their eyes must be blue.
Each one reasons (recursively) that if their eyes are brown then, given that common knowledge of the existence of blue-eyed people has been established, the remaining n-1 blue-eyed people will realize their eyes are blue (and kill themselves) on the n-1'th day. Since this doesn't happen, their eyes must be blue.
Here is the part that people seem to miss:
> 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.
> 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?
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?
This is not a variant of the puzzle above.
This is a variant of the hat puzzle, and the solution requires some set-theory.
This is a variant of the hat puzzle, and the solution requires some set-theory.
And none of them have any knowledge about anything?
They can all see everyone else's eyes. That is, person N can see person M's eyes, for all M,N.
[I don't know whether it's possible or not - it feels not, but it has been hinted to me that it is possible.]
They could all shout "red". 0 is finite.
Two points:
- It is very, very, very frequent in mathematics to describe a number as "finite" specifically to indicate that it is nonzero. This is because while zero is boundedly large, it is not boundedly small (it is "infinitesimal").
- The problem statement asks for finitely many to guess incorrectly, not for finitely many to guess correctly.
- It is very, very, very frequent in mathematics to describe a number as "finite" specifically to indicate that it is nonzero. This is because while zero is boundedly large, it is not boundedly small (it is "infinitesimal").
- The problem statement asks for finitely many to guess incorrectly, not for finitely many to guess correctly.
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.
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.
https://www.physics.harvard.edu/uploads/files/undergrad/prob...
https://www.physics.harvard.edu/uploads/files/undergrad/prob...
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.
[deleted]
[deleted]
I think the problem also is missing some part where the people know for sure that they can only have blue or brown eyes.
Well let's try the experiment a few times and see if our results match up with our theories in double-blind tests.
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.
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.