Seventeen "Blue Eyes" Objections and Responses [SPOILER]

[Lenoxus]

Ah, Ol' Blue Eyes. No, not the singer, the logic puzzle, which Mr. Monroe has dubbed the hardest in the world, and with some good reason.

If you haven't seen it yet, we recommend trying to solve it before reading further (as with any logic puzzle).

Here's the puzzle as worded by Randall, here's its solution, and here is the main thread discussing its solution. This post by Xias on that thread inspired me to create this particular thread, intended to serve as a kind of FAQ for the puzzle.

Following are some common objections to the solution, each one in bold. Underneath the bolded objection is an elaboration in italics, meant to provide support for the objection's argument and add more detail as to what someone making this objection might be trying to say. Both the bold and italics part are therefore being stated by the same hypothetical person, not different ones. In reality, I myself wrote the whole thing — there are no actual quotes of anyone else intended, just paraphrases of common ideas.

After each objection and elaboration comes my response. Each response is in a spoiler, more to avoid a wall of text than to hide any actual "spoliers"; I presume you won't read this until having learned the problem and solution (by one means or another) beforehand.

Within these responses I often use italics for emphasis and bolding for a "stronger" emphasis. Sometimes, italics are used to help distinguish some parts of a sentence from others, which might be helpful in understanding things like "A thinks that B thinks that C thinks…". (This style of mine has nothing to do with the bolding of the original objections and italicizing of their elaborations.)

There's enough text in this thing as a whole that I've split it into two parts. Part 1 deals with seven objections, Part 2 with the remaining ten. You can read the responses in any order you like, but since I wrote them just the way you see here (EDIT: Except for edits, of course), they'll probably make the most sense in that order.

In general, this is meant to address the problem whereby new posts and/or new threads raise the same points again and again, by people who were unwilling to read 25 pages of posts. So I read 'em for you, and I hope I managed to distill everything decently here. No more excuses, yes? (Until, of course, this thread manages to sink out of view. Even then it can still be linked to, of course.)

Feel free to post on this thread if you wish to add another common objection which you don't see here, or if you think I can be clearer with some of my responses, etc. If you wish to argue against the actual content of one of my responses (and by extension, to defend an objection), you may do so, but don't expect others here to be very happy about it, or to be convinced.

Let's begin!

1. The Guru's statement, "I can see someone who has blue eyes", does not provide new information to the islanders.

Everyone already knew that. No one will ever leave.

Spoiler:

It certainly appears that way at first. Everyone already knew that someone had blue eyes.

Everyone already knew that everyone knew that someone had blue eyes.

But we cannot add an arbitrary number of "everyone knew" to this statement, and that fact is crucial. Specifically, prior to the Guru's statement, the following statement is not true:

"Everyone knows that [repeat the last three words before this bracket such that they appear exactly one-hundred times] at least one person with blue eyes exists."

And yet the following statement is true:

"Everyone knows that [repeat the last three words before this bracket such that they appear exactly ninety-nine times] at least one person with blue eyes exists."

This really does make a big difference. It's rather like how "I will finish this novel the day after [repeat the last three words outside this bracket three hundred times] tomorrow" really does mean something different than "I will finish this novel the day after [repeat the last three words outside this bracket two hundred ninety-nine times] tomorrow". I'm referring to two different days. It just so happens that we have a nice shorthand to say this in the English language (I can simply say "in three hundred days" or "299 days"), and we don't have such a shorthand to refer to the "everyone knows that everyone knows" situation, at least not one that non-logicians use regularly.

Logicians do have a useful phrase for the type of infinitely-recursive situation the puzzle addresses: "Common knowledge".

If "X is true" is common knowledge for a group of people, that means that any statement of the following form is true: "Everyone in this group knows that [repeat the last six words before this bracket any number of times you want to] X is true." To understand this better, read the Wikipedia article on the subject.

Before the Guru's words, the statement "At least one person on this island has blue eyes" was not common knowledge. Then, after she said it, it was. The reason for this is not merely that she told everyone, but that she told everyone publicly, so that Sasha could see that James could see that Briana could hear the Guru's statement, and likewise for every possible ordering and permutation of the two hundred islanders.

2. I knew what common knowledge was (or, now I do). In this situation, "At least one person has blue eyes" was already common knowledge.

We can easily deduce that everyone already knows that everyone knows that everyone knows, ad infinitum.

Spoiler:

Not ad infinitum, which is crucial. To really get this, consider exactly the same problem with just one blue-eyed person. Then consider it with two, then three, and so forth. You might find yourself making Objection #5 or #6, both dealt with later on this page.

EDIT:

Here's a longer reply, which should also help you see what's wrong with the next (and very similar) objection, #3.

Imagine an island with just two people, blue-eyed Yolanda and brown-eyed Zoe. As usual, Yolanda doesn't know what color her eyes are. But suppose she performed the following syllogism:
1. I don't know what color my eyes are.
2. If I were Zoe, I would observe that I have blue eyes.
3. Therefore, my eyes are blue.
That's nonsense, obviously. Even though we know what color the real Zoe sees on Yolanda, we also know that Yolanda can't somehow deduce it.

However, if we nest Yolanda and Zoe within the nested thoughts of other people, then keeping track of the distinctions between what we know and what hypotetical islanders believe is much harder.

Consider the following statement, made about an island of exactly four blue-eyed people:

Wendy knows
that Xavier thinks
that Yogi thinks
that Zach believes
that at least one islander has blue eyes.

It sounds innocuous enough. Four is plenty of blue-eyed people, right? How could Zach possibly not know that someone has blue eyes? But there's a problem.

The problem arises when we try to answer the question: Which islander or islanders does this hypothetical Zach believe has blue eyes? First of all, it can't be Zach himself; like Yolanda, he can't "see" other people seeing that his own eyes are blue. So perhaps it is Wendy? Ah, but remember that it is Wendy herself who is supposing all this. For it to be Wendy, she would have to be doing the same magic that Yolanda did.

Well, how about Xavier? Doesn't Wendy know that Xavier is blue-eyed? Wouldn't Wendy be able to see that Yogi can see that Zach can see Xavier? Yes, that's all correct. The problem is that in the original sentence, Xavier was another one of the people doing the "thinking". So in order for it to be true that "Wendy knows that Xavier thinks that Yogi thinks that Zach sees that Xavier has blue eyes", then Xavier would have to already know his own eye color, or Wendy would have to think that he does.

At this point, I hope I don't have to explain why it also couldn't be Yogi.

So there you go. Even with four blue-eyed islanders, the existence of blue eyes cannot be common knowledge by the logical definition of common knowledge (until something happens, such as the Guru's announcement). Now, if you imagine a statement like the one above, but one hundred names long, it should be clear that the same problems will arise; each islander's ignorance of his own eye color means that the "last" islander, nested inside numerous hypotheticals, cannot see who has blue eyes. And of course, the ordering of the names is arbitrary, so this principle applies equally to all the islanders.

Some may insist that "Which islander does hypothetical-Zach think is blue?" is irrelevant or even a trick question. Various attempts have been made to show why the "innermost" islander in any chain like this can be inferred by the outermost islander to be aware of blue eyes, even if we can't name which ones the outermost islander thinks he sees. It has been argued that because the situation can be modeled as a net, and not just a chain, then we can "recurse" or "criss-cross" the lines of information. And because of this criss-cross, we can find that if A knows that C knows "Q", and A knows that B knows "Q", then A knows that B knows that C knows "Q" (or at least, this is somehow true if there are four agents instead of three).

Yes, the situation can be modeled as a net or graph, but any path on this graph will still be a chain, and must still be described in the same terms as the example here. For example, if it really is the case that W can "know" that X knows Y knows Z sees someone with blue eyes, then there must be an answer to the "Who does Z see?" question. No islander can "absorb" the abstract information "at least one blue-eyed islander exists" by some sort of osmosis or critical mass of islanders, any more than Yolanda could when it was just her and Zoe. The can only learn this fact by seeing it for themselves. And all islanders will know this about all other islanders.

Another point some have raised is: sure, W might suppose that X supposes that Y supposes that Z sees no blue-eyed people, but why suppose all that? Isn't it arbitrary? W may as well suppose that X supposes that his own eyes are blue. The answer to this is… yes, that's perfectly true. In fact, no islander is assuming that his own eyes either are or are not blue, or that other islanders are making such an assumption. That's not what's going on here. Each islander is simply considering both possibilities, and knows that everyone else is considering both possibilities, etc. These various possibilities multiply out. When a chain is extended to include every single islander, than every possible combination of eye colors is accounted for. For example, W knows that if:
• his own eyes are blue, and
• X (by coincidence, correctly) imagines that his own eyes are blue, and
• X supposes that Y (incorrectly) imagines that his own eyes are brown, this means that:
• W would suppose, in this one example, that X would suppose that Y would suppose that Z would see two blue-eyed people (W and X) and one brown-eyed person (Y).

That's just one of the many, many possibilities of nested beliefs. (I calculate 192, counting all the possible orderings of four islanders thinking about anoe another thinking about various combinations of blue and brown eyes.) All that matters for this particular problem is that "seeing no blue-eyed people" is at least one of these nested possibilities, and thus our logical islanders are considering it, along with all the other ones.

3. Yes, with just one blue-eyed person, it wasn't common knowledge, nor with two, or possibly three. But with over ninety blue eyes, it's obviously common knowledge.

Hypothetical blue-eyed islander A sees 99 blues. A knows that B sees at least 98 blue eyes. Clearly, A should know that B knows that C sees at least 98 blue eyes, because A can see C seeing the 98 other blue eyes, and A can see that B can see C seeing the 98 other blue eyes. Combine these two facts, and it is clear that the minimum possible number of blue-eyed people whose existence is common knowledge is 98, not 0 or 1.

Spoiler:

In order for that statement —

A should know that B knows that C sees at least 98 blue eyes, because A can see that B can see C seeing the 98 other blue eyes.

— to be true…

Then either A, B, or C must somehow know the color of their own eyes, or be believed by the others to know his/her own color. Neither of these can be the case, so 98 is too high a lower bound.

Every time you add the word "knows" to a statement of the form "A knows that B knows that… D sees at least N blue-eyed people", you have to subtract 1 from N. You must account for the fact that each person is ignorant of their own eye color, and is accounting for the next person's ignorance of their own eye color, and is accounting for the next person accounting for the next person's ignorance, etc.

Without any statement from the Guru, this process of "A knows that B knows…" will have to end with "that Z (here the 100th person on this list, not the 26th) knows that at least 0 blue-eyed islanders exist." For it to stop at a number greater than 0, someone has to know something which can't be known, or believe something which can't be believed, absent anyone's information.

After the Guru's statement, though, that number immediately goes to 1, and then increases by 1 every midnight thereafter. This leads to the eventual situation of all 100 blue-eyed people leaving on Day 100.

If you're confused (which is perfectly normal!), then again, we advise you to contemplate the situation with just one blue-eyed islander, then two, etc.

EDIT: Here's another thought about what's going on with the (correct) statement that "A knows that B knows that C knows there are at least 97 blue-eyed people." It's true that, darn it, A can just plain see 99 pairs of blue eyes, and that A can see that B sees 98, and that A can see that C sees 98. However, when A wonders about B's understanding of C's knowledge, A isn't simply curious about how many blue-eyed people there are. Nor is A simply curious about how many B thinks there are, or how many C thinks there are.

A really is curious about B's knowledge of C's knowedlege, and likewise for all other such orderings. A has to deduce this meta-knowledge in order to work out the whole situation. This deductive process can't just "stop" with three, so apart from 0, there is no "common knowledge minimum" of blue-eyed people before the Guru's statement establishes a minimum of 1.

EDIT 2: Here may be a simpler way to put it, a point raised by many dealing with this problem: If you think the blue-eyed people can nonverbally agree on some sort of common minimum which is greater than zero, than surely the browns should agree to the same minimum, or else it's not really common to the islanders. But how? Suppose each blue thought "I see 99 blues. 99 minus 2 is 97, so 97 is the absolute common minimum to which we all agree." In that case, a brown-eyed person would go "I see 100 blues. 100 minus 2 is 98, so 98 is the absolute common minimum". If a brown instead came to conclude that the minimum is 97, that means he went one step further than a blue would. Why would he? See, this is the (initially) surprising result of the existence of a one-person difference between two people's counts of eye color, all thanks to the commonly-known fact that no one knows the color of her own eyes.

4. Who on that island could possibly believe that no one with blue eyes lives there?

In order for the puzzle to work, each islander is hypothesizing an islander who sees no blue eyes— but they all already know that no such islander exists.

Spoiler:

This objection is answered in more or less the same way as the previous two.

No one is hypothesizing such an islander, despite appearances. Rather, they are hypothesizing that everyone else is hypothesizing that [repeat an arbitrary number of times] there is such an islander. This person is nested within numerous nested hypotheticals. Don't feel bad if that doesn't seem to make sense right away.

Again, try it with three blue-eyed islanders, which seems to be a point many people get stuck on. If there are three, then it is true that everyone knows that everyone else can see at least one person with blue eyes. So Objection #4 seems to apply when there are just three blues total — no one would possible imagine someone who imagines someone who sees no blue eyes.

But this is not sufficient to establish blue eyes as common knowledge. If A, B, and C all have blue eyes, the only way for A to know that B knows that C sees at least one pair of blue eyes is if A knows A's own eye color to be blue, or if A thinks that B knows B's own eye color to be blue. Neither of these can be the case.

This brings us to the next objection…

5. Yes, it works if there are just one or two blue-eyed people, but not three or more.

Induction cannot prove everything.

Spoiler:

The proof doesn't just stop at two, nor does it have to. We've talked a lot about nested hypotheticals, so let's look at it in a different way altogether.

Imagine that you are one of the islanders. The Guru has made her statement. You happen to see exactly two pairs of blue eyes. How many blue-eyed people are there altogether? Either two (just them) or three (including you); you don't know yet.

Now, you accept the logic that if the total number of blue-eyed islanders is two, they will both leave on Day 2. You know that there is no way for this not to occur; no one is going to forget to leave, or forget to deduce that the other one can see his eyes. Nor will anyone leave sooner for some reason. If there are just two, then the exodus will occur on Day 2 and Day 2 only.

You wait until Day 1. Nothing happens, which doesn't surprise you (but may have surprised the two blue-eyed folks you see).

You know now that if there are just two blue-eyed folks, they will each have figured this out, and prepare to leave the next day.

Day 2 arrives. You wake up, look around, and see… that they are still here. Why would that be? Why would they not have left yet?

The only possible answer is that each of them also saw more than one person with blue eyes. Which means they each saw some blue-eyed person you couldn't see, and the only person that could have been is you. In short, they were each waiting for you (and one another) to leave first. So, now you know the color of your eyes: blue.

This applies equally to all the blue-eyed islanders, of course. So we have now established that if there are exactly three blue-eyed people, they will all leave Day 3. An absolute, undeniable rule. If three blue eyes, then all of them leave on Day 3.

6. I knew that it works for three (or, now I realize that). But it breaks down at four.

I have a very good reason to say it breaks down at four. (Different people provide different reasons here.)

Spoiler:

Whatever that reason is, we doubt it's good enough. All you need to do is re-read the entire response to Objection #5 and mentally replace each "two" with "three" and each "three" with "four", modifying it as needed. To make that easier, I've done it for you in the paragraphs below.

Imagine that you are one of the islanders. You happen to see exactly three pairs of blue eyes. How many blue-eyed people are there altogether? Either three (just them) or four (including you); you don't know yet.

Now, you accept the logic that if the total number of blue-eyed islanders is three, they will all leave on Day 3. There is no way for this not to occur; none of the three is going to forget to leave, or forget to deduce that the other two can see his eyes. Nor will any of them leave sooner for some reason. If there are just three, then the exodus will occur on Day 3 and Day 3 only.

You wait until Day 1. Nothing happens, which doesn't surprise you. There was no way for anyone to leave that soon.

Day 2 arrives. Nothing happens, which doesn't surprise you — however, you know now that if there are just three blue-eyed folks, they will now figure this out, and prepare to leave the next day.

Day 3 arrives. You wake up, look around, and see… that they are still here. Why would that be? Why would they not have left yet?

The only possible answer is that each of them saw more than two people with blue eyes. Which means they saw some blue-eyed person you couldn't see, and the only person that could have been is you. In short, they were each waiting for you (and for each other) to leave first. So now (and not a day before) you all know the color of your eyes: blue.

This applies equally to all the blue-eyed islanders, of course. So we have now established that if there are exactly four blue-eyed people, they will all leave Day 4. An absolute, undeniable rule. If four blue eyes, then all of them leave on Day 4.

7. It works for one, two, three, or four. It stops working at five.

I know the induction thing is looking good for you so far, but trust me, it doesn't keep going forever.

Spoiler:

I don't mean to sound exasperated — I know you honestly are thinking this through — but this is getting ridiculous. It's been shown, twice now, that if it works for a number N, then it works for N + 1.

This means it works for up to at least 45 billion blue-eyed islanders, after which we don't know, because 45 billion is the largest number known to mathematics.

EDIT: Here's another useful way of putting it, paraphrased from several posts in the original solution thread. If you claim that N blue-eyed people will deduce correctly, but N+1 will not, then you are arguing that different outcomes will occur depending on which islander's perspective we take. For example, say you think it works with four, but not five. That means that if you, an islander, see exactly four pairs of blue eyes, then you know that:
• there are either four or five blues total (a basic induction)
• if you don't have blue eyes, then the four you see will all leave on Day 4 (because it works with four)
• If you do have blue eyes, then even after seeing no one leave on Day 4, no one will ever deduce their own eye color (because it somehow doesn't work with five)

The last premise must be wrong.

[Lenoxus]

8. I accept that all the blue-eyed islanders will eventually figure out their own eye color, no matter how many there are. But why do they have to wait so long to leave?

Since they each know that the wait would be at least 99 days, surely they can logically skip most or all of that?

Spoiler:

It does look that way at first. Good question. This is a tricky one to address.

(Edit: I'm interrupting myself here to point out a much simpler response than what follows. That resonse: anyone asserting that the blue-eyed people might leave sooner than Day 100 has to explain exactly why the brown-eyed people would not use the same logic to conclude themselves to be blue-eyed, and leave on the same day as all the true blue-eyes. Any such explanation must be flawed somewhere. Perhaps the most interesting version of the "skipping" argument is presented here, because its author acknowledges the brown-eyes problem and simply asserts that incorrect conclusions will be drawn by perfectly logical people who were given no false information.)

One way to show "skipping" doesn't work is a variation of the answers given to objections 5 and 6.

Let's say that you see 99 pairs of blue eyes. You suppose that if your eyes are not blue, then all those 99 people will leave on Day 1. If they don't, then you deduce that your eyes are blue, and leave on Day 2. Sounds good so far.

Well, put yourself in the shoes of one of those 99 people. As far as you know, they might each only see 98 blue-eyed people. So what algorithm will they use, based on the reasoning whereby you waited a day? The answer is that they, too, would each wait a day, then decide what color they were. If they just went ahead and left, that would mean they instantly knew that they had blue eyes following the Guru's announcement, which isn't possible. So no matter what, they'll wait a day.

But wait! By your original algorithm, if those 99 were the only blue-eyed people, then they would have (somehow) immediately realized this, and they wouldn't have waited a day. There's a contradiction.

It's solved by realizing that "There are at least 99 people with blue eyes" is not common knowledge. And believe it or not, neither is "There are at least 98 people with blue eyes", or the same with 97, or 96… or 4, or 3, or 2. "There is at least 1 blue eyed person" is common knowledge, but only because the Guru had established it by saying so. 1 is thus the only possible "common minimum".

The "skipping days" idea still doesn't work if you think that a given person should wait two days instead, or whatever. Then everyone is waiting for everyone else to wait for everyone else to wait (etc)… for 2 days, which would actually add up to twice the original solution, or 200 days instead of 100.

One core issue here is that while the following is common knowledge —

"There are exactly two different estimates of the total number of blue eyes, and these estimates are apart by only 1."

— it can't be common knowledge what those estimates are. Nor can any islander know if her estimate is the lower one or the higher one. If she did, she would already know her eye color without anything else having to happen.

In the original puzzle, each blue-eyed person correctly estimated 99 to 100 blue-eyed people, even before the Guru spoke. However, they can't each know "99 to 100" to be every other blue-eyed person's estimate, or else they would just immediately know their own eyes are blue. Instead, their guess of other people's guesses would range from 98 to 101 (because if I have blue eyes, then my brown-eyed neighbor sees 100 and considers that he himself has blue eyes, thus bringing his upper limit to 101).

Even still, the range "98 to 101" isn't common knowledge; it can't be known that everyone knows that everyone knows that everyone knows [ad infinitum] this range. That would require the hypothetical 98 inside the hypothetical 99's minds to each know that they are 98 in number and not 97, and they can't.

The range expands by 1 on each side as we add another layer. Long before Day 1, we all reach a maximum range of "0 to 200". (Both the fact that island's total population is 200 (ignoring the Guru), and the fact that there can't be a negative number of blue-eyed folks, are common knowledge.) On Day 0, immediately after the Guru's announcement, it collapses to "1 to 200", as a result of the common knowledge that everyone trusts the Guru. On Day 1, the threshold becomes "2 to 200", as a result of the common knowledge that if there were just 1, he would have left the previous midnight. On Day 3, it becomes "3 to 100", etc.

Eventually, if you see 99 blue eyed people and Day 99 goes by without anyone leaving, then the common-knowledge estimate becomes "100 to 200". You know that it can't be more than 100 (your personal estimate had been "99 to 100"), so that means there are exactly 100 and you are one of them (and that each of the other blue-eyed people have now realized exactly the same thing).

The 200 part doesn't matter. Once all the blue-eyed people have left, the remaining people can safely estimate the blue-eyed population as "0 to 0", or simply "zero", and it is now common knowledge that all the blue-eyed people are gone. Which brings up the next objection…

9. The standard solution fails to mention that on the day after the blue-eyed people leave, the brown-eyed people do.

They would each deduce that their own eyes are not blue, and therefore brown.

Spoiler:

They would indeed do that — if they knew that brown was the only alternative to blue. But they don't. As far as each of the brown-eyed islanders is concerned, his own eyes might be yellow or green or red, and nothing in the puzzle changes these possibilities. All the brown-eyed people know is "My eyes are not blue", and that's it. Forever.

Now, if the Guru had said, "I see at least one person with blue eyes, and everyone without blue eyes shares a single eye color," then the brown-eyeds would indeed each deduce their own color on Day 101. In fact, weirdly enough, they would each know immediately after the Guru speaks that they will make the deduction on Day 101; they just won't know until then whether the cause of this deduction will be seeing 100 blue-eyed people leave on Day 100 (thus leaving only the browns), or seeing nobody leave on Day 100 (in which case there must be 101 blues). Likewise, each of the blue-eyed people will know that they will leave on Day 100, but won't know why until then.

Meanwhile… if on Day 0 the Guru had said "There is at least one person with blue eyes, and at least one person with brown eyes", then everyone leaves on Day 100, because both the "blue" and "brown" processes of deduction happen simultaneously, at the same speed. (You can work it out yourself by starting from one of each, then two of each, etc.)

In the original puzzle, it is not the case that the brown-eyed people ever leave. Not even 200 days later, which is a related notion, and it relates to the thinking behind Objection # 11, coming up shortly.

EDIT: There is a related but contrary objection which appears a lot in response to other formulations of the puzzle — for example, in the comments on this blog post (warning: that page is very large) — but not here on XKCD. Call it Objection #18 (I only thought of it a few days after posting this).

According to this objection, the official solution doesn't work because each of the islanders doesn't know there are only two colors. Of course, it should be clear by now that it doesn't matter how many colors each islander thinks there may be (so long as their beliefs don't outright contradict reality, eg, an islander in the original puzzle somehow thinking that only green is a possible eye color, which would obviously lead to nonsense). The official solution does not rely on any islander thinking that "not brown means blue". For purposes of this problem, there is just "blue" and "not blue", and of course, "not blue" is not any one color.

10. Wouldn't the Guru herself have to leave at some point?

She would use the same process of logical deduction as everyone else.

Spoiler:

No. This is because everyone knows that the Guru does not know her own eye color, and everyone knows that everyone knows this, etc. Therefore, when the Guru spoke, she could only possibly have been referring to people other than herself (and this remains the only possibility in any number of nested hypotheticals). This causes the Guru to be "exempted" from the puzzle — her failure to leave on a given day doesn't tell anyone anything, nor does it tell anyone that it tells anyone anything, etc. (In some versions of the puzzle, she is replaced with an outside visitor who doesn't know the local customs; the effect is the same.) This is the case even if the Guru's eyes are blue.

If you're still confused about this one, consider the scenario of just two blue-eyed people: The Guru and Bob. After the Guru said "At least one person here has blue eyes", Bob would immediately know his own eye color — knowing that the Guru must have meant someone other than herself — and leave on Day 1. If there are two others besides the Guru, than each of them would expect the other to leave on Day 1, then see that they didn't and deduce their own eye color, etc.

The Guru is simply "not part of the situation", and it is common knowledge that she herself will never, ever leave. If she gets access to a mirror or something, or if there's some possibility that one or more islanders could somehow forget which islander the Guru is, then that's another story.

11. I agree with the solution almost completely. However, it appears that the effect of the Guru's action is curious: It triggers an arbitrary countdown, synchronizing the islanders, without actually doing anything.

The Guru could have said something like "Let's all think about blue eyes from now on", or even just "Hey everyone, today is Day Zero", and the long chain of deductions would still occur, leading to the same result. In fact, it would occur equally for both colors, since there's nothing special about blue. The brown-eyed people would also start thinking "Hmm, my eyes might be brown", and they would end up leaving on Day 100. Or, perhaps on Day 200 (they only consider the color "brown" after the blue eyes are gone).

Spoiler:

It sort of looks that way, especially if you don't understand exactly why the Guru's statement does, in fact, provide information (see Objection #1).

Consider the case with just 1 blue-eyed person, Joe, and 100 brown-eyed people. If the Guru says "Everyone: Think about blue eyes!" will Joe leave the next day? No, because from Joe's perspective, it could still logically be the case that everyone on the island has brown eyes (or that Joe has yellow eyes, etc). It might be a strange thing for the Guru to say in a world with no blue eyes, but it in no way guarantees that Joe has blue eyes. In order for the Guru to make Joe leave, she has to either tell him his own eye color directly, or imply as much by specifically stating that "at least one person" with blue eyes lives on the island (or by saying something similar). Just any old "trigger" won't do.

So, what if there were exactly two blue-eyed people, and they heard the Guru say "hey, think about blue"? Would they both, just like in the "regular" version, be able to deduce their eye color from nothing happening on Day 1? No, because they still have no reason to think the other person would leave if she saw no one with blue eyes. Their personal assumption that "If no one at all leaves on Day 1, then I have blue eyes" is strictly dependent on "If that blue-eyed person sees no one with blue eyes, then he is going to leave on Day 1." An assumption which in turn requires additional information input, either from the Guru or elsewise.

(EDIT: In keeping with the theme of my other edits, a related problem should be pointed out. If you agree that a lone blue would not leave on Day 1 following a "synchronizing event", but you feel that two blues would leave on Day 2, then what should you do if you are on the island yourself and see exactly one blue? Remember, you might be blue in this situation. So after not seeing the lone blue leave on Day 1, then you would leave on Day 2, right? Go ahead and leave. Well, it turned out that you were brown-eyed, and that all the other browns followed the same logic and left with you. Oops. So maybe our thinking should be modified to say that Lone Blue-Eyed Joe would leave on Day 1 after hearing the Guru shout "Blue!". Okay, but if the actual number of blues were zero and the Guru announced "Today is Day Zero for the consideration of blue eyes!", then everyone following this reasoning would assume himself to be a lone blue, leaving on Day 1. This would leave behind a very confused Guru, who would wonder if the islanders had misinterpreted her words to mean "I can see someone who has blue eyes" -- which, of course, is identical to the original puzzle's statement.)

In the original puzzle, 100 blues leave on Day 100 because they know that if there were only 99, those 99 would have left the day before. If those 100 people have no reason to believe this, though, then they won't deduce their own eye color and leave. Likewise if the real number is instead 99 — they'll all leave if and only if they expect a hypothetical 98 blue-eyed people to leave, etc. Let's take it down to three people.

We know that with just three blue-eyed people, then in the original puzzle, they all leave on Day 3. (If you disagree, go back to Objection # 5). They know that the other two would have left on Day 2 if they each saw just one person. The three know this because they know that the other two people know that the one person those other two people see would have left on Day 1 if that other person saw zero blue-eyed people.

This is all correct, and it all rests on that last situation — the one where a hypothetical lone blue-eyed person sees no blues and deduces that his eyes must be blue. And this lone situation cannot possibly happen if the Guru merely says "Hey, folks, have you ever considered that you might have blue eyes?". Without the bottom situation caused by the Guru's statement in the original puzzle, the whole thing topples.

12. How could they have lived on the island for "endless years" without all eventually leaving? Shouldn't the process of deduction have begun the moment that all 200 people were "given the rules"?

I think there exists a minimum number of certain eye color ratios such that each person can use the various deductive processes described all over this page to eventually figure out their own eye color. For example, they would observe other people's eyes and use that information to limit the number of possible colors for their own eyes. They should all be gone before infinite years have passed.

Spoiler:

This objection is very similar to # 11, answered above. Remember,the whole sequence in the original puzzle rests on there being common knowledge of a nested hypothetical single person's action given that this hypothetical single person can deduce their own color with certainty, and the Guru's statement is necessary to create this common knowledge. No one can deduce anything either out of thin air, or based on mere probabilistic estimates.

If you started out with, say, a lone islander who knows all the rules, she won't guess her own color. If you add another islander, then add another, there is no "magic number" or proportion of any particular eye color that initiates a countdown. For example, suppose that Islander Sarah "pops into existence" fully aware of all the rules, on an island with exactly five other such people. She sees two people with blue eyes and three with brown. She knows that blue and brown are "possible eye colors" (although she also knows this about green, red, etc).

Can she deduce her own eye color? Can anyone else deduce their own eye color? No, never, and when you think about it, that makes complete sense. In this particular situation, it really is similar to what many people think is going on when they present Objection #1. Here, no key information has been given whatsoever! So if your intuition told you Objection #1 was correct (which it's not, but that's a complex thing to understand) then perhaps it is easier to see why Objections #11 and #12 are mistaken. Islanders cannot "deduce" their own color without a source of outside information that would be different if they had a different color, any more than you can deduce real facts from the principle of explosion.

To put it another way: In the original puzzle, people deduce their eye color based on other people not deducing their own eye color and thus not leaving. But without mirrors or Gurus or other outside sources of information, no one has reason to make that deduction in the first place, so no one has reason to leave, so nothing is concluded by other islanders not leaving. The idea that a sufficient number of people will deduce their own eye color solely by observing the eyes iof the people around them is tantamount to thinking that if enough people look at my eyes, their knowledge of my eye color will somehow "transmit" to me, as with the so-called hundredth-monkey effect. (Maybe it works with monkeys, but it doesn't work with logic-puzzle islanders. )

As it happens, if Islander Sarah believes (for whatever reason) that blue and brown are the only possible colors, then she still can't ever deduce her own color. Not even if it is common knowledge that blue and brown are the only possible colors. (The original problem lacks this common knowledge; in fact, the existence of the green-eyed Guru precludes it.) This is because the statement "Each pair of eyes is either blue or brown" does not mean that there must be at least one of each; it is still a true sentence on an all-blue or all-brown island, albeit not a sentence the average person would speak. If I have three pet dogs and no other pets, then it is logically true (if a bit odd to say) that each of my pets is either a dog or a cat.

Now, if it is common knowledge on one of these islands that "at least one blue and at least one brown exist", then yes, the puzzle works as usual, except that all the brown-eyed folks leave on Day 100 as well. But as established in various answers above, someone or something has to provide this information in a way that makes it common (and not just "almost" common).

13. The islanders are perfect logicians. Therefore, they will collectively derive their eye colors by whatever algorithm happens to be the maximally perfect logical one. No Guru is needed, except possibly to trigger a game of "let's all figure out our eye colors".

For example, they might (silently and without actually communicating) agree to a "bubble sort", whereby everyone stands in a line and runs around in a certain pattern until they can see that all the blues are on the left and all the browns on the right, hence each person knowing who they are. Or perhaps they would have a partnered "dance" — each person finds two people with the same color eyes and "partners" them, and they all keep doing that until everyone is partnered.

Spoiler:

The original puzzle states "it doesn't involve people doing something silly like creating a sign language", and both of those definitely qualify. Plus, the fact that there even are more than two possible "perfect" ways is clearly problematic, because it prohibits people from agreeing on one of them (and after that, agreeing on the exact details, things like left-vs-right, etc.)

Another, perhaps deeper, issue is that this assumes that everyone "wants" to get off the island. In fact, they don't, which is part of why the solution works. If the islanders had a strong enough desire to leave, they simply would (which means no deductions could be made from anyone else leaving). If they had an even stronger collective desire to learn their own eye colors as a requirement before leaving, they simply would, whether by talking to each other or using mirrors. If they have an even stronger desire to learn their eye colors without actually saying words aloud, well, they can go right ahead and develop the right "language", be it sign language, or a dance, or a sort. These could very well lead to interesting directions for a logic puzzle, such as islander-based metaphors for computer programming. But all that is different from the original puzzle, in which there is no communication, period, as well as no desire to leave — and for that matter, no desire to stay.

If you want to, you can choose to interpret "perfectly logical" to mean something like "capable of deducing anything true from just about any other datum", which in turn means "nigh omniscient". But that's obviously a very different (and arguably trivial) sort of puzzle. ("The islanders deduce every past event in human history, including the genomes involved in their own conceptions.") In the original version, the islanders don't even know anything about genetics, much less everything else in the entire universe. They simply spend all their time thinking about each other, recursively.

14. The islanders would not bother with all the counting and deducing necessary for the solution to work, because that would increase their risk of deducing their own eye color, and it's irrational to want to leave the island. Being perfect logicians, they would know that everyone else would do the same.

In their deliberate collective ignorance, they never leave.

Spoiler:

These islanders simply can't choose not to count and deduce. Consider them obsessive, if you like, but at least they all know each other well. Furthermore, because they can't help but make all possible deductions, they know that everyone else will, too (et cetera). None of them can expect any of the other blue-eyed people to do anything but leave the day after Day N, where N is the number of pairs of blue eyes they see.

This one is basically the opposite of Objection #13, and it naturally comes from an opposite direction, assuming that leaving is "bad" instead of "good". As stated above, however, there is no incentive to either stay or leave.

Some versions of the puzzle involve the islanders committing suicide instead of merely leaving the island. In terms of human intuition and our real-world knowledge about how people think, this can make it harder for puzzle-solvers to believe that these islanders would really do all that deducing instead of just deliberately remaining ignorant to save their own and others' lives (especially if there's such a strong taboo about thinking about the subject of eye color).

If you like, you can make the whole thing even milder than exile; those who have figured out their own eye color just publicly declare that they have done so, or stand on their heads, or whatever. The overall effect is exactly the same.

If the islanders are not the "automatons" we know them to be, but merely very good game players who are trying to work out their own color, then the puzzle doesn't quite work. This is because in the case of just one blue-eyed person, she would indeed deduce her color, but she wouldn't necessarily leave right away, because she can leave any time she likes and still "win" (she'll never forget that she has blue eyes, after all). This makes the whole thing break down. In order for all the deducing to work, the conditions of the puzzle have to be such that no one can stay once they knew their color, and at the same time, no one can leave if they don't know, or if they merely guessed correctly.

15. How do the islanders know that all the other islanders are perfect logicians (and that everyone knows, etc)?

Furthermore, how is it common knowledge that the Guru is reliable and trustworthy?

Spoiler:

That all the islanders are logicians is common knowledge, because the paragraph which says so states "Everyone on the island knows all the rules in this paragraph." Admittedly, this could be confusing, because it might imply that there's common knowledge somehow involving the words "rules" and "paragraph", which implies weird things, like that the islanders have an internet connection and can read the puzzle itself. So one might naturally read that sentence to instead mean, "Everyone on the island knows all the rules in this paragraph prior to this sentence." But that's not the intention; the intention is just to (in a brief way) say, "everyone knows all that, and everyone knows, etc."

Meanwhile, it's true that the Guru's trustworthiness is not established common knowledge per a very strict reading of the original puzzle. For purposes of the solution, and of of playing around with all this, well, we can grant it as an additional premise. The puzzle does state that "It doesn't depend on tricky wording or anyone lying", which could be seen as establishing this, but it could be also seen as "The Guru doesn't ever lie — no actual lying occurs — but everyone thinks she might". Which, if true, makes it all fall apart. But that sounds like "tricky wording" to me.

16. So, it's Day 99. Each of the blue-eyed people is waiting to see if any of the others take the ferry. After a brief pause, they each observe that none of them do — and therefore they each deduce their own color, so they each do take the ferry, one day "early".

But the 99 would have likewise observed none of the 98 leaving the day before, and so they too would have paused long enough for all 100 to get on the boat. If we extrapolate this indefinitely, then everyone with blue eyes leaves on the first night, separated not by days but by "pauses".

Spoiler:

This is more or less true. The problem, of course, is how long is a "pause"? It has been suggested that human reaction time is 1/6 of a second. If so, perhaps we can re-describe the problem in terms of "pauses", which means that instead of "one day", a person leaves 1/6 of a second after they deduce their color (but deductions are still instantaneous). The solution in this case is that the 100 islanders leave after 16 2/3 seconds. Perhaps this is silly.

A reasonable way to interpret the original puzzle, which achieves the "correct" solution, is that leaving the island is instantaneous, but can only occur at exactly midnight. Imagine that it's some sort of teleportation device which is connected to each islander's brain state.

Or perhaps leaving the island is not instantaneous but anonymous; maybe each islander lives alone, they all spend 9AM to 11PM outside their own house, they each always go home by 11PM, and each has a secret passageway from his/her house to the dock, which is behind walls no one can see over. They only take this passageway if they intend to leave. The puzzle should work out correctly in this case.

EDIT: A third way to work it out is to require that the islanders leave within a well-defined time period, such as between midnight and 1AM, and add the stipulation that if an islander happens to deduce her own color within this hour, then she must leave during the next night's ferry trip. So during the first hour of the hundredth day, the 100 blue-eyed people could all board the ferry at various times within that hour, rather like how boat, trains, and airplanes are boarded in real life.

16.5. (A new one that I only thought of more than a week after posting this.) Since each islander already sees blue eyes, then each one could in principle imagine, "Hey, the Guru could say 'I see someone with blue eyes,' and if she did, then all the blue-eyed people would leave." Why doesn't that trigger the whole thing?

For that matter, they all also know this about the brown-eyed people, so this should happen for them, too.

Spoiler:

Because it's not the content of the Guru's statement which provides information, it's the common knowledge that all islanders heard it. It wouldn't be enough for each islander to individually think "I can imagine the Guru saying X, and I know that everyone I see can imagine this." That is true, but not for 100 iterations of "imagining that everyone else is imagining that everyone else is imagining", etc. This is because it's still not common knowledge that blue eyes exist. (Re-read the response to Objection #2).

However, if any blue-eyed islander somehow comes under the impression that all other islanders really did hear the Guru make the public announcement "I see someone with blue eyes," then that islander would, by sheer luck, "deduce" their own eyes to be blue and leave on Day 100. But this would be the effect of a delusion, just like a blue simply having the delusion that his friend told him "Hey, you have blue eyes." Plus, if we allow for such hallucinations, a brown-eyed islander could just as easily do the same thing, falsely leaving on Day 101. (He would observe the 100 blues not leaving and think that this means there are more than 100 of them.)

However, if all 200 islanders somehow simultaneously hallucinate a Guru saying "There's at least one blue", then the problem would work out as in the original, because the situation is isomorphic to the effect of a "real" Guru.

17. I think I understand it all now. There's just one thing: the puzzle relies on each islander imagining what each blue-eyed islander they see is in turn imagining. This recursive hypothesizing cannot continue past zero steps, because, as established by Townshend (1971), no one knows what it's like to be the sad man, to be the bad man, behind blue eyes.

In order for the solution to be arrived at, it would have to be common knowledge that all male inhabitants of the island are neither sad nor bad.

Spoiler:

Technically, if "no one" knows what it's like, then a sad, bad, male blue-eyed islander will not know what it is like to be himself. In that case, additional premises are required to make sense of the situation.

[Gwydion]

Thank you for this. I only hope this thread doesn't make the other one disappear into the ether, because it was a fun few years arguing about the blue-eyes puzzle.

[skullturf]

Yes, I, too, thank you for this. It may perhaps appear redundant to some, but the large number of responses on the other blue eyes thread suggests that it might be necessary or helpful.

I really like your example in the response to Objection #1. "The day after [repeat 300 times] tomorrow" refers to something different from "the day after [repeat 299 times] tomorrow".

Not to deny the subtlety and the mind-bendingness of the problem, because I certainly had to wrestle with it quite a bit, but some of the objections almost feel like they boil down to the "one, two, many" problem. People get a little sloppy and they think, "If everyone knows that everyone knows that everyone knows that there at least 97 blue-eyed people, well, that's a lot of layers and 97 is a big number, so it's pretty much common knowledge, because come on."

Three isn't infinity, and 97 isn't infinity.

[Lenoxus]

I really like your example in the response to Objection #1. "The day after [repeat 300 times] tomorrow" refers to something different from "the day after [repeat 299 times] tomorrow".

Of course, I got it from your posts in the other threads, so the credit is all yours. Thank you for it!

Not to deny the subtlety and the mind-bendingness of the problem, because I certainly had to wrestle with it quite a bit, but some of the objections almost feel like they boil down to the "one, two, many" problem. People get a little sloppy and they think, "If everyone knows that everyone knows that everyone knows that there at least 97 blue-eyed people, well, that's a lot of layers and 97 is a big number, so it's pretty much common knowledge, because come on."

Three isn't infinity, and 97 isn't infinity.

I agree that nearly all the objections boil down to: "More than two instances of 'everyone knows' must be logically identical to any other number of such instances". Interestingly, from this premise, many different conclusions may be drawn, including that they never leave (because the situation hasn't "really" changed), or they leave super fast (any number greater than two ought to leave at the same speed with which two would).

[skullturf]

Heh, I forgot that the "day after the day after the day after tomorrow" stuff was said by me.

But I do remember using similar examples in classes I've taught. Not when discussing the blue eyes puzzle -- I've never taught a class where it came up -- but I think the "day after the day after the day after" stuff is useful when talking about the different ways things can be difficult.

I can't remember where I read it, but I think it was in a Roger Penrose book, where the author described something as "confusing, but merely confusing".

Things like "the day after the day after the day after tomorrow" are certainly confusing, in the sense that you tend to lose track of where you are in the nesting, and you can't just intuitively grasp a large number of layers at once. It's vaguely similar to how you can distinguish between three and four objects by "just looking", but you can't distinguish between 17 and 18 objects by a sort of immediate effortless perception.

But something can be difficult in the sense of being confusing without necessarily being difficult in other senses. You know what "the day after" means, and you just have to keep track of where you are in the "nesting". (And counting to 17 or 18 isn't difficult; it's just that it's possible to lose track in the middle if you get distracted.)

[skeptical scientist]

I'd also like to add my thanks for this. Some of the objections you raise seem rather silly though. Be honest: you decided to make the number of objections seventeen first, and then had to come up with a few extras to get to seventeen, didn't you?



Would it also be worth talking about some variants and what happens in this thread? I think that even when you know the right answer, and why it's correct, there are still some things that you might not fully understand without considering some variants on the original puzzle. Some good variants are:
1. What happens if the Guru herself has blue eyes?
2. What happens if one of the blue-eyed islanders is absent when the Guru makes her statement?
3. What happens if one of the brown-eyed islanders is absent when the Guru makes her statement?
4. What happens if the Guru tells everyone individually that she's seen someone with blue eyes on the island, instead

[Lenoxus]

Be honest: you decided to make the number of objections seventeen first, and then had to come up with a few extras to get to seventeen, didn't you?

Nope; I originally had fewer than that, but kept thinking of more and counted them when I was all done. Only the last one is deliberately silly. All the others are ones I have seen either here on XKCD or elsewhere. Of course, no one person has made all sixteen "serious" objections (that would be silly).

I feel like there are subtle differences between Objections #1, #2, #3, and #4, so that's why I made each one of them. I wanted to really tease it apart and wrestle it to the ground.

I admit that #2 and #3 are quite similar. However, people making Objection #2 are simply failing to appreciate the difference between 99 and 100 layers of knowledge (despite what they claim, they don't know what common knowledge means). It's a bit confusing in the context of my posts because they usually don't say this after someone has spelled out "99 vs 100", but before. Their usual process is a simple bad induction, whereby they demonstrate first that everyone knows, second that everyone knows x2, third x3, and then say "etc", assuming that there's nothing wrong with the "etc".

Meanwhile, people making Objection #3 are getting that there's a distinction between 99 and 100 layers, yet assuming that past a certain point (say, eighty or ninety eyes), a certain minimum becomes common knowledge "anyway". They reason that we can "truthfully" say things like "A knows that B knows that C sees 98 blue eyes" (not really truthfully, but it's easy to skip that groove). They think that one can "re-insert" or repeat one hypothetical islander's knowledge back into the "top layer", or something odd like that, and thus establish a common minimum. It's similar to the mistake behind Objection #5, but made from the top down instead of the bottom up.

1. What happens if the Guru herself has blue eyes?

I think I answered this in my response to Objection #10, but perhaps not with much elaboration. Your other questions here were not answered in my posts, except for your fourth one being obliquely answered by my pointing out that the public nature of the Guru's statement is important.

My answers to your second and third questions are:

Spoiler:

If one blue-eyed person didn't attend the meeting, then no one ever leaves. That one blue-eyed person is a necessary link in every possible chain of deduction, yet it's common knowledge that he'll never deduce his own color and leave, so his not leaving cannot provide information to any meta-hypothetical islander. I admit I didn't so much work this out myself as see a similarity to the notion of an islander called "the Fool", brought up in some thread or other here.

Actually, come to think of it, since the Guru's original statement was "I see at least one person with blue eyes," and not "There's at least one person with blue eyes," then what happens is the 99 other blue-eyed people leave day 99, just as if the meeting-skipper had brown eyes or didn't exist (since there's no way the Guru could have meant him, and this fact is common knowledge).

Meanwhile, if a brown-eyed person misses the meeting, it makes no difference to the original solution. In fact, apart from the Guru, the non-blue-eyed folks can each be as irrational or nonexistent as we like, and the basic outcome is the same.

I'd like to add a couple variations of my own.

1. During the meeting, all the islanders were sitting in a large circle around the Guru. After she makes her big announcement, she goes up to each islander in turn and publicly asks, "Do you know the color of your eyes?" She keeps going around in this circle forever. What happens in this version?

2. Instead of holding a public meeting, the Guru tells each islander privately: "There is at least one person on this island with blue eyes." Then, every single day thereafter, the Guru says privately to each islander: "Yesterday, I spoke to every islander just once, and my message to every islander was identical." What happens in this version?

[Qaanol]

1. During the meeting, all the islanders were sitting in a large circle around the Guru. After she makes her big announcement, she goes up to each islander in turn and publicly asks, "Do you know the color of your eyes?" She keeps going around in this circle forever. What happens in this version?

Assuming it is common knowledge that each islander responds immediately, truthfully, and publicly when questioned,

Spoiler:

If there is no ferry and everyone stays on the island forever answering the Guru, then the first 99 blue-eyed islanders she asks will always say “No”, and the 100th blue-eyed islander will always say “Yes”.

If there is still a ferry that comes every night at midnight to take away all islanders who know their own eye color, the situation is more complicated. In particular, it depends how quickly the Guru goes from person to person asking questions. At some time on some day k, exactly 100-k of the blue-eyed islanders will have responded, all saying “No”. Immediately, the remaining k blue-eyed islanders, who have not yet responded, all know their own eye color, and will all leave at midnight.

No other islanders ever leave.

2. Instead of holding a public meeting, the Guru tells each islander privately: "There is at least one person on this island with blue eyes." Then, every single day thereafter, the Guru says privately to each islander: "Yesterday, I spoke to every islander just once, and my message to every islander was identical." What happens in this version?

Spoiler:

All 100 blue-eyed islanders leave on day 100, just like in the original puzzle.

[Gwydion]

I'd like to add a couple variations of my own.

1. During the meeting, all the islanders were sitting in a large circle around the Guru. After she makes her big announcement, she goes up to each islander in turn and publicly asks, "Do you know the color of your eyes?" She keeps going around in this circle forever. What happens in this version?

2. Instead of holding a public meeting, the Guru tells each islander privately: "There is at least one person on this island with blue eyes." Then, every single day thereafter, the Guru says privately to each islander: "Yesterday, I spoke to every islander just once, and my message to every islander was identical." What happens in this version?

To expound a bit more on #2:

Spoiler:

On day 1, every islander knows there is someone with blue eyes. On day 2, every islander knows that every islander knows that there is someone with blue eyes... On day 100, [every islander knows that]^n there is someone with blue eyes, which is exactly the same datum that is learned on day 100 in the original, just requiring a lot more speaking by the guru.

[Lenoxus]

Ah, I should have clarified that I intended my first variation to be "ferry-free". An islander saying "Yes" serves as a substitute for leaving on the ferry. Arguably, this is a simpler problem, because it doesn't require that people who know their own eye color must leave because of some taboo, but merely that they say "Yes, I know my own eye color", out of basic honesty. At the same time, the problem is arguably less interesting, and more of a stepping-stone to understanding the official version.

When I tried to solve it myself, I got the following answer, which I now believe is wrong:

Spoiler:

The period from the beginning until right after the Guru questions the last blue-eyed person is equivalent to the first day. Each round after that, starting with whoever is next to the last-questioned-blue and ending with the last-questioned-blue, is like a full day, so the Guru has to make 100 full rounds "plus change", only during this last round will all the blues answer "Yes."

However, I now realize Qaanol must be right; the hundredth (or otherwise last) blue to be questioned will say yes, and thereafter each other blue will say yes; it should take the Guru somewhere from 299 to 399 turns for all the blues to say yes, depending on how they are arranged in the circle.

Meanwhile, I agree with Qaanol's answer to my second variation.

[Qaanol]

When I tried to solve it myself, I got the following answer, which I now believe is wrong:

Spoiler:

The period from the beginning until right after the Guru questions the last blue-eyed person is equivalent to the first day. Each round after that, starting with whoever is next to the last-questioned-blue and ending with the last-questioned-blue, is like a full day, so the Guru has to make 100 full rounds "plus change", only during this last round will all the blues answer "Yes."

However, I now realize Qaanol must be right; the hundredth (or otherwise last) blue to be questioned will say yes, and thereafter each other blue will say yes; it should take the Guru somewhere from 299 to 399 turns for all the blues to say yes, depending on how they are arranged in the circle.

I’m not sure if you mean you believe both your spoiler’d paragraphs are wrong, or if you believe the second of them is not wrong. In fact, they are both wrong, and my previous answers are both right.

Spoiler:

No islander ever changes their answer. In the ferry-less version, the first 99 blue-eyed islanders who are asked, will each say “No” every time they are asked, forever. The 100th blue-eyed islander will say “Yes” every time he or she is asked, forever.

You can satisfy yourself that this is true by considering the n=2 case. The guru speaks, and it becomes common knowledge that there is at least one blue-eyed islander. The guru asks the first blue-eyed islander “Do you know your eye color?” That islander replies “No”. The other blue-eyed islander thinks “If my eyes were not blue, that person would have answered ‘Yes’, so my eyes must be blue.”

The guru asks the second blue-eyed islander, “Do you know your eye color?” That islander replies “Yes”. The first blue-eye islander thinks “If my eyes were not blue, that person would have answered ‘Yes’. If my eyes were blue, that person would have answered ‘Yes’. I have gained no information about my own eye color.”

For the “actual” logical train of thought with nested hypotheticals, you need to think about who knew what about whom when they spoke, and who gained information from that response.

[skeptical scientist]

The logic puzzle forum rules say that I don't have to use spoiler tags in spoilery solution threads, so I won't.

Instead of holding a public meeting, the Guru tells each islander privately: "There is at least one person on this island with blue eyes." Then, every single day thereafter, the Guru says privately to each islander: "Yesterday, I spoke to every islander just once, and my message to every islander was identical." What happens in this version?

On day 1, every islander knows there is someone with blue eyes. On day 2, every islander knows that every islander knows that there is someone with blue eyes... On day 100, [every islander knows that]^n there is someone with blue eyes, which is exactly the same datum that is learned on day 100 in the original, just requiring a lot more speaking by the guru.

That information is learned on day 1 in the original, not day 100. I think you meant that it's not useful until day 100, which is true, but requires some argument. In the original, the only information the islanders use on day n is n levels of hypotheticals, and these hypotheticals are still available in the variant (just not the further non-useful hypotheticals).

[Lenoxus]

In fact, they are both wrong, and my previous answers are both right.

D'oh! I was trying too hard to see it as akin to the original. You're right. (Also, I had misinterpreted your answer to mean that none of the non-blues would ever leave.)

Suppose that before the Guru even makes her big public announcement, it is agreed that her questioning will be in a clockwise direction. The first islander she questions will be named [1], and the last one [200]. The highest-numbered islander with blue eyes shall be called [X].

Immediately after the Guru says "I see at least one blue", and before she goes up to [1], it becomes common knowledge within the set of islanders [1] through [X-1] that everyone before [X] will say no, and that [X] will say yes. (Of course, [X] doesn't know that he is [X] until after the highest-numbered blue before him says "No.")

After [X] says yes, it becomes common knowledge to all the islanders that everyone after [X] (and before [1]) has non-blue eyes.

After this point, nothing can happen to add to the common knowledge pool for any set of islanders.

I admit that when I first read the original puzzle (on this blog post, not here on XKCD) I didn't work out the correct solution before reading it, or any other solution, and I was semi-skeptical of the answer. I know the answer didn't "feel" right, but that it or something like it had to be right (in part because if the answer were "nothing happens", the puzzle would be pointless, because that's not counter-intuitive!).

With most puzzles/problems, I don't tend to work out the correct solutions if the algorithms for doing so are not ones I have used or seen before. I'm smart but I ain't that smart

[Qaanol]

D'oh! I was trying too hard to see it as akin to the original. You're right. (Also, I had misinterpreted your answer to mean that none of the non-blues would ever leave.)

Wait, what? None of the non-blues will ever leave.

[Lenoxus]

D'oh! I was trying too hard to see it as akin to the original. You're right. (Also, I had misinterpreted your answer to mean that none of the non-blues would ever leave.)

Wait, what? None of the non-blues will ever leave.

Right, I should have been even clearer. I mean that I somehow originally read your answer as implying that the other blues leave next (not sure where I got that), and that when you said no one else leaves, you only meant that no one apart from the other blues leave.

[SheffJames]

I registered just for this. I've been lurking and following this puzzle for best part of a year now, and I still don't see it.

I just want, before I state my objection, to be clear on one thing. I am absolutely convinced that I am wrong and you guys are write. I'm certain that the logic holds true and that the chain of iteration is correct. I'm not arguing, I'm asking for clarification.

My problem is roughly within your Objection 2 above, but I think its slightly different. The alternative is I haven't fully understood your response to Objection 2.

Wendy knows
that Xavier thinks
that Yogi thinks
that Zach believes
that at least one islander has blue eyes

Thats fine, and I get your response to it. But it seems like it only works on one particular route through the people. It seems we're talking about two Zacs - a hypothetical one who might see any number of blue eyes and an actual one who Wendy can see looking at Xavier and clearly knows there is at least one pair of blue eyes. In fact, five minutes ago he was looking at Yogi so knows theres at least two.

This point:

Well, how about Xavier? Doesn't Wendy know that Xavier is blue-eyed? Wouldn't Wendy be able to see that Yogi can see that Zach can see Xavier? Yes, that's all correct. The problem is that in the original sentence, Xavier was another one of the people doing the "thinking". So in order for it to be true that "Wendy knows that Xavier thinks that Yogi thinks that Zach sees that Xavier has blue eyes", then Xavier would have to already know his own eye color, or Wendy would have to think that he does.

seems to be where you address this. But the problem I have is that we don't seem to need to define who Zach sees. With four people we know he can see at least two pairs of blue eyes and possibly three if Wendy's are blue. We also know that Xavier and Yogi are in the same position. In fact, if Wendy can see x pairs of blue eyes we know that everyone else can see x or x-1. Who is the hypothetical person Zach can see? Well, its either Xavier or Yogi, surely.

So we have one walk through that says:

Wendy knows
that Xavier can see at least two pairs of blue eyes which means that she knows he knows
that Yogi can see at least one of blue eyes which means that she knows he knows
that Zach can maybe not see any blue eyes at all.

Which seems fine. Nothing can happen until everyone knows Zach sees Blue eyes, from that. But we also have a walkthrough that says:

Wendy knows
that Zach can see at least two pairs of blue eyes which means that she knows he knows
that Xavier can see at least one of blue eyes which means that she knows he knows
that Yogi can maybe not see any blue eyes at all.

Which makes it not fine. Because she can put x,y,z in any order she wishes she knows that each of them see at least two pairs of blue eyes.

And thats where I'm stuck. Every answer thread I've read seems, to me, to ignore the fact that the order of he thinks that she thinks that he thinks can be put in any order whatsoever.

Does that make any sense?

I'm sorry for having to ask this. If I were you I'd hate me right now, but I've been reading thread after thread about this for, as I say, best part of a year and I just don't see it.

J

[phlip]

I think your post essentially boils back to this:

It seems we're talking about two Zacs - a hypothetical one who might see any number of blue eyes and an actual one who Wendy can see looking at Xavier and clearly knows there is at least one pair of blue eyes.

which is completely right. When you later talk about "W sees X sees Y sees Z" and then "W sees Z sees Y sees X", then they are two different hypothetical Zachs - in particular, different people are hypothsising about. In the second scenario, it's a Zach that Wendy is hypothesising may exist... in the former, it's a Zach that could be hypothesised by a Yogi that's behing hypothesised by a Xavier that's behind hypothesised by Wendy.

Say I'm on the island, and I don't know my own eye colour. I can hypothesise that if my eyes are blue, then Zach will see situation A, and do thing B in response. Whereas if my eyes are not blue, then Zach will see situation X, and do thing Y in response. Now, I don't know which of these is correct, they're both hypotheses. And the hypothetical Zach in the first option is a different to the hypothetical Zach in the second option. The actual Zach may be the same as one of these two options (if my facts are right and my reasoning is sound, then he should match one of them), but I don't know which.
Call this the first level of hypothesising.

Now, say you're an independent observer of all of this. You can see me, and determine that I'd be doing all the reasoning above, and come up with my two hypotheses. Now, because you can see my eye colour, you'll be able to determine which of those two hypotheses are true - you'll know that one of the hypothetical Zachs matches the real one, and the other is entirely imaginary. However, you can't simply ignore that imaginary one, as it's not irrelevant - yes, the real Zach won't actually act like that, but it's still relevant because my knowledge that it's a possibility will change the way I act.
Call this the 1.5-level of hypothesising.

Now, instead, say you're on the island along with me, Zach, and all the others. Now you, too, have incomplete information, and don't know your eye colour. You could hypothesize that if your eyes are blue, then I'll see a certain situation, while if your eyes are not-blue, then I'll see a different situation. And then, if I see that first situation, then I'll hypothesise that if my eyes are blue, Zach will see situation A,and do thing B in response, whereas if my eyes are not blue then Zach will see situation X and do thing Y in response. In the other hand, in that second situation, where your eyes are not-blue, then I'll instead hypothesise that if my eyes are blue, Zach will see situation A' and do thing B' in response, whereas if my eyes are not blue, then Zach will see situation X' and do thing Y' in response. So now there are four hypothetical Zachs, one seeing each combination of blue and not-blue eyes for you and me, and responding accordingly.
Now, I can see your eyes, so the real me can discount two of these hypothetical Zachs as being the real one. However, you don't know which two those are. Similarly, since you can see my eye colour, you know that one of the two Zach's I'm hypothesising in each case aren't real, but as before (in the 1.5-level) that doesn't make them irrelevant, as me considering them as possible will change the way I react to things, so you need to still consider them in that context.
Call this the second level of hypothesising.

The same reasoning continues, as more levels get added. And that's just the hypothetical Zachs for "you see me see Zach", not even counting the other paths like you seeing Zach directly, or "you see Zach see me" or what have you. The solution for the real puzzle nests this up to the 99th level (creating 2⁹⁹ hypothetical Zachs for each allocation of hypothetical eye colours to the 99 non-Zach blue-eyed actors) and then picks one of those hypothetical Zachs from the bottom of the nesting (specifically the one that sees everyone else as not-blue-eyed) and shows that its existance prevents people from leaving the island. However, after the guru announcement that hypothetical Zach learns new information, and as the days pass that new knowledge causes more knowledge that propagates up the nesting until it reaches the actual real person at the top.
Specifically, the particular hypothetical Zach at the bottom we're looking at is the one that you get by, every time someone in the chain thinks "either my eyes are blue or not-blue", we pick the wrong one... and then each day, the hypothetical person at the bottom of the pile realises that the not-blue option is wrong, therefore their eyes are blue, and the nested hypotheticals unravel another layer.

[SheffJames]

Now, I can see your eyes, so the real me can discount two of these hypothetical Zachs as being the real one. However, you don't know which two those are. Similarly, since you can see my eye colour, you know that one of the two Zach's I'm hypothesising in each case aren't real, but as before (in the 1.5-level) that doesn't make them irrelevant, as me considering them as possible will change the way I react to things, so you need to still consider them in that context.

There.

I'd totally discounted the existence of everyone else following their own individual chains of reasoning hadn't I.

Thanks so much for that. I can sleep now.

[hamsterofdeath]

i found this riddle somewhere else and wasn't satisfied with the recursive solution, so i came up with a simpler one:
everyone sees n or n-1 blue eyes. everyone goes looking for a counter. since all think alike, they will all pick the same counter. now they think: i will join the group that gathers if counter ticks = the number of blue eyed persons i see. if a group gathers one tick before it would have been my turn, i don't have blue eyes. otherwise, i do. it doesn't have to be days. could be minutes, they just need to pick the same timer.

and another one: (for this one, there need to be a sorting criteria. random will also do if the logic guys can handle it)
first guy does nothing: X
next guy comes, might have same color, might have different, one, doesn't matter: XX or YX or XY
everyone else either adds himself to the right if all have the same eye color or between the two guys having different colors.
in the end, it will look like this:
XXXXXXXXXXXXXXXXXXXXXXXXXXXX*last guy here*YYYYYYYYYYYYYYYYYYYYYYYYY

now everyone except the last one knows if he's in the blue group. now they just have to do the same thing in reverse until the last guy knows his color, and all blue eyes persons can leave on the first night.

what gave me the most trouble was the way the solution was presented:
"if there are 5, each lets the other 4 figure out if they are four. and recursively, each of those 4 lets each of the other 3 figure out if.." hey wait. there never are "the other 3", there are only "the other 4". the whole things breaks if you go several steps back because then you say something like "if there are 5 with blue eyes, then ...." but everyone either sees 99 or 100.
i came up with the solution above (the counter one) while trying to code the recursive algorithm. actually, i didn't manage to code the recursive one. i just couldn't - it just didn't make sense. go on and try to explicitly write down what each guy thinks each day, i'd be interested to see that. if i try, everything just collapses (except for the correct number)

[Gwydion]

Spoiler:

i found this riddle somewhere else and wasn't satisfied with the recursive solution, so i came up with a simpler one:
everyone sees n or n-1 blue eyes. everyone goes looking for a counter. since all think alike, they will all pick the same counter. now they think: i will join the group that gathers if counter ticks = the number of blue eyed persons i see. if a group gathers one tick before it would have been my turn, i don't have blue eyes. otherwise, i do. it doesn't have to be days. could be minutes, they just need to pick the same timer.

and another one: (for this one, there need to be a sorting criteria. random will also do if the logic guys can handle it)
first guy does nothing: X
next guy comes, might have same color, might have different, one, doesn't matter: XX or YX or XY
everyone else either adds himself to the right if all have the same eye color or between the two guys having different colors.
in the end, it will look like this:
XXXXXXXXXXXXXXXXXXXXXXXXXXXX*last guy here*YYYYYYYYYYYYYYYYYYYYYYYYY

now everyone except the last one knows if he's in the blue group. now they just have to do the same thing in reverse until the last guy knows his color, and all blue eyes persons can leave on the first night.

what gave me the most trouble was the way the solution was presented:
"if there are 5, each lets the other 4 figure out if they are four. and recursively, each of those 4 lets each of the other 3 figure out if.." hey wait. there never are "the other 3", there are only "the other 4". the whole things breaks if you go several steps back because then you say something like "if there are 5 with blue eyes, then ...." but everyone either sees 99 or 100.
i came up with the solution above (the counter one) while trying to code the recursive algorithm. actually, i didn't manage to code the recursive one. i just couldn't - it just didn't make sense. go on and try to explicitly write down what each guy thinks each day, i'd be interested to see that. if i try, everything just collapses (except for the correct number)

Spoilered for length. A few problems here, the main one dealing with the fact that all of your proposals require that a plan be in place and agreed upon. Of course, if the islanders were able to communicate and establish such a plan, the entire question is moot and there are numerous ways to determine one's eye color. Solutions that include statements like "they just have to all pick the same _____" or "they just need to start from ______ and go from there" tend to get tripped up by this, as that starting point needs to be logically deducible and not just convenient because "it works".

Additionally, any time a post starts by saying "since they all think alike" or something similar, the problem of superrationality tends to come up. Of course, since all the same-eyed islanders are symmetric and identical, they will reach the same logical conclusions. This, however, is insufficient to show that such a solution does, or must, exist, or to determine whether such a solution is optimal.

Everything does not, in fact, collapse when we write out exactly what people are thinking, and this is well-described in the OP. To help you out, let's have an island with 10 blue-eyed people, named 0-9 for convenience. Also spoilered for length:

Spoiler:

9 says
"I see 9 other blue eyed people, and if I have brown eyes, then 8 is thinking
'I see 8 other blue eyed people, and if I have brown eyes, then 7 is thinking
"I see 7 other blue eyed people, and if I have brown eyes, then 6 is thinking
'I see 6 other blue eyed people, and if I have brown eyes, then 5 is thinking
"I see 5 other blue eyed people, and if I have brown eyes, then 4 is thinking
'I see 4 other blue eyed people, and if I have brown eyes, then 3 is thinking
"I see 3 other blue eyed people, and if I have brown eyes, then 2 is thinking
'I see 2 other blue eyed people, and if I have brown eyes, then 1 is thinking
"I see 1 other blue eyed person, and if I have brown eyes, then 0 is thinking
'I see no other blue eyed people.' " ' " ' " ' " ' ".
This is true, even though 9 clearly knows that 1 knows that 6 doesn't have brown eyes, and that 8 knows that 4 knows that 2 doesn't have brown eyes, and that 0 sees at least 8 blue eyed people.

On the day the guru speaks, 9 thinks the same thing, except when he gets to the last level, 0 is thinking "I see no other blue eyed people, so I must have blue eyes because of the guru's statement' and leaves. " ' " ' " ' " ' "

The next day, 9 thinks the same thing, but 1 appends the following: Since 0 didn't leave yesterday, I must have blue eyes also" and leaves. ' " ' " ' " ' " ' "

Thus, on day 10, the thought process is as follows:
9 says
"I see 9 other blue eyed people, and if I had brown eyes, then 8 would have thought
'I see 8 other blue eyed people, and if I had brown eyes, then 7 would have thought
"I see 7 other blue eyed people, and if I had brown eyes, then 6 would have thought
'I see 6 other blue eyed people, and if I had brown eyes, then 5 would have thought
"I see 5 other blue eyed people, and if I had brown eyes, then 4 would have thought
'I see 4 other blue eyed people, and if I had brown eyes, then 3 would have thought
"I see 3 other blue eyed people, and if I had brown eyes, then 2 would have thought
'I see 2 other blue eyed people, and if I had brown eyes, then 1 would have thought
"I see 1 other blue eyed person, and if I had brown eyes, then 0 would have thought
'I see no other blue eyed people' and left on day 1.
Since that didn't happen, I must have blue eyes also" and 1 would have left on day 2.
Since that didn't happen, I must have blue eyes also' and 2 would have left on day 3.
Since that didn't happen, I must have blue eyes also" and 3 would have left on day 4.
Since that didn't happen, I must have blue eyes also' and 4 would have left on day 5.
Since that didn't happen, I must have blue eyes also" and 5 would have left on day 6.
Since that didn't happen, I must have blue eyes also' and 6 would have left on day 7.
Since that didn't happen, I must have blue eyes also" and 7 would have left on day 8.
Since that didn't happen, I must have blue eyes also' and 8 would have left on day 9.
Since that didn't happen, I must have blue eyes also" and 9 actually leaves on day 10.

This is obviously tough to follow, so I alternated single- and double-quotes to help keep track of who actually says what. I thought braces, brackets, and parentheses could help as well, but that just made it worse when I tried it. Ten is a larger number than <n> for most everyone who says "it collapses after <n> islanders", but obviously one could extend this pretty easily with cut/paste to as big an island as you can wrap your head around.

[hamsterofdeath]

let me rephrase my problem:

"if this obviously red apple was green, then *ultra complex deduction logic with several nested recursions". since that which the ultra complex algorithm predicted did not happen, the apple cannot be green."

i do not doubt the correctness of the solution, but i see it like this:

Code: Select all

boolean leaveToday(int daysPassed, int numberOfPersonsWithBlueEyesThatICanSee) = ....


my solution "return daysPassed == numberOfPersonsWithBlueEyesThatICanSee" represents the same function as the official solution, just without all the cpu cycles being wasted checking situations which are obviously never true to begin with.

[phlip]

my solution "return daysPassed == numberOfPersonsWithBlueEyesThatICanSee" represents the same function as the official solution, just without all the cpu cycles being wasted checking situations which are obviously never true to begin with.

Perhaps, but those "wasted cycles" as you put it aren't being spent calculating the answer... they're being spent proving the answer is correct, which is an aspect that doesn't come through in the "computer program" metaphor.

[Gwydion]

let me rephrase my problem:

"if this obviously red apple was green, then *ultra complex deduction logic with several nested recursions". since that which the ultra complex algorithm predicted did not happen, the apple cannot be green."...

my solution "return daysPassed == numberOfPersonsWithBlueEyesThatICanSee" represents the same function as the official solution, just without all the cpu cycles being wasted checking situations which are obviously never true to begin with.

Perhaps, but your solution begs the question - it assumes that anyone who sees n-1 blue eyes will leave on day n, provided that nobody left sooner. This is as arbitrary as any other counting method, sorting algorithm, or other artificial solution. Even though it's how things actually go down, there is no logical basis for that behavior without all of the other considerations I mentioned.

It's not obvious to anyone what color their own eyes are, right? So, each person envisions two possible world-states: one in which he has blue eyes, and one in which he has non-blue eyes. If I see 9 pairs of blue eyes, I might imagine there are only 9 such pairs on the island (mine are not blue), in which case the person next to me (blue-eyed) would only see 8 pairs. He might envision that a world with only 8 pairs exists (his might not be blue, in his mind), and thus might envision the person next to him seeing only 7 pairs. This is not as ridiculous as you seem to think - we're still inside MY head, and I don't know my eye color and am assuming my eyes are brown. If I'm wrong, then so be it - this is a hypothetical situation.

Of course, that guy (in someone else's head, in someone else's head, in my head) might see 7 pairs of blue eyes (even crazier) and imagine that he, too, has non-blue eyes. Obviously, that guy in real life can't possibly think that, but in this hypothetical situation inside my imagining of someone else's imagining of someone else's imagining of the world, he might. The idea of nested hypotheticals takes this to it's full conclusion: If I envision my eyes as non-blue, and then put myself in someone else's shoes imagining the same thing, who puts himself in another person's shoes... eventually we reach someone who hypothetically might be the only blue-eyed person - because everyone thinks they're non-blue eyed.

The same idea is at work whenever we do proofs by contradiction - assume something that isn't true, deduce something that would follow from your assumption, then show that this leads to an inconsistency. In other words, if I assume I have brown eyes, and demonstrate that *if that were true* X would happen, and then X does not happen, I don't have brown eyes. Try not to get caught up on the fact that I actually have blue eyes, but rather try to focus on the fact that by assuming I don't, I can demonstrate that something ought to happen, which in reality does not.

[Qaanol]

let me rephrase my problem:

"if this obviously red apple was green, then *ultra complex deduction logic with several nested recursions". since that which the ultra complex algorithm predicted did not happen, the apple cannot be green."

i do not doubt the correctness of the solution, but i see it like this:

Code: Select all

boolean leaveToday(int daysPassed, int numberOfPersonsWithBlueEyesThatICanSee) = ....


Here is one possible recursive implementation:

Code: Select all

bool leaveToday( int daysPassed, int numVisibleBlueEyed )
{
   if ( (numVisibleBlueEyed == 0) && (daysPassed == 0) ) {
      // A lone blue-eyed person leaves on the first night.
      return true;
   } else if ( (numVisibleBlueEyed < 0) || (daysPassed < 0) ) {
      // Cannot leave before Guru's announcement, and there cannot be negative people.
      return false;
   }
   // If the blue-eyed people I see didn't leave yesterday, but would have if they were the
   // only blue-eyed people, then I know my eyes are blue and leave today. Otherwise I stay.
   return leaveToday( daysPassed - 1, numVisibleBlueEyed - 1);
}


And here is the main program that each individual can be thought of as running:

Code: Select all

int main ( int argc, char *argv[])
{
   int numVisibleBlueEyed = 99; // Replace with 100 as appropriate.
   int dayCount = 0;
   while ( !leaveToday(dayCount, numVisibleBlueEyed) )
   {
      waitUntilTomorrow();
      numVisibleBlueEyed = numVisibleBlueEyed - bluesOnFerry( dayCount );
      dayCount = dayCount + 1;
   }
   boardFerryTonight( dayCount );
   return 0;
}


[Peeling]

Hello all I just came across this puzzle and worked out the 'official' answer. Then I had some further thoughts. I've read through the objections listed here and think I may have a new wrinkle to add: a non-inductive strategy that allows everyone who doesn't have a unique eye colour to get off the island:

Take an island with 100 people (it's easier on the notation than 200; bear with me) and an arbitrary number of eye colours.

It's common knowledge that:

Everyone who shares hypothetical eye colour A can see exactly the same pattern of numbers of eye colours A,B,C,D etc. in the people around them.

So if an A sees, for instance, 9A 40B and 50C, so will every other A.

Alan, who is one of the A's but doesn't know it, puts those numbers in ascending order, reserving two digits for each number:

094050

Bob, who is one of the B's but doesn't know it, puts HIS numbers in ascending order, reserving two digits for each number

103950

If Alan waits for 94,050 days before going down to the ferry, he knows that everyone he meets there also saw the same pattern.

If he arrives at the ferry alone, he knows there must have been an eye colour he alone couldn't see - his own - and has to admit defeat.

If there are other people there, he knows he has the same colour eyes as they do. They can all give their answer to the ferryman and leave the island.

Problem: It's possible for people of different eye colour to see the same pattern of numbers, but with the colours transposed.

For instance:

50A 40B 5C 5D

The Cs and Ds all saw the pattern 04 05 40 50, so would head down to the ferry on the same day.

Not a problem:

The only way for two or more groups to see the same pattern with colours transposed is if the groups are the same size.

So the Cs, upon reaching the ferry on the 4,054,050th day, will see 4C 5D and declare themselves confidently to be C. Likewise for the Ds

Problem: What about these situations:

48A 50B 1C 1D
48A 50B 2C

In both situations, two people will head down on day 14850 - but in one case their eye colours are the same and in the other they're different.

Not a problem:

In both cases, C (and equivalently D) know that the Bs saw either 01014849 or 024849. This is common knowledge between C and D. Therefore, they know that if the Bs are still around after 24,849 days, their (C and D's) eyes are different colours, otherwise they are the same.

I can't be sure I haven't missed anything, but it seems an interesting strategy - and one everyone could independently adopt as the 'best' because:

a) The numeric base of the pattern (in this case 100) is common knowledge
b) Ordering results small to large is sensible as it results in the earliest possible leaving date.

So in the original puzzle with 100B 100G:

Everyone waits (99*200)+(100) days, goes down to the ferry together and declares themselves to have whatever the minority colour is that they can see.

Obviously the guru can shortcut the process by making her announcement, but once the blues have gone the greens can follow the same strategy.

There may be a more mathematically optimal way to accomplish the same ends, involving less waiting - but if there is, fine: we're talking about perfect logicians here.

I'm sure someone will be able to spot a hole in it though

[jestingrabbit]

Yeah, the hole is that you're expecting that everyone will magically come up with the same way of thinking. Why would they? Why should they? They're not trying to work out their eye colour, they're just living their lives, seeing what they see, and drawing natural inferences from it.

[Peeling]

Yeah, the hole is that you're expecting that everyone will magically come up with the same way of thinking. Why would they? Why should they? They're not trying to work out their eye colour, they're just living their lives, seeing what they see, and drawing natural inferences from it.

Incorrect, so far as I can see. The 'official' solution depends absolutely upon the common knowledge that people will leave if they can figure out how. Anyone watching 99 blues to see if they leave on the 99th day would not be able to draw the correct inference from them staying unless he knew for certain that the only reason they didn't leave is that they were logically incapable of knowing their eye colour.

Also, the official solution similarly assumes everyone will figure out the same inductive solution, and pick the optimal version of it.

For instance, imagine a version of the 'official' solution where the 'one guy with blue eyes' at the core of the logic decides to follow the strategy of 'leaving one day after you know what your eye colour is'. If everyone adopts that strategy, it'll still work (people will just leave in twice as many days as before), but we (and they) are assuming it's common knowledge that nobody would pick that strategy and will instead pick the optimal one.

[t1mm01994]

Wait. That's false.
I think objection 11, 13 and 14 are most relevant. You see, as they are perfect logicians, they don't really have a choice. In your example, that person HAS to deduce that he's the only one, and HAS to leave, because the rules tell him so. It's common knowledge that everyone knows and follows the rules, and that everyone is a perfect logician.

[jestingrabbit]

Also, the official solution similarly assumes everyone will figure out the same inductive solution, and pick the optimal version of it.

In the correct solution, no one is figuring out an inductive solution. They are inferring based on the rules of action that are laid out in the problem statement ie they all know

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.

So, there's no possibility of the alternate version you described in your last paragraph: it breaks the rule in the fifth sentence. The denizens of the island aren't trying to be optimal or efficient, they are merely drawing what inference they can.

How can anyone draw the inference that someone will use your procedure?

[Gwydion]

I think my biggest objections to Peeling's suggestion are the following:

1) As has been mentioned, implementing this strategy among everyone would require some degree of cooperation. Why should the transformation from {eye colors} into a number of days be chosen your way? Why shouldn't it be an alphabetical ordering based on the visualized eye colors? Why should there be a leading zero? The official solution requires no artificial transformations or plans, but rather simple logic.

2) He suggests that islanders should be going to the ferry docks without actually knowing their eye color, with the intent of finding it out when they arrive. This violates the spirit of the puzzle, if not the explicit wording. The idea is that the islanders leave when they know their eye color. By going to the ferry sooner, despite not actually having that knowledge... I dunno, it just feels like that breaks the rules.

Also, the official solution similarly assumes everyone will figure out the same inductive solution, and pick the optimal version of it.

Actually, it doesn't matter how they choose to reason through the puzzle. What matters is that a particular method exists by which islanders with blue eyes can KNOW WITH CERTAINTY that they have blue eyes on day N following the guru's announcement. In addition, as has been demonstrated in the original thread and discussed at length, we've laid out a proof that it is impossible for them to KNOW WITH CERTAINTY on any day prior to day N. If it's impossible to know before day N, and possible to know on day N, the blue-eyed islanders will leave no sooner and no later than day N. If there's another way to determine one's eye color, it can't possibly do so faster than the given solution, and if it's slower then it won't be used, because these are perfect logicians who will deduce that fact through any and all possible means, simultaneously.

[skeptical scientist]

Incorrect, so far as I can see. The 'official' solution depends absolutely upon the common knowledge that people will leave if they can figure out how.

Not exactly. It says that they will leave if they figure out their eye color, but doesn't force them to take any actions in order to figure out their eye color. Think about it this way: if I'm an islander and some stranger brings a mirror to the island and holds it up in front of my face so that I can see my own eye color, I am then forced to leave, because I know my eye color. But if I could build a mirror out of beach sand, I don't have to. So any answer based on the islanders following a certain strategy with the intent of figuring out their eye color is misunderstanding the problem.

What actually happens as outlined in the original solution may look like the islanders following a strategy (leave on the nth night if you see n-1 people with blue eyes, and nobody else has left yet). But it's actually what the islanders are logically forced to do, just like if there was an islander on day 1 who couldn't see anyone else with blue eyes, he would be forced to conclude he's the guy the guru was talking about, and leave on the first night.

[Peeling]

I think my biggest objections to Peeling's suggestion are the following:

As has been mentioned, implementing this strategy among everyone would require some degree of cooperation. Why should the transformation from {eye colors} into a number of days be chosen your way? Why shouldn't it be an alphabetical ordering based on the visualized eye colors? Why should there be a leading zero? The official solution requires no artificial transformations or plans, but rather simple logic.

This is related to the very pertinent question jestingrabbit asked: "How can anyone draw the inference that someone will use your procedure?"

To answer your specific questions first, before dealing with the general:

It shouldn't be an alphabetical sorting for two reasons:

1. Ordering from lowest to highest is guaranteed to yield the smallest waiting period, and that is common knowledge Ordering alphabetically might not.
2. Ordering alphabetically would require common knowledge of what everyone would call each colour, which doesn't exist.

The leading zero, I only included for clarity (which clearly didn't work), to emphasise the two-digit 'base' of the algorithm. Obviously 014849 == 14849 in terms of number of days waited.

Strictly speaking, the optimal algorithm for 100 people would involve base 99 (since it's common knowledge nobody can see more than 99 of one colour), so '014849' would be 49 + (99*48)+ (99*99+1) = 14602, a saving of 247 days.

So, to the general question: does my solution require mutual planning, or only pure logic?

My answer is that I can't say for sure that the exact solution I laid out can be arrived at independently by pure logic, because I haven't taken the time to work out if it's the solution that's most efficient. In fact, I know it isn't: like I just said, I should have used base 99 instead of 100 for 100 inhabitants. The salient point is that there is, unquestionably, a way for the inhabitants to deduce their own eye colours (unless unique) using only common knowledge and direct personal experience without the guru speaking. That, to me, is a pretty big deal, because it strikes me that the raison d'etre of the puzzle is, in large part, to demonstrate the subtle necessity of the guru's words despite their superficial uselessness.

Once we know that there is a way for the inhabitants to deduce their own eye colours without the guru speaking, we are free to assume the 'perfect logicians' inhabiting the island share the common knowledge that it exists. We can also assume that the existence of the most efficient solution, howsoever it may differ, is also common knowledge.

2) He suggests that islanders should be going to the ferry docks without actually knowing their eye color, with the intent of finding it out when they arrive. This violates the spirit of the puzzle, if not the explicit wording. The idea is that the islanders leave when they know their eye color. By going to the ferry sooner, despite not actually having that knowledge... I dunno, it just feels like that breaks the rules.

I confess, I'm sailing close to the wind there, taking advantage of some physical idiosyncrasies of the puzzle's description. Certainly it would be very, very easy to shut the door on my solution by specifying (for instance) that each inhabitant is required to state their eye colour in private before they can associate with anyone else who is trying to leave. So I accept without hesitation that there is a closely similar puzzle to which the official answer is the only solution - and judging by the way the puzzle is presented, it has already been refined several times to explicitly exclude other 'wrong' answers. In that sense I'm not even saying the official answer is wrong: it seems clear that it's the surprising elegance of the official answer that people want to preserve, as opposed to the details of the puzzle. In which case, I'm just (maybe) demonstrating the need for a bit of belt-tightening.

Actually, it doesn't matter how they choose to reason through the puzzle. What matters is that a particular method exists by which islanders with blue eyes can KNOW WITH CERTAINTY that they have blue eyes on day N following the guru's announcement. In addition, as has been demonstrated in the original thread and discussed at length, we've laid out a proof that it is impossible for them to KNOW WITH CERTAINTY on any day prior to day N. If it's impossible to know before day N, and possible to know on day N, the blue-eyed islanders will leave no sooner and no later than day N.

[/quote]

I disagree on some points here, though not all.

I agree it is impossible for N islanders with blue eyes to know their eye colour with certainty via inductive reasoning based on the extra common knowledge introduced by the guru on any day prior to N after her statement. That is definitely the fastest they could work out their eye colour based on that set of common knowledge (and considerably faster than my method). What I dispute is that they needed that additional common knowledge to be able to leave. I think the implication that the island could have been around forever without anyone being able to leave prior to the guru's statement is wrong.

To me, both answers look very similar. Both involve people waiting for a number of days that is based on what they observe, and doing so on the assumption that everyone who shares their eye colour can and will deduce the same optimal strategy and follow suit. Indeed: the official answer looks like a subset of mine: if everyone is induced to count and encode just one colour rather than all those they can see, the day the lucky owners of that colour eyes can leave is radically hastened. But that doesn't stop the remaining greens following my strategy and leaving after the next 99 days.

Like I said, it's trivial to add a rider to the puzzle that defeats my solution. I think invoking apathy or fatalism on the part of the inhabitants is a bit weak, to be honest.

[skeptical scientist]

To me, both answers look very similar. Both involve people waiting for a number of days that is based on what they observe, and doing so on the assumption that everyone who shares their eye colour can and will deduce the same optimal strategy and follow suit. Indeed: the official answer looks like a subset of mine: if everyone is induced to count and encode just one colour rather than all those they can see, the day the lucky owners of that colour eyes can leave is radically hastened. But that doesn't stop the remaining greens following my strategy and leaving after the next 99 days.

Like I said, it's trivial to add a rider to the puzzle that defeats my solution. I think invoking apathy or fatalism on the part of the inhabitants is a bit weak, to be honest.

Your "solution" already violates one of the explicit rules of the puzzle: no communication. You are basically arranging for each person who sees a particular distribution of eye colors amongst the others to go to the ferry on day X, where X codes that particular distribution of eye colors. If they see others there, they can work out their eye color from the fact that all the others who also see distribution X have eye color Y, so they must have eye color Y as well, and all can leave. In effect, you are working out a code for the inhabitants to communicate to each other their eye color.

[Peeling]

To me, both answers look very similar. Both involve people waiting for a number of days that is based on what they observe, and doing so on the assumption that everyone who shares their eye colour can and will deduce the same optimal strategy and follow suit. Indeed: the official answer looks like a subset of mine: if everyone is induced to count and encode just one colour rather than all those they can see, the day the lucky owners of that colour eyes can leave is radically hastened. But that doesn't stop the remaining greens following my strategy and leaving after the next 99 days.

Like I said, it's trivial to add a rider to the puzzle that defeats my solution. I think invoking apathy or fatalism on the part of the inhabitants is a bit weak, to be honest.

Your "solution" already violates one of the explicit rules of the puzzle: no communication. You are basically arranging for each person who sees a particular distribution of eye colors amongst the others to go to the ferry on day X, where X codes that particular distribution of eye colors. If they see others there, they can work out their eye color from the fact that all the others who also see distribution X have eye color Y, so they must have eye color Y as well, and all can leave. In effect, you are working out a code for the inhabitants to communicate to each other their eye color.

The official solution also involves deducing your own eye colour to be the same as another group by observing their movements (staying on the island or leaving).

[t1mm01994]

The difference between the 2 is that in the "official" solution the islanders don't have to move somewhere to figure it out. In your solution, people have to gather by the ferry to figure out their eye colour, whereas in the official solution they merely have to stay put and look. Objection 13 is very close to yours.

[skeptical scientist]

The official solution also involves deducing your own eye colour to be the same as another group by observing their movements (staying on the island or leaving).

The exact wording is that

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.

Observing other people staying or leaving is explicitly the only communication allowed. Showing up at the ferry on a pre-specified night with the intention of figuring out your eye color based on the other people who show up that night is communication which violates this rule.

[jestingrabbit]

The salient point is that there is, unquestionably, a way for the inhabitants to deduce their own eye colours (unless unique) using only common knowledge and direct personal experience without the guru speaking.

This is false. You have to assume that they all want to work out their eye colour, and you have to assume that they all arrive at the same procedure. Even if I grant you that they all want to leave, how can you suggest that your proposed strategy is the one that they will all arrive at? Because they can't confer a single strategy that would work if they all knew about it demonstrates nothing.

[Peeling]

The official solution also involves deducing your own eye colour to be the same as another group by observing their movements (staying on the island or leaving).

The exact wording is that

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.

Observing other people staying or leaving is explicitly the only communication allowed. Showing up at the ferry on a pre-specified night with the intention of figuring out your eye color based on the other people who show up that night is communication which violates this rule.

Hmm. Ok, I'll go along with that. I'd managed to convince myself it was much the same, on the grounds that people would be going to the ferry knowing they would be leaving that night, and putting the last piece of the puzzle together when they got there.

Thanks I might put together a 'tribute' puzzle with modified constraints where my solution is the answer, because I think it's sort of neat

[Peeling]

The salient point is that there is, unquestionably, a way for the inhabitants to deduce their own eye colours (unless unique) using only common knowledge and direct personal experience without the guru speaking.

This is false. You have to assume that they all want to work out their eye colour, and you have to assume that they all arrive at the same procedure. Even if I grant you that they all want to leave, how can you suggest that your proposed strategy is the one that they will all arrive at? Because they can't confer a single strategy that would work if they all knew about it demonstrates nothing.

Like I said, I'm not sure the specific encoding I chose would be the most efficient, and thus the one chosen.

However, the existence of a strategy to deduce eye colour without the guru speaking implies the existence of a most efficient strategy - and if there are more than one strategies that are equally the most efficient, then there will be strategy that is the most 'uniquely' efficient.

Given that all the inhabitants are perfect logicians, the most uniquely efficient strategy would be common knowledge, as would be the need for everyone to utilize the same strategy in order for it to work. Thus they would all instantly and independently know the earliest day they could go down to the ferry and deduce their eye colour.