Live data from Hacker News

Blue Eyes Logic Puzzle

math.ucla.edu

51–60 of 94 posts

Re: Blue Eyes Logic Puzzle

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

Re: Blue Eyes Logic Puzzle

#52
post #38

Earlier quoted context omitted.

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

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

Re: Blue Eyes Logic Puzzle

#54

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

Re: Blue Eyes Logic Puzzle

#55

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

Re: Blue Eyes Logic Puzzle

#56

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

Re: Blue Eyes Logic Puzzle

#57

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

This is hard to wrap my head around.

Re: Blue Eyes Logic Puzzle

#58

Earlier quoted context omitted.

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.

Re: Blue Eyes Logic Puzzle

#60

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…

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).
Post reply on HN