3
$\begingroup$

The commonest answer to these 3 follow-up questions is: 'someone has blue eyes' must be common knowledge, for all the blue-eyed people to leave. But why? Don't you only need know your own eye color to leave?

This is clearest where $n=1$. You don't care whether it's common knowledge that someone has blue eyes. Only you need to know that someone has blue eyes, and given that you don't see anyone else, you will deduce that 'someone' must be you.

The case where $n=2$ is similar. Now you do care whether the other blue-eyed person knows that there is someone with blue eyes, but you don't care that they know that you know the same fact (hence you don't care whether it's common knowledge). As long as they know, and they don't leave the first night, then you will deduce that they also see someone with blue eyes, which must be you.

Suppose that the guru told each of you separately that there is someone with blue eyes, but she only told you that she told the other guy this fact. Then you would be able to leave on the second night, whereas the other guy would not.

So why does common knowledge matter for being able to leave? Also, common knowledge doesn't seem to matter because it is defined as having an infinite series of "knows that" propositions, but here n=100 is finite.

ETA: Common knowledge is used as an argument for why the guru's imparted information matters, but if common knowledge doesn't matter, then the question remains: why does the guru's imparted information matter (i.e. what new information does it contain)?.

I would guess that it contains no new information and the inductive solution is in fact invalid, and that no one leaves the island.

$\endgroup$
2
$\begingroup$

I give a quite detailed answer at the linked question, that tries to explain in detail how each event changes the state of (mental) affairs on the island, and how much of "common knowledge" is really required to eventually cause the individuals concerned to leave. In my notation there with $C$ for "it is common knowledge that" and $E$ for "everybody knows that", common knowledge $C(P)$ means $\forall k\in\Bbb N:E^k(P)$; of the information $C(n>0)$ caused by the declaration, it is the instance $E^{100}(n>0)$ that ultimately gets things moving.

$\endgroup$
  • $\begingroup$ Okay, I see what you're saying. The guru makes it common knowledge ($C(n>0)$), which contains $E^{100}(n>0)$, which is sufficient. But a follow up question: if you were on the island, and the guru says her thing, what about it makes you think that induction can be used to solve the problem in the first place? $\endgroup$ – Ken Aug 23 '14 at 8:07
  • $\begingroup$ There's two different things: stating precisely what happens, as if debugging a program (which is what I tried in my answer), and proving some property of the process. For the latter, possibly after studying in detail what happens to get an idea, it is most efficient for an iterative process like the one at hand to prove by induction, even though it is not absolutely necessary for a finite process. $\endgroup$ – Marc van Leeuwen Aug 23 '14 at 10:18
1
$\begingroup$

If $n=1$ and no one knows any more than they can see, then the one blue-eyed person does not know that there are blue-eyed people on the island.

If $n = 2$, then blue-eyed person $a$ does not know that blue-eyed person $b$ knows that there are blue-eyed people on the island. For all $a$ knows, $b$ could be alone in his blue-eyed-ness, in which case $b$ wouldn't know that there are blue-eyed people.

Something about the knowledge of blue-eyed people has to change in order for the mass-exodus to happen, and making it common knowledge is such a thing. But as you point out, common knowledge is a bit stronger than what is needed in each case.

Yes, in the case $n = 2$, if someone told $a$ that $b$ knows a blue-eyed person, then $a$ would leave the first night. There are many other more specific things you could tell $a$ or $b$, but that's not the point of the puzzle. The point of the puzzle is that no matter how many blue-eyed people are on the island, exclaiming that there exists blue-eyed people will bring new information to the table. That, in turn, will make all the blue eyed people leave on the same night.

$\endgroup$
  • $\begingroup$ Common knowledge is used as an argument for why the information the guru imparted matters, but if common knowledge doesn't matter, then the question remains: why does the information the guru imparted matter (i.e. what new information does it contain)? -- one hypothesis being that it contains no new information and the inductive solution is in fact invalid, and that no one leaves the island. $\endgroup$ – Ken Aug 19 '14 at 7:49
  • $\begingroup$ @Ken Common knowledge contains in it everything that matters and more still. You don't need common knowledge, but common knowledge is sufficient to make things happen. $\endgroup$ – Arthur Aug 19 '14 at 8:37
  • $\begingroup$ @Ken you can think of it as: the guru tells person A "there is a person with blue eyes" and the guru tells person A "and B now knows there is a person with blue eyes" and the guru tells A "and now C knows that B knows that there is a person with blue eyes" etc. You see it is important that the guru makes his declaration in front of everyone, so that he is telling everyone more than just what he says. $\endgroup$ – DanielV Aug 22 '14 at 6:29
  • $\begingroup$ In the case n > 2, no new information is given. However, a synchronized starting point is created for a daily countdown that demonstrates how many blue-eyed people are on the island. The special cases n = 1 and n = 2 use a different argument than when n > 2. $\endgroup$ – Jed Schaaf Jul 14 '16 at 23:47
1
$\begingroup$

There is a difference between the hypothetical of 2 blue eyed people and the hypothetical of 3 or more blue eyed people. A lot of the answers to this puzzle seem to miss this distinction in their rush to an answer.

As many have said, with the hypothetical of 2 blue eyed people, they hear the proclamation of the guru, and after the 1 blue eyed person they see doesn't leave, they deduce that they are the second, and leave the second night.

Conversely, in the hypothetical of 3 blue eyed people... every person on the island can see someone with blue eyes, in fact, they can see at least 2 of them. This means that they can deduce that not only is there a blue eyed person on the island... but that everyone already knows that there is! Even the people with blue eyes see 2, which means they know that the other blue eyed people see... at least 1. This changes everything, as the proclamation of the guru is NOT required.

So, with the hypothetical of 3 blue eyed people or more, everyone has preexisting knowledge that everyone knows there are blue eyed people.

Given the knowledge in this case, each of the 3 blue eyed people knows that there is a blue eyed islander, and they know that the guru sees a blue eyed islander. So from moment zero the countdown begins.

The new nestled hypothetical is that if there is only one blue eyed islander, knowing that the guru sees a blue eyed islander, it must be themselves, as they see none. They leave immediately.

With two, they each watch as the other doesn't leave and realizes that they are the 2nd. And leave the following night.

Etc.

What is interesting is that the same occurs for the brown eyed islanders. As before, in a hypothetical of 3 or more brown eyed islanders, everyone knows that there is a brown eyed islander, and that everyone knows this. So, the countdown begins for the brown eyed islanders as well.

Why is this important? Because this means that everyone except the guru left the island on day 100. Long, long before the guru ever spoke her famous proclamation.

(TLDR; Common Knowledge is established immediately in any scenario wherein there are 3+ of an eye color, the guru's utterance isn't useful)

$\endgroup$
  • $\begingroup$ Two problems: First, the brown eyed people do not know that the only other eye color is brown, so a brown-eyed person cannot deduce his own eye color and leave. Second, in the case of 3 blue-eyed people, if I have blue eyes I will see 2 others will blue eyes. Therefore, I know that the other blue-eyed people see either 1 or 2 other people will blue eyes, which means I do not know whether everyone knows that everyone knows that blue eyes exist, which is a requirement for common knowledge. $\endgroup$ – Ken Sep 16 '15 at 3:02
  • $\begingroup$ +1 for "So from moment zero the countdown begins." But in your own "rush to an answer" you have not addressed the effect of the knowledge of the minimum possible number of blue-eyed people. The implications of this additional point means that the maximum number of required days is 4. If it is known that there are only blue and brown, then the brown-eyed people would know by the 5th day (the day after the blue-eyed people left). With more than two eye colors, no one else will leave. $\endgroup$ – Jed Schaaf Jul 14 '16 at 23:43
0
$\begingroup$

The blue-eyed people determine their eye colour by a proof-by-contradiction that creates hypothetical people each of whom uses a proof-by-contradiction based on hypothetical people etc. It assumes that every one of these hypothetical people is able to fully reason out the thinking of each of the hypothetical people they think of. In order for the proof to word, the hypothetical only-blue-eyed-person must know that there is someone with blue eyes.

So I think the guru is not passing on information about the eye-colour of anyone. They are changing everyone's beliefs about everyone else's beliefs. Before her statement, I can consider the possibility that others can consider a hypothetical person who does not know there is anyone with blue eyes (because they are the only one, and haven't been told). After the guru has spoken, I must now assume that everyone on the island now only thinks about hypothetical people who know there are blue-eyed people. Everybody simultaneously changes their belief about what everyone else believes, and the only reason they are correct to do so (and therefore do so at all) is because all the changes happen simultaneously.

So I think it's a bit like the sentence 'this sentence is true'. If you think of it as true, then it is true. If you think of it as false, then it is false. There are two accurate and self-sustaining states. The guru's statement changes the situation on the island from one consistent state to another.

$\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.