10
$\begingroup$

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?

EDIT: IMPORTANT NOTE

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.

EDIT2: 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?”.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Puzzling! A few questions about the Blue Eyes problem have already been asked here - does this one answer your question? puzzling.stackexchange.com/questions/236/… $\endgroup$ – Deusovi Jul 22 at 19:10
  • 2
    $\begingroup$ That is a question with many answers, but none of them touch this point. $\endgroup$ – Roland Kuhn Jul 23 at 5:54
  • 3
    $\begingroup$ So it seems that this question has been closed, presumably because enough people jumped to the conclusion that everything must have been said five years ago — even though this aspect was never discussed. Is there any recourse to this? $\endgroup$ – Roland Kuhn Jul 23 at 12:58
  • 1
    $\begingroup$ This is definitely a different question. It's not about the need for the oracle. It's about the nature of information and how one can consider information in such a situation, which informs how one goes about solving the puzzle. $\endgroup$ – Glen O Jul 24 at 4:30
  • 1
    $\begingroup$ We're voting to reopen your question now; it's currently sitting at 4 votes to reopen out of the required 5. $\endgroup$ – Rand al'Thor Jul 24 at 5:54
4
+50
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This answer has the same flaw — unless my argument is wrong, which nobody so far tackled! — in that the inductive (here: recursive) process is hand-waved after two steps, whereas in the third step my point is that new information changes the game (and breaks the recursion). Why does person 1 need to admit the nested hypothesis that person 2 assumes that person 3 assumes that person 4 sees less than 98 pairs of blue eyes? It is a fact that everybody can verify that there are at least 98, and everybody knows that everybody can derive this, no assumptions necessary. $\endgroup$ – Roland Kuhn Jul 23 at 12:31
  • $\begingroup$ It's because it can't be derived inside the hypotheticals. The "hand waving" is a necessary shortening to fit inside the stackexchange post size limit, but I've added a full expansion of the last layer of the hypothetical (which is disproven after the first night). $\endgroup$ – Tim C Jul 23 at 19:25
  • $\begingroup$ Thank you for appending the recursion trace, Tim C, and you might like to tailor a copy of this solution at the designated pre-duplicate In the 100 blue eyes problem - why is the oracle necessary?. This is indeed the first answer at either question that fully grabs the bull by the horns (top-down recursion, as opposed to catching-a-tiger-by-the-tail bottom-up induction). I want to bounty this approach (and your derring-do) at both questions. Signed, rabid for recursion $\endgroup$ – humn Jul 23 at 21:25
  • 1
    $\begingroup$ @humn Done! puzzling.stackexchange.com/a/100305/16990 $\endgroup$ – Tim C Jul 24 at 0:37
  • $\begingroup$ @TimC Thanks for fully expanding and thus making explicit the tower of hypotheses. My question is still not answered, though — perhaps I should make a new question to ask it with unmistakable precision, which I think I can do now thanks to your answer to this one. puzzling.stackexchange.com/questions/100313/… $\endgroup$ – Roland Kuhn Jul 24 at 6:15
10
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Those last two sentences nail it, +1. $\endgroup$ – Rand al'Thor Jul 22 at 19:06
  • $\begingroup$ This is the best explanation that I have read. Even better than the dupe. $\endgroup$ – justhalf Jul 23 at 1:21
  • $\begingroup$ You answer the case of 3 pairs of blue eyes, which is distinctly different from 4 or more. If you take 4: blue1 makes the hypothesis that they have brown eyes in which case blue2 will see three pairs of blue eyes, so making the hypothesis that they have brown eyes they conclude that everyone will see at least two pairs of blue eyes. blue1 cannot make the hypothesis that blue2 thinks that blue3 thinks that blue4 sees only one pair because they know that everybody actually sees at least two pairs. Thus the case where information is added by seeing nobody leave is disproven on the first day. $\endgroup$ – Roland Kuhn Jul 23 at 6:15
  • $\begingroup$ @RolandKuhn Hypotheticals within hypotheticals. $\endgroup$ – Rand al'Thor Jul 23 at 6:23
  • $\begingroup$ What if the guru says "I see at least 98 people with blue eyes"? Does this change when they all are up and leave? $\endgroup$ – Andrew Savinykh Jul 23 at 7:13
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The trick of this puzzle seems to be to lead people into “let’s take this simpler case and then generalize”, where the simpler case actually is fundamentally different from the one that is asked — my reasoning requires that everybody knows that everybody sees at least two pairs of blue eyes, so this answer has nothing to do with my question. If you can make your reasoning work for at least four blue-eyed people then please update! $\endgroup$ – Roland Kuhn Jul 23 at 6:19
  • $\begingroup$ @RolandKuhn I added the 4-person case, but it really does extend in the same way. $\endgroup$ – Rand al'Thor Jul 23 at 6:22
  • $\begingroup$ It only extends if you assume that that treatment of the hypotheticals is the best that can be done by the logicians. But if — as I ask to consider — there is more common knowledge that can be derived as soon as there are at least four blue-eyed people, then this common knowledge changes the game, does it not? In other words, your pyramid works because you built it as a pyramid, but is that the only way to think about this problem? $\endgroup$ – Roland Kuhn Jul 23 at 6:27
  • $\begingroup$ @RolandKuhn just to make sure I understand you correctly, in the first comment you say that the reasoning in the answer does not work, and in the second comment you accept that it works, and asking if there is an alternate reasoning to show the same? $\endgroup$ – Andrew Savinykh Jul 23 at 6:39
  • $\begingroup$ The first comment was made when the answer included one two blue-eyed people, which is not relevant to my question. What I am saying is that the logicians know more than the information derived by the accepted chain of induction. $\endgroup$ – Roland Kuhn Jul 23 at 12:26
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I like this answer a lot, as it cuts through much of the confusing hypotheticals. I used to think that there was some information gained each day even for the logicians, in the form of some kind of growing common knowledge, but you've convinced me that this isn't really the case. $\endgroup$ – Jaap Scherphuis Jul 24 at 14:59
  • $\begingroup$ So you are confirming (somewhat indirectly) that in the original riddle’s setting nobody learns anything new after the first night. That other guru of yours obviously learns something during the first night, but that does not answer my question, nor does it contradict the statement in my first sentence here. The rub is: if I’m right, then nobody will ever leave. IOW the widely accepted answer is wrong. $\endgroup$ – Roland Kuhn Jul 24 at 16:50
  • $\begingroup$ @RolandKuhn - not quite. The key thing is that they don't learn anything new, but that doesn't mean that information isn't being generated. It just so happens that, until the critical night, the information that is generated isn't new information to the logicians. Imagine a box, which produces square numbers in order. The first one is 1, then 4, then 9, then 16, and so on. You know these square numbers. But eventually, there will be a square number you don't already know. That the first square number isn't new information to you doesn't mean you'll never get new information. $\endgroup$ – Glen O Jul 25 at 2:25
1
$\begingroup$

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. :-)

| improve this answer | |
$\endgroup$
  • $\begingroup$ If you presuppose the “K monks leave on Kth night” solution, then you’ll obviously be able to prove that the night has an effect. But you cannot do that, since that is circular logic. Now since you agree that nobody learns any new information (other than “now is one day after the guru spoke), you also agree that Randall Munroe’s solution to the riddle is incorrect, removing the basis for all your following paragraphs. $\endgroup$ – Roland Kuhn Jul 24 at 16:54
  • 1
    $\begingroup$ The question was not to prove the solution to the blue-eyed monk problem. The question was what information is learned in the first night. So I show how, in the solution, no information is learned by anybody except for the last 2 nights. So the answer is "none". $\endgroup$ – Florian F Jul 24 at 18:57
  • $\begingroup$ After seeing the mistake in my reasoning (puzzling.stackexchange.com/a/100357/70583) I conclude that puzzling.stackexchange.com/a/100236/70583 is the correct answer to the question of what piece of information is actually learnt after the first night: the elimination of the nested hypothetical that there is a person that does not see any blue eyes. $\endgroup$ – Roland Kuhn Jul 24 at 20:03
  • $\begingroup$ @RolandKuhn You are saying that the hypothetical monk who would see no blue eyes would learn something the first night. OK, but the actual night that passes has no effect on the hypothetical monk. You can reason about what a monk would think and do after the second or third night without waiting for the actual night to pass. So none of the actual monks learn anything from the actual night. The hypothetical monk learn something on a hypothetical night that is set in its own time. $\endgroup$ – Florian F Jul 26 at 11:13
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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