You are very good at putting this simply. However, the one minor explanatory note about your wording I would make, which was the same note I made to Chessic Sense, is that we should stress that wherever you write “thinks” here, what you mean by that word is “is not able to rule out the possibility that”, rather than “is able to definitively establish that”, which a reader might easily misinterpret it as.
You did of course make something of such a note before, but I just want to stress it again.
Not if he already has enough information to collapse the probability chain, no - he would start discarding probabilities pre-emptively. So does he have that information?
Looking at it, if we restrict them to the line of thinking you propose, he doesn’t; there will be no collapse, and he would learn nothing about the possibilities therefrom on day 0 or any other day - the line of thinking wouldn’t even resolve on the day when, by other logical methods, he might expect all the other blues to kill themselves. Because this line of thinking doesn’t tell the blues when to kill themselves; they do all the thinking they’re going to about it on day 0, and it doesn’t tell them when to expect the blues they see to die.
But they already all know there will be no day 1, 2, or n killings, until the day before they themselves expect to die. So you can’t possibly be right here - there’s nothing to learn on day n (until their penultimate day n).
Keep going over this in your mind - perhaps you’ll see why the model of their thought processes you propose can’t possibly what leads to their death.
Any villager who sees 99 blues and thinks it’s possible that the blues they see would kill themselves on day 1 is an idiot. Thus only idiots could learn something when the blues they see don’t all kill themselves on day 1. And nobody on this island is an idiot.
It’s true that “Everyone knows no one will kill themself on Day 1”.
It’s false that “Everyone knows that everyone knows that everyone knows that … everyone knows that no one will kill themself on Day 1”, where the number of “everyone knows that” is one less than the number of blue-eyed islanders. (That is, this is false before the Day 1 killing-time; it of course becomes true after the Day 1 killing-time, as the Day 1 killing results become common knowledge)
Just because everyone knows [whatever], it doesn’t follow that everyone knows that everyone knows [whatever]. Anyway, go look at Carmady’s post.
Suppose, prior to any public announcements, A knows that B knows that C knows that at least two islanders are blue-eyed.
Well, changing A’s eye color doesn’t change what A knows. Changing B’s eye color doesn’t change what B knows (and A knows this). Changing C’s eye color doesn’t change what C knows (and A knows that B knows this).
Accordingly, even if we change A’s eye color to brown, change B’s eye color to brown, and change C’s eye color to brown, it would still have to be the case that A knows that B knows that C knows that at least two islanders are blue-eyed.
Which means if A knows that B knows that C knows that at least two islanders are blue-eyed, there must in fact be two islanders who are blue-eyed apart from {A, B, C}.
Which means that, for example, if there are only four islanders total, then it cannot be the case that A knows that B knows that C knows that at least two islanders are blue-eyed. Accordingly, in the four-person case, not everyone knows that everyone knows that everyone knows that no one will die on Day 1.
The exact same thing happens with larger numbers, of course. The truth value of “A knows that B knows that C knows that … D knows that [whatever]” is independent of A’s eye color, B’s eye color, C’s eye color, D’s eye color, etc., because the truth value of “X knows that [whatever]” is independent of X’s eye color. If “A knows that B knows that C knows that … D knows that [whatever]”, then it must be possible to deduce [whatever] just from the eye colors of the islanders who aren’t among A, B, C, …, D.
Everyone knows that [whatever] just in case you can deduce that [whatever] from knowedge of all but any one islander’s eye color.
Everyone knows that everyone knows that [whatever] just in case you can deduce that (you can deduce that [whatever] from knowledge of all but any one islander’s eye color) from knowledge of all but any one islander’s eye color. It follows that everyone knows that everyone knows that [whatever] just in case you can deduce that [whatever] from knowledge of all but any two islanders’ eye colors.
Similarly, everyone knows that everyone knows that everyone knows that [whatever] just in case you can deduce that [whatever] from knowledge of all but any three islanders’ eye colors, and so on.
I didn’t see where he explains how villager A collapses the possibilities due to new information he gets on on day 2. If A can’t, then his explanation is useless - it’s not how the villagers decide when to die.
In actuality, of course, the endless speculation can never be resolved. The death happens due to a different thought process - this one:
Every islander knows that every islander has studied the islander problem. He thus knows that every islander will kill himself on the day of the number of blues he sees, plus 1.
An islander who sees N blues knows that there are two possible cases:
He’s got brown eyes, and so there are N blues total:
The browns see N blue eyes, and will all kill themselves on day N+1.
The blues see N-1 blue eyes, and will all kill themselves on day N.
He’s got blue eyes, and so there are N+1 blues total:
The browns see N+1 blue eyes, and will all kill themselves on day N+2.
The blues see N blue eyes, and will all kill themselves on day N+1.
Given this, he knows for an absolute certainty that no deaths will occur until day N, no matter what. Any thought process that says otherwise is clearly introducing unnecessary unknowns - for a relevent example, including as data the thought processes of anybody, including himself. What people think isn’t what dictates when they die, it’s what they see.
Of course, the actual mechanism inducing his death is the fact that in the only two actual possible cases, the blues he sees will behave differently on day N. At that point he learns his eye color and must die, on schedule, on day N+1.
Yes, every islander knows for an absolute certainty that no deaths will occur until day N-1 (where N is the number of blues). I agree. This is because every islander knows that either there are N-1 or N blue-eye islanders, depending on his own eye color.
It does not follow that every islander knows for an absolute certainty that every islander knows for an absolute certainty that every islander knows for an absolute certainty that no deaths will occur until day N-1. The things which every islander knows are the things which can be deduced from knowledge of all eye colors except for any particular one. The things which every islander knows that every islanders knows that every islander knows are the things which can be deduced from knowledge of all eye colors except for any particular three. The latter does not encompass everything within the former.
At the start:
There are N blues.
Every islander knows that there are at least N - 1 blues.
Every islander knows that every islander knows that there are at least N - 2 blues.
Every islander knows that every islander knows that every islander knows that there are at least N - 3 blues.
Every islander knows that every islander knows that every islander knows that every islander knows that there are at least N - 4 blues.
And so on.
Of course, the missionary’s public statement and each new day’s public killing results makes new facts into “common knowledge”, changing this higher-order knowledge.
You don’t need to look at what happens with the changes in higher-order knowledge to explain what ultimately goes down. You can give a sufficient explanation that never touches upon it, save for the initial change engendered by the missionary’s statement. That’s fine. But the changes in higher-order knowledge happen nonetheless.
John, James, Jim, and Jacob all know that Sally has a crush on Tom which she’s going to announce publicly on Wednesday. In fact, everyone in school knows that Sally has a crush on Tom which she’s going to announce publicly on Wednesday. But no one realizes that everyone in school knows this.
So even though no one learns anything new from Sally’s Wednesday announcement, the following change still occurs:
On Tuesday night, “Everyone knows that everyone knows that Sally has a crush on Tom” is false.
On Wednesday night, “Everyone knows that everyone knows that Sally has a crush on Tom” is true.
This change happens despite the fact that the only relevant occurrence was Sally making an announcement everyone already knew ahead of time she was going to make.
That’s the phenomenon which occurs on each day when that day’s killing-results are made public.
And they still know all of this with the same certainty at noon on day N-1. What part of this tells anyone to die?
I say they don’t. There is nothing to cause such changes.
Also, I think I may have figured out how the village can be saved - if a blue dies early for any reason, this should end it. I think. I base this theory on the fact that if the visitor amended his comment with “And that’s the blue-eyed guy I saw”, pointing at any one of the blue-eyed people in the village, that would effectively separate the victim from the tribe and he would die alone on day 1. But if the cause of death was food poisoning on day 56, would that end it too?
Incomparable situation - there will be an actual change to the world state, which everyone observes. Nothing comparable happens to the islanders on day 2.
What causes such changes is the fact that each day’s killing results are public; i.e., “common knowledge” in the technical sense. This is the analogue of Sally’s announcement. “Ah, it was today publicly revealed that no one died” is the same as “At, it was today publicly revealed that Sally has a crush on Tom”. If you like, imagine there’s a town crier whose job it is to announce such things every afternoon.
There can be changes in higher-order knowledge even if everyone knows ahead of time exactly how all the relevant occurrences and announcements are going to go down, which is exactly what is illustrated in the gossip-mill example and what happens with the islanders.
All the results through day N-2 are known by all in advance on day 0; they can (and will) use the induction to precalculate them. Nothing happens on day 2.
The fact that all the results through whenever are known in advance does not preclude changes in higher-order epistemological state over that time.
Everyone knows ahead of time that Sally will announce her crush on Tom on Wednesday. Yet, all the same, when she does so, it causes a change in higher-order epistemological state. Prior to her announcement, “Everyone knows that everyone knows that Sally has a crush on Tom” is false, and after her announcement, it is true.
Of course, no one actually learns anything new. Everyone knows on Tuesday that everyone will know on Wednesday that Sally has a crush on Tom. And everyone knows on Wednesday that everyone will know on Wednesday that Sally has a crush on Tom. People haven’t learnt something to be true which they didn’t know to be true before; it’s just that temporally-indexical statements may change in truth value as the reference of “now” changes. The change is just this sort of change.
There is nothing temporally indexed in any of the “A thinks B thinks C thinks D thinks” statements.
You are practically arguing against yourself.
The temporal indexing is the implicit “A knows now” as opposed to the truly non-indexical “A knows on Day 97” or “A knows on Day 3”. Same as in the Sally example.
Why are you so opposed to the idea that the things that A knows on Day 1 that B knows on Day 1 that C knows on Day 1 to be true can be different from the things that A knows on Day 2 that B knows on Day 2 that C knows on Day 2 to be true? It can happen. It does happen. It happens by exactly the same mechanism as in the Sally example.
When you see that the “A thinks that…E thinks…” is the same as the process you’re describing, you’ll understand our argument. When we talk about brrrr’s and whatnot, it’s the same thought process that says “Oh crap, Tom and John didn’t kill themselves on Day 2, so they must see 2 blues each.”
When no one kills themselves on any given day prior to the announcement, it still leaves open the probability that A.B.C.D.E has rrrrr as a possibility. Once the missionary makes his statement, it scratches off rrrrr from A.B.C.D.E and allows the collapse of the chain.
Failure to die on day 1 announces to everyone that there can’t be only one blue. Prior to the missionary, however, this was not the case. That merely said “There are either at least 2 blues or none.” Remember, that’s for the A.B.C.D.E. case, not the A.B.C. case or the A.C.E case or the B.C.D. case or anything other than A.B.C.D.E.
If I might digress for a moment from islanders’ eyes (or eyelanders’ Is), the answer to SurrenderDorothy’s last riddle (how many months have 28 days):All of them do. Most also happen to have a few extra, too.
This will be my last post on the islanders. I’m afraid this is the second time I’ve participated in one problem’s discussion entirely overtaking and thus strangling the thread, though in my defense, there were many people involved this time.
Suppose there are a whole bunch of islands, each labelled by a pair of numbers saying how many blue-eyed inhabitants and how many brown-eyed inhabitants it has, with there being an island for each such pair. [Thus, island (1, 3) has a single blue-eyed inhabitant and 3 brown-eyed inhabitants].
Now, any particular islander is not entirely aware of which island they’re on; they can only narrow it down to two possibilities. For example, the blue-eyed inhabitant of island (1, 3) can only be sure that he’s either on island (1, 3) or on island (0, 4), but doesn’t know which of the two. Call two islands “neighbors” if each has an inhabitant who is unable to rule out the possibility that he is on the other; thus, (1, 3) and (0, 4) are neighbors, and every island is one of its own neighbors, but (1, 3) and (3, 1) are not neighbors. Let’s also define the distance between two islands as the shortest number of hops between neighboring islands which it takes to get from one to the other.
Clearly, “Everyone on island X knows that their island has property p” just in case “Property p holds of every neighbor of island X”. In other words, “Property p holds of every island within distance 1 of island X”.
So, for example, everyone on island (4, 0) knows that their island has someone blue on it just in case every island neighboring (4, 0) has someone blue on it. (And, indeed, there are only two islands neighboring (4, 0): itself and (3, 1), and both have someone blue on them. Thus, everyone on island (4, 0) does know that their island has someone blue on it).
Ok, so what? So let me be less verbose for a moment. If p is some property that might hold of an island, I’ll write p to mean “Everyone on this island knows it has property p”. Thus, the above observation was that p holds of an island just in case p holds of all its neighbors. By [sup]2[/sup]p, I mean p, by [sup]3[/sup]p, I mean p, and so on. (In keeping with this pattern, by [sup]0[/sup]p, I just mean p.)
Theorem: An island has the property [sup]k[/sup]p just in case every island within distance k of it has property p.
Proof: By induction on k. The base case is when k = 0, and it is trivially true that an island has the property [sup]0[/sup]p (i.e., p itself) just in case every island within distance 0 of it has property p.
As for the inductive step, let’s suppose the theorem is true for k and show it to be true for k + 1. Note that [sup]k + 1[/sup]p is just . Thus we see that an island has this property just in case every neighbor of that island has the property that (by the inductive hypothesis) every island which is within distance k of that neighbor has the property p. In other words, an island has the property [sup]k + 1[/sup]p just in case every island which is within distance k + 1 of it has the property p. This completes the inductive proof.
So what? In particular, this tells us that the statement [sup]4[/sup](someone on the island is blue) holds of an island just in case every island within distance 4 of it has someone blue on it.
However, (4, 0) neighbors (3, 1) which neighbors (2, 2) which neighbors (1, 3) which neighbors (0, 4), and this last island has no one blue on it. Thus, (4, 0) does not have the property [sup]4[/sup](someone on the island is blue).
In other words, in the situation where there are four blue islanders and no brown ones, it is not true that “Everyone knows that everyone knows that everyone knows that everyone knows that someone on the island is blue”. Similar results hold for every other contested point about higher-order knowledge in the thread; one can always unwind according to the above rule. (The inductively proven theorem above can save you time, of course, but if you don’t trust it, you can always retrace its steps by manually unwinding in any particular case)
You’re kidding, right?
The mechanism in the Sally example is that, and I quote, “Sally will announce her crush on Tom on Wednesday”. Nobody has any information about what anyone else knows prior to this event. Everybody knows that after the even, everyone will know that Sally has a crush on Tom.
There is nothing comparable about that situation with the villager problem. It’s good that you won’t be beating that dead horse anymore.
I know, I know - you think that on day -1 A.B.C.D.E is
bbbbb, bbbbr, bbbrb, bbbrr, bbrbb, bbrbr, bbrrb, bbrrr, brbbb, brbbr, brbrb, brbrr, brrbb, brrbr, brrrb, brrrr, rbbbb, rbbbr, rbbrb, rbbrr, rbrbb, rbrbr, rbrrb, rbrrr, rrbbb, rrbbr, rrbrb, rrbrr, rrrbb, rrrbr, rrrrb, rrrrr.
So, you think that after the visitor speaks on day 0, that A.B.C.D.E is bbbbb, bbbbr, bbbrb, bbbrr, bbrbb, bbrbr, bbrrb, bbrrr, brbbb, brbbr, brbrb, brbrr, brrbb, brrbr, brrrb, brrrr, rbbbb, rbbbr, rbbrb, rbbrr, rbrbb, rbrbr, rbrrb, rbrrr, rrbbb, rrbbr, rrbrb, rrbrr, rrrbb, rrrbr, rrrrb.
And that after noon on day 1 that A.B.C.D.E is bbbbb, bbbbr, bbbrb, bbbrr, bbrbb, bbrbr, bbrrb, bbrrr, brbbb, brbbr, brbrb, brbrr, brrbb, brrbr, brrrb, rbbbb, rbbbr, rbbrb, rbbrr, rbrbb, rbrbr, rbrrb, rrbbb, rrbbr, rrbrb, rrrbb.
And that after noon on day 2 that A.B.C.D.E is bbbbb, bbbbr, bbbrb, bbbrr, bbrbb, bbrbr, bbrrb, brbbb, brbbr, brbrb, brrbb, rbbbb, rbbbr, rbbrb, rbrbb, rrbbb.
And that after noon on day 3 that A.B.C.D.E is bbbbb, bbbbr, bbbrb, bbrbb, brbbb, rbbbb.
And that after noon on day 4 that A.B.C.D.E is bbbbb. Or bbbbr, bbbrb, bbrbb, brbbb, rbbbb*, if the blues killed themselves.
I know that’s what you think. But that’s because you’re deliberately pretending the villagers can’t predict the outcomes of days 1-3 in advance. In actuality, they can, and would. So, in reality, all else being equal:
On day -1 A.B.C.D.E is
bbbbb, bbbbr, bbbrb, bbbrr, bbrbb, bbrbr, bbrrb, bbrrr, brbbb, brbbr, brbrb, brbrr, brrbb, brrbr, brrrb, brrrr, rbbbb, rbbbr, rbbrb, rbbrr, rbrbb, rbrbr, rbrrb, rbrrr, rrbbb, rrbbr, rrbrb, rrbrr, rrrbb, rrrbr, rrrrb, rrrrr.
And after the visitor speaks on day 0, they predict the outcomes of days 1-3 and know that A.B.C.D.E is bbbbb, bbbbr, bbbrb, bbrbb, brbbb, rbbbb.
And after noon on day 1 A.B.C.D.E is still bbbbb, bbbbr, bbbrb, bbrbb, brbbb, rbbbb.
And after noon on day 2 A.B.C.D.E continues to be bbbbb, bbbbr, bbbrb, bbrbb, brbbb, rbbbb.
And after noon on day 3 A.B.C.D.E yet further remains bbbbb, bbbbr, bbbrb, bbrbb, brbbb, rbbbb.
And after noon on day 4 A.B.C.D.E finally changes, to bbbbb. Or bbbbr, bbbrb, bbrbb, brbbb, rbbbb*, if the blues killed themselves.
Not that they have any reason to bother wondering what anyone thinks about what E thinks - at no point does this thought process tell them as much about their future as the awareness of the induction that allows them to predict the outcomes of days 1-3.
Which raises the question of why he put off using his own knowledge as a filter before now.
The answer, of course, is obvious - unless he maintains this absurd pretense of ignorance until the last minute, then A.B.C.D.E’ is bbbbb, rbbbb the entire time, until d-day. How many different ways are we going to have the villagers deliberately pretend at ignorance in order to argue that they’d use this esoteric method of deducing their eye color?
And you know what? I think I’m done posting on the subject of the poor villagers. I know why they’re dying, I know the thought process they’d inevitably use - and it wouldn’t be the A.B.C.D.E one, for the obvious reason that that’s only ever a post-rationalization after the answer is already gotten by induction. I want to say that I’m glad to have learned/realized that the each villager knows the date of his death from the start long before he knows his eye color; that much is interesting, and I thank you lot for giving me the chance to figure that out, despite the fact that the contrived rationale you argue for does not grant them that knowledge.
Though, if anybody wants to discuss ways to save the villagers, that might be interesting, especially since it changes the answer. After all, if there’s something the villagers can to to resolve this predicament, they’d figure it out and do it, rather than just sitting on their hands for 100 days.
At the moment I’m tentatively offering “On day 1, some percentage of the blue-eyed villagers are found dead, and everyone else lives” as the actual correct answer, on the theory that the villagers realize that the death of a single blue islander breaks the deadly system, and thus every single one of them would pick a blue islander that they see and sneak off in the night to kill them. Presumably they won’t all pick the same islander to off (unless he’s very unpopular), so several different ones would be killed before the remaining islanders come upon blue-eyed corpses instead and conclude that the necessary death has already taken place.
Feel free to argue against this theory of you like; I’ll respond. An alternate theory is that they’d all wait until day 98 to do the deed, on the principle of letting their victim live as long as they could, though I presume that some might be nervous or impatient, and after the first night some blue-eyed guy is found dead nobody will bother killing any others.