Blue Eyes Logic Puzzle
math.ucla.edu
math.ucla.edu
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.
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)
The brown eyed people are however modeling an N+1 person case.
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.
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.
Or, the other interesting thing is what if there were 500 and 500?
It's a very weird logic puzzle for sure.
> 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?
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.
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.
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 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.
Edit: my comment is still correct thanks to parent's 2nd edit.
> 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.
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.
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.
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.
(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.)
http://xkcd.com/solution.html (Though you might want to click his link to the problem description first since his is a variation.)
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?
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.
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.
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.
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.
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.
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.
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.
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.
* 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.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.
The blue eyed member doesn't see anyone else with 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.
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.
If each blue eye can see 99 others and nothing happens on day 99, then they know what has to happen on day 100.
As far as I can see, the brown eyes all kill themselves the next day.
.... and so have to kill themselves
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 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.
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?
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.)
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.
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.
> 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.
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 a variant of the hat puzzle, and the solution requires some set-theory.
- 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.
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.
https://www.physics.harvard.edu/uploads/files/undergrad/prob...
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.