The Blue-Eyed Islanders Puzzle
06 Jan 2014
If you have never seen the Blue-Eyed Islanders Puzzle before, then hold onto your hats and stand near some sterilised plastic sheeting because your brain is about to explode. If you have seen it before but have never thought to use it at a dinner party then you are insane. In either case, be warned that you may be overwhelmed and/or seriously injured by the unmanageable influx of respect, kudos and attractive women/men/both that will follow this puzzle’s use at your next evening engagement.
The following script gives you substantial chunks of time with the whole room’s rapt attention. You may wish to use this opportunity to slip in some of your more controversial views on immigration and women’s rights. Interspersed are opportunities to sit back and watch in smug satisfaction as the minds of your dining companions are mangled more and more with every second they spend in your island world.
0. The setup
If you want to completely obliterate someone’s standing in your group (for example a rival alpha male or a romantic enemy), try and tempt them into venturing another, infinitely inferior brainteaser that you can use as a segue into stomping them mercilessly into the ground. However, by the time you’ve finished, no one will remember anything else that happened earlier, so feel free to shoehorn it in with a complete non-sequitur too. Take care not to start too late in the evening or just before an interval in the proceedings like a change of course. As with any tour de force, you do not want to have to pause for plate-clattering or mass urination.
1. The basic puzzle
I first saw the problem here. I will reproduce it for completeness (and SEO) in a slightly edited, dinner party optimised form. Adjust to taste:
“There’s an island with a tribe of 1000 people. 100 of them have blue eyes, 900 have brown eyes. But their religion completely forbids them from knowing their own eye colour, or even discussing the topic. There are no reflective surfaces anywhere, so each person can see everyone else’s eye colour, but has no idea what their own is. If a tribesperson discovers their own eye colour then they have to commit ritual suicide at noon the next day, in the town square, for all to see. Each person is highly devout, and there is no way that any of them would try and cheat this process. Each person is also a perfect logician - anything that they could deduce from the information and observations available to them, they instantly will.
So one day an explorer comes along, saves the lives of several children and wins the total trust of everyone on the island. In the evening he gives a speech to thank everyone in the tribe for their hospitality. However, he doesn’t know about their eye-colour superstitions, and opens his speech with “It’s incredible to see one or more people with blue eyes in this part of the world”.
The question is - what effect, if any, does his faux pas have on the island?”
Remember that your formulation of the question must:
- Have a strong sense of story to draw listeners in
- Be as precise as possible, in order to both head off the stupider of the stupid questions that will subsequently be asked, and more importantly to prevent anyone from claiming “oh well you didn’t explain THAT, it’s easy if you know THAT” during your grand reveal. You may wish to clarify things like “everyone has both eyes the same colour”, “everyone has eyes and no one is blind”, or just use a catch-all assurance that the question is deep, not trying to mislead and is not solved by these kinds of tricky shenanigans.
As with all puzzles of any fame, there exist a few other slightly different formulations [0][1], but Terence Tao’s is my favourite and I believe the most precise one. I have found that if anyone present at your dinner party starts trying to hijack your puzzle by dismissing it as derivative old hat, punching them in the face usually makes them stop.
2. The answers
I don’t think it’s unreasonable to say that anyone who is able to come up with the correct answer at this point, despite never having seen the problem before and having had a few glasses of wine, is a total genius and you should immediately start worshipping them accordingly. If anyone pipes up with “ah yes I’ve heard this before” then I generally like to suggest that we take a walk in the garden and then lock them in a shed. These obstacles out of the way, I would suggest not pausing for too long at this point, as it is unlikely that anyone will have anything constructive or interesting to say. Instead, posit these two contradictory but both seemingly convincing arguments:
2.1 Common sense
It will have no effect, as it doesn’t tell anyone anything they didn’t know already. Everyone can already see that there are multiple people with blue eyes.
2.2 Proof by induction
All 100 blue-eyed people will kill themselves on day 100 after the speech.
Pretend that I am the only person on the island with blue eyes. I would look around and see no one else with blue eyes. I would reason “oh crap, I must have blue eyes” and kill myself the next day.
Now pretend that both me and <insert name of dinner party guest> have blue eyes. We would each look at the other person and think “OK, so that guy is going to kill himself tomorrow because he is the only one with blue eyes and now he knows it”. Tomorrow comes and neither of us kills ourselves. We each reason, “oh crap, that guy didn’t kill himself because he must have seen someone else with blue eyes and expected them to kill themselves. I can’t see anyone else with blue eyes, so I must have blue eyes.” We both kill ourselves on day 2 after the speech.
NOW pretend that me, <insert name of dinner party guest> and <insert name of other dinner party guest> all have blue eyes. We would each see the other 2 people with blue eyes, and expect them to kill themselves on day 2, as above. When they don’t, we would reason, “oh crap, they didn’t kill themselves because they BOTH saw a further person with blue eyes, and expected that person and the other person to kill themselves on day 2. I can’t see anyone else with blue eyes, so I must have blue eyes.” We all kill ourselves on day 3.
Keep chaining this logic up to 100 people, and the conclusion is that all 100 blue-eyed people will kill themselves on day 100 after the speech.
(Add references to proof by induction and base cases according to mathematicality of your audience. I have found that characterising the people in the explanation as you and your companions makes things easier to visualise.)
2.3 Wtf
The question is now “which of these contradictory explanations is right and why?” Uproar and chaos will typically break out.
3. The real answer
This is where it is most fun to let the table stew for a while. Common (and wrong) beliefs are:
- There is a limit on the value of n where the induction argument breaks down
- The question is flawed - everyone on the island should have killed themselves already
- It has no effect obviously, argh argh rargh
The explanation is the most delicate step, and must be handled very carefully. If you do not manage to convincingly explain to your audience why you are right, you risk being seen as the arrogant, attention-seeking sociopath you are are not.
The proof by induction is correct. New information IS being introduced to the island, and so common sense answer 1 is wrong.
Pretend again that I am the only person with blue eyes. In this case, when the explorer says “it’s incredible to see one or more people with blue eyes in this part of the world”, new information is obviously being introduced. I didn’t know that there was anyone with blue eyes on the island, and now I do. This new information causes me to kill myself.
Now pretend that me and Bob have blue eyes. The explorer says “it’s incredible to see one or more people with blue eyes in this part of the world”. I already knew that there were blue-eyed islanders, as I could see Bob. But now I also know that Bob knows there are blue-eyed islanders. This is new information to me, as if I had brown eyes then Bob wouldn’t be able to see anyone with blue eyes. When neither of us kills ourself on day 1, it is this new knowledge, that came from the explorer’s statement, that cause our dual suicide on day 2.
Now pretend that me, Bob and Charlie have blue eyes. I already knew that there were blue-eyed islanders. I already knew that Bob knew there were people with blue eyes on the island, as I knew that he could see Charlie. But now I know that Bob knows that Charlie knows there are blue-eyed islanders, and this change is again what eventually causes us to deduce our own eye colours.
Beyond this number of people a detailed mapping gets very abstract and unhelpful. But anyone who has properly understood the induction should now also see the form of the new information that triggers it. As more and more people come to see the light, they will start trying to help the rest of the group. If/when they get out of their depth they will typically defer to you, making you seem and feel even more like a boss.
4. Extensions
The amazement doesn’t stop there. You may wish to schism off a little group of those who really got the answer in order to exclude and exert further dominance over the others. You can probably let anyone you had to lock in the shed out now.
4.1 Questions
- What happens if everyone knows that an islander with blue eyes was in the toilet whilst the explorer was giving his speech and so didn't hear him? What if the islander had brown eyes?
- Everyone on the island knows that there will be no suicides for the first 98 days, as they can all see either 99 or 100 people with blue eyes. Is it therefore necessary to wait those first 98 days, and if so then why? (source - [0])
- Having realised that he has doomed 100 people to death with his careless speech, how could the explorer minimise the damage he has caused? Would it be ethical for him to do so? (source - [2])
4.2 Answers
- Blue eyes - no one has to kill themselves. Brown eyes - all the blue-eyed islanders still have to kill themselves. Explanations left as exercise for the reader.
- It is indeed necessary to wait the first 98 days. As each day goes past, the lack of suicides increases each islander's knowledge of the other islander's knowledge (of the other islander's knowledge of the other islander's knowledge…etc.), and it takes this initial period for the full effect of the explorer's speech to propagate. Consider the case with 3 blue-eyed islanders - Alice, Bob and Charlie. As external observers, we know that they will all kill themselves on day 3. But on day 0, Alice doesn't know whether Bob knows whether Charlie knows he is not the only blue-eyed islander. As far as Alice is concerned, if she had brown eyes then the only blue-eyed person that Bob could see would be Charlie, so Bob could be anticipating Charlie killing himself on day 1. When Alice sees Bob seeing Charlie NOT kill himself on day 1, she now knows that Bob knows that Charlie knows he is not the only blue-eyed islander. This is not enough for her to know what colour her eyes are, but information increases in this way every day of non-suicide, until eventually the blue-eyed islanders have enough information to know their eye colour and have to kill themselves.
- If on day 0 the explorer also names a specific person who has blue eyes, then that person will have to kill themselves on day 1, but then no one else will have to. Go back to the case with 2 blue-eyed islanders - Alice and Bob. As we know, without further intervention they will both kill themselves on day 2. But if the explorer tells the whole tribe that Alice has blue eyes, and she kills herself on day 1, then Bob now has no way of knowing what his eye colour is. The explorer's second, more specific statement effectively shuts down the chain of non-suicide days by providing a specific plausible explanation for his earlier, more generic statement, ending the leaking of information that these days cause. As far as ethics are concerned, it seems sensible to me but the philosophers of your group will no doubt have more to add. (Extension extension - what if he only realises his mistake on day 5? (source - [2]))
5. Conclusion
Once you have collected and reassembled the fragments of your now exploded brain, you will see how awesome this puzzle is, and therefore what an incredibly powerful tool it represents. With repetition, you will find yourself becoming progressively more accomplished at wielding it, and will accumulate little flourishes and accoutrements that put the icing on this already unfeasibly delicious cake. I should reiterate that you must be prepared for the inevitable conclusion where you become known for winning so hard at dinner parties that you stop being invited because you make everyone else look like massive idiots. You should also be aware that the hoards of attractive men and/or women queuing up to buy you dinner will quickly become disappointed and frequently violent when it turns out that you don’t have any other material close to this quality. I’ve heard that studying James Blunt’s Twitter feed can help, but other that this you are on your own.
6. References
[0] http://xkcd.com/solution.html
[1] http://www.math.dartmouth.edu/~pw/solutions.pdf
[2] http://www.math.ucla.edu/~tao/blue_variant.html
See also:
Wikipedia - Common Knowledge
Stack Exchange question with a great first answer
If you have never seen the Blue-Eyed Islanders Puzzle before, then hold onto your hats and stand near some sterilised plastic sheeting because your brain is about to explode. If you have seen it before but have never thought to use it at a dinner party then you are insane. In either case, be warned that you may be overwhelmed and/or seriously injured by the unmanageable influx of respect, kudos and attractive women/men/both that will follow this puzzle’s use at your next evening engagement.
The following script gives you substantial chunks of time with the whole room’s rapt attention. You may wish to use this opportunity to slip in some of your more controversial views on immigration and women’s rights. Interspersed are opportunities to sit back and watch in smug satisfaction as the minds of your dining companions are mangled more and more with every second they spend in your island world.
0. The setup
If you want to completely obliterate someone’s standing in your group (for example a rival alpha male or a romantic enemy), try and tempt them into venturing another, infinitely inferior brainteaser that you can use as a segue into stomping them mercilessly into the ground. However, by the time you’ve finished, no one will remember anything else that happened earlier, so feel free to shoehorn it in with a complete non-sequitur too. Take care not to start too late in the evening or just before an interval in the proceedings like a change of course. As with any tour de force, you do not want to have to pause for plate-clattering or mass urination.
1. The basic puzzle
I first saw the problem here. I will reproduce it for completeness (and SEO) in a slightly edited, dinner party optimised form. Adjust to taste:
“There’s an island with a tribe of 1000 people. 100 of them have blue eyes, 900 have brown eyes. But their religion completely forbids them from knowing their own eye colour, or even discussing the topic. There are no reflective surfaces anywhere, so each person can see everyone else’s eye colour, but has no idea what their own is. If a tribesperson discovers their own eye colour then they have to commit ritual suicide at noon the next day, in the town square, for all to see. Each person is highly devout, and there is no way that any of them would try and cheat this process. Each person is also a perfect logician - anything that they could deduce from the information and observations available to them, they instantly will.
So one day an explorer comes along, saves the lives of several children and wins the total trust of everyone on the island. In the evening he gives a speech to thank everyone in the tribe for their hospitality. However, he doesn’t know about their eye-colour superstitions, and opens his speech with “It’s incredible to see one or more people with blue eyes in this part of the world”.
The question is - what effect, if any, does his faux pas have on the island?”
Remember that your formulation of the question must:
- Have a strong sense of story to draw listeners in
- Be as precise as possible, in order to both head off the stupider of the stupid questions that will subsequently be asked, and more importantly to prevent anyone from claiming “oh well you didn’t explain THAT, it’s easy if you know THAT” during your grand reveal. You may wish to clarify things like “everyone has both eyes the same colour”, “everyone has eyes and no one is blind”, or just use a catch-all assurance that the question is deep, not trying to mislead and is not solved by these kinds of tricky shenanigans.
As with all puzzles of any fame, there exist a few other slightly different formulations [0][1], but Terence Tao’s is my favourite and I believe the most precise one. I have found that if anyone present at your dinner party starts trying to hijack your puzzle by dismissing it as derivative old hat, punching them in the face usually makes them stop.
2. The answers
I don’t think it’s unreasonable to say that anyone who is able to come up with the correct answer at this point, despite never having seen the problem before and having had a few glasses of wine, is a total genius and you should immediately start worshipping them accordingly. If anyone pipes up with “ah yes I’ve heard this before” then I generally like to suggest that we take a walk in the garden and then lock them in a shed. These obstacles out of the way, I would suggest not pausing for too long at this point, as it is unlikely that anyone will have anything constructive or interesting to say. Instead, posit these two contradictory but both seemingly convincing arguments:
2.1 Common sense
It will have no effect, as it doesn’t tell anyone anything they didn’t know already. Everyone can already see that there are multiple people with blue eyes.
2.2 Proof by induction
All 100 blue-eyed people will kill themselves on day 100 after the speech.
Pretend that I am the only person on the island with blue eyes. I would look around and see no one else with blue eyes. I would reason “oh crap, I must have blue eyes” and kill myself the next day.
Now pretend that both me and <insert name of dinner party guest> have blue eyes. We would each look at the other person and think “OK, so that guy is going to kill himself tomorrow because he is the only one with blue eyes and now he knows it”. Tomorrow comes and neither of us kills ourselves. We each reason, “oh crap, that guy didn’t kill himself because he must have seen someone else with blue eyes and expected them to kill themselves. I can’t see anyone else with blue eyes, so I must have blue eyes.” We both kill ourselves on day 2 after the speech.
NOW pretend that me, <insert name of dinner party guest> and <insert name of other dinner party guest> all have blue eyes. We would each see the other 2 people with blue eyes, and expect them to kill themselves on day 2, as above. When they don’t, we would reason, “oh crap, they didn’t kill themselves because they BOTH saw a further person with blue eyes, and expected that person and the other person to kill themselves on day 2. I can’t see anyone else with blue eyes, so I must have blue eyes.” We all kill ourselves on day 3.
Keep chaining this logic up to 100 people, and the conclusion is that all 100 blue-eyed people will kill themselves on day 100 after the speech.
(Add references to proof by induction and base cases according to mathematicality of your audience. I have found that characterising the people in the explanation as you and your companions makes things easier to visualise.)
2.3 Wtf
The question is now “which of these contradictory explanations is right and why?” Uproar and chaos will typically break out.
3. The real answer
This is where it is most fun to let the table stew for a while. Common (and wrong) beliefs are:
- There is a limit on the value of n where the induction argument breaks down
- The question is flawed - everyone on the island should have killed themselves already
- It has no effect obviously, argh argh rargh
The explanation is the most delicate step, and must be handled very carefully. If you do not manage to convincingly explain to your audience why you are right, you risk being seen as the arrogant, attention-seeking sociopath you are are not.
The proof by induction is correct. New information IS being introduced to the island, and so common sense answer 1 is wrong.
Pretend again that I am the only person with blue eyes. In this case, when the explorer says “it’s incredible to see one or more people with blue eyes in this part of the world”, new information is obviously being introduced. I didn’t know that there was anyone with blue eyes on the island, and now I do. This new information causes me to kill myself.
Now pretend that me and Bob have blue eyes. The explorer says “it’s incredible to see one or more people with blue eyes in this part of the world”. I already knew that there were blue-eyed islanders, as I could see Bob. But now I also know that Bob knows there are blue-eyed islanders. This is new information to me, as if I had brown eyes then Bob wouldn’t be able to see anyone with blue eyes. When neither of us kills ourself on day 1, it is this new knowledge, that came from the explorer’s statement, that cause our dual suicide on day 2.
Now pretend that me, Bob and Charlie have blue eyes. I already knew that there were blue-eyed islanders. I already knew that Bob knew there were people with blue eyes on the island, as I knew that he could see Charlie. But now I know that Bob knows that Charlie knows there are blue-eyed islanders, and this change is again what eventually causes us to deduce our own eye colours.
Beyond this number of people a detailed mapping gets very abstract and unhelpful. But anyone who has properly understood the induction should now also see the form of the new information that triggers it. As more and more people come to see the light, they will start trying to help the rest of the group. If/when they get out of their depth they will typically defer to you, making you seem and feel even more like a boss.
4. Extensions
The amazement doesn’t stop there. You may wish to schism off a little group of those who really got the answer in order to exclude and exert further dominance over the others. You can probably let anyone you had to lock in the shed out now.
4.1 Questions
- What happens if everyone knows that an islander with blue eyes was in the toilet whilst the explorer was giving his speech and so didn't hear him? What if the islander had brown eyes?
- Everyone on the island knows that there will be no suicides for the first 98 days, as they can all see either 99 or 100 people with blue eyes. Is it therefore necessary to wait those first 98 days, and if so then why? (source - [0])
- Having realised that he has doomed 100 people to death with his careless speech, how could the explorer minimise the damage he has caused? Would it be ethical for him to do so? (source - [2])
4.2 Answers
- Blue eyes - no one has to kill themselves. Brown eyes - all the blue-eyed islanders still have to kill themselves. Explanations left as exercise for the reader.
- It is indeed necessary to wait the first 98 days. As each day goes past, the lack of suicides increases each islander's knowledge of the other islander's knowledge (of the other islander's knowledge of the other islander's knowledge…etc.), and it takes this initial period for the full effect of the explorer's speech to propagate. Consider the case with 3 blue-eyed islanders - Alice, Bob and Charlie. As external observers, we know that they will all kill themselves on day 3. But on day 0, Alice doesn't know whether Bob knows whether Charlie knows he is not the only blue-eyed islander. As far as Alice is concerned, if she had brown eyes then the only blue-eyed person that Bob could see would be Charlie, so Bob could be anticipating Charlie killing himself on day 1. When Alice sees Bob seeing Charlie NOT kill himself on day 1, she now knows that Bob knows that Charlie knows he is not the only blue-eyed islander. This is not enough for her to know what colour her eyes are, but information increases in this way every day of non-suicide, until eventually the blue-eyed islanders have enough information to know their eye colour and have to kill themselves.
- If on day 0 the explorer also names a specific person who has blue eyes, then that person will have to kill themselves on day 1, but then no one else will have to. Go back to the case with 2 blue-eyed islanders - Alice and Bob. As we know, without further intervention they will both kill themselves on day 2. But if the explorer tells the whole tribe that Alice has blue eyes, and she kills herself on day 1, then Bob now has no way of knowing what his eye colour is. The explorer's second, more specific statement effectively shuts down the chain of non-suicide days by providing a specific plausible explanation for his earlier, more generic statement, ending the leaking of information that these days cause. As far as ethics are concerned, it seems sensible to me but the philosophers of your group will no doubt have more to add. (Extension extension - what if he only realises his mistake on day 5? (source - [2]))
5. Conclusion
Once you have collected and reassembled the fragments of your now exploded brain, you will see how awesome this puzzle is, and therefore what an incredibly powerful tool it represents. With repetition, you will find yourself becoming progressively more accomplished at wielding it, and will accumulate little flourishes and accoutrements that put the icing on this already unfeasibly delicious cake. I should reiterate that you must be prepared for the inevitable conclusion where you become known for winning so hard at dinner parties that you stop being invited because you make everyone else look like massive idiots. You should also be aware that the hoards of attractive men and/or women queuing up to buy you dinner will quickly become disappointed and frequently violent when it turns out that you don’t have any other material close to this quality. I’ve heard that studying James Blunt’s Twitter feed can help, but other that this you are on your own.
6. References
[0] http://xkcd.com/solution.html
[1] http://www.math.dartmouth.edu/~pw/solutions.pdf
[2] http://www.math.ucla.edu/~tao/blue_variant.html
See also:
Wikipedia - Common Knowledge
Stack Exchange question with a great first answer