Puzzling Asked by Roland Kuhn on March 15, 2021
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:
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?”.
I'll try to answer the question directly, without simplifying to a smaller case.
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.
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.
Definitions:
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.
Correct answer by Tim C on March 15, 2021
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.
Or let's say three people, Alice, Bob, and Charlie.
Similarly with four people, Alice, Bob, Charlie, and Dorothy.
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.
Answered by Rand al'Thor on March 15, 2021
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.
Answered by isaacg on March 15, 2021
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.
Answered by Glen O on March 15, 2021
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. :-)
Answered by Florian F on March 15, 2021
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:
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/...
Answered by Steve on March 15, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP