5 ms·

Randall Munroe has a much more thorough write-up on (a variation on) this puzzle: http://xkcd.com/solution.html http://xkcd.com/solution.html (Though you might

Randall Munroe has a much more thorough write-up on (a variation on) this puzzle: http://xkcd.com/solution.html http://xkcd.com/solution.html (Though you might want to click his link to the problem description first since his is a variation.)

md224 13y ago
And for an even more detailed examination of the underlying philosophical issues: http://en.wikipedia.org/wiki/Common_knowledge_(logic) http://en.wikipedia.org/wiki/Common_knowledge_(logic) http://plato.stanford.edu/entries/common-knowledge/ http://plato.stanford.edu/entries/common-knowledge/
- bonobo 13y 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?
  - jwpeddle 13y ago
    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.
    - plaid_hatter 13y ago
      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)
      - axus 13y ago
        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.
        thaumasiotes 13y ago
        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.
        jwpeddle 13y ago
        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.
        axus 13y ago
  - matchu 13y ago
    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.
    - dllthomas 13y ago
      Also, you need "everyone knew on day X that..."
    - matchu 13y ago
      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.)
  - deleted 13y ago
    [deleted]
elwell 13y ago
This is hard to wrap my head around.

md224 13y ago

And for an even more detailed examination of the underlying philosophical issues: http://en.wikipedia.org/wiki/Common_knowledge_(logic) http://en.wikipedia.org/wiki/Common_knowledge_(logic) http://plato.stanford.edu/entries/common-knowledge/ http://plato.stanford.edu/entries/common-knowledge/

bonobo 13y 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?
- jwpeddle 13y ago
  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.
  - plaid_hatter 13y ago
    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)
    - axus 13y ago
      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.
      - thaumasiotes 13y ago
        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.
      - jwpeddle 13y ago
        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.
        axus 13y ago
- matchu 13y ago
  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.
  - dllthomas 13y ago
    Also, you need "everyone knew on day X that..."
  - matchu 13y ago
    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.)
- deleted 13y ago
  [deleted]

elwell 13y ago

This is hard to wrap my head around.