Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Today I read the Blue Eyes puzzle here.
I also read the solution which I find quite interesting.
But there are three follow up questions which I don't know the answer to:

  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, 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?

  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?

Can someone explain?

EDIT: Most of the answers seem to concentrate on question 1, which, I guess, I understand partly, but I'm also feeling confused (because of different answers).
Also can someone share their views on questions 2 and 3?

share|improve this question
21  
It's a good puzzle, but certainly does not qualify as the hardest logic puzzle in the world. –  Ittay Weiss Sep 10 '13 at 10:03
5  
A useful reference is en.wikipedia.org/wiki/Common_knowledge_(logic) –  Andreas Caranti Sep 10 '13 at 10:47
1  
I've read the verions with the monks and the gnomes before. –  Raskolnikov Sep 10 '13 at 10:55
5  
Previously: Is there no solution to the “hardest” puzzle? –  Rahul Sep 10 '13 at 15:08
10  
Maybe after 99 answers, someone will post a correct and comprehensible solution. –  nbubis Sep 10 '13 at 18:47

25 Answers 25

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 time. It's only when they can't do this that it becomes clear you must have blue eyes too.

share|improve this answer
6  
But WHY doesn't brown eye leave after 100 days as well? Each islander sees at least 99 brown eyes, KNOWING that each of those knows that there are at least 98 brown eyes in the group? Every single brown eyed person knows that there are 99 or 100 brown eyes in the group, so that is common knowledge as well. –  SinisterMJ Sep 10 '13 at 16:31
14  
Because the brown-eyes see the blue-eyes leaving the island, and think "Hey, those blue-eyed guys figured it out. I guess that means there aren't any others, so my eyes aren't blue. But what color are they? There are lots of colors; just look at the Guru's green eyes. I still don't know." And so they stayed. –  The Spooniest Sep 10 '13 at 16:45
11  
This seems to me to be an explanation of the answer to the puzzle, but not an answer to the three enumerated questions the asker is asking about. –  Kevin Sep 10 '13 at 17:39
3  
I was attempting to illustrate the answers to the three questions. In the first question, the Guru doesn't give the islanders any new information: the new information comes from the fact that, given what the Guru said, they still can't figure it out. The answer to the second question is that the 1-person and 2-person cases establish how to determine if you have blue eyes (though you need a 3-person case to really get it going). These then go on to the third question: you need the full 99 days because that's how long it takes for people to figure it out if you don't have blue eyes. –  The Spooniest Sep 10 '13 at 18:10
1  
@TheSpooniest: Saying that the Guru did not give new information and that the new information came from the fact that, given what the Guru said, they still can't figure it out is self-contradictory. If there were no new information, then there would be nothing new to figure out, and the fact that indeed nothing was figured out would not be new information either. The speaking of the Guru does provide new information, but that information does not have to be contained in the message itself. –  Marc van Leeuwen Sep 14 '13 at 15:33

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.

share|improve this answer
8  
That's true, but it doesn't contradict what I wrote! –  Derek Holt Sep 10 '13 at 12:16
6  
@Keinstein, It is true that the islanders know both of those things. But those two facts alone are not sufficient to qualify as common knowledge. They need to know: "1) there are blue eyed people on the island. 2) Everyone is aware of fact 1. 3) Everyone is aware of fact 2. 4) Everyone is aware of fact 3... X) everyone is aware of fact X-1." for an X of any size. Prior to the guru's statement, each islander only knows facts 1 through N, which falls infinitely short of qualifying as common knowledge. –  Kevin Sep 10 '13 at 12:18
5  
@Keinstein I disagree. I have answered Question 1, by specifying something that they all knew immediately after the Guru spoke that they did not know before he spoke. –  Derek Holt Sep 10 '13 at 13:25
1  
@Keinstein: suppose there were 3 people, not 99. Then everybody already knew that “(1): at least one person has blue eyes”, and that “(2): everybody knows fact (1)”, but they didn’t already know that “(3): everybody knows fact (2)”. This statement (3) is the new knowledge the guru gives. Similarly, in the case with 99 people, the 99th fact in this series is the new information the guru gives. –  Peter LeFanu Lumsdaine Sep 10 '13 at 16:33
6  
@Songo It isn't common knowledge that the remaining people all have brown eyes; I believe it's only common knowledge that they do not have blue eyes. Of course, if every islander knew they had either blue or brown eyes, then I think the answer is yes, but otherwise, no. –  Andrew D Sep 10 '13 at 17:43

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 is causes (everybody to be 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$.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
2  
It has always been common knowledge that there are blue-eyed people. So the last sentence is not correct. –  Keinstein Sep 10 '13 at 11:29
6  
@Keinstein: Though everybody always knew there were blue-eyed people, it was not in a technical sense common knowledge until the Guru spoke. –  Marc van Leeuwen Sep 10 '13 at 12:33
2  
No. Everyone has seen that there are more than one people with blue eyes. Thus everyone knew that there are people with blue eyes. Everyone knows further that everyone has seen someone with blue eyes. Thus, everyone knows that everyone knows that there are people with blue eyes. As all know that all know this logic. The recursion goes ad infinitum. So it was common knowledge that there have been people with blue eyes. That has been emphasised in the linked version provided by A Googler. The only thing they didn't know was the exact number which became clear after 99 nights. –  Keinstein Sep 10 '13 at 12:46
13  
@Keinstein: You are wong. Suppose for simplicity there are just three pairs of blue eyes. Everybody knows there are blue eyes (they see two pairs). Everybody also knows that everybody knows this, because they know the two pairs they see can see each other. But nobody among the blue-eyed knows that the previous sentence it true (i.e. that everybody knows that everybody knows), because if those two pairs of blue eyes were the only ones, each of them would see only one pair, and the argument used (I can see two pairs that can see each other) would not apply for them. –  Marc van Leeuwen Sep 10 '13 at 14:04
1  
This is true for 3 pairs. Ok. But it doesn't imply that it is true for more pairs especially for 100. Otherwise I'd like to see a proof that constructs a real contradiction for $n∈\mathbb N$. We know that there cannot be a circle of knowing the explicit color. But that is not a contradiction against a circle of knowing that someone knows that there is at least one person with blue eyes. So suppose that there has been an external source of information without an initial moment that implanted the common knowledge that there is at least one blue-eyed person. Why should everyone know the truth? –  Keinstein Sep 10 '13 at 20:31

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

share|improve this answer
    
I do not think that the claim marked * is true. Consider the case where the guru announces "98 people who have blue eyes": everyone has known this before (universal knowledge), because everyone sees at least 99 blue-eyed people. Moreover, everyone knows that everyone knows: blue-eyed people see 99 other blue-eyed people, so these must each see at least 98 blue-eyed people. But there it stops. It is not true that everyone knows that everyone knows that everyone knows that the guru sees 98 blue-eyed people. This, however, is a necessary condition for "common knowledge". –  Ansgar Esztermann Sep 12 '13 at 8:35
    
You say: He could also have been saying "I got some sand in my eyes, I don't see anything[,]" and still the solution would be the same. Accepting this, it follows by symmetry that the blue-eyeds and brown-eyeds will act the same, contradicting the original answer. A way out of this contradiction would be to say that the original answer is wrong, and all brown-eyeds and blue-eyeds leave on the 100th day. –  Fillet Sep 12 '13 at 8:46
    
The symmetry is that there are "100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes)." The original guru statement could possibly break the symmetry, as it refers to blue eyes. If the guru statement is "I have sand in my eyes", then you have no reason to break the original symmetry. The world views are also symmetric, blue sees 99 blue and 100 brown, brown sees 99 brown and 100 blue. –  Fillet Sep 12 '13 at 9:13
    
@AnsgarEsztermann I tossed it out. My bad. –  Glen The Udderboat Sep 12 '13 at 14:07
1  
This is the best answer in my opinion, thanks! –  Philip Feb 16 at 3:56

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, noone 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.

share|improve this answer
3  
I think the real challenge is that there were also more than $99$ days before the Guru spoke yet nothing happened. Therefore something must have changed due to the Guru speaking; it did provide new information. –  Marc van Leeuwen Sep 10 '13 at 12:50
2  
It didn't provide new information so much as a coordinating action to begin counting ferry departures. The people were sitting in a state of N=99 or N=100 blue eyed people. –  Kyle Hale Sep 10 '13 at 16:04
3  
@KyleHale it must have provided new information, since in the absence of new information, how can anything change? –  Ittay Weiss Sep 10 '13 at 18:32
2  
Suppose that a given person on the island can see k people with blue eyes. The information given by the guru is then, "if k blue-eyed people are gone after k nights, then my eyes are brown, otherwise my eyes are also blue." –  Jaycob Coleman Sep 10 '13 at 20:03
1  
I will also add: the only way the islanders have to communicate with each other is to get on the ferry or not. The Guru's information is "Today is the day you would get on the ferry if you were the only person with blue eyes." All logic flows from there. Which you can see why it isn't really information, it's more of a ... decision? Again, it's firing the starting pistol. –  Kyle Hale Sep 10 '13 at 21:55

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. Blue4 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: Blue5 does not know that Blue4 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 Blue4 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)

share|improve this answer
    
The induction starts at 3 blue eyed people not with 2. –  Keinstein Sep 10 '13 at 13:29
1  
@Keinstein how does that mean it's not useful, informally, to describe the case with two? –  Random832 Sep 10 '13 at 13:31
1  
Lets take A, B, C, D, E, F where A, B, C are blue and D, E, F not. Then A nows that B sees C and that C sees B, B knows that C sees A and A sees C, C knows that A sees B and B sees C. The other three know that. Thus everyone knows that everyone sees someone blue. –  Keinstein Sep 10 '13 at 13:43
    
Doesn't matter, since my point is about what people know about what other people know: i.e. that C doesn't know that A knows that B sees C. Describing the A/B case is useful for explaining it this way, since the facts of A/B are equivalent to what C knows in A/B/C. –  Random832 Sep 10 '13 at 13:54
1  
I'd love to meet these Alice and Bob, they're all over the mathematics world, even in modern physics. –  MyUserIsThis Sep 10 '13 at 16:14

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
If the guru add no information, then nothing can change. Imagine that it is a written law that all blue-eyes people must leave. A law known to anybody. Without the guru's words nothing will happen and no-one will leave. So the Guru must add some information (look-up complete knowledge). –  Ittay Weiss Sep 10 '13 at 18:36
    
@IttayWeiss The new knowledge is that "nobody else left". –  Manishearth Sep 10 '13 at 18:41
    
that isn't it either, since the guru did not say that. The question is: at the instance the guru speaks, what new information does at least one of the people have that (s)he did not have before. The answers can't be 'nothing' since then behavior can't change (and if the guru said nothing, then nobody ever leaves). So the answer must be something, and it must be some piece of information not knows before guru speaks, yet known immediately afterwards. –  Ittay Weiss Sep 10 '13 at 18:49
    
@IttayWeiss The new information is "nobody left". See the last section, it becomes clearer as the thought process is outlined carefully. Information need not be externally injected. –  Manishearth Sep 10 '13 at 18:56
1  
@IttayWeiss Ah, so we do agree :p I thought we were talking about incremental knowledge on each day; that's where the confusion seemed to be coming from. I'll correct that. –  Manishearth Sep 10 '13 at 20:40

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.

share|improve this answer
    
This doesn't answer question 1.: What information has been provided by the Guru? $P$ is common knowledge as all statements are common knowledge. $1$ is not the information that the Guru provided. This number is a conclusion that arrived one day after her statement. To which knowledge refers this conclusion and which information has been added? –  Keinstein Sep 10 '13 at 11:44
2  
The statement $P(n)$ is wrong. It is in fact a non-statement for all $n\neq100$ as it makes a false side-remark that there are $n$ blue-eyed people. It is a side-remark because it is not part of what $P(n)$ states, or else $P(n)$ would just state "there are $n$ blue-eyed people and they all leave on day $n$", something that cannot be proved by induction simply because it is false for $n\neq100$. You probably meant $P(n)$ to be "if there are $n$ blue-eyed people then they will all leave on day $n$", but this doesn't work either with induction (the induction hypothesis gives a vacuous truth). –  Marc van Leeuwen Sep 10 '13 at 12:43

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.

share|improve this answer

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.

share|improve this answer
    
This is dual to the other one: "The inductive reasoning that proves $P(k)$ [the statement 'it is true and common knowledge that if $k$ nights have passed uneventfully, then everyone can see at least $k$ blue-eyes'], 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.". –  zyx Sep 13 '13 at 18:38
    
Looks like we had the same idea at the same time. –  Ryan Reich Sep 14 '13 at 5:11

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.

share|improve this answer
    
Sorry to deprive you of the honour of having the fourth longest post on the site with a score of $0$, but I had to upvote ;-) –  Donkey_2009 Oct 9 '13 at 8:35
    
Thanks! I came to the party after it ended, but still wearing my party hat. –  Matt Oct 9 '13 at 16:40

Ok may be we can see it as recursion with base case 2 blue eyed people. So lets talk about the case of three blue eyed persons. As everyone is highly logical persons they can easily think about the 2 eyed base case. So lets take one of the three blue eyed person. He can see other 2 blue eyed persons, So as he can easily deduce the 2 eyed situation so he knows that the second day the other two must leave. But as the case they don't leave. So he can easily say he also have blue eyes. So they all leave on 3rd day. Similarly. in case of 4 blue eyed persons. Lets take one person and he can easily deduce the situation of three. So if there are M blue eyed persons then at Nth day all will leave.

share|improve this answer
  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).

share|improve this answer

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..
share|improve this answer

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$.

share|improve this answer
  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.

share|improve this answer
1  
the question is what new piece of information do the guru's words provide. Since they each know blue-eyed people exist, your answer does not address that. –  Ittay Weiss Sep 10 '13 at 18:39
    
They all already know blue-eyed people exist, IF there is more than one blue-eyed person. If there are none that they can see, they must be the one. It's an absolute quantity. At LEAST one, but possibly more. They haven't been told how many, just that at least one must exist, because presumably the oracle cannot lie. A more interesting question might ask what would happen if the oracle CAN lie. I suppose a better way to phrase the first conclusion is that at least one blue-eyed person can be observed by the oracle. –  Zibbobz Sep 10 '13 at 18:47
    
but each of them already knows that there is at least one person with blue eyes since there are lots and lots of blue-eyed people. –  Ittay Weiss Sep 10 '13 at 19:13
    
And they can come to the conlusion that if they are not blue-eyed, then that many blue eyed people must exist, but if they ARE, then there must be that many +1, all information that they could already conclude. It is not the fact that blue eyed people exist that they were informed of, nor the number that exist, but that there is a quantity that can be observed and includes as many people as either they can see, or they can see plus one. Without the knowledge, they could only conclude that a certain number exists, and they cannot conclude what anyone else knows either. –  Zibbobz Sep 10 '13 at 19:27
    
I don't understand your distinction between they can conclude that "there is a quantity that can be observed and included as many people as either they can see, or they can see plus 1" and that without the knowledge "they could only conclude that a certain number exists, and they cannot conclude what anyone else knows either". Of course with and without the information they can conclude quite a lot about their own knowledge and the knowledge of others. For instance, "everybody knows blued eyed people exist" is a statement known by everybody. So, I think the distinction you aim at is unclear. –  Ittay Weiss Sep 10 '13 at 19:39
  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.
share|improve this answer
    
Dear Mr. Downvoter. The best way to improve a post is to comment on it, not just downvoting. –  Doktoro Reichard Sep 12 '13 at 16:10

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.

share|improve this answer
    
Who downvoted this, and WHY? –  Dorus Sep 12 '13 at 15:28

Consider the time before the guru gave her hint. Assume that the people already knew the general solution to this puzzle. If someone starts to count the days and watches what's going on after 99 days. What information does he get? He comes to the conclusion:

  • “I have blue eyes or
  • someone started to count at a different day or
  • someone didn't count the days at all.”

So there is no logical evidence that the first conclusion is the right one. This is just a hint to the answer of question 1. But it's a puzzle, right?

Questions 2. and 3. are very closely related to each other and are covered by the other answers.

Maybe we could try some other questions in order to find alternative answers to questions 2. and 3.:

Let us assume the Guru talked to 3 people on the first day, the next day she told other 3 people what she did a day before, the next day another 3 persons, and so on until all people know it. How would the answer change if she also told everyone what she will do in the next days?

Edit: I wanted to keep the Idea of a puzzle. So my answer:

The main problem is that the people have no common algorithm to find out their own eye-color. They know that one way to link their own eye-color to the other ones would be an event that depends on the number of blue-eyed people. So counting the nights would be an approach. Assuming that there are infinitely many nights there are also infinitely many order isomorphisms between the integers and the set of nights (using later as greater than).

  1. The Guru marks a point in the time line. Thus, we need only a number that can be assigned to this unique point in the time line. This will be the day between 0 and 1, fixing the isomorphism between the integers and the nights. This also defines a mapping from the natural numbers into the set of nights.

  2. and 3. Technically the people need only to know when night 98, 99, 100 and 101 are. Unfortunately there is no way to define a good starting number after the guru has spoken. A blue-eyed person sees that another blue-eyed person sees at least 98 blue-eyed person and does not know whether the other person would agree with him upon 98. On the other hand a non-blue-eyed person would think 99 is small enough. Thus not all of them will know which night would be the best one to start at. So they need an algorithm that definitely ends. That is to start counting the nights from 1. That would always work as if there would be only one person with blue eyes he would have got additional information (that there are blue-eyed people on the Island at all) from the Guru and could leave in the following night. 1 is also the largest number that is non-ambiguous as for two blue-eyed people neither of them knows that he/she has blue eyes.

As already said, from the visual inspection there are still at least 2 different isomorphisms that must be considered if we would start to count at a higher number. This would not lead to a unique solution. Thus, mapping the next night after the event to 1 would solve this ambiguity. Using another increment than 1 would need communication between the people, which is impossible. So the most simple algorithm that they know must be followed. And this needs its time.

EDIT2 As far as common knowledge is involved the important information that has been given by the Guru is that in the next night all those blue-eyed people leave which know that they are the single unique one.

Suppose that common knowledge about the existence of blue-eyed people implies that there exists an algorithm to find out how many people have really blue eyes. Then this algorithm is useless before the Guru spoke if it involves any communication between the people. Especially all algorithms that count days before certain people leave or don't leave cannot be performed as the counters are not synchronized yet. As nobody can communicate with any other one person might be at day 24894043 and the other at day 2.

If common knowledge about the existence of blue-eyed people would have been impossible beforehand, then everyone would know his/her eye color immediately after the Guru spoke as all conclusions would be possible unsynchronized. While waiting 99 days is only useful if everyone starts waiting at the same day.

On the other hand common knowledge is not necessarily involved if a person realizes his/her eye color. Thus common knowledge is a nice tool, but not very helpful in this questions.

share|improve this answer
3  
How is this an answer? What does "counting the days" mean that is relevant to this problem (if there is nothing special about the being days counted, counting is not relevant). I don't see how the first part is even a hint. –  Marc van Leeuwen Sep 10 '13 at 14:16

I know this puzzle in a slightly different variant, which may also shed some light on the questions.

Basically, the story goes like this: A stranger comes to a remote village, spends one night there during which he cheats with a number of wives, then leaves. It so happens (don't ask me why) that every husband knows about all the cheaters except for his own wife. The guru then asks each husband to publicly declare his wife a cheater the very day he knows this for sure. After N days, all the cheated husbands have come forward. Prove that the number of cheaters is exactly N.

The difference is that in the blue eyes case there is information that they could have had before, whereas in this variant the cheating is news revealed by the guru after the stranger left, which starts the whole thing. But it does not really matter, the logic still works in both cases. The recurrent midnight deadline is critical for being sure. And, barring anyone being busy with irrelevant business at the time, all the affected should be able to come forward the very next second after midnight in the N-th day.

My counter-question, though, is: what does this have to do with modal logic? I do not see a $\square$ or a $\lozenge$ symbol in the answers above. I am not being picky: if there is a modal connection, I am really interested. Thanks.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.