8 ms·

The blue-eyed islanders puzzle (2008)

42 points by networked 11y ago

murbard2 11y ago
A dramatization http://slatestarcodex.com/2015/10/15/it-was-you-who-made-my-blue-eyes-blue/ http://slatestarcodex.com/2015/10/15/it-was-you-who-made-my-...
- gcr 11y ago
  Came here to post this story! It's so good.
eternauta3k 11y ago
How does it work out if you do it in continuous time?
- pervycreeper 11y ago
  No differently.
  - sopooneo 11y ago
    Then when does the mass suicide occur? At time n*0 after the pronouncement by the visitor?
pervycreeper 11y ago
Thread is a bit long. Which of the comments is particularly insightful/ worth reading?
- matroosberg 11y ago
  Prof. Tao himself links to the wikipedia article https://en.wikipedia.org/wiki/Common_knowledge_%28logic%29 https://en.wikipedia.org/wiki/Common_knowledge_%28logic%29 which uses this as an example for Common Logic.
deleted 11y ago
[deleted]
awesomepantsm 11y ago
I think there is a fallacy here actually. Some of the comments come close to touching it. If there are 3 islanders with blue eyes, each can see 2 blue-eyed people. The information that there is at least 1 blue is therefore not new information, and can't change the outcome. The outsider's comment is superfluous given that N > 3.
- alwaysmetara 11y ago
  The important point is that the outsider's comment "synchronizes" the islander's information. On Day 2, say you are a blue eyed person. You can see two other blue eyed people. Since these two people don't commit suicide during that day, you know there must be three blue eyed people with one of them being you. So now you know your eye color.
  - deleted 11y ago
    [deleted]
  - jack9 11y ago
    > you know there must be three blue eyed people Why? The visitor didn't synchronize anything. All of the villagers already knew there was at least 1 blue eyed person. Per the story, 99 or 100 depending on your perspective.
    - alwaysmetara 11y ago
      Everyone commits suicide at noon in view of everyone else. So the lowest possible number of blue eyed people go up one per day. Here's a longer explanation: Since people who know their eye color suicides at noon in plain sight of everyone else, we can set up induction. If there's only one blue eyed person, they would suicide the first day at noon. Since everyone sees > 1 blue eyed people, they know this wouldn't happen. Since this doesn't happen, it's common knowledge that there is more than 1 blue eyed person. So if you only see one other blue eyed person, you must have blue eyes (but you don't know this yet because you see two blue eyed people). On the second day, if there are only two blue eyed people, they would both suicide at noon. You see two blue eyed people. No one commits suicide because they either see two blue eyed people (if they have blue eyes) or three blue eyed people (if they don't). Now, everyone knows that there are more than two blue eyed people. Since no one committed suicide the day before, you reason that there must be three blue eyed people, with the 2 people you see plus yourself. Thus, you know your eye color. This is a bit long but I hope it's clear.
ars 11y ago
> 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” But no one knows n! So I am not following the logic in the slightest. Since no one knows n the entire logic sequence never gets started. Specifically: The only information the traveler gave them is that n >= 1. If n = 1 then the blue eyed person gained new information, which is how the inductive reasoning started, and I follow the logic that far. But if n > 1 then there is no new information and the inductive process never starts because no one knows n, no one. There is not a single person who knows n.
- tbrake 11y ago
  New information is gained every day there isn't a ritual self-sacrifice. Start with the simplest scenario that his words imply and work up every day from there. One blue eyed person could look around, see only brown (or other color) eyes, and figure out they must have been the one talked about, right? Boom, gone. Two blue eyed people would look around and see the other blue eyed person. However when the conditions for "one blue eyed person" aren't met, they would see the next day that there are 998 non-blue-eyed people and reason that the other blue eyed person must have seen a blue eyed person and it would have to be them. Boom. Gone. Three blue eyed people would look around and see two other blue eyed people. After the first two days they'd realize that since the conditions of the 2 blue eyed person scenario weren't met, there are 3 blue eyed people, and since they can see 997 other-eyed people, they must be the third in that scenario. Boom. Gone. And so on and so on.
- ubernostrum 11y ago
  The key of the problem includes the statement that all the islanders have seen all the other islanders and know their eye colors. From there we have the simple case of n = 1: suppose Bob is the only blue-eyed islander. He's seen everyone else's eyes, knows nobody else has blue eyes, and so can conclude from n >= 1 that in fact n = 1 and he is that one. For the case of n = 2: suppose Alice and Bob are the two blue-eyed islanders. Alice knows Bob is blue-eyed but doesn't know she is. Bob knows Alice is blue-eyed but doesn't know he is. There are two possibilities: n = 1 or n = 2, since they have seen every other person's eyes and know there are no other blue-eyed people. Each can watch the other's behavior on the first day. But since neither one knows their own eye color yet, neither one commits suicide that day. Then each one realizes that for the other not to commit suicide, it must be the case that n > 1. Since they know every other person's eye color, the only possible explanation is "n = 2 and I'm the other one". They commit suicide on day 2. From there we can just apply the same reasoning every time. If n = 3, Alice, Bob and Carol each look for the other two to commit suicide on the second day (from the reasoning for n = 2). When they don't, the only possible conclusion is "n = 3 and I'm the third one" and they all commit suicide on day 3. That line of reasoning then works with any successive value for n: if there are n blue-eyed islanders, each looks for the other n - 1 islanders to commit suicide on day n - 1. When that doesn't occur, the only possible conclusion those people can reach is "there's one more blue-eyed islander, and it's me". Then all n of them commit suicide on day n.
Steko 11y ago
Given the propensity of island based logic puzzles to define certain classes of people as always/sometimes lying or telling the truth, it's always bothered me that this puzzle never states that the foreigner never lies or is always believed.
- tbrake 11y ago
  The puzzle does state he is fully believed. > One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe. Why would it matter if he's a liar/truth teller in the classic island logic puzzle sense? It seems irrelevant to me because the islanders believe him fully and the puzzle is about figuring out the effects his statement has.
  - Steko 11y ago
    You are correct and thanks for the correction, wow do I feel dumb for missing that. Maybe I can save a small scrap of face in that at least occasionally this problem contains no such clause, e.g. the xkcd version although I should read that one again before submitting this reply.
- deleted 11y ago
  [deleted]
curun1r 11y ago
Wouldn't it be better to use the XKCD version [1] of the problem? That version was published 2 years earlier, doesn't make light of suicide and there's a ton of useful discussions [2] about the logic of it in the forums. [1] https://xkcd.com/blue_eyes.html https://xkcd.com/blue_eyes.html [2] http://forums.xkcd.com/viewtopic.php?f=3&t=3 http://forums.xkcd.com/viewtopic.php?f=3&t=3

42 points by networked 11y ago

A dramatization http://slatestarcodex.com/2015/10/15/it-was-you-who-made-my-blue-eyes-blue/ http://slatestarcodex.com/2015/10/15/it-was-you-who-made-my-...

gcr 11y ago
Came here to post this story! It's so good.

eternauta3k 11y ago

How does it work out if you do it in continuous time?

pervycreeper 11y ago
No differently.
- sopooneo 11y ago
  Then when does the mass suicide occur? At time n*0 after the pronouncement by the visitor?

pervycreeper 11y ago

Thread is a bit long. Which of the comments is particularly insightful/ worth reading?

matroosberg 11y ago
Prof. Tao himself links to the wikipedia article https://en.wikipedia.org/wiki/Common_knowledge_%28logic%29 https://en.wikipedia.org/wiki/Common_knowledge_%28logic%29 which uses this as an example for Common Logic.

deleted 11y ago

[deleted]

awesomepantsm 11y ago

I think there is a fallacy here actually. Some of the comments come close to touching it. If there are 3 islanders with blue eyes, each can see 2 blue-eyed people. The information that there is at least 1 blue is therefore not new information, and can't change the outcome. The outsider's comment is superfluous given that N > 3.

alwaysmetara 11y ago
The important point is that the outsider's comment "synchronizes" the islander's information. On Day 2, say you are a blue eyed person. You can see two other blue eyed people. Since these two people don't commit suicide during that day, you know there must be three blue eyed people with one of them being you. So now you know your eye color.
- deleted 11y ago
  [deleted]
- jack9 11y ago
  > you know there must be three blue eyed people Why? The visitor didn't synchronize anything. All of the villagers already knew there was at least 1 blue eyed person. Per the story, 99 or 100 depending on your perspective.
  - alwaysmetara 11y ago
    Everyone commits suicide at noon in view of everyone else. So the lowest possible number of blue eyed people go up one per day. Here's a longer explanation: Since people who know their eye color suicides at noon in plain sight of everyone else, we can set up induction. If there's only one blue eyed person, they would suicide the first day at noon. Since everyone sees > 1 blue eyed people, they know this wouldn't happen. Since this doesn't happen, it's common knowledge that there is more than 1 blue eyed person. So if you only see one other blue eyed person, you must have blue eyes (but you don't know this yet because you see two blue eyed people). On the second day, if there are only two blue eyed people, they would both suicide at noon. You see two blue eyed people. No one commits suicide because they either see two blue eyed people (if they have blue eyes) or three blue eyed people (if they don't). Now, everyone knows that there are more than two blue eyed people. Since no one committed suicide the day before, you reason that there must be three blue eyed people, with the 2 people you see plus yourself. Thus, you know your eye color. This is a bit long but I hope it's clear.

ars 11y ago

> 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” But no one knows n! So I am not following the logic in the slightest. Since no one knows n the entire logic sequence never gets started. Specifically: The only information the traveler gave them is that n >= 1. If n = 1 then the blue eyed person gained new information, which is how the inductive reasoning started, and I follow the logic that far. But if n > 1 then there is no new information and the inductive process never starts because no one knows n, no one. There is not a single person who knows n.

tbrake 11y ago
New information is gained every day there isn't a ritual self-sacrifice. Start with the simplest scenario that his words imply and work up every day from there. One blue eyed person could look around, see only brown (or other color) eyes, and figure out they must have been the one talked about, right? Boom, gone. Two blue eyed people would look around and see the other blue eyed person. However when the conditions for "one blue eyed person" aren't met, they would see the next day that there are 998 non-blue-eyed people and reason that the other blue eyed person must have seen a blue eyed person and it would have to be them. Boom. Gone. Three blue eyed people would look around and see two other blue eyed people. After the first two days they'd realize that since the conditions of the 2 blue eyed person scenario weren't met, there are 3 blue eyed people, and since they can see 997 other-eyed people, they must be the third in that scenario. Boom. Gone. And so on and so on.
ubernostrum 11y ago
The key of the problem includes the statement that all the islanders have seen all the other islanders and know their eye colors. From there we have the simple case of n = 1: suppose Bob is the only blue-eyed islander. He's seen everyone else's eyes, knows nobody else has blue eyes, and so can conclude from n >= 1 that in fact n = 1 and he is that one. For the case of n = 2: suppose Alice and Bob are the two blue-eyed islanders. Alice knows Bob is blue-eyed but doesn't know she is. Bob knows Alice is blue-eyed but doesn't know he is. There are two possibilities: n = 1 or n = 2, since they have seen every other person's eyes and know there are no other blue-eyed people. Each can watch the other's behavior on the first day. But since neither one knows their own eye color yet, neither one commits suicide that day. Then each one realizes that for the other not to commit suicide, it must be the case that n > 1. Since they know every other person's eye color, the only possible explanation is "n = 2 and I'm the other one". They commit suicide on day 2. From there we can just apply the same reasoning every time. If n = 3, Alice, Bob and Carol each look for the other two to commit suicide on the second day (from the reasoning for n = 2). When they don't, the only possible conclusion is "n = 3 and I'm the third one" and they all commit suicide on day 3. That line of reasoning then works with any successive value for n: if there are n blue-eyed islanders, each looks for the other n - 1 islanders to commit suicide on day n - 1. When that doesn't occur, the only possible conclusion those people can reach is "there's one more blue-eyed islander, and it's me". Then all n of them commit suicide on day n.

Steko 11y ago

Given the propensity of island based logic puzzles to define certain classes of people as always/sometimes lying or telling the truth, it's always bothered me that this puzzle never states that the foreigner never lies or is always believed.

tbrake 11y ago
The puzzle does state he is fully believed. > One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe. Why would it matter if he's a liar/truth teller in the classic island logic puzzle sense? It seems irrelevant to me because the islanders believe him fully and the puzzle is about figuring out the effects his statement has.
- Steko 11y ago
  You are correct and thanks for the correction, wow do I feel dumb for missing that. Maybe I can save a small scrap of face in that at least occasionally this problem contains no such clause, e.g. the xkcd version although I should read that one again before submitting this reply.
deleted 11y ago
[deleted]

curun1r 11y ago

Wouldn't it be better to use the XKCD version [1] of the problem? That version was published 2 years earlier, doesn't make light of suicide and there's a ton of useful discussions [2] about the logic of it in the forums. [1] https://xkcd.com/blue_eyes.html https://xkcd.com/blue_eyes.html [2] http://forums.xkcd.com/viewtopic.php?f=3&t=3 http://forums.xkcd.com/viewtopic.php?f=3&t=3