Blue Eyes Logic Puzzle

http://www.math.ucla.edu/~tao/blue.html

by ZeljkoS • 13 years ago

31 87 13 years ago

math.ucla.edu

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.)

md224• 13 years ago

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/

bonobo2• 13 years ago

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:

    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.

It seems natural to me why they didn't commit the suicide before the statement (somehow induction doesn't work here), and why they did it after the statement, but I don't understand why. Isn't the fact that there are k > 1 islanders with blue eyes common knowledge too?

I mean, what bit of information is added here?

elwell2• 13 years ago

This is hard to wrap my head around.

aolol• 13 years ago

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?

thaumasiotes11• 13 years ago

What if they had green eyes?

Jehar2• 13 years ago

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.

Mindless21127• 13 years ago

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.)

maxerickson4• 13 years ago

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.

benjohnson2• 13 years ago

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.

maxerickson4• 13 years ago

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.

axus3• 13 years ago

All they know is that every blue-eyed person killed themselves. So they know they have non-blue eyes, but not which color.

thaumasiotes11• 13 years ago

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.

hornd• 13 years ago

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.

Mindless21127• 13 years ago

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.

dllthomas4• 13 years ago

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.

Symmetry• 13 years ago

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.

lisper3• 13 years ago

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.

dllthomas4• 13 years ago

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.

voyou2• 13 years ago

"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.

lazyant• 13 years ago

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.

dllthomas4• 13 years ago

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).

dnautics2• 13 years ago

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.

tbrake• 13 years ago

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.

thedufer• 13 years ago

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.

herge• 13 years ago

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.

IanDrake2• 13 years ago

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.

Smaug1232• 13 years ago

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?

anonymoushn• 13 years ago

And none of them have any knowledge about anything?

Smaug1232• 13 years ago

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.]

pavelrub3• 13 years ago

This is not a variant of the puzzle above.

This is a variant of the hat puzzle, and the solution requires some set-theory.

miguelrochefort• 13 years ago

They could all shout "red". 0 is finite.

thaumasiotes11• 13 years ago

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.

spongerbakula• 13 years ago

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?

miahi• 13 years ago

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.

vytasgd4• 13 years ago

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.

Mindless21127• 13 years ago

Edit: it looks like I'm wrong.

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.

thaumasiotes11• 13 years ago

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.

vytasgd4• 13 years ago

Pardon? The parent's comment is correct.

Edit: my comment is still correct thanks to parent's 2nd edit.

backlava• 13 years ago

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.

jader201• 13 years ago

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?

Mindless21127• 13 years ago

Yes, I edited to clarify that a bit.

dnautics2• 13 years ago

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).

MereInterest• 13 years ago

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.

voyou2• 13 years ago

"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.

vytasgd4• 13 years ago

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....

Mindless21127• 13 years ago

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.)

DannoHung3• 13 years ago

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.

Mindless21127• 13 years ago

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.

pavelrub3• 13 years ago

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)

konceptz• 13 years ago

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...

elwell2• 13 years ago

Well let's try the experiment a few times and see if our results match up with our theories in double-blind tests.

thaumasiotes11• 13 years ago

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. ;)

DannoHung3• 13 years ago

I think the problem also is missing some part where the people know for sure that they can only have blue or brown eyes.

informatimago• 13 years ago

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.

Blue Eyes Logic Puzzle

Related Stories