|The Hardest Logic Puzzle in the World|
xkcd's 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; whether or not 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).
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?
Randall's solution is at 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.
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.
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 or not 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 and so on until night 100 when she can't see a 100th blue-eyed person, and then leaves.
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 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 whole 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 or not they are blue eyed. This means it is not 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 simple 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 2nd 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.
- The web page which contains the puzzle has no style sheet. The font size of the heading and subheading is increased with deprecated HTML tags, rather than the 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 by default display the page similarly to the way it is displayed in this page's screenshot, with a white background, black text and the Times New Roman font or a similar one. 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.
add a comment! ⋅ add a topic (use sparingly)! ⋅ refresh comments!
Is it really incomplete on the grounds that Joel hasn't be identified? Explanations of comics 57-59 leave no more explanation of "Scott" than that he appears to be Randall's friend. The fact that we don't have a last name for him doesn't make either Scott or those comic explanations incomplete. Similarly, not have a full identifier for "Joel" in this one doesn't, in my opinion, warrant an incomplete tag. I'm removing the tag. If anyone object, revert it. Djbrasier (talk) 19:22, 22 May 2015 (UTC)
The proof for this puzzle is incomplete, if not wrong. The theorem is too weak, it should be: "Theorem: N blue eyed people with Nth order knowledge of all N people being logicians, N people having blue eyes, and any blue eyed person will leave as soon as possible after deducing they have blue eyes, will be able to leave on the Nth day." This may seem pedantic, but it really gets to the heart of the problem, which is trying to illustrate the use of orders of knowledge. In the theorem as stated, just N blue eyed people will leave on the Nth day, the proof for the inductive steps does not hold. You need to further assume that the person is able to deduce the hypothesis (which should be proven). In other words, you say X-1 people would leave on the (X-1)th day by hypothesis, so the Xth person knows he can leave on the Xth day. But you did not prove that the Xth person can actually deduce this, namely that he has all the information necessary to do so. In the correctly stated hypothesis, you then need to show that N + 1 people with (N+1)th order knowledge of all those things can deduce that the N people would leave if it was just them, and further that N+1 people have (N+1)th order knowledge of all these things. This is very important, and holds true (Since N+1th order knowledge is equivalent to knowing the N people have the Nth order knowledge necessary to fulfill the hypothesis, and by symmetry if the N logicians can figure it out the (N+1)th can too. Also, they have (N+1)th order knowledge of people leaving as soon as they can and everyone being a logician since in the proper statement of the puzzle it should be noted this is common knowledge, and the guru makes the knowledge of someone having blue eyes common knowledge.). Then you have a full proof, since you have now included that they can actually deduce the inductive step. Again, this may seem pedantic, but is really necessary both to be correct and as it illustrates the key of the puzzle, namely the guru gives 100th order knowledge of someone having blue eyes (this is the main problem people have, realizing the concrete piece of information the guru gives). Jlangy (talk) 00:29, 9 July 2015
What I don't follow here is that there's no clarification that the Guru is talking about someone different each time. Just because she says "I see someone with blue eyes" N times doesn't mean that there are N people with blue eyes; she could be talking about the same person every time, or each of two people half the time, etc. Can anyone clarify this? Thanks - 188.8.131.52 13:20, 28 October 2015 (UTC)
(EDIT: Observe the process of comprehension in action...or don't? I've been thinking about my own brain, with itself, long enough for one day, I'm tired.) So, maybe I am indeed just "dumb", as the wiki insists. Clearly, I do not have a perfect understanding of formal logic. But frankly, my read of this puzzle is that "formal logic" just enables you to jump to ridiculous conclusions. Let's theorize a simpler version of this puzzle. There are now only two people besides the Guru on the island, both with blue eyes. We'll call them Bill and Ted (totally bogus, I know). No matter how logical Bill and Ted might be, when Bill hears the Guru say "I see a person with blue eyes" to himself and Ted, and Bill has seen Ted's blue eyes himself, why would Bill assume anything about his own eye color? It would seem to Bill that Guru was just talking about Ted's eyes, and Ted would believe the reverse. Even knowing* that Ted would leave that night if Ted deduced he had blue eyes too, I still don't see why Bill would jump to the conclusion that the Guru was talking about him - he remains in the dark, as does Ted, and neither of them can be any more certain of anything than they previously were. Adding 98 more blue-eyed people, let alone doubling the island's population with irrelevant brown-eyers, hardly reduces the confusion.
- This was the point at which I began to think I had understood it, but then I became unsure again. Like I said in the "edit", my brain is tired.
--So, that settles it, I do not understand how the puzzle can be true, and I'm not convinced that it actually is. Knowing Randall is, in general, smarter than me...I still do not have the ability to completely accept that he's always right, or that I'm always wrong to ignorantly question his rightness. I have long maintained that certain well-respected "systems of knowledge", of which formal logic is a textbook example, have been respected too well for too long for not-good-enough reasons. To me, they seem to be founded on an assumption which is itself founded on nothing. I'm not trying to insult Randall or anyone else, I'm just utterly failing to comprehend. I will appreciate if anyone else attempts to educate me on the subject, but I may prove an intractable student, since I am unable to extend much faith or trust (or even, on a day where my mood is worse than today, the moderate degree of politeness as I've already managed) to a teacher. 184.108.40.206 19:18, 30 October 2015 (UTC)
In your simplified version of the puzzle, Bill sees Ted has blue eyes.
Here's Bill reasoning:
- Either my eyes are blue or not.
- If my eyes are not blue, then Ted knows that his eyes are blue, because the Guru said at least one of us has blue eyes, and he'll leave the island tonight.
- Let's wait. If Ted doesn't leave tonight, that means he doesn't know his eyes are blue, and therefore my hypothesis is false.
When Bill sees Ted doesn't leave that night, he can deduce that he has blue eyes.
Ted can do the same reasoning.
After that first night, both will know they both have blue eyes.
--220.127.116.11 14:09, 14 December 2015 (UTC)
The solution relies on the fact that "at least 1 blue" is new information which triggers a cascade.
Wouldn't the entire population of the island be able to conclude that everyone else on the island knows there is at least 1 blue eyed individual already?
For example, every person on the island will see at least 99 blues and 99 browns. From this, they can assume that everyone else on the island can see at least 98 blues and 98 browns. Of course, the actual numbers will differ, but 98 is the lower limit for all perspectives.
A blue will see 99 blues and 100 browns, so he will assume that all other blues can see at least 98 and all browns can see at least 99 blues. Similar logic for a brown or any observer.
Flewk (talk) 09:26, 26 December 2015 (UTC)
The solution here is different to Randall's solution, and I think is actually incorrect for two reasons that add confusion and prevented me from understanding the solution until I'd thought about Randall's solution and realised these are actually different.
- It seems to falsely presume that the Guru is speaking to them each day, when this is explicitly not the case in the puzzle.
- I also believe it is incorrect to state that the brown-eyed people can be disregarded. The solution is actually dependent on a *combination* of hypothesis testing and on theory of mind; not just one or the other. It matters that everyone is also thinking about what the brown-eyed people around them must be thinking, otherwise you can't explain why mistakes will not happen with brown-eyed people getting on the ferry when they're not supposed to, and screwing up everybody else's logic.
- If you're on the island and you have blue eyes, there are two hypotheses: either there are 99 people with blue eyes or 100. If there are 99, then everyone one of those 99 people is thinking "either there are 98 people with blue eyes, or there are 99" (and therefore you do not have blue eyes). Blue-eyed people also know that if there are 99 of them, then the brown-eyed people are thinking, "Either there are 99 blue eyed people, or 100." If there are 100, then the brown eyed people are thinking, "Either there are 100, or 101". To summarise, blue eyed people are deciding between 99 or 100, and presuming that other blue eyed people are either suspecting there could be 98/99, or 99/100, while presuming that brown-eyed people are either suspecting there are 100/101, or 99/100. - If there are 99, then blue-eyes are thinking 98/99, and brown-eyes are thinking 99/100. Blue eyes will plan to leave if the 98th day passes and nobody has left, brown-eyes will plan to leave if the 99th day passes and nobody has left. - If there are 100, then blue-eyes are thinking 99/100, and brown-eyes are thinking 100/101. Blue eyes will plan to leave if the 99th day passes and nobody has left, brown-eyes will plan to leave if the 100th day passes and nobody has left. - So you know that if you have brown eyes, you'll watch all the blue-eyes leave on the 99th day. And you know that if you have blue eyes, you'll watch all the brown-eyed people hold back in case their day is the 101st. If you're allowed to leave, there will be no situation where brown-eyed people mistakenly leave on the 100th day, thus confusing things. If you're not allowed to leave, there'll be no reason for you to mistakenly make an attempt to leave on the 99th day. - Thinking about this fact - what the brown-eyed people are thinking - also reveals why the Guru's comment matters, and adds information, even though it should seem to most people as if no information is being added (because they can all already see that blue-eyed people exist). I think this is a key part of why the problem is so tricky. 18.104.22.168 07:42, 10 March 2016 (UTC)
The new information the guru gives is nothing more than a common marker (the day of the announcement) to use as a starting point for counting days. Before the announcement, being unable to communicate with each other, they were unable to coordinate a means of figuring out their own eye color. 22.214.171.124 21:52, 22 September 2016 (UTC)
That's wrong. In that case the browned eyed people would do the same, but they can't.
What I'd like to know: If there were 100 blue-eyes, 200 brown-eyes, 300 grey-eyes and 400 red-eyes, and the Guru says "I don't see anyone with a unique eye color", would that permit everyone to leave (except the Guru herself) using the same logic? Meaning the blue-eyes leave again on day 100, the brown-eyes on 200, the grey-eyes on 300, and the red-eyes on 301.
I think it would actually be days 99, 199, 299, and 300, because the 'what if there were only two blue-eyes' case would be solved on day 1 - i.e. both would see only one blue-eye and deduce that they are also a blue-eye, and both would leave - so everything gets moved up by one day.126.96.36.199 13:52, 4 January 2018 (UTC)
This was bugging me today - specifically the guru doesn't seem to actually give any information, because with at least 3 blue-eyed people, everyone on the island knows that the guru sees people with blue eyes, and also everyone knows that everyone knows the guru sees people with blue eyes. So for a while I thought the brown-eyed people must have as much information as the blue-eyed people, and either they both could leave or neither could leave.
- Consider this, if there were only 2 people with blue eyes, everyone would know that she sees someone with blue eyes beforehand, but everyone wouldn't know that everyone knows that, as the 2 people with blue eyes would not know if the other person with blue eyes can see anyone with blue eyes, so the 2 people with blue eyes would deduce they have blue eyes when the other person doesn't leave the first day, as themselves having blue eyes would be the only explanation for that person not leaving the first day. The dispute here is if you can extend that chain of reasoning past there being only two people. After all, with 3 people, as you said, everyone knows that everyone knows that she can see someone with blue eyes already, but when you consider the people who have blue eyes, everyone doesn't know that everyone knows that everyone knows that, even though each individual would personally know that everyone knows that everyone knows that, as the people with blue eyes know that if they don't have blue eyes, then the 2 people with blue eyes they see would only see one person with blue eyes and know that the Guru can see someone with blue eyes, but wouldn't know that the other person with blue eyes knows that. But would everyone follow such a chain of logic and make assumptions based one people not leaving based on days with significantly lower numbers passing that they personally know that no one would expect a possibility of anyone leaving on? This whole question is hinged on people following perfect logic that is based on other people following the same perfect logic that would predict this. If perfect logic necessitated people leaving in such a manner, then everyone would know the rest of the people would follow this rule and the solution would hold, but if it didn't, then it would be just as consistent if no one left. This is basically circular reasoning about using logic to predict the actions of people who are acting according to the same reasoning as yourself. Both this answer being correct and it wouldn't wouldn't violate pure logic based on a system of reasonable seeming logical principles and the terms of the question.--188.8.131.52 04:35, 12 October 2022 (UTC)
After a bunch of reading and testing possibilities I think I've actually figured it out now and why only blue-eyed people leave, but I haven't seen an actual good explanation for it yet, so here's my explanation: The information the guru gives is that, NO MATTER HOW MANY BLUE-EYED PEOPLE THERE ARE, they can figure out they have blue eyes. It is important that it is possible for blue-eyed people to be able to solve it for EVERY number, even if everyone knows there is more people than that number (basically because, everyone doesn't know that everyone knows there is more than that number and there's a gap in their logic without knowing that). If there is any number for which blue-eyed people cannot figure it out, then any solution (namely, what I thought before testing possibilities) would require that there is a number N of blue-eyed people that cannot leave, but a number N+1 of blue-eyed people that can leave. This is self-contradicting though. If N blue-eyed people can't figure it out, than N+1 people (regardless of eye color) can't get meaningful information from the action of those N blue-eyed people. And since they can't get meaningful information from N people's actions, N+1 people can't tell if there are N people and that individual is not blue eyed, or N+1 people and they are blue-eyed. It would be logically incorrect for them to assume an eye color at that point, which means they don't know if they can leave, and then N+2 people are similarly unable to get meaningful information from N+1 people's actions, and so on. Because a single blue-eyed person cannot figure it out, more blue-eyed people (regardless of number) cannot make any assumptions without additional information. Then the guru effectively states a single blue-eyed person could leave immediately (which means 2 could leave the next night confidently, and thus 3 the next, and so on in an UNBROKEN chain). Kejardon - 184.108.40.206 11:15, 9 January 2020 (UTC) (I doublechecked and edited/corrected my post kind of at the same time, so your reply doesn't make sense anymore, sorry Lupo. Feel free to delete these two sentences if you change/delete your reply)
- You bring up 2 points. First about the common marker. This is true, but it contains more information than "start counting from today," because every blueeyed person has 2 scenarios: With 99 blue eyed people and with 100. The numbers are not important, and it would also be needed with 1,2,3,etc. blue eyed people. The point about the brown eyed people: The brown eyed people have no way to conclude (remember, they are "perfect logicans" and their task is to figure out, not to make an estimated guess) that their own eyes are in fact brown, and not red, or green just like the Gurus. If the guru just said: "Start counting", then noone woul leave at any given night. --Lupo (talk) 11:05, 9 January 2020 (UTC)
I figured this out in less than a minute... there were so many warnings about the solution being convoluted that I thought I couldn't possibly have it right. It's not really that confusing and I've seen waaaaaaay harder logic problems.
This image is listed under "My Hobby" for some reason, despite not even being a comic, let alone a "My Hobby" comic. 220.127.116.11 00:58, 9 September 2019 (UTC)How sign edit
It's been years and I stumbled back across this post, and I think I finally understand what has been bothering me.
The examples always go up to 3 blue-eyed people, and then we just assume that it follows a the pattern, but a pattern has to be confirmed to all states to be a proof. This is why Fermat's last theorem remained unproven for years even though we had solved the N =1,2,3 cases. To expand on the biggest criticism, what new information does the guru give?
-Someone learns something : Only true from the perspective of someone who sees no-one with blue eyes.
-Someone could learn something : Only true from the perspective of someone who sees exactly one person with blue eyes.
-No-One can learn anything : True from the perspective from someone who sees multiple people with blue eyes.
This is where the problem occurs, because this only resolves with 3 blue-eyed people otherwise we don't learn anything, but how we acknowledge that we don't learn anything matters.
-Everybody must know that no-one can learn : True from the perspective of people who see people who must see multiple people with blue eyes.
-Everyone must be aware of the previous fact : I guess it does go on...
In the end, it's all about the meta-data.
I know, you know, they just don't have any proof...
Crow --18.104.22.168 00:12, 30 September 2021 (UTC)
Apostle's Solution: The first person to look into the water and see their own reflection. For a logic puzzle, people seem to forget about the situations actual logic. 22.214.171.124 (talk) (please sign your comments with ~~~~)
- What part of: "There are no mirrors or reflecting surfaces" do you not understand? --Lupo (talk) 09:54, 18 May 2020 (UTC)
- What can you even do to an island to remove all reflecting surfaces? Absolutely everybody would leave the the night after the weather is good enough to see their reflection in the sea.
- Then the weather is never clear enough to see their reflections. It's equally valid to question why the ferryman would only free people who knew their eye color, or whether some people would want to stay on the island instead of leaving...and far more valid to point out that perfectly logical beings like the problem describes don't exist. If you're not willing to suspend your disbelief enough to accept the premise of a logic puzzle, that's fine, but it's no more ridiculous than suspending your disbelief enough to accept that hobbits and wizards exist in Middle Earth. GreatWyrmGold (talk) 03:29, 17 July 2021 (UTC)
If there are N islanders with blue eyes, every person sees at least N-1 blue eyed persons. Person A with blue eyes seeing N-1 blue eyed persons has to consider the possibility that there might be a person B who only sees N-2 blue eyed people and acts accordingly. However, everyone in that scenario will agree that it is absolutely impossible for anyone to see N-3 or less blue eyed people and that case cannot possibly be considered by anyone. Therefore the induction step is invalid and nobody will ever leave the island for N>3. Boopers (talk) 18:07, 15 October 2021 (UTC)
If a person B only sees N-2 blue eyed people, then surely they have to consider the possibility of a person C who only sees N-3 people. Sure, person B doesn't actually exist in this scenario, but you'd have to consider that person A would have to consider what a hypothetical person B would have to consider. It's turtles all the way down. 126.96.36.199 00:17, 19 October 2021 (UTC)
No. It doesn't turtle down and nobody inside the scenario is free to consider any hypothetical persons. Instead, everything that one of the persons may consider about another person on the island has to be consistent with his observations of the persons who are actually there. And that breaks down at person C in my example. Yes, person B from the example does not exist, but the important thing that was being missed is that person C can be proven by everyone involved to be impossible which is not the case for B. Lets just consider the scenario with 4 blue eyed persons, the smallest number where the argument breaks down. Now lets choose two completely arbitrary persons A and B (And I really mean completely arbitrary - doesn't even require for A and B to be different persons). It can be shown that A knows that B sees at least 2 blue eyed persons. Now since A and B were chosen arbitrarily, that means that every person on the island knows that every person on the island sees at least 2 blue eyed persons. This observation is of great importance, because it contradicts an invalid assumption implicitly made in the induction step. The induction step relies on the incorrect assumption that at the end of day N knowledge is gained that the number of blue eyed persons is larger than N. That assumption works out well for 2 or 3 blue eyed persons, but completely breaks down at 4 blue eyed persons right at day 1, since we have shown that everyone is already aware that there is more than 1 blue eyed person before the end of day 1. This invalid assumption is extremely well hidden in the presented proofs. In the "Intuitive Proof" section, it is hidden inside the wrong assertion that the simplified problem supposedly is equivalent to the original one when it is absolutely not. And in the "Formal Proof" section, the islanders are just being assigned a reasoning without there being a proof to why they would reason this way. Of course following this flawed reasoning will lead to the desired result, but if they were the perfectly logical thinking people like the problem described, they wouldn't just miss the fact that there are cases where no knowledge can be gained on day 1 and therefore on any of the following days, and they would incorporate that into their reasoning. Boopers (talk) 18:31, 13 November 2021 (UTC)
Boopers, let me see if I can convince you it works for n=4 by making it a story. There are 4 blue-eyed people on the island; Arnold, Boopers (you), Carl, and Denise. You don't know your eye color, but have always thought of yourself as a brown-eyed person, and if you had to guess, you would guess you have brown eyes; after all, almost everyone does. When you hear the guru speak, you think that since there are only 3 blue-eyed people, A, C, and D. They are dear friends of yours, and you are very sad that after 3 days, you will never see them again. So you have a busy 3 days coming up, since there are things you've put off doing that you must do quickly, before A, C, and D leave your life forever.
A, while a good friend, has a habit of borrowing things and not returning them, and you don't want your stuff going with A on the boat. So you spend day 1 getting A to return your lawnmower, snowblower, and the dozen books he has borrowed over the years and not returned. You get all your stuff back. A good day 1.
While C is a friend, you haven't always treated him well. So day 2 you spend with C, doing whatever you can to ensure he has a good day on his next-to-last day on the island, and apologize to him for the ways you have wronged him in the past. He accepts your apology, and you are pleased that you haven't left things unresolved with your friend who will leave the island forever in 2 days. A great day 2.
On day 3; you confess to Denise (who is married to Arnold) your undying love for her. You've never told her this, out of respect for her marriage, but you've always suspected that your feelings were returned. Now that you will never see Denise or her husband again after noon tomorrow, so there will be no repercussions. To your delight, you discover that your feelings are indeed returned, and you and Denise spend what you think will be your last night together making love until the early morning hours. A perfect day 3. And since A and D are leaving on the boat the next day, and you, with your brown eyes, are staying on the island, probably forever, there will be no repercussions.
The next day, when you know A, C, and D will be leaving at noon, you rise early, and just before noon, you head to the pier, wanting to see Denise once more before she leaves on the noon boat. A, C, and D are of course there too. But to your great surprise, when the "all aboard" is sounding, A, C, and D do not move to get on the boat.
How can this be? What has happened? Again and again you go over the logic that says "if there are only 3 blue-eyed people on the island, they will all leave on day 3" and find it to be ironclad. And you know that your friends A, C, and D are perfect logicians, and can reason the same way you do, and you certainly know that they would never violate the rule that if you know your eye color, you must leave. And yet they remain! It seems impossible! How can this be? Unless...
Does a possibility occur to you to explain their inexplicably remaining on the island? You are certain of your logic that says "*If* there are exactly 3 blue-eyed people on the island, they will leave on day 3". So it must be that there are more than 3 blue-eyed people on the island. But you re-check the eye color of everyone else you can see, and they are all brown. Do you realize what must have happened?
Do you now know your eyes are blue? Do you get on the boat on day 4? Yp17 (talk) 19:14, 9 February 2022 (UTC)
I think that helps highlight why the induction as presented doesn't work. Indeed, I believe everyone leaves on the 4th night, and that the Guru provides no information at all -- only a random token which could not have existed before since communication was impossible.
Once the Guru speaks, the solution becomes possible for only the case of blue-eyed people, because only then can every person on the island be sure they are counting the same color. But the content of what she says is meaningless, as everyone already knows what she says. She could have simply said, "Blue eyes", and the same result could be accomplished (I in fact nominate that for a harder form of the puzzle).
Following this, the expected reasoning happens, but there is no reason for it to stop at the time presented. Waiting one day to see if there is one blue-eyed person that will leave is meaningless and completely irrational -- every person on the island can see enough blue-eyed people to know, with certainty, that every person knows there is more than one blue-eyed person. Therefore, waiting that first night is wasted, since the outcome is known with absolute certainty. Waiting must logically begin only on the first day where the outcome is not certain.
To find that day, the relevant metric is the lowest number of blue-eyed people that can be known to exist to every person on the island. That number is 97 -- consider a person A, blue-eyed, calculating the knowledge of another person B, also blue-eyed. (If either are brown-eyed they can mutually estimate more blue-eyed people, so this is the relevant case.) Since A is uncertain of their eye color, they must for the worst case assume it to be brown; therefore, they estimate 99 blue-eyed people, of which B is one, whom therefore sees 98 blue-eyed people in this scenario. B cannot be sure of their own eye color, so they will see 98 blue-eyed people, and when modelling a further person (C, say) following the same logic could conclude they themselves are not blue-eyed and therefore C will only be able to guarantee 97 blue-eyed people (A's model is, A is brown, and B's model is B is brown, so C's model excludes A and B and is uncertain about C.)
Importantly, this does not induct! There is no rational way in the given 100/100/1 distribution for someone to not be certain of 97 people, even though there is a temptation to chase a clear recursive pattern. The reasoning behind it does not hold -- A does not need to worry about B->C->D's model, because no one has that much uncertainty -- it is incorrect to model D, because you can observe everyone's computation at most two steps removed from directly. When establishing a pairwise estimate of the distribution of eye colors, there are only two points of uncertainty -- the observer, and the person being modelled. A knows, with certainty, that there is no situation where someone will model the behavior of another and find a lower bound of less than 97, because even if A is brown-eyed, they know every other person on the island will see at least 98 blue-eyed people, regardless of all other factors.
The salient modelling question is, therefore, only how much "worse" than 98 it can be. One may be tempted to assign another -1 to the new observer who then must assign another -1 to their target, but that is illusory -- in our previous example, the uncertainty with which C considers D is the same uncertainty that A already accounted for, i.e. the uncertainty of the observer. No matter who is modelling who, there is only one observer, one modeled-observer, and one modeled-observer-target. Further extrapolation isn't necessary. Therefore, since A knows they are looking at someone with blue eyes, that person B can conclude that of the 98 people they assuredly see, they must subtract only one more for the worst case -- the estimate of C, who knows not their own eye color. B doesn't need to account for their own eye color, because A already did that in their own uncertainty, and they know that B is blue-eyed -- no matter who they select of the 99 blue eyed people they see, that person will see (at least) 98 blue eyed people, and gives no greater uncertainty than the case where A is brown eyed and they are considering someone else blue-eyed, lowering the bound to 97. It in no circumstances is estimated lower than this.
That means that every knows, with certainty, there are 97 blue eyed people at a minimum, and therefore the first interesting day is the 97th on the "original timeline" -- but that clearly isn't the case, because everyone can already count more than 97 blue-eyed people. Indeed, everyone can count 99 blue-eyed people; it is only in question for each observer whether they are a 100th blue-eyed person, and the chain of reasoning exists to expose that. The worst-case 97 holds only if his own eyes are brown, and another blue-eyed person considers a third blue-eyed person. Since there is no way to communicate, there is no way to improve upon that uncertainty, so that must be the point of first decision:
The first interesting night requiring a decision is establishing whether 97 people have blue eyes, or more than 97 people. This could be known with ceratinty by the original reasoning, which persists until the 97th night. However, everyone knows, with certainty (due to the above) that every night prior to the 97th night will result in no action; therefore the only logical course of action is to begin with the first point of new information. They "start" with the 97th day, and leave on the 100th, for a total of 4 days. Dokushin (talk) 07:55, 26 February 2023 (UTC)
Unstated assumption (about motives)
While trying to solve this, I started questioning my assumptions about the motives of the islanders. It turns out my assumptions were correct, but I think they deserve to be explicitly stated:
- Everyone wants to leave the island ASAP.
- An islander only "figures out" their eye color through logical deduction (no guessing or playing the odds)
- The Guru's statement is meant to help others leave the island. (but as stated above, it may not be the optimal means of helping others leave -- "nobody has a unique eye color")
- Regarding the 1st point: Yes, that needs to be stated.--Lupo (talk) 11:37, 9 January 2020 (UTC)
- Regarding the 2nd point: It should be mentioned, but could be implied by the words "figure out" and by the fact that everyone is a "Perfect logican". --Lupo (talk) 11:37, 9 January 2020 (UTC)
- Regarding the 3rd point: If it was not meant to help people leave, it would still do the same job. Also the statement from the Guru "nobody has a unique eye color" would be wrong and misleading! In that case everyone would wrongly assume: "I must have green eyes, as otherwise the Guru would have an unique eye color." - The alternative statement "I see noone with a unique eye color" would work. --Lupo (talk) 11:37, 9 January 2020 (UTC)
Storming lighteyes (not sorry) SilverMagpie (talk) 17:50, 10 January 2020 (UTC)
Guru gives synchronizing signal to begin recursive cascade, without which it can’t start.
We might wonder why it is noted that the islanders have been on the island “all these endless years”, but the recursive cascade had never happened. The reason is that There must be a time zero, T0, from which the wait period is defined. Without that discrete starting point, there is no reference point to begin waiting to see who leaves. The Guru provides a starting event, visible (or audible) to all, where they can say “this is T0”, and our deductions can now proceed. So it synchronizes everyone to begin their waits.