Hacker News Reader

Comment by bonobo | Hacker News Reader

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?

View on HN

What's added is the common knowledge that everyone else knows that Blue > 1 (including the foreigner), and that everyone else knows that everyone else knows that Blue > 1, etc.

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.

Also, you need "everyone knew on day X that..."

Small clarification: For the two-person case, it's important that everyone knows that everyone knows that Blue ≥ 1. For the three-person case, it's important that everyone knows that everyone knows that everyone knows that Blue ≥ 1. (The last paragraph is a bit unclear and/or wrong.)

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.

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.

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.

Counting is how they measure the days passed versus how many blue-eyed people they see. I'm sure you're right, but I have to check the assumption that seeing everyone is the same as hearing a fact about everyone.

Reply on news.ycombinator.com