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

61–70 of 94 posts

Re: Blue Eyes Logic Puzzle

#61

Post by thaumasiotes »

vytasgd wrote: post #55
thaumasiotes wrote: post #54

Earlier quoted context omitted.

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

Pardon? The parent's comment is correct. 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.

Re: Blue Eyes Logic Puzzle

#62

Post by thaumasiotes »

axus wrote: post #58
plaid_hatter wrote: post #48

Earlier quoted context omitted.

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…

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.

Re: Blue Eyes Logic Puzzle

#63

Post by jwpeddle »

axus wrote: post #58
plaid_hatter wrote: post #48

Earlier quoted context omitted.

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…

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.

Re: Blue Eyes Logic Puzzle

#64

Post by MereInterest »

Mindless2112 wrote: post #51

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, eve…

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.

Re: Blue Eyes Logic Puzzle

#65

Post by Mindless2112 »

jader201 wrote: post #56
Mindless2112 wrote: post #51

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, eve…

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…

Yes, I edited to clarify that a bit.

Re: Blue Eyes Logic Puzzle

#66

Post by DannoHung »

Mindless2112 wrote: post #51

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, eve…

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.

Re: Blue Eyes Logic Puzzle

#68

Post by voyou »

lisper wrote: post #18
Symmetry wrote: post #15

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

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…

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

Re: Blue Eyes Logic Puzzle

#69

Post by voyou »

MereInterest wrote: post #64
Mindless2112 wrote: post #51

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, eve…

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

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

Re: Blue Eyes Logic Puzzle

#70

Post by pavelrub »

Mindless2112 wrote: post #51

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, eve…

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)

Post reply on HN