Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Blue Eyes Logic Puzzle

math.ucla.edu

Post reply on HN
Print view View original

31–40 of 94 posts

Re: Blue Eyes Logic Puzzle

#31

Post by Jehar »

maxerickson wrote: post #13
Jehar wrote: post #8

Earlier quoted context omitted.

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…

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.

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.

Re: Blue Eyes Logic Puzzle

#32

Post by dnautics »

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

Re: Blue Eyes Logic Puzzle

#33

Post by Smaug123 »

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?

Re: Blue Eyes Logic Puzzle

#34

Post by tbrake »

dnautics wrote: post #32

> 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 p…

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.

Re: Blue Eyes Logic Puzzle

#35

Post by axus »

aolol wrote: post #4

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?

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

Re: Blue Eyes Logic Puzzle

#36

Post by herge »

dnautics wrote: post #32

> 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 p…

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.

Re: Blue Eyes Logic Puzzle

#37

Post by maxerickson »

Jehar wrote: post #31
maxerickson wrote: post #13

Earlier quoted context omitted.

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.

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.

Re: Blue Eyes Logic Puzzle

#38

Post by lisper »

dllthomas wrote: post #25
lisper wrote: post #18

Earlier quoted context omitted.

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…

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?

Re: Blue Eyes Logic Puzzle

#39

Post by kybernetikos »

agf wrote: post #22
nchallak wrote: post #16

Earlier quoted context omitted.

But why will a non-blue eyed person not think the same then?

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

Re: Blue Eyes Logic Puzzle

#40

Post by IanDrake »

dnautics wrote: post #32

> 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 p…

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.

Post reply on HN