Blue eyes riddle: what information is gleaned after the first night?

Question

There are good explanations on this site and xkcd of the inductive reasoning leading to the riddle’s solution, but nowhere have I found an answer to the following aspect:

Exactly what information is learnt — and by whom — after the first night?

My question is triggered by the following train of thought:

• everybody knows that everybody sees at least 98 blue pairs of eyes
• with this knowledge, everybody concludes that nobody will leave during the first night
• since everybody knows that everybody will derive this, it seems to me that “nobody leaves” is common knowledge
• if it indeed is common knowledge, then no new information is learnt, so the second day is exactly like the first
• in this case, nobody would ever leave, because the system is static

Assuming that Randall Munroe’s solution is correct, my statement on common knowledge must be incorrect. However, I am unable to prove that.

I think the crucial point here is that all hypotheses that involve less than 98 pairs of blue eyes are irrelevant because every observer knows that no observer can observe a lower number. This intuition collides with the tower of nested hypotheses constructed in the inductive proof. So which way is right, and which way will lead to the immediate collapse of this universe?

Please refrain from answering with cases that involve less than 4 blue-eyed people: consider that my reasoning above requires that everybody knows that everybody sees at least two pairs of blue eyes. There are no induction steps within my question nor should they be needed to answer my question.

Thanks to @TimC’s answer I was able to come up with a more precise way of asking my question, the core of it is “why do all nested hypotheses need to be considered?”.

Answer 1

I'll try to answer the question directly, without simplifying to a smaller case.

Proof with recursion, rather than induction

If there are 100 blue eyed people on the island, person 1 sees 99 blue-eyed people.

Let's number them person 1 through person 100 (without loss of generality).

Person 1 imagines that person 2 sees either 99 blue eyed people (case 1A) or 98 blue eyed people (case 1B).

Person 1 imagines that in the case 1B, person 2 imagines person 3 sees either 98 blue eyed people (case 2A) or 97 blue eyed people (case 2B).

Continue this chain of recursion 99 times and you get:

Person 1 imagines that person 2 imagines that person 3 imagines... ... ...that person 97 imagines person 98 imagines that person 99 imagines that person 100 sees either one blue eyed person (case 99A) or zero blue eyed people (case 99B).

After night one, person 1 (which, since this was done without loss of generality, is all 100 people) can all simultaneously agree that everyone else is no longer imagining a hypothetical where there is only one person.

Because of this, they all now know that case 99B is impossible - more importantly, though, they know that everyone else knows case 99B is impossible.

Why does this work?

Each person does not know the color of their own eyes.

When these people imagine another person's perspective, they must imagine two hypotheticals - one where that person sees the imaginer's eyes as blue, and one where that person sees the imaginer's eyes as non-blue. Recursively, when they imagine another person imagining yet another person's perspective, they must then imagine two perspectives again, for a total of four possibilities. This would grow exponentially, but the solution of the puzzle only requires them to expand one arm of the tree.

This means that when person 1 imagines person 2's perspective, there are two hypotheticals: either person 1's eyes are blue, or they are not blue. There are two people's eyes who are indeterminate in this hypothetical. Person 1 still doesn't know what color their eyes are, so they must imagine multiple hypotheticals for what person 2 might be deducing from.

Similarly, when person 1 tries to imagine what person 2 might imagine person 3 thinks, person 1 must now evaluate four cases again - either person 1's eyes are blue or not blue, and either person 2's eyes are blue or not blue. At each layer of hypothetical, the color of another person's eyes is lost, because "person 1 imagining person 2 imagining person 3" doesn't know the colors of any of those three people's eyes.

After the first night, everyone, including the hypothetical people, knows that there is more than one person with blue eyes. Person 1 knows that person 2 is no longer imagining person 3 imagining person 4 imagining person 5 imagining... ...person 98 imagining person 99 imagining that person 100 is the only blue eyed person.

Appendix: The entire expansion the recursion

Definitions:

• Person(N) - The n'th person on the island (ordered 1-100 without loss of generality).
• Hypo(N) - The n'th layer of imagination, starting from Person(N), assuming that every person in the chain imagines their own eyes to be non-blue. For example, in Hypo(1), Person(1) imagines that Person(2) sees 98 pairs of blue eyes.

Hypo(1): Person(1) imagines that Person(2) sees 98 pairs of blue eyes.

Hypo(2): Person(1) imagines that Person(2) imagines that Person(3) sees 97 pairs of blue eyes.

Hypo(3): Person(1) imagines that Person(2) imagines that Person(3) imagines that Person(4) sees 96 pairs of blue eyes.

...

Hypo(99): Person(1) imagines that Person(2) imagines that Person(3) imagines that Person(4) imagines that Person(5) imagines that Person(6) imagines that Person(7) imagines that Person(8) imagines that Person(9) imagines that Person(10) imagines that Person(11) imagines that Person(12) imagines that Person(13) imagines that Person(14) imagines that Person(15) imagines that Person(16) imagines that Person(17) imagines that Person(18) imagines that Person(19) imagines that Person(20) imagines that Person(21) imagines that Person(22) imagines that Person(23) imagines that Person(24) imagines that Person(25) imagines that Person(26) imagines that Person(27) imagines that Person(28) imagines that Person(29) imagines that Person(30) imagines that Person(31) imagines that Person(32) imagines that Person(33) imagines that Person(34) imagines that Person(35) imagines that Person(36) imagines that Person(37) imagines that Person(38) imagines that Person(39) imagines that Person(40) imagines that Person(41) imagines that Person(42) imagines that Person(43) imagines that Person(44) imagines that Person(45) imagines that Person(46) imagines that Person(47) imagines that Person(48) imagines that Person(49) imagines that Person(50) imagines that Person(51) imagines that Person(52) imagines that Person(53) imagines that Person(54) imagines that Person(55) imagines that Person(56) imagines that Person(57) imagines that Person(58) imagines that Person(59) imagines that Person(60) imagines that Person(61) imagines that Person(62) imagines that Person(63) imagines that Person(64) imagines that Person(65) imagines that Person(66) imagines that Person(67) imagines that Person(68) imagines that Person(69) imagines that Person(70) imagines that Person(71) imagines that Person(72) imagines that Person(73) imagines that Person(74) imagines that Person(75) imagines that Person(76) imagines that Person(77) imagines that Person(78) imagines that Person(79) imagines that Person(80) imagines that Person(81) imagines that Person(82) imagines that Person(83) imagines that Person(84) imagines that Person(85) imagines that Person(86) imagines that Person(87) imagines that Person(88) imagines that Person(89) imagines that Person(90) imagines that Person(91) imagines that Person(92) imagines that Person(93) imagines that Person(94) imagines that Person(95) imagines that Person(96) imagines that Person(97) imagines that Person(98) imagines that Person(99) imagines that Person(100) sees no people with blue eyes.

At each layer of the hypothetical, each hypothetical person is imagining a world where they do not have blue eyes. At 99-hypotheticals deep, a world is imagined (being imagined being imagined... being imagined) where only one person has blue eyes.

Answer 2

Let's start with a simpler question. Suppose there were three blue-eyed people - then what information do the three people learn on the first night?

Before the first night, blue-eyed people see two blue-eyed people, and reason that there must be either two or three blue-eyed people total.

These people can reason hypothetically about the two cases of their eye color. They can say "Suppose I had brown eyes. What would other people believe?"

In this hypothetical case (let's call it Hypo Case 2), there are two blue-eyed people on the island. Those two people each see one other person with blue eyes, and reason that there must be either one or two blue-eyed people total.

The blue-eyed people in Hypo Case 2 do not know whether there are one or two blue-eyed people total before the first night. After the first night, since no one left, the blue-eyed people in Hypo Case 2 know that there must be two blue-eyed people total, and so they know that they are blue-eyed.

So that's what the hypothetical people have learned. What have the real people learned?

Before the first night, the blue-eyed people know that there are either two blue-eyed people who don't know whether they have blue eyes, or three blue-eyed people who don't know whether they have blue eyes.

After the first night, the blue-eyed people know that there are either two blue-eyed people who know that they both have blue eyes, or three blue-eyed people who don't know whether they have blue eyes.

So the knowledge of how many blue-eyed people there are has not changed, but the knowledge of the what the blue-eyed people know has changed.

---

In the 100 blue-eyed person case, the change in knowledge is similar, but with more hypotheticals. There are people in Hypo Case 99 reasoning about people in Hypo Case 98 reasoning about ..., and only at the bottom of the stack of hypothetical cases does something change. But some knowledge does change - a case is eliminated, not in the mind of a real person, but in the mind of a hypothetical person. And cases in the minds of hypothetical people do matter, because real people base their beliefs and actions off the actions of hypothetical people.

Answer 3

This is your mistaken assumption, I think:

no new information is learnt [...] the system is static

There is one new piece of information learned after each day: another day has passed and nobody has left. These incremental pieces of information aren't enough for anyone to solve the problem for the first 99 days, but when all 100 "nobody left that day" pieces of information are put together, it's enough for everyone to solve the problem.

---

As usual with this puzzle, it helps to think of a simpler case with fewer than 100 people. Let's say just two people on the island, Alice and Bob. Each of them can see that the other one has blue eyes, and the oracle says she can see someone with blue eyes.

• On day 1, Alice knows the oracle can see Bob with blue eyes. If Alice herself has non-blue eyes, then Bob will leave tonight.
• On day 2, Alice knows Bob didn't leave on night 1, which means Alice must have blue eyes.

Or let's say three people, Alice, Bob, and Charlie.

• On day 1, Alice knows the oracle can see Bob and Charlie with blue eyes. If Alice herself has non-blue eyes, then Bob and Charlie will each apply the above two-person logic and both will leave on the second night.
• On day 2, Alice knows that nobody left on night 1, but that was a given anyway, since she can see two blue-eyed people.
• On day 3, Alice knows that nobody left on night 2, which means Alice must have blue eyes.

Similarly with four people, Alice, Bob, Charlie, and Dorothy.

• On day 1, Alice knows the oracle can see Bob, Charlie, and Dorothy with blue eyes. If Alice herself has non-blue eyes, then Bob, Charlie, and Dorothy will each apply the above three-person logic and both will leave on the third night.
• On day 2, Alice knows that nobody left on night 1, but that was a given anyway, since she can see three blue-eyed people.
• On day 3, Alice knows that nobody left on night 2, but that was a given anyway, since she can see three blue-eyed people.
• On day 4, Alice knows that nobody left on night 3, which means Alice must have blue eyes.

Basically it's a waiting game: with $n$ people, each person knows that nobody will leave on the first $n-1$ nights, but they need to wait all $n$ nights to be sure of their own eye colour.

Answer 4

There is no new information after the first night.

Every logician already knows everything that is learned on the first night. Many will say that it's about nested hypotheticals, which is somewhat true, but there's another way to think about it, which doesn't require any nesting, just a single hypothetical observer.

Imagine that the guru never looks at people's faces. She only ever looks at notes given to her, and makes statements about those notes. She knows that her own eyes are green. Then, one day, she happens to see someone's face (without them noticing), and their eyes are blue. In her next speech, she announces that she has seen someone with blue eyes on the island.

Now, consider what happens for her after one night - what does SHE learn? She learns that there must be more than one person with blue eyes, because if there were only one, they would leave on the first night.

After the second night, she knows there must be more than two, because if there were only two, they'd figure it out after the first night.

She has no idea how many people have blue eyes, but each night, she can increase the minimum number of people who have blue eyes by one. Why? Because the information that she gains each night is information available equally to the logicians.

Of course, for the logicians, this information isn't new... until it reaches the critical night, where the blue-eyed logicians see 99 blue-eyed people, but they don't leave on the 99th night, therefore telling everyone there's at least 100 blue-eyed people.

There's no nesting needed, here, just induction. The guru draws the conclusion based on the only information available to her. The logicians get the same information, plus more. It just so happens that, for the first 98 nights, the information that the guru has access to is information that the logicians already get via another source.

But on the 99th night, the blue-eyed logicians get new information along with the guru - that there must be more than 99 blue-eyed logicians. That is the information they need to determine their own eye colour.

Answer 5

The new information gained when the oracle/guru makes a statement is that there is at least one person with blue eyes, and everyone is aware that this is the day on which it became common knowledge.

Each person also individually knows that there are at least 99 or 100 people with blue eyes (depending on whether their own eyes are blue - they also know there are at most 100 or 101, but that's less relevant), and that every blue eyed person knows there are at least 98 or 99 people with blue eyes, and that every brown eyed person knows there are at least 99 or 100 people with blue eyes, but there is no other SPECIFIC number that is common knowledge - that everyone can rely on everyone else knowing.

After the first night when nobody has left, the common knowledge is incremented by one. It is now common knowledge that everyone knows that everyone else knows there are at least 2 people with blue eyes.

After the second night, the common knowledge becomes that there are at least 3 people with blue eyes. Not only does everyone know this, but everyone also knows that everyone else knows this and can use it in their logic.

Eventually the common knowledge interacts with each person's personal knowledge and deductions.

When it is common knowledge that there are at least 99 people with blue eyes, everyone who can see 99 pairs of blue eyes still knows that the blue-eyed people they see will see either 98 or 99 pairs of blue eyes, but they also know that it is common knowledge across the island that everyone knows that everyone else knows that there are at least 99 blue-eyed people.

Each person seeing 99 pairs of blue eyes will deduce "either everyone with blue eyes leaves tonight, or there are actually 100 pairs of blue eyes, and the last one is my own".

When nobody leaves, the people who see 100 pairs of blue eyes will make the same deduction for the following night. On that night, all the blue-eyed people do in fact leave, and the non-blue-eyed people are able to correctly deduce from this that their own eyes are not in fact blue.

---

Where your train of thought goes wrong is in your statement:

• everybody knows that everybody sees at least 98 blue pairs of eyes

In fact, it is blue-eyed people who know that. Non-blue-eyed people know that everybody sees at least 99 blue pairs of eyes. They have no single common number known to be known to both groups other than by incrementing from the single public statement made by the guru/oracle/...

Answer 6

As correctly stated by the OP, what happens the first night is a surprise to nobody. So nobody has learned anything from the first night.

The OP is wrong in thinking that if there is no information learned by anybody the night has no effect.

If there are N monks and K blue-eyed monks, it can be shown that the blue-eyed monks leave on the Kth night. The reasoning is not obvious, I won't go through it again, but that is what it boils down to.

The only thing the monks don't know is the color of their eyes. When they see B blue-eyed monks, they don't know whether K is B or B+1.

The first morning where a monk learns anything is after B nights have passed. (B is K-1 if he has blue eyes, K if he has brown eyes). In the morning, if the blue-eyed monks have departed, he learns that he has brown eyes. If they haven't, that means K nights haven't passed and therefore he learns that has blue eyes.

In summary, with K blue-eyed monks, the blue-eyed monks will learn of their eye color after the (K-1)th night because nobody left. The brown-eyed monks will learn of their color after the Kth night because the blue-eye monks left.

What have they learned the 1st night? Just that a night has passed.

PS: rereading other answers I realize that what I say has been said before in a different formulation. Of course, I feel mine is better, I go straight to the point. :-)

Answer 7

The answer is that there is no new information learned on the first night when nobody leaves (everyone already knew that nobody would leave). There are only two times in which new information is gained:

• The moment when the guru states that someone has blue eyes.

• Night 99 when nobody leaves.

The really interesting question is, "What new information is gained when the guru says he sees someone with blue eyes?" Didn't everyone already know this? And didn't everyone already know that everyone else already know this too? Yes - person 1 already knew that person 2 knew that someone has blue eyes. In fact, person 1 already knew that person 2 knew that person 3 that person 4 had blue eyes. So what was the new information? It seems like everything was common knowledge already.

The answer is, that the new information is that person 1 now knows that person 2 knows that person 3 knows that person 4 knows that person 5 knows that person 6 knows...that person 100 knows that someone has blue eyes. (Plus that same symmetrical information in millions of other ways). Of course we can't really conceptualize this new piece of knowledge because it's so complex, so to believe it we need to look at simpler cases:

When there are 2 people, the new knowledge is not that someone has blue eyes. It is that each guy knows that the other guy knows that someone has blue eyes. With 3 people the new knowledge isn't that someone has blue eyes, and it's also not that each guy knows that the other guys know that someone has blue eyes (person 1 already knows that person 2 knows that someone has blue eyes because they both see person 3). The new knowledge here with 3 people is that each guy knows that each other guy knows that each other guy knows that someone has blue eyes. That's about the limit of the knowledge that I can really feel, but the pattern continues.

There's no new information on day 1. They're just waiting until day 99 to see if there are 99 people with blue eyes who are going to leave, or if not they'll know there are 100 people. This is where the other information is acquired.