5 ms·

The blue-eyed islanders puzzle

13 points by dwwoelfel 16y ago

StavrosK 16y ago
Does anyone know if the solution is posted anywhere? It seems that the only thing the stranger does is to give them a reference point to figure out how many blue-eyed people there are, and not much else.
- chime 16y ago
  Here's XKCD's blue-eyes problem http://www.xkcd.com/blue_eyes.html http://www.xkcd.com/blue_eyes.html and solution: http://xkcd.com/solution.html http://xkcd.com/solution.html
- deleted 16y ago
  [deleted]
- steverb 16y ago
  The solution is on that page although the way the puzzle is worded on xkcd is better I think. The key piece that xkcd adds is that each islander keeps a count of how many people of what eye color he/she sees. It's easier if we assume there are only 2 islanders with blue eyes. That means that each blue-eyed person can see one blue-eyed person. The day after the announcement each blue-eyed islander expects that if they themselves have brown eyes that the single blue-eyed person that they see would kill themselves, since if that person is the only blue eyed person they would only see other islanders with brown eyes. Since that doesn't happen, they know the day after the expected kill day that they themselves must also have blue eyes. So on day two, they both kill themselves. HTH
- ErrantX 16y ago
  As a logic puzzle it is very tenuous. The proposed solution (which is lower down the blog post) is that because any blue eyed Islander is able to count the number of blue eyed people (99), if on day 99 those people do not kill themselves it means that there is one further blue eyed Islander, and it is them. Brown eyed Islanders see 100 blue eyes, and so know that if mass suicide occurs on day 100 then they are not blue eyed. It's only a short reprieve though; because either the browns know that only two colours exist (and so on day 100 immediately know they are brown) or they face the same conundrum as blue, and commit suicide on day 900. The problem with the puzzle is not really the logical reasoning (which is sound, as described in the puzzle). The problem is that the Islanders, who are described as very logical, should know this information already. That they are still alive when the foreigner arrives is illogical. EDIT: to downvoters; consider the problem & solution very very carefully (or read my subsequent comment). Initially it seems a little illogical that the browns would die too, but it is ultimately the same basic problem that the blues face :)
  - andrew1 16y ago
    > It's only a short reprieve though; because either the browns know that only two colours exist (and so on day 100 immediately know they are brown) or they face the same conundrum as blue, and commit suicide on day 900. In the case where they aren't told that only two colours exist, why would they kill themselves on day 900? Suppose instead that one of the brown eyed people had green eyes, I don't see how the brown eyed people or green eyed person could deduce the colour of their own eyes.
    - ErrantX 16y ago
      Imagine the problem like this. The island is populated by just 100 Blue eyed people. An individual can therefore see 99 blue eyes. Their logical reasoning is that if they are not blue eyed then on day 99 all of the blue eyed people will commit suicide (because they can see 98 blue and 1 of another colour). Because the others don't commit suicide on day 99 the only logical inference is that everyone else can see 99 blue eyes too. And so they too must be blue. The reason the solution is so complex to comprehend is because the logical inference has little to do with what eye colours exist in the tribe. It is, ultimately, simple mathematics. If a tribe has n blue eyes, y brown eyes and z green eyes any of the individuals in the tribe will eventually be able to logically infer which colour they have, regardless of having any starter information. Another way to think of it is this; they know that there are either n people with X eyes. Or n+1. Where n is the number of people they can see with X eyes and the unknown factor is their own eye colour. For everyone without X eyes n is greater than those with X eyes.
      - andrew1 16y ago
        You originally said that the people with brown eyes would commit suicide after 900 days. Can you explain to me how any of them can know for sure that they don't have green eyes?
        ErrantX 16y ago
        I have done; I was using the "blue eyes on their own" as an example to demonstrate it. I'll try again (this can take a long while to get your head round :D). Once the Blue eyed people are dead each islander now knows that there are definitely at least 899 brown eyed people, with the unknown factor their own eye colour. Their hypothesis must be as follows (imagine this is the logical reasoning of ONE islander laying out the scenario): - If I do not have Brown eyes that means each of the brown eyed people can see 898 browns. If that is the case, then on day 899 all of those people will kill themselves. - If I did have Brown eyes then each of the brown eyed people can also see 899 brown eyes. If that is the case then no one will kill themselves on day 899, therefore as I can only see 899 browns, I must have brown Here is where most people struggle to understand: The number of brown eyes each individual can see is fixed at 899. The only unknown factor is their own eye colour. The solution is that everyone knows each other unknown factor. You know that either n or n+1 brown eyes exist (where n is the number of brown eyes they can observe). And so does everyone else (and, crucially, you know they know). If everyone's n matches yours, then on day n+1 you can infer what the unknown factor is. Another way of thinking about it is this; an individual can logically reason that only two types of people exist on the island. Those who see 899 browns (him, at the least), those who see 898 browns (potentially everyone else; on the hypothesis that his eye colour differs). If on day 899 no one commits suicide then each individual knows that only the former exists. And therefore they have brown eyes. (this is horribly hard to put across :S which is why it is such a delicious problem! The main thing to remember is that to the knowledge of one individual there is a known number of brown eyes, and a figure for the minimum and maximum number of brown eyes any other individual can see. If the number of days exceeds the number of browns you can see, you must be brown)
- deleted 16y ago
  [deleted]
- dansingerman 16y ago
  The solution (to the paradox which the OP is about, not the xkcd version, which the OP is not about) is not about what each individual knows after the foreigner has imparted the fact that there are people with blue eyes, but what each individual knows about what the others know after that. For n=1, after the foreigner has spoken, any other islander would know that the islander who can see no blue eyes (i.e. the one with blue eyes) will kill himself. For n=2, after one day, by the logic in the OP, an islander will know if the one blue-eyed islander has not yet committed suicide, then he himself must have blue eyes and commit suicide. For n+1 it follows the OP. The solution to the paradox therefore is before the foreigner speaks, each islander knows there are some islanders with blue eyes, after the foreigner speaks, each islander knows that each other islander knows that there are islanders with blue eyes. (The existence of blue eyes has become common knowledge http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29 http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29 ) Aside: I am not sure an English language description really covers the contortions of this logical conundrum.
lkozma 16y ago
Solution 2 is correct, Solution 1 is wrong because there is always transfer of information in the stranger's speech. Suppose there was only 1 blue-eyed person: [before]: Not everyone knows there exist blue eyed people (the blue eyed person doesn't know it) [after]: Everyone knows there exist blue eyed people. Suppose there are 2 blue-eyed persons: [before]: Everyone knows there are blue eyed persons. Not everyone knows that everyone knows that there are blue eyed persons (the 2 blue eyed don't know). If Alice and Bob are blue eyed, Alice knows Bob is blue eyed, but thinks that Bob thinks nobody has blue eyes. [after]: Everyone knows and knows that everyone knows etc. Suppose there are 3 blue-eyed persons: [before]: Everyone knows there are blue eyed people. Everyone knows everyone knows there are blue eyed people. Not everyone knows everyone knows everyone knows there are blue eyed people. This last statement changes after the speech. Similarly for any n: [before]: (everyone knows that)*(n-1) there are blue eyed people. [after]: everyone knows everything. EDIT: reworded for clarity.
- lkozma 16y ago
  Incidentally, this is why dictatorships don't allow gatherings of people (or free broadcast media). Everyone knows the regime is bad but not everyone knows that everyone knows etc. When the whole hierarchy collapses, revolutions break out.
- ckuehne 16y ago
  The case with 3 people always bugs me in solutions for this puzzle: If Alice, Bob, and Carol have blue eyes how can they not know that everyone knows that there are blue eyed people?
  - lkozma 16y ago
    They know that everyone knows that there are blue eyed people. What they don't know is that everyone knows this. In other words, they don't know that everyone knows that everyone knows that there are blue eyed people. Alice thinks like this: 1. there are blue eyed people (e.g. Bob and Carol) 2. everyone knows there are blue eyed people (Bob can see Carol, Carol can see Bob, everyone else can see them) 3. I know that 2 is true, but Bob and Carol might not know. Bob might think that Carol thinks that there are no blue-eyed people. (Of course, in reality, Bob does not think this because he can see Alice as well)

13 points by dwwoelfel 16y ago

Does anyone know if the solution is posted anywhere? It seems that the only thing the stranger does is to give them a reference point to figure out how many blue-eyed people there are, and not much else.

chime 16y ago
Here's XKCD's blue-eyes problem http://www.xkcd.com/blue_eyes.html http://www.xkcd.com/blue_eyes.html and solution: http://xkcd.com/solution.html http://xkcd.com/solution.html
deleted 16y ago
[deleted]
steverb 16y ago
The solution is on that page although the way the puzzle is worded on xkcd is better I think. The key piece that xkcd adds is that each islander keeps a count of how many people of what eye color he/she sees. It's easier if we assume there are only 2 islanders with blue eyes. That means that each blue-eyed person can see one blue-eyed person. The day after the announcement each blue-eyed islander expects that if they themselves have brown eyes that the single blue-eyed person that they see would kill themselves, since if that person is the only blue eyed person they would only see other islanders with brown eyes. Since that doesn't happen, they know the day after the expected kill day that they themselves must also have blue eyes. So on day two, they both kill themselves. HTH
ErrantX 16y ago
As a logic puzzle it is very tenuous. The proposed solution (which is lower down the blog post) is that because any blue eyed Islander is able to count the number of blue eyed people (99), if on day 99 those people do not kill themselves it means that there is one further blue eyed Islander, and it is them. Brown eyed Islanders see 100 blue eyes, and so know that if mass suicide occurs on day 100 then they are not blue eyed. It's only a short reprieve though; because either the browns know that only two colours exist (and so on day 100 immediately know they are brown) or they face the same conundrum as blue, and commit suicide on day 900. The problem with the puzzle is not really the logical reasoning (which is sound, as described in the puzzle). The problem is that the Islanders, who are described as very logical, should know this information already. That they are still alive when the foreigner arrives is illogical. EDIT: to downvoters; consider the problem & solution very very carefully (or read my subsequent comment). Initially it seems a little illogical that the browns would die too, but it is ultimately the same basic problem that the blues face :)
- andrew1 16y ago
  > It's only a short reprieve though; because either the browns know that only two colours exist (and so on day 100 immediately know they are brown) or they face the same conundrum as blue, and commit suicide on day 900. In the case where they aren't told that only two colours exist, why would they kill themselves on day 900? Suppose instead that one of the brown eyed people had green eyes, I don't see how the brown eyed people or green eyed person could deduce the colour of their own eyes.
  - ErrantX 16y ago
    Imagine the problem like this. The island is populated by just 100 Blue eyed people. An individual can therefore see 99 blue eyes. Their logical reasoning is that if they are not blue eyed then on day 99 all of the blue eyed people will commit suicide (because they can see 98 blue and 1 of another colour). Because the others don't commit suicide on day 99 the only logical inference is that everyone else can see 99 blue eyes too. And so they too must be blue. The reason the solution is so complex to comprehend is because the logical inference has little to do with what eye colours exist in the tribe. It is, ultimately, simple mathematics. If a tribe has n blue eyes, y brown eyes and z green eyes any of the individuals in the tribe will eventually be able to logically infer which colour they have, regardless of having any starter information. Another way to think of it is this; they know that there are either n people with X eyes. Or n+1. Where n is the number of people they can see with X eyes and the unknown factor is their own eye colour. For everyone without X eyes n is greater than those with X eyes.
    - andrew1 16y ago
      You originally said that the people with brown eyes would commit suicide after 900 days. Can you explain to me how any of them can know for sure that they don't have green eyes?
      - ErrantX 16y ago
        I have done; I was using the "blue eyes on their own" as an example to demonstrate it. I'll try again (this can take a long while to get your head round :D). Once the Blue eyed people are dead each islander now knows that there are definitely at least 899 brown eyed people, with the unknown factor their own eye colour. Their hypothesis must be as follows (imagine this is the logical reasoning of ONE islander laying out the scenario): - If I do not have Brown eyes that means each of the brown eyed people can see 898 browns. If that is the case, then on day 899 all of those people will kill themselves. - If I did have Brown eyes then each of the brown eyed people can also see 899 brown eyes. If that is the case then no one will kill themselves on day 899, therefore as I can only see 899 browns, I must have brown Here is where most people struggle to understand: The number of brown eyes each individual can see is fixed at 899. The only unknown factor is their own eye colour. The solution is that everyone knows each other unknown factor. You know that either n or n+1 brown eyes exist (where n is the number of brown eyes they can observe). And so does everyone else (and, crucially, you know they know). If everyone's n matches yours, then on day n+1 you can infer what the unknown factor is. Another way of thinking about it is this; an individual can logically reason that only two types of people exist on the island. Those who see 899 browns (him, at the least), those who see 898 browns (potentially everyone else; on the hypothesis that his eye colour differs). If on day 899 no one commits suicide then each individual knows that only the former exists. And therefore they have brown eyes. (this is horribly hard to put across :S which is why it is such a delicious problem! The main thing to remember is that to the knowledge of one individual there is a known number of brown eyes, and a figure for the minimum and maximum number of brown eyes any other individual can see. If the number of days exceeds the number of browns you can see, you must be brown)
deleted 16y ago
[deleted]
dansingerman 16y ago
The solution (to the paradox which the OP is about, not the xkcd version, which the OP is not about) is not about what each individual knows after the foreigner has imparted the fact that there are people with blue eyes, but what each individual knows about what the others know after that. For n=1, after the foreigner has spoken, any other islander would know that the islander who can see no blue eyes (i.e. the one with blue eyes) will kill himself. For n=2, after one day, by the logic in the OP, an islander will know if the one blue-eyed islander has not yet committed suicide, then he himself must have blue eyes and commit suicide. For n+1 it follows the OP. The solution to the paradox therefore is before the foreigner speaks, each islander knows there are some islanders with blue eyes, after the foreigner speaks, each islander knows that each other islander knows that there are islanders with blue eyes. (The existence of blue eyes has become common knowledge http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29 http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29 ) Aside: I am not sure an English language description really covers the contortions of this logical conundrum.

lkozma 16y ago

Solution 2 is correct, Solution 1 is wrong because there is always transfer of information in the stranger's speech. Suppose there was only 1 blue-eyed person: [before]: Not everyone knows there exist blue eyed people (the blue eyed person doesn't know it) [after]: Everyone knows there exist blue eyed people. Suppose there are 2 blue-eyed persons: [before]: Everyone knows there are blue eyed persons. Not everyone knows that everyone knows that there are blue eyed persons (the 2 blue eyed don't know). If Alice and Bob are blue eyed, Alice knows Bob is blue eyed, but thinks that Bob thinks nobody has blue eyes. [after]: Everyone knows and knows that everyone knows etc. Suppose there are 3 blue-eyed persons: [before]: Everyone knows there are blue eyed people. Everyone knows everyone knows there are blue eyed people. Not everyone knows everyone knows everyone knows there are blue eyed people. This last statement changes after the speech. Similarly for any n: [before]: (everyone knows that)*(n-1) there are blue eyed people. [after]: everyone knows everything. EDIT: reworded for clarity.

lkozma 16y ago
Incidentally, this is why dictatorships don't allow gatherings of people (or free broadcast media). Everyone knows the regime is bad but not everyone knows that everyone knows etc. When the whole hierarchy collapses, revolutions break out.
ckuehne 16y ago
The case with 3 people always bugs me in solutions for this puzzle: If Alice, Bob, and Carol have blue eyes how can they not know that everyone knows that there are blue eyed people?
- lkozma 16y ago
  They know that everyone knows that there are blue eyed people. What they don't know is that everyone knows this. In other words, they don't know that everyone knows that everyone knows that there are blue eyed people. Alice thinks like this: 1. there are blue eyed people (e.g. Bob and Carol) 2. everyone knows there are blue eyed people (Bob can see Carol, Carol can see Bob, everyone else can see them) 3. I know that 2 is true, but Bob and Carol might not know. Bob might think that Carol thinks that there are no blue-eyed people. (Of course, in reality, Bob does not think this because he can see Alice as well)