| Latest revision |
Your text |
| Line 1: |
Line 1: |
| − | {{comic | + | {{Incomplete|I started it, someone else (preferably who's actually solved the puzzle) can finish}} |
| − | | date = October 11, 2006 | + | XKCD's [http://xkcd.com/blue_eyes.html Blue eyes] puzzle is a logic puzzle posted around the same time as comic [[169]]. [[Randall]] calls it "the hardest logic puzzle in the world" on it's page; whether or not it really is the hardest is up to speculation. |
| − | | title = Blue Eyes
| |
| − | | lappend = blue_eyes.html#
| |
| − | | extra = yes
| |
| − | | before = <center><table width="90%"><tr><td><center><big>If you like formal logic, graph theory, sappy romance, bitter sarcasm, puns, or landscape art, check out my webcomic, <span class="plainlinks">[https://www.xkcd.com/ xkcd]</span></big>.
| |
| | | | |
| − | [[File:frame.jpg|link=https://www.xkcd.com/]] | + | The solution is at [http://xkcd.com/solution.html xkcd.com/solution.html]. |
| | | | |
| − | <font size="+3">Blue Eyes:</font>
| + | The page contains two comics. On the top is [[82: Frame]], and on bottom is [[37: Hyphen]]. |
| | | | |
| − | <font size="+1">The Hardest Logic Puzzle in the World</font></center>
| + | [[Category:Meta]] |
| − | | |
| − | <big>A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.
| |
| − | | |
| − | On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.
| |
| − | | |
| − | The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:
| |
| − | | |
| − | '''"I can see someone who has blue eyes."'''
| |
| − | | |
| − | Who leaves the island, and on what night?
| |
| − | | |
| − | | |
| − | There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."
| |
| − | | |
| − | And lastly, the answer is not "no one leaves."
| |
| − | | |
| − | <font color="#BB3333">I've done my best to make the wording as precise and unambiguious as possible (after working through the explanation with many people), but if you're confused about anything, please let me know. A word of warning: The answer is not simple. This is an exercise in serious logic, not a lateral thinking riddle. There is not a quick-and-easy answer, and really understanding it takes some effort.</font></big>
| |
| − | | |
| − | <center>[[File:hyphen.jpg|link=https://www.xkcd.com/]]</center>
| |
| − | | |
| − | <center><big>I didn't come up with the idea of this puzzle, but I've written and rewritten it over the the years to try to make a definitive version. The guy who told it to me originally was some dude on the street in Boston named Joel.</big></center>
| |
| − | </td></tr></table></center>
| |
| − | }}
| |
| − | {{TOC}}
| |
| − | ==Explanation==
| |
| − | xkcd's [http://xkcd.com/blue_eyes.html Blue Eyes] puzzle is a logic puzzle posted around the same time as comic [[169: Words that End in GRY]]. [[Randall]] calls it "The Hardest Logic Puzzle in the World" on its page, but whether it really is the hardest is up to speculation.
| |
| − | | |
| − | The page contains two comics. On the top is [[82: Frame]], and at the bottom is [[37: Hyphen]]. These particular comics may have been chosen intentionally, as 82 involves a mind screw (and formal logic can be pretty mind-screwy to the uninitiated) and 37 involves linguistic ambiguity, which Randall has explicitly gone out of his way to avoid (interestingly, [[169]] involves the infuriating ambiguity caused by misquoting riddles). That said, Randall could have simply picked those comics out of a hat to plug for his comic (which he also does explicitly), and the date of release could also be completely random.
| |
| − | | |
| − | Randall cites "some dude on the streets in Boston named Joel" as his source for the comic idea (although he's rewritten it).
| |
| − | | |
| − | ==The Puzzle==
| |
| − | A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can always see everyone else and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.
| |
| − |
| |
| − | On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So, any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.
| |
| − |
| |
| − | The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:
| |
| − |
| |
| − | "I can see someone who has blue eyes."
| |
| − |
| |
| − | Who leaves the island, and on what night?
| |
| − | | |
| − | ==Solution==
| |
| − | Randall's solution is at [http://xkcd.com/solution.html xkcd.com/solution.html].
| |
| − | | |
| − | Here are some observations that help simplify the problem.
| |
| − | | |
| − | No one without blue eyes will ever leave the island, because they are given no information that can allow them to determine which non-blue eye color they have. The presence of the non-blue-eyed people is not relevant at all. We can ignore them. All that matters is when the blue-eyed people learn that they actually are blue-eyed.
| |
| − | | |
| − | There are two ways in which blue-eyed people might leave the island. A lone blue-eyed person might leave on the first night because she can see that no one else has blue eyes, so the guru must have been talking about her. Or an accompanied blue-eyed person can leave on a later night, after noticing that other blue-eyed people have behaved in a way that indicates that they have noticed that her eyes are blue too.
| |
| − | | |
| − | The problem is symmetrical for all blue-eyed people, so this means they will either all leave at once or all stay forever.
| |
| − | | |
| − | ===Theorem===
| |
| − | If there are N blue-eyed people, they will all leave on the Nth night.
| |
| − | | |
| − | ===Dual Logic===
| |
| − | Blue-eyed people leave on the 100th night.
| |
| − | | |
| − | If you (the person) have blue eyes then you can see 99 blue-eyed and 100 brown eyed people (and one green eyed, the Guru).
| |
| − | If 99 blue-eyed people don't leave on the 99th night, then you know you have blue eyes and you will leave on the 100th night knowing so.
| |
| − | | |
| − | ===Intuitive Proof===
| |
| − | Imagine a simpler version of the puzzle in which, on day #1 the guru announces that she can see at least 1 blue-eyed person, on day #2 she announces that she can see at least 2 blue-eyed people, and so on until the blue-eyed people leave.
| |
| − | | |
| − | So long as the guru's count of blue-eyed people doesn't exceed your own, then her announcement won't prompt you to leave. But as soon as the guru announces having seen more blue-eyed people than you've seen yourself, then you'll know your eyes must be blue too, so you'll leave that night, as will all the other blue-eyed people. Hence our theorem obviously holds in this simpler puzzle.
| |
| − | | |
| − | But this "simpler" puzzle is actually perfectly equivalent to the original puzzle. If there were just one blue-eyed person, she would leave on the first night, so if nobody leaves on the first night, then everybody will know there are at least two blue-eyed people, so there's no need for the guru to announce this on the second day. Similarly, if there were just two blue-eyed people, they'd then recognize this and leave on the second night, so if nobody leaves on the second night, then there must be a third blue-eyed person inspiring them to stay, so there's no need for the guru to announce this on the third day. And so on... The guru's announcements on the later days just tell people things they already could have figured out on their own.
| |
| − | | |
| − | It's obvious that our theorem holds for the "simpler" puzzle, and this "simpler" puzzle is perfectly equivalent to the original puzzle, so our theorem must hold for the original puzzle too.
| |
| − | | |
| − | Another way of looking at it is to use selective attention. Although each blue-eyed person can see each other blue-eyed person on the island, she doesn't need to. The only thing she needs to know in order to determine whether to leave on night N is whether she can see an Nth person with blue eyes. On night 1, she only needs to see 1 other blue-eyed person to not leave; on night 2, she can see 2 other blue-eyed people, so she doesn't leave; and so on until night 100 when she can't see a 100th blue-eyed person, and then leaves.
| |
| − | | |
| − | ===Formal Proof===
| |
| − | To prove this more formally, we can use mathematical induction. To do that, we'll need to show that our theorem holds for the base case of N=1, and we'll need to show that, for any given X, *if* we assume that the theorem holds for any value of N less than X, then it will also hold for N=X. If we can show both these things, then we'll know the theorem is true for N=1 (the base case), for N=2 (using the inductive step once), for N=3 (using the inductive step a second time) and so on, for whatever value of N you want.
| |
| − | | |
| − | Base case: N=1. If there is just one blue-eyed person, she will see that no one else has blue eyes, know that the guru was talking about her, and leave on the first night.
| |
| − | | |
| − | Inductive step: Here we assume that the theorem holds for any value of N less than some arbitrary X (integer greater than 1), and we need to show that it would then hold for N=X too. If there are X blue-eyed people, then each will reason as follows: "I can see that X-1 other people have blue eyes, so either just those X-1 people have blue eyes, or X people do (them plus me). If there are just X-1 people with blue eyes, then by our assumption, they'll all leave on night number X-1. If they don't all leave on night number X-1, then that means that there is an Xth blue-eyed person in addition to the X-1 that I can see, namely me. So, if they all stay past night number X-1, then I'll know I have blue eyes, so I'll leave on night number X. Of course, they'll also be in exactly the same circumstance as me, so they'll leave on night number X too."
| |
| − | | |
| − | This suffices to prove our theorem. The base case tells us the theorem holds for N=1. That together with the inductive step tells us that it therefore holds for N=2, and that together with the inductive step again tells us that it holds for N=3, and so on... In particular, it holds for the case the original puzzle asked about, N=100, so we get the conclusion that the 100 blue-eyed people will leave on the 100th night.
| |
| − | | |
| − | ==Randall's thought-provoking questions==
| |
| − | After giving his solution, Randall posed three questions for further thought about the puzzle. (We'll answer them in a different order than he asked.)
| |
| − | | |
| − | '' '''Question 2.''' Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?''
| |
| − | | |
| − | Blue-eyed people can't see their own faces, so blue-eyed people can see one less blue-eyed face than non-blue-eyed people can. Even though I can see that there are at least 99 blue-eyed people, I don't know that they can see that, so I need to imagine people who see only 98, who would base their actions in part by imagining people who can see only 97 who would base their actions in part by imagining people who can see only 96, and so on... All the levels are relevant. (It's like [https://www.youtube.com/watch?v=U_eZmEiyTo0 the Princess Bride scene] where Vizzini is trying to think about what Wesley would choose in part based upon Wesley thinking about what Vizzini would choose in part based upon... "So clearly I cannot choose the one in front of me!") Each layer of thinking about what someone else might be thinking about can decrement by 1 the number of blue-eyed people visible to the lattermost imagined person, so it turns out that even the base case with N=1 blue-eyed person is relevant. As the days go by, some of the more far-fetched "he might be thinking that I might be thinking that he might be thinking that I might be thinking that..." hypotheses get ruled out. But it's only after night N-1 that the blue-eyed people rule out all the possibilities in which they have brown eyes, whereas the brown-eyed people only learn on night number N that they don't have blue eyes.
| |
| − | | |
| − | It might help to think of all the different situations people might be in. (Remember brown-eyed people always are situated where they can see one more blue-eyed face than blue-eyed people can.)
| |
| − | | |
| − | '''Situation 0.''' If I see 0 blue-eyed people, I can leave right after the announcement on night 1.
| |
| − | '''Situation 1.''' If I see 1 blue-eyed person, then she might be in situation 0 and about to leave on night 1; or else she might be in situation 1 just like me, in which case we'll both leave together on night 2.
| |
| − | '''Situation 2.''' If I see 2 blue-eyed people, they might each be in situation 1 watching to see whether anyone in situation 0 leaves the first night (I know nobody will leave that night, but they wouldn't know this), in which case they would leave together on night 2; or else they might be in situation 2 just like me, in which case we'll all leave together on night 3.
| |
| − | | |
| − | :
| |
| − | :
| |
| − | :
| |
| − | '''Situation N.''' If I see N blue-eyed people, they might be in situation N-1 watching to see whether any people in situation N-2 leave on night N-1 (I know nobody will leave that night, but they wouldn't know this), in which case they would leave together on night N; or else they might be in situation N just like me, in which case we'll all leave together on night N+1.
| |
| − | :
| |
| − | :
| |
| − | | |
| − | Even though I start out in situation 99, I need to worry that the blue-eyed people might be in situation 98, so I need to wait long enough for people in situation 98 to figure out what's going on, and then see whether they act like they are indeed in situation 98. But if they're in situation 98, then they're worrying about whether all the blue-eyed people might be in situation 97, so they're going to need to wait long enough for people in situation 97 to figure out what's going on. Of course, that requires waiting long enough for people in situation 96 to figure out what's going on, and so on, down all the way to situation 0. All the levels are relevant, and it takes a separate day to eliminate each level, which is why the entire process takes N days.
| |
| − | | |
| − | '' '''Question 3.''' Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?
| |
| − | ''
| |
| − | | |
| − | Consider an analogy. I've heard that miners used to take canaries down into mines because canaries pass out more quickly in poor air than miners do. Suppose you know the canary will do fine for 98 or so seconds, and then pass out if the air is bad. As you watch the canary for those 98 seconds, there's a sense in which you're just verifying something you already know (it'll do fine), but it seems more accurate to say that your best detector for the quality of the air takes 98 seconds to give you a reading, and you're waiting 98 seconds to see what that reading is.
| |
| − | | |
| − | When the blue-eyed people wait 98 or so days to leave, that's because their best available detector of their own eye-color takes 98 or so days to give a reading. (This detector involves watching what the other blue-eyed people do, and of course they themselves are waiting on a detector that takes 97 or so days to yield its result...) There's a sense in which they're "simply verifying something that they already know", but it seems more accurate to say that they're waiting for their best available detector of their own eye-color to deliver its reading.
| |
| − | | |
| − | '' '''Question 1.''' What is the quantified piece of information that the Guru provides that each person did not already have?''
| |
| − | | |
| − | Before the Guru speaks, the hypothetical chain of A imagining B imaging C imagining D... imagining Z seeing N blue-eyed people cannot terminate uniquely. Z seeing no blue-eyed people can consider whether they are blue-eyed. This means it is not {{w|Common knowledge (logic)|common knowledge}} that there are blue eyes. Once the guru makes their pronouncement it is common knowledge, and every chain of reasoning must terminate at 1 blue-eyed person and Z above would have to conclude that they had blue eyes. From then on, every midnight the common knowledge that there are N blue-eyed people increments by 1 as everyone sees nobody leaving on the ferry.
| |
| − | | |
| − | Stated another way, there's only one stable set of beliefs for the blue-eyed people that would allow them to have so many exist on the island indefinitely. That is if each blue-eyed person believed not only that they have brown eyes, but also that every other blue-eyed person believed, incorrectly, that they had brown eyes. Logic reduces this to "all blue-eyes believe that all blues-eyes have brown eyes". The Guru eliminates that particular possibility.
| |
| − | | |
| − | Another straightforward way to understand why the Guru's information is important is thus. Each blue-eyed person knows two sets of information: what the actual situation is on the island (both now and in the past), and what would happen in a hypothetical situation. Each blue-eyed person then needs only to compare the actual situation to a known hypothetical one, and if it matches up, then they take the corresponding action. Consider this: If there were only one blue-eyed person, and the guru never made the announcement, she would not leave on day 1 because she would not know that N is greater than or equal to 1. Now let's add a second blue-eyed person. Blue-eyes 2 would not be able to inductively determine whether or not to leave on night 2, because blue-eyes 2's knowledge of whether or not to leave on night 2 is dependent on what blue-eyes 1 does on night 1 if and only if blue-eyes 1 knows what to do on night 1. If blue-eyes 1 doesn't know that N is greater than or equal to 1, then blue-eyes 1 doesn't know what to do on night 1. So, her lack of leaving gives blue-eyes 2 no new information, since it was an uninformed action and blue-eyes 2's inductive reasoning was dependent on blue-eyes 1 knowing what to do, and so the inductive process never takes off for the hypothetical situation. This means a hypothetical situation for N people cannot be induced. As such, blue-eyes 100 does not have certain knowledge of the hypothetical situation that would occur on nights 99 and 100, and so even though she knows N = either 99 or 100, she can't take action on either of those nights, because she has no certain hypothetical situation to compare reality to, and as such cannot have certainty about the actions she should take.
| |
| − | | |
| − | ==Trivia==
| |
| − | The web page which contains the puzzle has no {{w|CSS|style sheet}}. The font size of the heading and subheading is increased with deprecated HTML tags, rather than with heading tags. The way the page is displayed therefore depends on the browser's settings. Despite this fact, due to a similarity of default settings between computers, most computers will display the page with a white background, black text, and the {{w|Times New Roman}} font. However, it has two line breaks after every paragraph instead of HTML paragraph breaks, meaning that paragraph spacing will not vary between browsers, relative to the font size.
| |
| − | | |
| − | {{comic discussion}}
| |
| − | | |
| − | [[Category:My Hobby]]
| |
| − | [[Category:Multiple Cueballs]]
| |
| − | [[Category:No title text]]
| |
| − | [[Category:Comics with lowercase text]] | |
