When the announcement that n>=1 is made in public to all islanders, then all islanders know that n>=1 and all know that all know that n>=1 and all know that all know that all know that n>=1, and so on to infinity. I don’t understand why you think otherwise. There is no level of extension at which the knowledge that n>=1 stops.
You keep claiming the explorer’s information is redundent. If that is so, on island n=3 all the blues kill themselves on day 3. Can you explain exactly how that happens?
No I meant that exactly. In the original puzzle as stated everyone knows that everyone knows that n=98 is a lower boundary. What isn’t common knowledge is if n>=99.
You can keep tumbling down the rabbit hole, if you will, but it’s unnecessary. It is sufficient to establish it is common knowledge that every A knows some B has blue eyes, then every additional statement about the necessary common knowledge follows. That happens from n=3 on. Even the blue-eyed islanders then know that everyone knows some islander has blue eyes. (Or, it is common knowledge that all A’s know some B has blue eyes.)
Probably because I’m trying to work it out intuitively rather than mathematically, where I stumble is that I don’t see how the chain starts. Everyone knows blue eyed people exist and everyone knows that everyone knows blue eyed people exist, so the traveler shouldn’t be able to influence the tribe. The logic seems to be social - since they refuse to speak about it even though they know, they have to pretend they don’t know. But I don’t see how they go about determining how many blue eyed people there are. Obviously if the traveler revealed a number were off and running.
Yet again, it is NOT common knowledge that n>=1 in the absence of the announcement. When n=3, in the absence of the announcement everyone knows that n>=1 and everyone knows that everyone knows that n>=1, but it is not the case that everyone knows that everyone knows that everyone knows that n>=1.
We’re on island n=3. There is no announcement made. You claim the situation is unstable and the blues will kill themselves on day 3. Again, can you explain how that happens?
magnet
1826
I’m really coming around to skedastic’s side, but trying to make it more intuitive for myself.
Here’s the thought process I’m toying with.
Suppose you were one of 4 blue eyed natives. You could say to yourself, “Maybe I have brown eyes and there are only 3 blue eyes. If so, blue-eyed Bob over there might be looking around and thinking there might be only 2 blue-eyes. I wonder what Bob thinks about blue-eyed Charlie. Maybe Bob thinks that Charlie might be thinking he has brown eyes. Because if I have brown eyes and Bob supposes he has brown eyes, then when Bob looks at Charlie he sees someone who might think that David is the only blue eyed native. And if so, then Bob actually thinks it’s possible that Charlie believes that David thinks there might be no blue eyed natives at all.”
Whew. This puzzle is insane.
Enidigm
1827
Yea, but that doesn’t work like that does it? If n=4 and n(b)=3, because everyone will always see at least two blue, everyone will know that everyone at least thinks that n(b)=1 at a minimum (because B2 who sees B3 and B4 will know that B3 and B4 will at least see B3 or B4 and know there are at least one B). Unless you’re talking about a larger total data set than 4?
Sometime late last night I realized my intuition for what formally constitutes common knowledge is probably flawed. (There are no epistemic logics in the math department.)
I’ll have to think about it some more, but I suspect skedastic is actually right.
Zylon
1829
Can you explain how the islanders could be so monumentally unobservant?
The crux of the problem isn’t about whether all of the islanders individually know that everyone sees a blue-eyed islander. It’s whether they can simultaneously know that everyone knows that fact. It’s the shared knowledge of what everyone else knows that determines the problem.
Zylon
1831
In any sane reality how could it NOT be common knowledge that it’s common knowledge? That would require yet another silly condition to the riddle, like “Oh and everyone walks around with bags on their heads.”
CraigM
1832
That’s what gets me. If you observe 2 people with blue eyes then, logically, you know that each blue eye person sees at least 1 blue eye person or 2 blue eyed people. For you to have perfect knowledge of how many (non you) blue eyed people there are, but not assume they can observe the same, requires you to be on an island of idiots, who are obviously not perfect logicians.
ShivaX
1833
Yeah, that’s my issue with it. Dude comes in a says something everyone obviously already knows. Somehow this does something. No. Just, no.
Edit: I honestly feel like this is a challenge between people with High Int and High Wis in D&D terms. High Int guys work out all this math and conclude everyone dies in X days. High Wis people are like… “Dude, nothing happens because they already knew.”
magnet
1834
Now pretend that you are one of those 2. You only see one blue eyed person. You think to yourself, “If I have brown eyes, then I don’t need to kill myself. And if I have brown eyes, then that blue eyed guy might see me and think nobody on the island has blue eyes. So then he won’t kill himself, either.”
So even though you know that there is one blue eyed person on the island, you don’t do anything until the explorer arrives and announces what you already know.
Here’s a good, relatively non-technical, paper on common knowledge: http://classes.maxwell.syr.edu/ecn611/Geanakoplos2.pdf
The puzzle we are discussing is considered starting on the second page (in the form of the girls with hats). There is also discussion of some other curious puzzles, I like this one:
Consider a second example, also described by Littlewood, involving betting.
An honest but mischievous father tells his two sons that he has placed 10^n
dollars in one envelope, and 10^(n+1) dollars in the other envelope, where n is
chosen with equal probability among the integers between 1 and 6. The sons
completely believe their father. He randomly hands each son an envelope. The
first son looks inside his envelope and finds $10,000. Disappointed at the
meager amount, he calculates that the odds are fifty-fifty that he has the smaller
amount in his envelope. Since the other envelope contains either $1,000 or
$100,000 with equal probability, the first son realizes that the expected amount
in the other envelope is $50,500. The second son finds only $1,000 in his
envelope. Based on his information, he expects to find either $100 or $10,000
in the first son’s envelope, which at equal odds comes to an expectation of
$5,050. The father privately asks each son whether he would be willing to pay
$1 to switch envelopes, in effect betting that the other envelope has more
money. Both sons say yes. The father then tells each son what his brother said
and repeats the question. Again both sons say yes. The father relays the
brothers’ answers and asks each a third time whether he is willing to pay $1 to
switch envelopes. Again both say yes. But if the father relays their answers and
asks each a fourth time, the son with $1,000 will say yes, but the son with
$10,000 will say no.
Zylon
1836
If the text you mention supported your argument, I assume you would have posted it, instead of this obvious “Look, cows!” distraction attempt.
You know, except for you, everyone is being pleasant in this conversation. The text does support my argument:
Each student knew the apparentlyinnocuous fact related by the teacher- that there was at least one red hat in theroom - but the fact was not common knowledge between them. When it becamecommon knowledge, the second and third children could draw inferences fromthe answer of the first child, eventually enabling the third child to deduce her hatcolor.
The discussion at the beginning of section 4 formalizes this result.
Zylon
1838
It does not support your argument, since the hat example requires that everyone be wearing the same-colored hat. In any even trivially more complex scenario it breaks down, and indeed most variants of this puzzle with more hat colors and/or participants rely on various collusion strategies to figure out the hat colors. In the islander scenario there would obviously be no collusion since nobody wants to know their own eye color.
It’s exactly the same puzzle as the island with n=3, the three blue-eyed islanders are the analytically identical to the three red-hatted girls. The solution does not break down even in arbitrarily more complex scenarios, it is true for any n.
You’ll have to give an example of a variant of this puzzle in which “various collusion strategies” are required.
Thanks to magnet’s example, I think I’m convinced.
I think this would be immensely helped by whiteboarding it to demonstrate the chain of what each person thinks the next person thinks. It’s too bad the xkcd answer is just text, because I think he’d be able to diagram it pretty well.
