100 blue-eyed islanders puzzle: 3 questions

Question

I read the Blue Eyes puzzle here, and the solution which I find quite interesting. My questions:

1. What is the quantified piece of information that the Guru provides that each person did not already have?

2. Each person knows, from the beginning, no fewer than 99 blue-eyed people to be on the island. Then how is considering the 1 and 2-person cases relevant, if each person can dismiss these 2 cases immediately as possibilities?

3. Why must they wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

EDIT: Most answers seem to concentrate on question 1 which I understand partly: but I remain confused because of different answers. Can someone answer questions 2 and 3?

Answer 1

Just work out the case where there are 2 people, then 3 people, then 4 people. It's the same principle, just more mind-boggling, for higher $n$. When there are just 2 people the situation is pretty much clear. When there are 3 people, does each know that everybody knows that everybody knows that there are people with blue-eyes? (there was no typo in what I wrote). To make it clearer, give the people distinct names and ask yourself: if John has blue eyes, does he know that Jeff knows that Ted knows that there are people with blue eyes. Then answer the question: if John does not have blue eyes, does he know that Jeff knows that Ted knows that there are people with blue eyes. The answers are different. But, the answers become trivially 'yes' if it becomes common knowledge that there are blue-eyed people.

Answer 2

Let $n$ be a natural number and let us think of a statement: $P(n)$: "On the day $n$ all $n$ blue-eyed people leave." Now the piece of information the Guru provides is very important, as it makes $P(1)$ true. Indeed, if there was only one blue-eyed person and the Guru said nothing, that person could not deduce he/she is the only one with blue eyes, like described in the solution (I am assuming, however, that there is no other way to deduce this).

So with the information Guru provided, we know, that $P(1)$ holds, so now we can use mathematical induction to prove, that $P(n)$ holds for every natural number $n$. When proving this, we can use the similar steps and thoughts that are used in the solution for the case of two blue-eyed people.

Answer 3

I think the answer to Question 1 is that after the Guru has spoken they all know that they all know that they all know that they all know that (repeat as many times as you like) someone has blue eyes. Previously they did not know that, and the statement is only true when it contains at most 99 "they all know that"s.

Answer 4

With more than one blue-eyed islander, the guru's statement on its one is obvious to everyone, so in isolation it provides no information. As a result, no one heads for the ferry that night. However, without any more words being spoken, each passing day results in more information.

On day one, the guru's statement alone says "There is at least one blue-eyed person".

On day two, the guru's statement, plus the fact that the boat left empty, says "There are at least two blue-eyed people" (for if not, then someone would have left).

On day three, the guru's statement plus two observations of the boat, says "There are at least three blue-eyed people".

Now, the blue-eyed people can all see 99 others, so up to day 99 they still cannot deduce any more than they can see. And each is in the position that he knows there are at least 99 blueys, but he doesn't know if any of the blueys he can see knows that. On the 100th day, however, they have the one extra piece of information that is enough to complete the deduction.

Answer 5

The reason it's not "common knowledge" beforehand that there is someone with blue eyes is:

Let's simplify the case to four people other than the guru: Two (Alice and Bob) with blue eyes, and two (Carol and Dave). It is true that everyone can, in fact, see at least one person with blue eyes. Alice can see Bob, Bob can see Alice, and Carol and Dave can see both of them. However, Alice does not know that Bob can see anyone with blue eyes, or vice versa. Alice and Bob also do not know that Carol and Dave can see two people with blue eyes.

Now extend it to six people. Erin has blue eyes, Frank has brown eyes. Erin can see that Alice and Bob both have blue eyes, but as far as she knows, either one of them can only see one person [i.e. the other one respectively], so she does not know that Bob knows that Alice knows that there is someone with blue eyes.

Now extend it to eight people. Blue₄ can see Alice, Bob, and Erin all have blue eyes, but likewise does not know that Erin knows that Bob knows that Alice knows there is someone with blue eyes. Now extend it to ten people: Blue₅ does not know that Blue₄ knows that Erin knows that Bob knows that Alice knows. Now twelve, fourteen, etc.

This same logic, by the way, extends to why you can't shortcut and say that "people know in advance that nothing happens until day 99", because the Guru has not said there are two people with blue eyes, and [etc] does not know that Blue₄ knows that Erin knows that Bob knows that there are two people with blue eyes, until the first day has passed. (since it is common knowledge that if there had been only one, they would have left immediately)

Answer 6

The guru starts the doomsday clock. Before the guru speaks, there is no "day 1". Without the common reference time, every blue eyed person (BEP) lives happily with the knowledge that there must be either 99 or 100 BEPS. But there is no way to decide which is true. The common reference time is the key to the apparent paradox. Without it, there is no expectation for the timely behavior of others.

The guru's statement essentially informs everyone on the island, "you better hope all of the X BEPs that you see leave X days from today otherwise it means you have blue eyes". To a BEP, X=99. Otherwise X=100.

Here is slightly different view of where the recursion comes from vs that from the wikipedia page.

Every BEP knows there are either 99 or 100 BEPs. And they all know that every BEP they see either sees 98 or 99.

Alice BEP (like all BEPs ) knows there are either 99 or 100 BEPs.

Bob BEP knows that Alice is considering either the hypotheses {98,99} or {99,100} (Bob himself knows the true number is not 98, he hopes Alice is not considering 100) -- range=[98:100]

Carol BEP has the same view of what Alice is thinking as Bob does. Carol hopes that Bob thinks Alice is thinking [97:99] but realizes that if Carol herself has blue eyes, then Bob's Alice range is [98:100]. range=[97:100]

Dave BEP hopes Carol's Bob's Alice range is [96:99].

and so on....

On the 99th day, every BEP realizes that lastmost person in the chain of hope has not left. So they all leave.

Answer 7

Here's the story of one blue-eyed islander. The Guru said she saw someone with blue eyes. He looked around and thought "Hey, I don't see anyone with blue eyes. I guess she means me." And so he left right away.

Here's the story of two blue-eyed islanders. The Guru said she saw someone with blue eyes. They looked around and thought "OK, I see someone with blue eyes. I guess she means him," and they stayed. But the next day came, and they thought "Hey, that blue-eyed guy didn't figure it out. I guess he must have seen someone else with blue eyes, but I don't see anyone else with blue eyes. I guess that means me." And so they left together on the second day.

Here's the story of three blue-eyed islanders. The Guru said she saw someone with blue eyes. They looked around and thought "OK, I see two people with blue eyes. I guess she means one of them," and they stayed. A day passed, and nobody left, and they thought to themselves "OK, this is the day those two guys figure it out." But another day passed, and nobody left. The blue-eyed people thought "Wait; those two guys didn't figure it out yet. I guess they must have seen another person with blue eyes, but I don't see anyone else with blue eyes. I guess that means me." And so they left together on the third day.

Here's the story of four blue-eyed islanders. The Guru said she saw someone with blue eyes. They looked around and thought "OK, I see three people with blue eyes. I guess she means one of them," and they stayed. A day passed, and nobody left, but they were not worried; they knew it would take a couple of days. A second day passed, and nobody left, and they all thought to themselves "OK, this is the day those three guys figure it out." But another day passed, and nobody left. The blue-eyed people thought "Wait; those three guys didn't figure it out yet. I guess they all must have seen another person with blue eyes, but I don't see anyone else with blue eyes. I guess that means me." And so they left together on the fourth day.

...and this is why they have to wait the full 99 days. It's not important that the Guru can see someone with blue eyes, unless there's only one islander. What's really important is that, given that the Guru can see someone with blue eyes, "those blue-eyed guys" should be able to figure it out among themselves, and that takes a specific amount of time for a given number of blue-eyed islanders. It's only when they can't do this for a number of islanders that doesn't include you that it becomes clear you must have blue eyes too.

Answer 8

1. I think the information that the Guru provides, is that all blue eyed people have to leave. This starts the whole process of inductive reasoning.

2. The 1, 2 cases are relevant, because if I had blue eyes and I didn't know, I'd think others would leave at 99th day since each of them would reason other 98 would leave on 98th day, and so on. The number goes down with each blue guy's hypothetical inductive reasoning, where he thinks there could also be one less blue eyed people since he is not sure about himself.

3. On the first $n-1$ nights, they are not verifying. They are waiting, for the remaining $n-2$ blue guys to reason out their stuff. They know for sure nothing will happen on first $n-1$ days, because if there are really $n-1$ blue eyed people, they would each know nothing will happen on the first $n-2$ days and so on. This wait is unavoidable. Only interesting night would be the $n-1$th night, when everyone will leave if others saw only $n-2$ blue eyed, but won't if they also saw $n-1$ blue eyed (i.e. if the person thinking is himself blue eyed).

Answer 9

I believe the key question for a tribesman to ask after the Guru's statement is:

If I am not a blue, when would the blues I see be forced to leave?

They would then reason that the blues they see would ask the same question with one less blue:

If I am not a blue, when would the blues I see be forced to leave?

This continues recursively without a clear answer until the 2 blue's question is reached, in which case the 1 blue would be forced to leave the first night. Before the guru had spoken, that sole blue would NOT have left the island because of the knowledge of the color of their eyes. This is the key to why the guru's statement starts the countdown!!!

Update:

Here are the answers to your questions:

1. That signifies the day that 1 blue would have left.
2. We don't consider the 1 and 2-person cases directly. We consider the 99 case, which necessitates considering the 98 case, which necessitates considering the 97 case, .. which necessitates considering the 2 and 1-blue cases.
3. Blues know that either the other blues will leave on the 99th night (only 99 blues) or they are blue (and will leave on the 100th). If there were only 99, those blues would know that either the other blues will leave on the 98th night or they are blue. Etc..

Answer 10

What is the quantified piece of information that the Guru provides that each person did not already have?

The Guru provides the common knowledge that there is somebody with blue eyes. Basically, every person knows that $\exists$ somebody with blue eyes, and every person knows that every person knows that, and so on ad infinitum.

Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?

Because for this person (person A), there are two possibilities:

• He is blue eyed (100:100)
• He is brown eyed (99:101)

So A can't leave immediately.

For the second one, let's pick a person B in person A's visualization. B sees only 98. In B's mind (remember, B is a figment of A's imagination while visualizing option 2), there are two possibilities:

• He is blue eyed (99:101)
• He is brown eyed (98:102)

So, A knows that B can't leave immediately.

Now, in B's mind in A's mind, there are two possibilities for a person C to leave:

• He is blue eyed (98:102)
• He is brown eyed (97:103)

Again, two possibilities, A knows that B knows that C can't leave.

This keeps going, till we reach person Y in an Inception-esque layered imagination of the rest, who has two options:

• He is blue eyed (2:198)
• He is brown eyed (1:199)

If it is the latter, he can see a person Z and imagine his options:

• He is blue eyed (1:199)
• He is brown eyed (0:200) This is not possible, as there has to be at least one blue eyed person.

Z has only one option, then. But we can't just pick this because this option only comes into play if Y knew that he was brown eyed, which only comes into play if X knew he was brown eyed, and so on all the way back up to B.

So, on the first day, because Z doesn't leave, the idea of there only being one blue eyed person is ruled out.

Wasn't it ruled out from the beginning? Yes, however it could not be ruled out from the minds of the others while visualizing.

Remember, A knows that if he had brown eyes (9:101), then B would be considering the option that he has brown eyes too (98:101), even if that doesn't add up from A's perspective. We have to take into account what options are being considered.

Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

They don't know it. Each blue person knows that it's either 99:100 or 100:100, but can't pick. They need to wait to ensure that it works.

---

A simpler problem

Let me try to work out the second part again for 6 islanders, where the actual distribution is (3:3). The bullets are chronologically ordered, the nesting is Inception-esque imagination.

• Blue eyed person A knows that there are at least 2 blue eyed people. He knows that if he is blue eyed, the other blue eyes are thinking the same as him. But this isn't the only possible case. The lack of any definite knowledge means that they don't leave (yet). If he considers the case that he has brown eyes, he visualizes that:
  • Blue eyed person B knows that there is at least 1 blue eyed person. If there were 2, then both would be thinking the same thing, and again, due to lack of definite knowledge, they can't leave. It there is one, he visualizes that:
    • Blue eyed person C sees 0 blue eyed people. Concludes that he must be The One. Leaves.
• On the first day, no one leaves. On the second day,
  • Blue eyed person A knows that there are at least 2 blue eyed people. He knows that if he is blue eyed, the other blue eyes are thinking the same as him. The lack of any definite knowledge means that they don't leave (yet). However, if he considers that he has brown eyes, he visualizes that:
    • Blue eyed person B knows that there is at least 1 blue eyed person. If there were 2, then both would be thinking the same thing. If there is one (C), then B knows that C would have left the day earlier. That didn't happen. So.. there must be two. As both are thinking the same thing, both leave.
• On the second day, no one leaves. On the third day,
  • Blue eyed person A knows that there are at least 2 blue eyed people. He knows that if he is blue eyed, the other blue eyes are thinking the same as him. If there are only two blue eyed people, then they would have left the day earlier. Which didn't happen. So he must have blue eyes, and as all three are thinking the same thing, they all have blue eyes. The three leave.
• The brown eyes leave the next day.

Note that while initially it is clear that the number of blue eyes $>=2$, the number of blue eyes can be less from the point of view of someone when another is considering the option that he is brown eyed. The lower numbers only come in due to this "but what is he thinking" thought that gets nested.

Answer 11

1. The quantifiable piece of information provided is that at least one person on the island has to have blue eyes. Since they are perfect, logical machines, they will count how many individuals have blue eyes, and come to the conclusion that, if no other person has blue eyes, then they must, and they must leave the island.

2. If, however, they see at least one person with blue eyes, they have only the evidence that one person has blue eyes, and thus, shall remain. If, however, they see TWO blue-eyed people, they must assume that these two blue-eyed people are assuming that the other is the only one remaining, and thus shall wait for the two to leave. If, however, they see THREE blue eye people, they must assuem that each blue-eyed person is assuming there are two blue-eyed people, and that each of those two blue-eyed people will leave. Because they are perfectly logical beings, they can make no presumption of their own eye color, but cannot be aware of it either. But they are aware that other individuals can observe eye colors, and that they will base their own presumptions on those eye colors that they see, so they will presume that their own eye color is excluded, and that each blue-eyed individual also excludes their own eye color.

3. Is actually a short-form explanation of 2. In much, much shorter form, it is because they must exclude themselves from the count, even if they have blue eyes. Ironically, not a single person on the island will know their own eye color until the last day becsause of this exlusion requirement (They MUST stay if they do not have blue eyes), because they assume every blue-eyed person is exluding themselves as well.

Answer 12

Let's skip over the original solution, I'm going to assume you read that. I'm going to answer the questions stated:

Imagine we have 2 people on this island of 201. Bob, who has blue eyes, and jane, who has brown eye's.

1) What is the quantified piece of information that the Guru provides that each person did not already have?

The Guru gave information about the colour of bob's and Jane's eye's. Namely, Bob and Jane do not know if they have blue, brown, red or green eye's. They still don't know anything about there own eye colour on day 1, but following the original solution, they can deduce it on day 100.

2) Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?

Imagine that Bob tries to be smart. He decide that no-one will leave the first 99 days, since there are 99 blue-eyed people excluding himself. Jane also tries to be smart, she decide that no-one will leave the first 100 days, since there are 100 blue-eyed people excluding herself. But now what? They can't skip 99 or 100 days, because then the difference between what a blue-eyed and a brown-eyed person would do it no more. Hence they can't deduce anything from the other not leaving on day 1.

3) Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

Because they might be verifying something they already know, but they also communicate something they can not communicate otherwise. Bob know he can leave on day 100. Jane know she can leave on day 101. There is no way for them to communicate this information any other way.

Ps. How bummed out must Jane be to see 100 blue-eyed people leave on day 100. Perhaps the Guru can be nice and say "I can see someone who has brown eyes.", so that history can repeat itself and 100 brown-eyed people can leave another 100 day's later.

Answer 13

1.) The quantified piece of new information that the Guru provides is not 'at least one person has blue eyes' (except in the $n=1$ case), since everyone knew that already. In fact, this quantified piece of information is rather complicated.

If there is one islander, then the new information is exactly 'there is at least one person on the island with blue eyes'. Then the one islander knows that that one person must be them.

If there are two people on the island, then it's not news to the first islander that there's someone on the island with blue eyes: they can see that their friend has blue eyes. However, after a day has passed and their friend hasn't left, they know the following piece of information that they didn't know before:

The fact that there's at least one person on this island with blue eyes was not news to the other person on the island.

If there are three people on the island, then the new piece of information, with brackets added to show structure, is

The fact that (the fact that there's at least one person on this island with blue eyes was not news to the other islanders) was not news to the other islanders.

And so on.

In fact, it occurs to me that you can state the new piece of information for $n$ islanders rather simply if you don't mind hiding the detail of the islander's logical deductions. It is:

The information that the Guru can see at least one islander with blue eyes was not enough to convince the other islanders that they had blue eyes in $n-1$ days.

Or even:

I have blue eyes.

But I suppose that those don't really count as 'quantified'.

I think that it's because the new piece of information is so complicated (and only becomes more complicated as we increase the number of islanders) that this puzzle seems so counter-intuitive.

2.) This time, we'll start with $n=100$, and work back down. If I am on the island, and I look round, I see $99$ people with blue eyes. If you're on the island with me then, as far as I know, you might be seeing $98$ people with blue eyes and one person (me) with brown eyes. This is because I don't know my own eye colour. So the $n=98$ case becomes relevant.

Let's suppose that I am absolutely convinced that I have brown eyes, and that everyone else on the island is convinced that they have brown eyes, at least until they're proved wrong. I look at you, looking at $98$ people with blue eyes, and think, 'Haha! Each of those $98$ people is looking around and seeing $98$ people with blue eyes, but you probably think that you have brown eyes, so you think that those people can only see $97$ people with blue eyes.'

In other words, in my imagination, there are $99$ people on the island with blue eyes, and in my imagination of your imagination, there are only $98$. Then in my imagination of your imagination of someone else's imagination, there are only $97$. Eventually, we get to some sub-sub-...-sub-imagination where there are only one or two people with blue eyes even though all of the islanders in fact know that there are at least $99$.

Don't worry if you have trouble getting your head round that one. The human mind isn't designed to handle so many conceptual layers - that's why tools such as induction are so useful.

Answer 14

1. What is the quantified piece of information that the Guru provides that each person did not already have?

   • Certainty and possibility opening. Everyone knew each other's eyes color, up until the Guru stated someone had blue eyes. That someone could be you, and that is reciprocal to all players. He gave "a hint" that your eye color was blue, a hint you could eventually check.

2. Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?

   • Although they aren't possibilities, they are logical building blocks. The 1-person case is singular, but the 2-person case allows for the 3, 4, 5, n people cases to be inferred from it.

3. Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

   • Rephrasing: Why do a n group of people have to wait n-1 nights if on the first n-2 nights they are simply verifying something they know? The fact is, as stated on 1., they don't know their eye's colors, they have a hint that their eye's color is blue. As stated on 2., the process is based in inference, so, they need to check that no one figured their eye color during the n-1 nights to finally conclude that their eye color is, by the Guru's hint, blue. Since this process is common to all players, after n-1 nights everyone figures, by deduction, that each one's eye color is blue and as such, exit the island.

Answer 15

The answer to question 1, if we assume no one ever knew their eye color since the beginning of time on that island and that no one ever left the island, is that the Guru told every blue-eyed islander that their eyes were blue. Because only after she says that can the thought process below be followed by blue-eyed islanders. What she said has no effect on the islanders with other eye colors. After 100 days, no one else can leave until the Guru mentions another color.

Regarding questions 2 and 3, to illustrate why we need to wait 100 days, we need to consider what each blue-eyed islander thinks every other blue-eyed islander perceives. When we do that, we can clearly see why we need to go down to the case of 1 and 2 blue-eyed islanders.

Each blue-eyed islander thinks:

• I can see 99 blue-eyed islanders. If I am not blue-eyed, then:
  • Each of the 99 blue-eyed islanders I can see will see 98 blue-eyed islanders. If each of the 99 consider the possibility that they are not blue-eyed, then they will each think that:
    • Each of the 98 blue-eyed islanders they see will see 97 blue-eyed islanders. If each of the 98 consider the possibility that they are not blue-eyed, then they will each think that:
      • Each of the 97 blue-eyed islanders they see will see 96 blue-eyed islanders. If each of the 97 consider the possibility that they are not blue-eyed, they will think that:
        • ...
          • Each of the 2 blue-eyed islanders they see will see 1 blue-eyed islander. If each of the 2 consider the possibility that they are not blue-eyed, they will think that:
            • The one blue-eyed islander they see will leave today.
          • If no one leaves today, then the 2 they see will leave on the 2nd day.
        • ...
      • If no one leaves on the 96th day, then the 97 they see will leave on the 97th day.
    • If no one leaves on the 97th day, then the 98 they see will leave on the 98th day.
  • If no one leaves on the 98th day, then the 99 I can see will leave on the 99th day.
• If no one leaves on the 99th day, then I am blue-eyed and I shall leave with the 99 I see on the 100th day.

Answer 16

The passage of time is important input because an event happens every night, and that event provides information to every islander what the others know or do not know. Whether or not anyone leaves on a given night, the information content changes. By not leaving, everyone has communicated clearly, "I do not know my eye color".

When the guru speaks, he polarizes the group into two, let's call them groups S and groups T. Group S is blue-eyed, and so they see one fewer blue-eyed people than group T.

Everyone's question is then, do I belong to group S (snappy), or group T (tardy)?

And executes this algorithm: "I will leave the island on night X, where X is the number of blue people I see".

So for instance if there are 50 blue-eyed people, then group S is planning to leave on night 49, and group T on night 50.

Nobody knows whether he or she is part of group S or group T, but this comes to light on night 49 when group S leaves, leaving group T.

Of course, group T's travel plan is thereby wrecked! On night 49, everyone in group S knows they are in group S, and thereby know that their eyes are blue, and those in group T also know that they are group T. But all they know is that their eyes are not blue, which does not amount to knowing their own eye color, and so they must stay on the island forever.

So, why do the islanders go through this charade of waiting out all these days? Well, the algorithm requires it. They cannot simply trim 49 days out of the wait because that would require a collective decision. To trim 49 days of waiting you have to know that the two days in question are 49 and 50, of which 49 is the minimum. Everyone who plans to leave on night X knows that people with a different plan are either targetting X-1 or X+1, but does not know which! So there is no way to avoid having to count the days: nobody knows what "bias offset" value to subtract from the number of nights to shorten the waiting game.

If you look at this another way, counting the nights and leaving is a way for the islanders to communicate a message to all the other islanders. By waiting until night X and bailing from the island, each islander expresses the message "I saw X blue-eyed people on the day the guru spoke". The value of X is significant and so the days must be counted out earnestly; no shortcuts. It is this key piece of communication which triggers the exodus of blue-eyed people. If on day zero everyone were allowed to speak to say how many blue-eyed people he or she sees, then all the blue-eyed people could leave that same night, because only two numbers would be spoken (e.g. 49 and 50). And those uttering 49 would all know that they are part of group S.

Answer 17

Without outside information, every islander can prove, for every $k$, that

"Island logic" proves $P(k) \implies P(k+1)$

where $P(k)$ is the statement

(it is true and is common knowledge that) if nothing happens after $k$ nights then every person can see at least $k$ blue-eyed persons

The guru provides common knowledge [arbitrary finite chains of "X knows that Y knows that Z knows ..."] of $P(1)$, which implies all higher $P(k)$ and therefore a relationship between number of nights and number of blue eyes. After $k$ nights it forces common knowledge of the fact that everyone can see at least $k$ blue-eyed persons. At $k=99$, this reveals the exact eye-color distribution to all islanders.

Proof of $P(k) \to P(k+1)$: After the $k$th night, every person is known to see at least $k$ blue-eye persons. Anybody who sees only $k$ blue persons knows that those blue-ers see $k-1$ blue on each other and $1$ other (himself), and leaves the island the next night. Thus, $k+1$ nights of inactivity implies that everyone can see at least $k+1$ blue-eye persons. Everyone knows that everyone else can perform this deduction, so that $P(k)$ true and commonly known implies the same for $P(k+1)$.

Now, to the numbered questions.

1. The islanders do not have unlimited-depth common knowledge of the fact that there is at least $1$ blue-eyed person, nor of $P(1)$, before the guru speaks.

2. The inductive reasoning that proves $P(k)$, if unwound, contemplates a hypothetical island where an islander (seeing only $k-1$ blue-eyes) has non-blue eyes and thinks about another islander (seeing only $k-2$ blues) contemplating an island in which he has non-blue eyes, etc, arriving eventually at the $1$-person situation which finally has to confront the guru's statement deciding that case.

3. The extent of what is common knowledge is increasing every night, until critical mass is reached.

Answer 18

I'll take up the challenge in nbubis's comment (even though there are not yet $99$ answers), and try to give a precise answer. And since this is a mathematics rather than a philosophy site, I'll try to use some formulas to describe what is going on.

As has been noted, the technical notion of common knowledge is important here. Clearly there is in this problem need to distinguish between (the truth of) a proposition and the fact that some person knows this proposition to hold. In fact there is no need distinguish individuals (and actually only the blue-eyed ones really matter), and it suffices to state when everybody (in the problem) knows a proposition. So if $P$ is any proposition, I will note $E(P)$ a new proposition which states that everybody knows $P$ to be true. Since everybody applies logic flawlessly $E(P)$ implies $P$, but $P$ does not imply $E(P)$. And $E(P)$ does not imply $E(E(P))$ either, which is yet a new proposition; it will be convenient to abbreviate it $E^2(P)$, and define $E^n(P)$ similarly for all $n\in\Bbb N$. Finally some things (like the general state of affairs on the island, including the logico-compulsive behaviour of its inhabitants) are common knowledge; I will write $C(P)$ for $\forall n\in\Bbb N:E^n(P)$.

Let $n$ denote the number of blue-eyed inhabitants. Now for instance according to the problem statement $n=100$ is true, but $E(n=100)$ is false; in fact none of the inhabitants know that $n=100$. But on the other hand $E(99\leq n\leq 101)$ is true (all inhabitants know that $99\leq n\leq 101$, even though the way they know this differs). I'll focus on lower bounds; while $E^2(n\geq99)$ is false (while everybody knows that $n\geq99$ holds, the blue-eyed inhabitants don't know that the other blue-eyed ones know this), $E^2(n\geq98)$ does hold. Similarly for all $i$ one has $E^i(n\geq100-i)$ but not $E^i(n>100-i)$. The new information provided by the public statement of the Guru is $C(n>0)$; this implies $E^i(n>0)$ for all$~i$, of which the instance relevant to the problem is $E^{100}(n>0)$, which was not previously true.

While this points to the key factor in the explanation of the riddle, it is somewhat more challenging to describe in detail what happens with the state of knowledge during the $100$ days before the blue-eyes finally leave the island. For that I will denote by $L(i)$ the statement "on night$~i$, some islanders leave". By the problem statement it is always common knowledge when this happens, but I will still write $C(L(i))$ or $C(\lnot L(i))$ to emphasize this common-knowledge status.

The problem statement gives us the following fact, which is in fact common knowledge:

For any $i\geq0$ and $k>0$, one has $n=k\land C(\lnot L(i))\land E(n\geq k)\to C(L(i+1))$.$\quad(*)$

In words, if $n$ is actually $k$, and on some day no islanders have left (yet), and everybody knows that $n\geq k$, then some islanders will leave the next night. This is because the $k>0$ blue-eyed islanders see $k-1$ others, and know that there must be at least $k$ of them. The following is true, and (therefore, as its proof is based on logic only) common knowledge:

Lemma. For all $l,k\in\Bbb N$ one has $E^{l+k}(n>0)\land C(\forall i\leq k:\lnot L(i))\to E^l(n>k)$.

This states informally that with sufficiently general knowledge (i.e., a sufficient power of $E$ applied to it) of the fact that $n>0$, it will after $k$ successive nights of nobody leaving be clear to all that $n>k$, but this new fact will have lost $k$ of its levels of $E(\cdot)$. One could simplify the lemma and its proof considerably by replacing the powers of $E$ by $C$, and given that the Guru indeed provides $C(n>0)$, this would suffice to explain what actually happens. However the refined statement is helpful in understanding for instance why $E^{99}(n>0)$, which is true without the Guru speaking, will not suffice to bring anybody into action. I admit that the lemma does not very well express the temporal element of the problem; it implicitly supposes that the information contained in its hypothesis was available before $(*)$ had the first occasion to be applied, i.e., before night$~1$ (but not before night$~0$, as $C(\lnot L(0))$ represents the given initial state).

Proof by induction on $k$, uniformly in $l$. For $k=0$ the conclusion is among the hypotheses; there is nothing to prove. Now assume the statement for $k$, and also the hypotheses $E^{l+k+1}(n>0)\land C(\forall i\leq k+1:\lnot L(i))$ of the statement for $k+1$ in place of $k$. The second part of the hyposthesis implies the weaker $C(\forall i\leq k:\lnot L(i))$, so we can apply the induction hypothesis with $l+1$ in place of $l$, and get its conclusion that $E^{l+1}(n>k)$. We instantiate $(*)$ with $(i,k):=(k,k+1)$, giving $$ n=k+1\land C(\lnot L(k))\land E(n\geq k+1)\to C(L(k+1)), $$ which implies (because $C(\lnot L(k+1))\implies \lnot L(k+1)\implies\lnot C(L(k+1))$) $$ C(\lnot L(k))\land E(n>k)\land C(\lnot L(k+1))\to n\neq k+1. $$ If $H$ is the hypothesis of this last statement, we actually know $E^l(H)$ (from our assumptions and the conclusion of applying our induction hypothesis). This allows us to conclude $E^l(n\neq k+1)$, which together with $E^l(n>k)$ gives $E^l(n>k+1)$, completing the proof.

Now to the detailed description of what happens; our $100$ blue-eyes wait until they know that $n\geq100$ before $(*)$ forces them to leave. The lemma for $l=1$ and $k=99$ says this will happen provided $E^{100}(n>0)$ holds and $\forall i\leq99:C(\lnot L(i))$. Our Guru provides $C(n>0)$ and hence $E^{100}(n>0)$, and $C(\lnot L(0))$ holds from the problem statement. One still needs to wait for the $99$ other instances of $C(\lnot L(i))$ to provide the prerequisite facts for action.

Summarising, one has the following answers to the questions.

$1$. What is the quantified piece of information that the Guru provides that each person did not already have?

This is $C(n>0)$, and it is its instance $E^{100}(n>0)$ that is really new information, and necessary for any action to take place (higher powers are also new information, but $E^{100}(n>0)$ alone gets things moving). Note that this requires the statement of the Guru be public (giving the information separately to individual inhabitants would have no effect; indeed it is not new information to them), and moreover the fact that it is public must be public (a television broadcast would not suffice if the inhabitants could have some doubt about whether everybody was watching), and this again must be known to everybody, and so forth $100$ levels deep. (One really needs a very strong problem statement to ensure this. If any inhabitant had a doubt whether another inhabitant might maybe have some doubt whether ... some inhabitant was really paying attention to the Guru, the logic would fail.)

So there is genuinely new information in the making of the statement by the Guru, but it is not contained in the message she brings itself, but in the fact that it causes that (everybody is aware that)$^{100}$ there are people with blue eyes.

$2$. Each person knows, from the beginning, that there are no less than $99$ blue-eyed people on the island. How, then, is considering the $1$ and $2$-person cases relevant, if they can all rule them out immediately as possibilities?

While everyone knows that say $n>10$, wrapping it in a sufficient number of applications of $E(\cdot)$ makes it untrue. It is these wrapped-up statements that play a role in the reasoning.

$3$. Why do they have to wait $99$ nights if, on the first $98$ or so of these nights, they're simply verifying something that they already know?

Every night brings its new information, namely $C(\lnot L(i))$. While most of the times $\lnot L(i)$ itself was already known to everyone, the fact that it becomes common knowledge is genuine new information, and again this is essential for the problem.

Final remark. I note that I have used the rule that if $P\to Q$ holds, then $E^l(P)$ implies $E^l(Q)$. This might seem suspicious, as $E$ does not commute with all logical connectives, notably $E(P\lor Q)$ does not imply $E(P)\lor E(Q)$. Although I am not aware of all rules of the formalism, the one I applied is intuitively valid, by the "infallibly logical" nature of the inhabitants: if $P$ in fact implies $Q$, this will not escape their attention, and anyone who in addition knows $P$ to hold will therefore also know $Q$ to hold; in particular if everyone knows $P$ then they will also all know$~Q$.

Answer 19

Here is my take on question 2. Let's take $n=4$, the first non-obvious case, and look at the perspective of islander 1. He thinks, "I am not sure what my eye color is, so assume it isn't blue. I see three blue-eyed people, but they all also think they are not blue-eyed. Among them is my good friend islander 2." He begins to imagine what islander 2 thinks, creating a fantasy where he (islander 1) is not blue-eyed and putting himself in the head of islander 2.

His fantasy self thinks, "Now, I see islander 1, but he is not blue-eyed, so I only see two blue-eyed people. Among them is my friend islander 3." The fantasy islander 1 taking the role of islander 2 now begins to think what islander 3 is thinking, creating a fantasy where neither islanders 1 nor 2 has blue eyes and taking the role of islander 3.

His fantasy self's fantasy self thinks, "Now, I see both islanders 1 and 2, neither of which is blue-eyed, so I see only one blue-eyed person, the hated islander 4. I hope that guy picks up on the fact that he is the only blue-eyed person here! "

But the real islander 4 is two levels deep in his own fantasy and is waiting for one is the others to "realize" they are the only one with blue eyes. Since everyone is waiting, nothing happens that day.

So after one day, when islander 4 does not realize he is the only one with blue eyes, the fantasy of the fantasy of islander 1 realizes he is wrong and thus had blue eyes. Thus, the fantasy of islander 1 (playing the role of islander 2) reconsiders and on the second day thinks that today, both islanders 3 and 4 will realize they are the only ones with blue eyes.

However, the real islanders 3 and 4 are one level into their respective fantasies that two of the others will figure it out. Everyone is waiting, so no one does anything.

So after two days, the fantasy of islander 1 (as islander 2) realizes that he is wrong and actually has blue eyes. So islander 1 himself reconsiders and expects that today is the day the others all realize they are the only the with blue eyes.

But all of the others came out of their own fantasies as well, and are expecting that the other three "figure out" they are the only blue-eyed islanders today. Everyone is waiting, so no one does anything.

Three days have passed, all the fantasies have been dissolved, and yet no one has left. The only remaining assumption that islander 1 entertained was that he himself is not blue-eyed. He realizes that this must be false, and leaves the island. Everyone else has the exact same thought process, so they leave too.

So that's why the base cases are important even though none of them are realistic: until the last day, every islander is in some fantasy within a fantasy within...and in those fantasies, the island really does have fewer blue-eyed people. They don't communicate directly about their eye color, but by their actions and the common knowledge that they must be thinking identically, they do tell the others what they have deduced. Eventually they collectively deduce that everyone expects all the others to have blue eyes, so since they are perfect logicians, they realize they have blue eyes.

The fantasies are necessary because from the start, they all are in denial and all expect the others to be in denial as well, and it takes a few rounds of observation for the fact that it is denial to penetrate all levels of their consciousness.

As for question 1, the guru only plays the role of a reference point to synchronize their fantasies. Otherwise no one would know where in their deductions the others were. They are always trying to do deductions, but not knowing what the others' actions mean, they don't get anywhere until someone says "hey, think about it together."

As for question 3, I think this is already explained, since on the first 99 days, they are not verifying what they knew; they are actually escaping from some kind of Inception delusion.

Answer 20

The question doesn't ask for the solution to the puzzle, which it already linked to.

---

The first paragraph of the linked puzzle ends with:

[...] Everyone on the island knows all the rules in this paragraph.

The whole paragraph is crucial, but two strongly interacting aspects may be overlooked. First, "[t]hey are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly." This means that they will update their knowledge logically and act accordingly. Second, "[e]veryone on the island knows all the rules in this paragraph" is also a rule in the paragraph. It also refers to itself. That implies that everyone knows that everyone knows that [infinite repetition] everyone knows that everyone on the island knows all the rules in this paragraph. This is called common knowledge (which is much stronger than, say, universal knowledge: everybody knows $P$). Combined with the first aspect, this is sometimes called common knowledge of rationality or CKR, which is often used in game theory (although its full power usually isn't needed, as in this case).

What is the quantified piece of information that the Guru provides that each person did not already have?

"I can see someone who has blue eyes[,]" in itself already was universal knowledge. Its public announcement makes it common knowledge. This, together with the repeated non-leaving of islanders, launches a cascading set of common knowledge that will eventually include that (and which) 100 islanders have blue eyes. (The public observation, i.e., all islanders observe all islanders observe all islanders observe all islanders ... not leaving the island, can, technically, be viewed also as a public announcement.)

Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?

To get the blue-eyed islanders to realize that they are blue-eyed, they need to have i) common knowledge that at least 99 islanders have blue-eyes, and that, after that realization, ii) still nobody left. To get the common knowledge thing going it needs to pass through the 1 and 2-person cases.

Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

It is only after 99 nights, that they know that 99 nights wasn't sufficient for any blue-eyed islanders to figure out that they had blue-eyes themselves (notwithstanding CKR). After only 98 or less nights, this was still an uncertainty, not deducible and therefore not known. The islanders aren't "simply verifying something that they already know"; they are stepwise turning knowledge into common knowledge that is necessary for the last step.

---

NB: I believe the puzzle is more-or-less identical to (and therefore an adaptation of) "Muddy Children" (Fagin et al. 1995; Geanakoplos 1992), which is a textbook example in modal logic.

Keywords: epistemic modal logic, public announcement logic (PAL), dynamic logic of public observation, common knowledge

Answer 21

Sorry this answer became so long. If you want the two-minute answer, just read the Terminology then skip down to the Answers to the Questions. You can then fill in the details as desired.

Terminology

• Let $A, B, C, A_i$ denote the blue-eyed islanders.
• Let $A_i^*$ denote the proposition that $A_i$ has blue eyes (which does not imply that $A_i$ knows this).
• We'll use the standard symbols and rules of propositional logic.
• $A\leadsto P$ means islander $A$ knows that $P$ is the case, where $P$ is a proposition. The operator "$\leadsto$" is right-associative and has higher precedence than the logical implication operator "$\Rightarrow$".
• $\cal O$ is the proposition that there is at least one blue-eyed islander. This is what the Guru announces on day 1.

1 Blue-eyed Islander

To introduce use of this notation, let's briefly go over what happens when there is 1 blue-eyed islander $A$.

Day 1

After the Guru makes her announcement, it is the case that $$A\leadsto{\cal O}.\tag{1.1.1}$$ Since $A$ sees no islanders with blue eyes, she concludes it's her: $$A\leadsto A^*.\tag{1.1.2}$$ This fact entitles $A$ to leave the island on day 1, so we are done with the case of the 1 Blue-eyed Islander.

2 Blue-eyed Islanders

Before the Guru makes her announcement, the following statements can be said about blue-eyed islanders $A$ and $B$: $$A\leadsto{\cal O}\\ B\leadsto{\cal O}.\tag{2.0.1}$$ This follows simply from the fact that they can each see one other blue-eyed person on the island.

Day 1

After the Guru announces $\cal O$, it is the case that $$A\leadsto B\leadsto{\cal O}\tag{2.1.1}$$ as well as the one other permutation of this: $B\leadsto A\leadsto\cal O$. The above reads "$A$ knows that $B$ knows that $\cal O$." It is important to grasp at this point that this fact wasn't the case prior to the Guru's announcement. Even though both $A$ and $B$ knew there was at least one blue-eyed person on the island, $A$ didn't know that $B$ knew this, because for all $A$ knows, she may have brown eyes.

(2.1.1) can be written as $$A\leadsto B\leadsto(A^*\vee B^*).\tag{2.1.2}$$ The substitution ${\cal O}\mapsto A^*\vee B^*$ is valid in this particular context, because everyone else on the island other than $A$ and $B$ do not have blue eyes, which is known to both $A$ and $B$, and $A$ knows that $B$ knows this.

(2.1.2) can be written as $$A\leadsto(\neg A^*\Rightarrow B\leadsto B^*)\tag{2.1.3}$$ which will be useful for Day 2. To prove this, the following axiom is needed:

Knowledge Conjunction Axiom $$((A_i\leadsto P)\;\wedge\;(A_i\leadsto Q))\;\;\Leftrightarrow\;\; (A_i\leadsto(P\wedge Q))$$ $A_i$ knows $P$ and $A_i$ knows $Q$ if and only if $A_i$ knows $P$ and $Q$.

The proof for (2.1.3) is of primary importance, as it readily generalizes to any number of blue-eyed islanders and days, so a detailed proof is given here for the interested reader.

1. $A\leadsto(\neg A^*\Rightarrow(B\leadsto\neg A^*))$
2. $A\leadsto((B\leadsto\neg A^*)\Rightarrow(B\leadsto\neg A^*))$
3. $A\leadsto(((B\leadsto\neg A^*)\Rightarrow(B\leadsto\neg A^*))\wedge (B\leadsto(A^*\vee B^*)))$
4. $A\leadsto((B\leadsto\neg A^*)\Rightarrow((B\leadsto\neg A^*)\wedge (B\leadsto(A^*\vee B^*))))$
5. $A\leadsto((B\leadsto\neg A^*)\Rightarrow(B\leadsto( \neg A^*\wedge(A^*\vee B^*))))$
6. $A\leadsto((B\leadsto\neg A^*)\Rightarrow(B\leadsto B^*))$
7. $A\leadsto(\neg A^*\Rightarrow B\leadsto B^*)$

Step-by-step justifications:

1. $A$ knows that if she doesn't have blue eyes, then $B$ will know this.
2. $P\Rightarrow P$ tautology.
3. Knowledge Conjunction Axiom of step 2 with (2.1.2).
4. $((P\Rightarrow P)\wedge Q)\;\Rightarrow\;(P\Rightarrow(P\wedge Q))$ tautology applied to step 3.
5. Knowledge Conjunction Axiom applied to step 4.
6. Disjunctive syllogism applied to step 5.
7. Knowledge Conjunction Axiom applied to steps 1 and 6, and transitivity of $\Rightarrow$.

This just delineates in detail what many people can reason without the symbolic logic, which is the fact that $A$ knows that if she doesn't have blue eyes, then $B$ will know he does. The value of this formalism is that it extends readily into more complicated scenarios where our intuition may have trouble keeping up.

Day 2

No one left the island on Day 1, so no one knew they had blue eyes. In particular, $$\neg(B\leadsto B^*)\tag{2.2.0}$$ otherwise $B$ would have left. This fact is publicly known, so in particular $A$ knows it: $$A\leadsto\neg(B\leadsto B^*)\tag{2.2.1}.$$ Combining this with (2.1.3) via the Knowledge Conjunction Axiom gives $A\leadsto((\neg A^*\Rightarrow B\leadsto B^*)\wedge\neg(B\leadsto B^*)).$ Modus tollens yields $$A\leadsto A^*.\tag{2.2.2}$$ This is $A$'s ticket off the island, so she leaves today. These arguments for both days are symmetric in $A$ and $B$, so apply to $B$ as well. Both blue-eyed islanders leave the island on Day 2.

3 Blue-eyed Islanders

Before the Guru makes her announcement, $C\leadsto\cal O$, $B\leadsto\cal O$, and $A\leadsto\cal O$. In addition, $$A\leadsto B\leadsto{\cal O}\\ B\leadsto C\leadsto{\cal O}\\ C\leadsto A\leadsto{\cal O}.\tag{3.0.1}$$ For example, $A$ knows $B$ knows $\cal O$, because $A$ knows $B$ knows $C^*$.

Day 1

After the Guru announces $\cal O$, it is the case that $$A\leadsto B\leadsto C\leadsto{\cal O}\tag{3.1.1}$$ as well as the $3!-1=5$ other permutations of this in $(A,B,C)$. It is important to pause at this point and understand that this was not true prior to the Guru's announcement. Especially if one wishes to understand what quantified information the Guru is actually providing that each person didn't already have, this is it. Even though everyone knew that everyone else knew $\cal O$, that's only 2 levels deep. It required the Guru's public announcement to get to the 3rd level. $A$ did not know that $B\leadsto C\leadsto\cal O$ prior to her announcement.

Though the symbols provide the formalism, one informal but ituitive notion to consider is that of each person's "world"—the information available to a person. The world as seen through the eyes of $A$ is one in which there are 2 other blue-eyed people $B$ and $C$. Now consider the world of $B$ as considered by $A$. In this world, there is only 1 person whom with certainty has blue eyes: $C$. Moreover $C$ does not know if anyone else has blue eyes; $C$ does not know $\cal O$ until the Guru speaks, whose announcement penetrates through these worlds so that even in this doubly layered consideration, $C\leadsto\cal O$. In other words, $A\leadsto B\leadsto C\leadsto{\cal O}$. (Why am I reminded of the movie Inception?)

Moving forward as before, from (3.1.1), $$A\leadsto B\leadsto C\leadsto(A^*\vee B^*\vee C^*)\tag{3.1.2}$$ using the substitution ${\cal O}\mapsto A^*\vee B^*\vee C^*$. This is just representing the fact that any of $A$, $B$, or $C$ might be the one the Guru was talking about, which everyone knows that everyone knows etc. to arbitrary depth.

It follows from (3.1.2) that $$A\leadsto B\leadsto(\neg(A^*\wedge B^*)\Rightarrow C\leadsto C^*). \tag{3.1.3}$$ The proof for this takes on an analogous structure as the proof for (2.1.3) above.

Day 2

As before, no one left on Day 1, so it is concluded that $\neg(C\leadsto C^*)$ (as well as for $A$ and $B$). Since this is just as public as the Guru's announcement, everyone knows everyone knows etc. this to arbitrary depth. In particular: $$A\leadsto B\leadsto\neg(C\leadsto C^*)\tag{3.2.1}.$$ This fact, and its 5 other permutations, were not true until it was publicly observed that no one left on the ferry the prior midnight. Combining this with (3.1.3) via the Knowledge Conjunction Axiom, and applying modus tollens as before, yields: $$A\leadsto B\leadsto(A^*\vee B^*).\tag{3.2.2}$$ Now we are beginning to see a pattern here. This can be written as $$A\leadsto(\neg A^*\Rightarrow B\leadsto B^*)\tag{3.2.3}$$ which is identical to (2.1.3).

One might wonder, since $A$ knows that $\neg(B\leadsto B)$, because $B$ did not leave last night, can it be deduced from (3.2.3) that $A\leadsto A$?

The answer is no, but to see this it must be noted when certain knowledge was obtained. It would be more precise to write (3.2.3) as $$A\leadsto_2(\neg A^*\Rightarrow B\leadsto_2 B^*)\tag{3.2.4}$$ where $\leadsto_k$ denotes knowledge on Day $k$. The knowledge described in (3.2.3) was not known until Day 2, after observing that $C$ did not board the ferry, which means $\neg(C\leadsto_1 C^*)$, or that $C$ did not know she had blue eyes on Day 1. Similarly, $$A\leadsto_2\neg(B\leadsto_1 B^*).\tag{3.2.5}$$ Thus modus tollens cannot be applied to (3.2.4) and (3.2.5) because $B\leadsto_1 B$ and $B\leadsto_2 B$ are two different propositions.

Day 3

No one left again the previous night, so $$A\leadsto\neg(B\leadsto B^*).\tag{3.3.1}$$ Combined with (3.2.3), $A\leadsto A^*$ so $A$ can now leave the island. Same reasoning applies to $B$ and $C$, so all 3 islanders leave on Day 3.

$n$ Blue-eyed Islanders

Assume $2<n$. Prior to the Guru's announcement, it is a fact that $$A_1\leadsto A_2\leadsto\cdots \leadsto A_{n-2}\leadsto A_{n-1}\leadsto{\cal O}\tag{4.0.1}$$ including all other combinations and permutations of this chain of equal or lesser length, out of the the $n$ blue-eyed islanders $A_i$ for $i\in\{1,2,...,n\}$. Note that (4.0.1) includes only $n-1$ islanders, not $n$. This is because $A_1$ can imagine the world through $A_2$'s eyes, who looks through $A_3$'s eyes, ..., who looks through $A_{n-2}$'s eyes, who looks through $A_{n-1}$'s eyes, who gazes upon $A_n$ but in this world no information is available to guarantee any other blue-eyed person is on the island. So it cannot be concluded in this $(n-1)$-nested world that $A_n\leadsto\cal O$. Without the Guru's announcement, the longest chain of distinct blue-eyed islanders that can be stated is one which includes no more than $n-1$ islanders, such as (4.0.1).

Day 1

Once the Guru announces $\cal O$, the chain can now include all $n$ blue-eyed islanders. The guru's statement is equivalent to $n!$ statements, which are all the permutations of $A_i$ in $$A_1\leadsto A_2\leadsto\cdots \leadsto A_{n-1}\leadsto A_n\leadsto{\cal O}.\tag{4.1.1}$$ In anyone's world, no matter how deep the levels, the knowledge of $\cal O$ is always available.

Substituting as before for $\cal O$, this becomes $$A_1\leadsto A_2\leadsto\cdots \leadsto A_{n-1}\leadsto A_n\leadsto\bigvee_{i=1}^n A_i^*.\tag{4.1.2}$$ Using analogous steps to prove (2.1.3) from (2.1.2), it follows from (4.1.2) that $$A_1\leadsto A_2\leadsto\cdots\leadsto A_{n-2}\leadsto A_{n-1}\leadsto \left(\neg\bigvee_{i=1}^{n-1}A_i^*\Rightarrow A_n\leadsto A_n^*\right) .\tag{4.1.3}$$

Day 2

As in previous scenarios, since $A_n$ in particular didn't leave, it is publicly known that $\neg(A_n\leadsto A_n^*)$. Everyone already knew this so what new information is there? The new information may be expressed as another set of chain statements, of all $n!$ permutations in $A_i$ of $$A_1\leadsto A_2\leadsto\cdots\leadsto A_{n-2}\leadsto A_{n-1}\leadsto\neg(A_n\leadsto A_n^*).\tag{4.2.1}$$ This wasn't the case until the previous ferry left with no passengers.

Combining (4.1.3) and (4.2.1) together, using the Knowledge Conjunction Axiom and modus tollens yields $$A_1\leadsto A_2\leadsto\cdots \leadsto A_{n-2}\leadsto A_{n-1}\leadsto \bigvee_{i=1}^{n-1} A_i^*.\tag{4.2.2}$$ Following the same pattern as before, it can be deduced that $$A_1\leadsto A_2\leadsto\cdots\leadsto A_{n-3}\leadsto A_{n-2}\leadsto \left(\neg\bigvee_{i=1}^{n-2}A_i^*\Rightarrow A_{n-1}\leadsto A_{n-1}^*\right) .\tag{4.2.3}$$

Day $k$

Assume $1<k\le n$. On the previous night $A_{n-k+2}$ didn't leave, so it is publicly known that $\neg(A_{n-k+2}\leadsto A_{n-k+2}^*)$. The new information that wasn't previously available allows for all permutations and combinations in $A_i$ of identical length of the following statement to be made: $$A_1\leadsto A_2\leadsto\cdots\leadsto A_{n-k}\leadsto A_{n-k+1}\leadsto\neg(A_{n-k+2}\leadsto A_{n-k+2}^*).\tag{4.3.1}$$ Combined with the conclusions from the previous day, it is the case that $$A_1\leadsto A_2\leadsto\cdots\leadsto A_{n-k}\leadsto A_{n-k+1}\leadsto\bigvee_{i=1}^{n-k+1} A_i^*.\tag{4.3.2}$$ This can be proven from induction on $k$, which is omitted for brevity but is of the same form as the proof for (2.1.3). Also if one follows how (4.2.3) was derived from (4.2.2), (4.2.1) and (4.1.3) then this will also outline how one can prove this via induction.

Day $n$

(4.3.2) shrinks by one islander on each passing day, until finally when $k=n$ we are left with $$A_1\leadsto A_1^*.\tag{4.4.0}$$ Since these arguments have been symmetrical in all the $A_i$, $$\forall i\in\{1,2,...,n\}:A_i\leadsto A_i^*.\tag{4.4.1}$$ On Day $n$, all blue-eyed islanders leave the island.

Answers to the Questions

1) What is the quantified piece of information that the Guru provides that each person did not already have?

All $100!\approx 9.3\times 10^{157}$ permutations in $A_i$ of the statement $$A_1\leadsto A_2\leadsto\cdots \leadsto A_{99}\leadsto A_{100}\leadsto{\cal O}.\tag{5.1.1}$$ Everyone already knows ${\cal O}=\bigvee_{i=1}^{100}A_i^*$. That is not the value of the Guru's announcement. It is that everyone knows that everyone know that everyone knows ... that $\cal O$ is the case, that is the new information provided by the Guru's announcement that wasn't previously known. In contrast, if the Guru were to tell all the islanders in private the same fact $\cal O$, no islanders would be able to leave the island. So it is not simply the information content of her words that we must look at; there is additional information in knowing that everyone else heard her too. Correspondingly, each day that passes provides a new piece of information that is comparably subtle. When an islander doesn't leave, it is like another public announcement, which includes more information than just the fact that $A_i$ didn't leave last night. It is the knowledge that everyone else knows too. This knowledge is quantified in the answer to question 3 below. Eventually, after 100 days, these additional pieces of information will shrink (5.1.1) down to a fact that the islander can act upon. Namely, $A_i\leadsto A_i^*$ for all $i\in\{1,2,...,100\}$.

2) Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?

Yes, everyone knows that there are no less than 99 blue-eyed people on the island. The key concept to this problem is the recursive nature in which islanders deduce what they can, knowing only the information that they bring with them as they consider the world through one anothers' eyes. As $A_1$ does this from the perspective of $A_2$ who sees through the eyes of $A_3$, ..., who sees through the eyes of $A_{98}$, $A_{98}$ is left only to gaze upon and consider what $A_{99}$ and $A_{100}$ can possibly know within a world of such limited information. In this nested world 98 levels deep, we cannot take for granted that islanders $A_1$ through $A_{98}$ have blue eyes, just as we cannot take for granted that $A_1$ has blue eyes when we consider only her point of view on all the rest of the 99 blue-eyed islanders. Therefore considering the logic of a 2 blue-eyed-inhabited island is a worthwhile consideration. When 2 days go by in which $A_{99}$ and $A_{100}$ don't leave the island, then $A_1$ knows $A_2$ knows ... knows $A_{97}$ knows $A_{98}$ knows that someone else other than $A_{99}$ and $A_{100}$ have blue eyes. Now there's only 98 days to go.

If this escapes the intuition, then consider the case of 1, 2, and 3 blue-eyed islanders, and allow the logical formalism as deliniated above to provide the scaffolding that extends the intuition.

3) Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

Because they're not. Every day that passes, new information is provided that wasn't previously known. It's not as simple as a statement that islander $A_k$ didn't leave, because yes that was already known and anticipated. There is additional information in the knowledge that everyone else knows that everyone else knows etc. that $A_i$ did not leave the island. To be precise, on day $k$, for $k>1$, the new facts that weren't previously the case are all $100!/(k-2)!$ permutations and combinations in $A_i$ of $$A_1\leadsto A_2\leadsto\cdots\leadsto A_{100-k}\leadsto A_{101-k}\leadsto\neg(A_{102-k}\leadsto A_{102-k}^*).\tag{5.1.2}$$ With each passing day $k$, it is these facts that whittle away at the chain of knowledge (5.1.1) setup by the Guru for each islander on Day 1.

Answer 22

I'll add one answer to the 99 answers to appear here :)

I'll simulate a situation with $3$ islanders, named X, Y and Z. By symmetry, every predicate of the form $P(X, Y, Z)$ that holds will also hold under any permutation of $X$, $Y$ and $Z$, so I will not present the permuted statements.

Let's start after the Guru speaks:

$X$ thinks that

1. If I don't have blue eyes, then $Y$ and $Z$ would be the only people with blue eyes. $Y$ would think that
   1. If I don't have blue eyes, then $Z$ would see no one with blue eyes, and leave the next day.
   2. So, if $Z$ does not leave the next day, I must have blue eyes, and we both leave on the second day.
2. So, if $Y$ and $Z$ do not leave in two days, I must have blue eyes, and we all leave on the third day.

Now go back to before the Guru speaks. Why would this line of reasoning not work?

The obstruction is the innermost reasoning, where only one person has blue eyes. The sequence of reasoning starts by assuming "If I don't have blue eyes", and that propagates to the next person until there is only one person left. Note that this is all in one person's head. In this particular instance, where we have $3$ people, $X$'s reasoning in 1.2 above relies on the fact that

$X$ knows that $Y$ knows that $Z$ knows $B$

where $B$ is the statement "there is at least one person with blue eyes".

Note that this statement is not true before the Guru speaks. $X$ only knows that $Z$ knows $B$. $X$ does not know that $Y$ knows that $Z$ knows $B$, because $X$ doesn't know $X$'s eye color, and $X$ cannot assume that $Y$ knows $Y$'s eye color either.

So, the Guru does add the information: $X$ knows that $Y$ knows that $Z$ knows $B$.

Some may argue that 3 people is such a special case. Let's consider when we add another person. Let's say $W$ is added to the system. $W$ also has blue eyes.

How can we reason that

$X$ knows that $Y$ knows that $Z$ knows that $W$ knows $B$

is not true before the Guru speaks?

Again, $X$ doesn't know $X$'s eye color. When $X$ thinks for $Y$, $X$ knows that $Y$ knows that $Z$ knows $B$, because $X$ knows that $Y$ can see that $Z$ sees $W$ with blue eyes. Note that we need $W$'s blue eyes for $X$'s reasoning for $Y$. The fact that $Z$ also sees $X$ with blue eyes is known to $Y$, but is not known to $Y$ in $X$'s mind.

Permuting people, we know that

$Y$ knows that $Z$ knows that $W$ knows $B$

because $Y$ sees that $Z$ sees $W$ and $X$ with blue eyes. But $Y$ in $X$'s mind does not know this, because it relies on the fact unknown to $X$: that $X$ has blue eyes.

I believe this should be enough to convince most people that this situation generalizes to an arbitrary number of people. This is an answer to question 1: the consequence of Guru's speaking is that everyone knows that everyone knows that ... (repeat as many times as desired) that $B$ holds.

As some people have suggested, one variant of the problem is when the Guru tells everyone personally about $B$. This would yield no new information, and nothing will ever change.

Another interesting variant is if the Guru is specific and says that "$X$ has blue eyes" instead of just "someone has blue eyes". The consequence is obvious: $X$ will leave the next day. Everyone else will retain their behavior. It is somewhat counterintuitive because the sentence "$X$ has blue eyes" seems to give more information than "someone has blue eyes". One explanation of this situation that I can think of is that the statement "$X$ has blue eyes" actually gives no more information except to $X$, and the rules of the game force $X$ to leave the next day, so $X$ cannot give back information to others after $X$ leaves. In a sense, more information on the first day could lead to less information on all the following days because of the island rules.

Questions 2 and 3 are kind of answered, but I can try to elaborate more.

The reason smaller cases are relevant is because the strategy that each person derives from following "If I don't have blue eyes, then the next would think..." repeatedly until the one person case is reached. In a way, one can say that the small cases help everyone form a strategy. This can sound ignorant or deep, depending on what you think my understanding of the problem is. To me, it is quite an appropriate answer to the question.

To answer question 3, suppose everyone had a chance to discuss the strategy before the problem starts (without seeing each other's eyes). They could try to agree on cutting down the number of days if they can agree what the number is. Unfortunately, this is impossible. The problem is this "common number" has to be built from another relevant number, and each person only has as a source the number of blue-eyed people he/she sees. Since not everyone sees the same number of blue-eyed people, not everyone deduces the same number of days to cut down.

I will demonstrate why my strategy of cutting down the number of days will not work. (I do think my strategy is quite general though.) Suppose $f(x)$ is the number of days a person who sees $x$ blue-eyed people will cut down. $f$ should be a non-decreasing function, and $f(x) \le x - 1$ for every positive integer $x$. If there are $n$ blue-eyed people, these blue-eyed people will cut down $f(n - 1)$ days, while those without blue eyes will cut down $f(n) \ge f(n - 1)$ days. If $f(n) = f(n - 1)$, then it's a jackpot, and everyone cuts down the same number of days. Otherwise, those without blue eyes will cut down more days than those with blue eyes, and end up leaving on the same day as (or even before) those with blue eyes. So, to make it safe for all $x$, we must have $f(x) = f(x - 1)$ for all $x$. Since $f(1) = 0$, we end up with $f(x) = 0$ for all $x$.