The blue-eyed islanders puzzle (2008)
terrytao.wordpress.com
terrytao.wordpress.com
If there are 3 islanders with blue eyes, each can see 2 blue-eyed people. The information that there is at least 1 blue is therefore not new information, and can't change the outcome.
The outsider's comment is superfluous given that N > 3.
So now you know your eye color.
Why? The visitor didn't synchronize anything. All of the villagers already knew there was at least 1 blue eyed person. Per the story, 99 or 100 depending on your perspective.
Here's a longer explanation: Since people who know their eye color suicides at noon in plain sight of everyone else, we can set up induction.
If there's only one blue eyed person, they would suicide the first day at noon. Since everyone sees > 1 blue eyed people, they know this wouldn't happen. Since this doesn't happen, it's common knowledge that there is more than 1 blue eyed person. So if you only see one other blue eyed person, you must have blue eyes (but you don't know this yet because you see two blue eyed people).
On the second day, if there are only two blue eyed people, they would both suicide at noon. You see two blue eyed people. No one commits suicide because they either see two blue eyed people (if they have blue eyes) or three blue eyed people (if they don't). Now, everyone knows that there are more than two blue eyed people.
Since no one committed suicide the day before, you reason that there must be three blue eyed people, with the 2 people you see plus yourself. Thus, you know your eye color.
This is a bit long but I hope it's clear.
That's incorrect, in a subtle way. The villagers (every single one) knew that before. It isn't discovered knowledge. Everyone (including the visitor) knows there are 99 or 100 because they can count them already, prior to the visitor.
So nobody is suiciding for 99 days. As an individual who sees 99 other blue eyes, why would you think or not think that you have blue eyes on the next day?
If you can see 99 blue eyes, you know that all the other people see either 98 or 99 (if there's a total of 99 blue eyes) or 99 or 100 (if there's 100 blue eyes). However, if some people see 98 and know that there's at least 99 people with blue eyes, then they would all suicide. Since they don't, you know everyone sees either 99 or 100 blue eyes. Since you see 99, you must have blue eyes.
This does not help in deducing if you have blue eyes.
> then they would all suicide
No they wouldn't. Nobody should suicide at all. The visitor saying someone has blue eyes, was already known by every member of the village and every member of the village saw more than 1 person with blue eyes prior. Nothing is different because he said something.
> Since you see 99, you must have blue eyes
I don't know there's 100, so I don't know I have blue eyes.
You are ignoring islander A's view of B's view of C's view of ... Z's view of situation.
Think about 3 islander's, where A thinks "if I have green eyes, then B and C are in a situation equivalent to me not being here, and B sees exactly 1 blue eyed person C, and B knows that 'C sees 0 or 1 blue eyed people, but then C learned that 0 is impossible'"
From Ben's perspective, Betty might be the only blue-eyed person, so Ben does not know if Betty knows there is at least one blue eyed person. This is important because Ben needs to correlate Betty's actions with her knowledge; he can't do that if he doesn't know what her knowledge is.
After the traveler's announcement, Ben knows that Betty knows there is at least one blue eyed person. This is the new information.
And with three people, we add another layer: Ben does not know if Betty knows that Bobby has blue eyes. And so on.
The visitor's announcement is special because it is infinitely layered. Everyone knows one person has blue eyes, and everyone knows that everyone knows, and so on, ad infinitum. This is called common knowledge: https://en.wikipedia.org/wiki/Common_knowledge_(logic)).
Though to be fair, this isn't explicitly stated: the traveler "addresses the entire tribe" but it's critical that everyone in the tribe knows this is common knowledge. Merely addressing the entire tribe is not enough: if the traveler's announcement was in the form of a BCC mass mailing, there would be no new information and so no suicides.
If there was some reason to start a count, sure, but there isn't. The foreigner just states that there are other blue-eyed people, which the tribe already knows.
Put more clearly: Foreigner says "blue eyes!". n is 2. If you have blue eyes and you don't see the other blue-eyed person top themselves, you conclude that you also have blue eyes as does the other person, and it's belly-opening time.
But when n is 100, that initiation is missing. No-one tops themselves the next day? Hardly suprising - there are a hundred of the buggers. There is no reason to start counting, no "hang on, why didn't ol' blue eyes over there kick the bucket?".
And, given that these are humans and not cronjobs, no-one is going to be patiently waiting day in, day out for 100 days to see when they'll all kill themselves. Drama can't even fester, since the tribesfolk are forbidden from talking about the issue. Life goes on, and over three months later, the foreigner's statement wouldn't cause a bloodbath :)
TL;DR: if you want to make a fancy logic puzzle, don't use 'humans with bizarre rules' as your subjects. :)
Also, the characters are definitively not 'completely rational', as they're also described as being 'devout' :)
Given that, the statement that there is at least 1 blue eyed person doesn't provide new info. The argument that this "synchronizes" them is a little strange. For all we knew, they were in the middle of counting to 100 days prior to this statement due to the aforementioned common knowledge that everyone already knew there were blue eyed people.
So you know there's no reason for all the blue eyed people to commit suicide together, so you can't reason anything out about the total number of blue eyed people.
They can't discuss it. That would be a difficult social experiment, that would risk your life.
1. I note that you say that when N = 3, there's no new information given. But when N = 2, all islanders are still aware that there is at least one person with blue eyes.
I'm guessing that despite that fact, you see how in the N = 2 case, the two people with blue eyes can infer they have blue eyes. So the leap of intuition you should've had there is that somehow, new information is being conveyed, even though every islander already knows that there is at least one person with blue eyes.
2. But let's just tackle this with straightforward inductive logic. For now, we aren't going to worry about what new information is given, we're just going to do induction.
If I see that N people have blue eyes, then I know that either there are N people with blue eyes, or there are N+1 people with blue eyes, and I have blue eyes. If after N days, the people I see with blue eyes haven't killed themselves, then I know that there must be N+1 people with blue eyes, and I have blue eyes, ergo I must kill myself.
This holds with N=0 and N=1 and N=2, so it on some level doesn't matter what the logic is, induction works.
3. But okay, let's figure out what information is actually given. Let's say that on a 100 person island, I have blue eyes and Alice and Bob also have blue eyes. So from my perspective, I know that there are two possible scenarios:
a. Alice, Bob, and I have blue eyes. b. Only Alice and Bob have blue eyes.
Let's consider situation b. In situation b, what does Alice think? Since we're stipulating that I have brown eyes, Alice sees that Bob has blue eyes and that's it. Therefor, Alice thinks that there are two subscenarios of situation b:
b1: Alice and Bob have blue eyes. b2: Only Bob has blue eyes.
Hypothetical Alice in hypothetical situation b considers situation b2. She thinks about what Bob would know in situation b2. He would see that nobody besides potentially him has blue eyes. So he would kill himself when the visitor explained that at least one person had blue eyes.
If Bob does not kill himself, then hypothetical Alice in situation b knows that she is not in situation b2. There is only one other subscenario of situation b, and that is b1, in which both Alice and Bob have blue eyes. So Alice would kill herself on day 2 (as would Bob).
If Alice does not do that, then Alice clearly did not consider herself to be in situation b. The only alternative to situation b is situation a, in which Alice, Bob, and I have blue eyes. So we all kill ourselves on day 3.
And obviously since all of this is symmetrical -- neither Alice, Bob, or I have any privileged information, that means that if I can see three people with blue eyes, and they don't kill themselves on day 3, then the only other valid scenario is that I also have blue eyes, so on day 4, I kill myself.
The information added is information about what we know that other islanders know about people's eyes, not what we know about people's eyes.
But no one knows n!
So I am not following the logic in the slightest.
Since no one knows n the entire logic sequence never gets started.
Specifically:
The only information the traveler gave them is that n >= 1. If n = 1 then the blue eyed person gained new information, which is how the inductive reasoning started, and I follow the logic that far.
But if n > 1 then there is no new information and the inductive process never starts because no one knows n, no one. There is not a single person who knows n.
One blue eyed person could look around, see only brown (or other color) eyes, and figure out they must have been the one talked about, right? Boom, gone.
Two blue eyed people would look around and see the other blue eyed person. However when the conditions for "one blue eyed person" aren't met, they would see the next day that there are 998 non-blue-eyed people and reason that the other blue eyed person must have seen a blue eyed person and it would have to be them. Boom. Gone.
Three blue eyed people would look around and see two other blue eyed people. After the first two days they'd realize that since the conditions of the 2 blue eyed person scenario weren't met, there are 3 blue eyed people, and since they can see 997 other-eyed people, they must be the third in that scenario. Boom. Gone. And so on and so on.
From there we have the simple case of n = 1: suppose Bob is the only blue-eyed islander. He's seen everyone else's eyes, knows nobody else has blue eyes, and so can conclude from n >= 1 that in fact n = 1 and he is that one.
For the case of n = 2: suppose Alice and Bob are the two blue-eyed islanders. Alice knows Bob is blue-eyed but doesn't know she is. Bob knows Alice is blue-eyed but doesn't know he is. There are two possibilities: n = 1 or n = 2, since they have seen every other person's eyes and know there are no other blue-eyed people. Each can watch the other's behavior on the first day. But since neither one knows their own eye color yet, neither one commits suicide that day. Then each one realizes that for the other not to commit suicide, it must be the case that n > 1. Since they know every other person's eye color, the only possible explanation is "n = 2 and I'm the other one". They commit suicide on day 2.
From there we can just apply the same reasoning every time. If n = 3, Alice, Bob and Carol each look for the other two to commit suicide on the second day (from the reasoning for n = 2). When they don't, the only possible conclusion is "n = 3 and I'm the third one" and they all commit suicide on day 3.
That line of reasoning then works with any successive value for n: if there are n blue-eyed islanders, each looks for the other n - 1 islanders to commit suicide on day n - 1. When that doesn't occur, the only possible conclusion those people can reach is "there's one more blue-eyed islander, and it's me". Then all n of them commit suicide on day n.
But the flaw is assuming that they will start counting at one.
The blue eyed person number 3 can see that there are 2 others at least, so they know for sure that n != 1, since n != 1 they have no reason to expect anyone to commit suicide.
So the whole sequence never gets started.
The distinction that matters to get the chain started is the difference between "I personally know there is at least one blue-eyed islander" and "everybody knows there is at least one blue-eyed islander and I know everybody knows it and they know I know it and I know they know I know it... (so on)".
Prior to that you can't know that other islanders could deduce all the things you can deduce from available information, and they can't know that you could deduce all the things they could. Afterward, you know exactly what they can deduce from the available information, they know what you can deduce, and you know that it produces a guaranteed conclusion, by day n, that n is the number of blue-eyed islanders.
> One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.
Why would it matter if he's a liar/truth teller in the classic island logic puzzle sense? It seems irrelevant to me because the islanders believe him fully and the puzzle is about figuring out the effects his statement has.