Blue-Eye Paradox: Solution Not Unique

[Andreas C]

I see what you mean. Yes, one needs to run back to RBB, but only for reductio ad absurdum. To prove that something cannot be, one considers the possibility that it can be and derives a contradiction.

But I don't think that there is any disagreement between you and me on that. The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.

I used to be confused in the same way that you are, then I thought about it, and realized that it was simple. You have to use 3 individuals and pretend you are them (so that it's easier to understand):

Person A:
I see 2 blue eyed people. Let's pretend I have brown eyes, and let's get in Person B's shoes:

Person B: I see a person with brown eyes and a person with blue eyes. Let's pretend I have brown eyes and get into Person C's shoes.

Person C: I see 2 brown eyers. I might have brown eyes, maybe nobody has blue eyes.

Person B: I KNOW Person C has blue eyes, but he doesn't. I can't be sure that Person C knows there is at least one person with blue eyes. I would only be sure if I was sure I had blue eyes, but I am not.

Person A: Hmm, it turns out that if I have brown eyes, I can't be sure that Person B knows that Person C knows there is at least one person with blue eyes. I know C knows that, but B doesn't. I know for sure that B has blue eyes, but B doesn't, just like I don't know for sure if I have blue or brown eyes.

 

[Laurie K]

Person A: I see 2 blue eyed people. Let's pretend I have brown eyes, and let's get in Person B's shoes:

Person B: I see a person with brown eyes and a person with blue eyes. Let's pretend I have brown eyes and get into Person C's shoes.

Person C: I see 2 brown eyers. I might have brown eyes, maybe nobody has blue eyes.

Wouldn't C see the same as B as A sees B and C as both being blue eyed?

 

[andrewkirk]

I find it very easy to get confused about this problem, however, my first instinct is that this statement is both incorrect and irrelevant. Why wouldn't Monk 1 already know that? And why would that knowledge make any difference?

Read through post 94, to see why it makes a difference. That covers the general case.

For the specific case of four monks, here's what is learned when the oracle speaks.

Monk 1 (M1) doesn't already know (that M2 knows that M3 knows that M4 knows that there is at least one blue), because M1 believes M1 could be non-blue, and if that were the case then*:
... - M2 sees only two blues. And M2 believes M2 could be non-blue, and if that were the case then:
... - M3 sees only one blue. And M3 believes M3 could be non-blue, and if that were the case then:
... - M4 sees no blues. And, provided the oracle has not spoken yet, M4 believes M4 could be non-blue (and if that were the case then there would be no blues at all).

When the oracle says there is at least one blue, the underlined scenario is ruled out, so now M1 knows that M2 knows that M3 knows that M4 knows that there is at least one blue. Put more succinctly, in the terminology of post 6, we then have $K^4C(1)$, whereas before we only had $K^3C(1)$ and $K^4C(0)$.

* note the nesting in the next bit, denoted by indentation. It signifies the number of levels of people thinking about what other people think, and is crucial, like in the movie Inception.

EDIT: I've just noticed Andreas C's post a couple up from here. I think he does a good job of explaining the same sort of concept as I'm describing here, from a different angle involving putting oneself in somebody else's shoes.

 

[D H]

The story tells that one day, which I call day-zero, the prophet said what he said, but the story does not tell what other events were happening before that.

To which version of the story are you referring? There are many, many versions, dating back to 1953 at a minimum. Some variations have previously been discussed right here on PhysicsForums. (Aside, NUTS! I'm still not quite used to this new setup, and as a result I just lost half an hour of research and writing as a result.)

Nitpicking can be fun, but it can also distract. In this case, nitpicking distracts from the very key distinction between mutual knowledge versus common knowledge. Mutual knowledge (for example, every dragon knows that some dragons have green eyes) is not the same as common knowledge (for example, every dragon knows that every dragon knows that some dragons have green eyes).

There certainly are issues with the concept of "common knowledge." All properly stated versions of the puzzle make the distribution between mutual knowledge and common knowledge quite clear. This distinction is key to understanding the puzzle. Nitpicking jut gets in the way. Whether common knowledge is attainable in the real world is a perpetual issue.

 

[.Scott]

@lukesfnWhen the guru makes the announcement on an island with four blue monks, what Monk 1 now knows to be the case, which he did not know to be the case earlier, is that Monk 2 knows that Monk 3 knows that Monk 4 knows that there is at least one blue.

That is similar to it, but it's not it. It's more complicated than that. Before the guru makes his announcement, all the monks realize that there is not enough information for anyone to deduce their eye color, and that is why years can go by without any monk committing suicide.

I've taken a few shots at trying to construct an English sentence describing what four blue-eyed monks know, but it's a very awkward sentence. For 3 blue-eyed monks ("blues") it is this: Every monk know that there are 2 or 3 blues and that every other blue knows that there are 1 to 3 blues. They also know something about what every other monk might know about what every other monk might know, but I won't try to describe that - and for 3 blues, it doesn't matter. What matters is that without the guru, there is nothing to contradict any of this progression.

Then the guru makes his announcement and everyone knows that at the next suicide opportunity, every monk will know that it is not possible for any monk to think that any monk thinks that 1 blue is possible. With that possibility eliminated, the next suicide opportunity will eliminate the 2 blue possibility.

But I think I described it more simply in post 100. Basically, once the guru makes his announcement, it triggers a series of "rules" that the monks (with perfect logic) have already deduced.

 

[.Scott]

Try this one:
Suicides opportunities are only at midnights.

Given that all monks:
1) Recognize all other monk on the island that they share with them.
2) Always exercise perfect logic.
3) Will commit suicide if and only if they know they are blue-eyed.
4) Always know when a suicide has taken place on their island.
5) Know that all other monks are like themselves, always logical, always follow the rules, always recognize all other monks, always know when a suicide has taken place on the island they are on.

You, a perfectly logical monk, arrive on the island on day 100 and see 12 blue-eyed monks (blues). On day 103, the guru makes his declaration. Then on day 104, six blues commit suicide.

If the guru makes no additional announcements, what if any suicide activity will occur?

 

[Andreas C]

Wouldn't C see the same as B as A sees B and C as both being blue eyed?

Yes and no. I think you misunderstood what I said. I am talking about what Person B would be thinking IF Person A had brown eyes (which, for all Person A knows, may or may not be true).

 

[TheQuietOne]

I think they would either kill the man or make him commit suicide because them not asking questions about their color the ones with blue eyes would not know ( neither would the tribesmen with brown eyes). But seeing that he knows his own eye color they would either force him to commit suicide or, if he refused (tried to escape) they would kill him. (unless a brown eyed guy looks at his blue eyed friend and says "goodbye").

 

[lukesfn]

Monk 1 (M1) doesn't already know (that M2 knows that M3 knows that M4 knows that there is at least one blue), because M1 believes M1 could be non-blue, and if that were the case then*:
... - M2 sees only two blues. And M2 believes M2 could be non-blue, and if that were the case then:

Ok, I was wondering if that was your intended meaning of M1, M2, but ironically, I couldn't be sure until I got this extra information. I already understand all this, and I think you might be missing the point I am trying to make.

... - M3 sees only one blue. And M3 believes M3 could be non-blue, and if that were the case then:
... - M4 sees no blues. And, provided the oracle has not spoken yet, M4 believes M4 could be non-blue (and if that were the case then there would be no blues at all).

Ok, this is where assumption comes in which I can't see the justification for.
M4 is a hypothetical case where there is only one blue eyed monk. I am not sure the monks can assume the hypothetical monk would have heard a hypothetical guru speak.

From the gurus speech, the 4 monks know that the guru told 3 or 4 blue eyed monks that at least one of them had blue eyes. Why does that make M1 consider that if there where 3 Monks, M2 would consider that if there where 2 monks, M3 would consider that there is a guru, or that the guru told the 2 monks that at least one of them has blue eyes?

But I think I described it more simply in post 100. Basically, once the guru makes his announcement, it triggers a series of "rules" that the monks (with perfect logic) have already deduced.

My point is that this is not correct. It appears to me that a logic short cut has been taken making an unjustified assumption, and feel like I have already pointed it out in this post and more so in post 102.

You have to consider that the rules of how the guru work in hyperthentical cases may be unknown. The monks only know that a guru spoke to either 3 or 4 blue eyed monks. How can they know that all other monks would come up with the same strategy based on counting from a time when they imagine a guru speaking to 1 monk?

 

[Astudious]

As I said in a previous post, no you don't need a prophet for that case, because it is an extreme... watch out; not needing him does not mean you get something wrong if you include him. We can just say that in that particular case his existence is unecessary...
But in all other cases his presence is needed to reach a reliable answer... (as I mentioned the RRB state, in which without the prophet everybody'd die)...I guess the prophet makes the problem solvable in all cases then, and so he's necessary for the solution, and for some special cases his information is just repeating.

But I believe that the bbb case where all 3 islanders are b allows an extension to a very large number of cases.

To be precise, as I see it, we only need 3 or more islanders with b for the prophet's pronouncement to be useless. In that case, there is no new relevant common knowledge and they would have committed suicide on a count starting from finding out about the suicide law.

*****

Why? Consider one of the other islanders, X, besides the 3 (say A, B, C) who must have blue eyes - these other islanders may have blue or brown (let's go with red, r) eyes. Of course all the islanders know [someone has blue eyes] already (X sees A, B, C with blue eyes; A sees B, C with blue eyes; B sees A, C with blue eyes; etc.). Do all the islanders know that {all the islanders know that [someone has blue eyes]}?

Well, X knows A can see B, C with blue eyes, and X knows B can see A, C with blue eyes, etc. so X knows {A knows [someone has blue eyes]}, X knows {B knows [someone has blue eyes]}, etc. X knows all the other islanders besides the 3 (A, B, C) will make the same inference about A, B and C, so X knows that {all the islanders know that [someone has blue eyes]}. (So all islanders besides the 3 (A, B, C) know that {all the islanders know that [someone has blue eyes]}.)

A knows B can see C with blue eyes, so A knows that {B knows that [someone has blue eyes]}. By symmetry A knows that {C knows that [someone has blue eyes]} (here the someone is B), and B knows that {A knows that [someone has blue eyes]}, B knows that {C knows that [someone has blue eyes]}, so forth. Also, A knows X can see B, C with blue eyes, so A knows that {X knows that [someone has blue eyes]}. By symmetry, B knows that {X knows that [someone has blue eyes]} (here someone is A, C), and C knows that {X knows that [someone has blue eyes]} (here someone is A, B). Since the same as applies to X also applies to all islanders besides these 3, thus A, B, and C know that {all the islanders know that [someone has blue eyes]}.

So all islanders know that {all the islanders know that [someone has blue eyes]}.

So if there are at least 3 islanders with blue eyes, then all islanders know that {all the islanders know that [someone has blue eyes]} - no need for a prophetic announcement.

****

It is true that the prophetic announcement cannot hurt, but the problem is that in many cases (those above) it does not suffice as a time-marker for starting the count. Rather, the suicide law itself (along with the villagers first seeing each other) would be the marker for the time to start in such cases.

 

[andrewkirk]

I am not sure the monks can assume the hypothetical monk would have heard a hypothetical guru speak.

Neither the monks nor the guru's statement are hypothetical. What is hypothetical is the state of knowledge of those monks, plus the colour of M1's eyes.

Bear in mind though that these recent posts are just loose attempts to render accessible the more formal argument in post 94. If you are concerned about validity of assumptions, that needs to be addressed in relation to post 94, as any apparent assumptions in the more recent posts may just be artefacts of the informal language they use.

Having said that, even 94 is not completely formal, as the problem of how to axiomatise the deductive system used by the monks remains unsolved. I think I may have a lead on that, based on Russell's solution to his own set theory paradox, and am investigating what I can do with it.

 

[.Scott]

I feel like there is flaw in the solution to the problem as posed because the monks must determine what the guru’s behaviour would be in a hypothetical situation which is not observed. It seems to a hidden assumption which I am confused about whether or not is justified.

No, nothing like that is happening. At the root of it, the monks know that if there were only one blue-eyed monk, that monks would respond to the guru's declaration by committing suicide at the next suicide time (midnight or whenever). So, once the guru makes the declaration and a suicide time passes with no suicide, every monk has a new way of determining that the number of monks among them with blue eyes is not 1. And they know all other blue-eyed monks know this. And the logic proceeds from there as described in post #100.

Examining the case of 4 blue eyed monks, once the guru makes the announcement, they all know that there are either 4 or 3 blue eye monks, but they don’t know if the guru made the announcement to 3 blue eye monks or 4 blue eye monks, so they can’t determine that if there where 3 blue eye monks the the guru would have said anything, so when they consider the possibility that there are only 3 monks as a hypothetical, they have to also have to consider the hypothetical that if there are 3 monks, then than the guru would not have spoken.

You're right in the sense that you have created a straw horse argument and then disproved it. But you are distracting yourself. What you are thinking is the proposed solution (in post 100) is not. All the blues know is that all blues, whether it be 3 or 4, will see a new demonstration that it is not 1 at the next suicide opportunity - and that they will see a consequential demonstration that it is not 2 on the second opportunity. None of them know what will happen on the third opportunity. This is all the result of logical deduction - not strategy.
When the guru makes his statement that he sees a blue-eyed monk, none of these perfectly logical monks is distracted by the fact that they already have certain evidence of this.[/quote]

Even though all 4 know they know that the if are only 3 blue eye monks, they know the guru has made the announcement to 3 blue eye monks, they don’t know there are 3 blue eye monks, so they don’t know what the guru’s behaviour actually might be in that case.

They know that the guru would only have made his statement that there is at least one blue-eyed monk, truthfully. That is sufficient for the post #100 logic to be used.

For the puzzle solution to work, the monks must determine that all other monks would determine though a chain of recursive hypothetical determinations that in the hypothetical situation of there being only one blue eyed monk that the guru would have made the same announcement, but by the above logic, I am not sure they can determine that.

All monks know that all other monks are perfect logicians. The rules are deduced as I stated them in post #100. Which specific rule have I not proven to your satisfaction?[/quote]

 

[.Scott]

My point is that this is not correct. It appears to me that a logic short cut has been taken making an unjustified assumption, and feel like I have already pointed it out in this post and more so in post 102.

You have to consider that the rules of how the guru work in [hypothetical] cases may be unknown. The monks only know that a guru spoke to either 3 or 4 blue eyed monks. How can they know that all other monks would come up with the same strategy based on counting from a time when they imagine a guru speaking to 1 monk?

Only blue-eyed monks matter. Monks of all other eye color are just furnishings.
It should be stated in the problem that when the guru speaks, all blue-eyed monks are listening, and that all blue-eyed monks know that all other blue-eyed monks are listening.
What I am describing isn't a "strategy" that a monk can come up with. It is of a set of logical rules that all monks will discover because they are "perfect logicians". And, all monks know that the other monks also a perfect logicians so they know that all of them will also discover these rules.

I took another look at your post #102 and will reply to it above.

 

[Heinera]

So if there are at least 3 islanders with blue eyes, then all islanders know that {all the islanders know that [someone has blue eyes]} - no need for a prophetic announcement.

But "all islanders know that {all the islanders know that [someone has blue eyes]}" is not enough. The proposition "all the islanders know that" must be nested the same number of levels as there are number of blue eyed islanders for the induction to work.

So if there are exactly 3 islanders with blue eyes, we need "all the islanders know that {all the islanders know that {all the islanders know that [someone has blue eyes]}}".

 

[.Scott]

It is true that the prophetic announcement cannot hurt, but the problem is that in many cases (those above) it does not suffice as a time-marker for starting the count. Rather, the suicide law itself (along with the villagers first seeing each other) would be the marker for the time to start in such cases.

The guru announcement will serve as a trigger to the countdown because it eliminates the possibility on only one blue-eyed monk on the next suicide opportunity. That is all that is critical. Any incident that creates that will trigger the count down. Simply showing up on the island together won't do this.

Many of the recursion statements in this thread about monks knowing about other monks are either wrong or irrelevant - and are effectively straw horses in the discussion. For example, this is an argument against a straw horse:

So all islanders know that {all the islanders know that [someone has blue eyes]}.

So if there are at least 3 islanders with blue eyes, then all islanders know that {all the islanders know that [someone has blue eyes]} - no need for a prophetic announcement.

The simplest way of stating what happens when the guru makes his declaration is that it sets up a public demonstration that the number of blue-eyed monks is not 1. The logic that follows is described in post 100.

 

[D H]

So all islanders know that {all the islanders know that [someone has blue eyes]}.

This is mutual knowledge, but it is not common knowledge.

So if there are at least 3 islanders with blue eyes, then all islanders know that {all the islanders know that [someone has blue eyes]} - no need for a prophetic announcement.

Yes, there is. This announcement is the common knowledge that starts the countdown. There is a big difference between mutual knowledge and common knowledge.

I haven't seen the post that explains the version of this problem that is being discussed, and there are so many variations of this problem. A partial list:

• Terence Tao's version, posted here, here, and here. This version involves an island populated with tribespeople with various eye colors. It is forbidden to discuss eye color because someone who does discover the color of their eyes must commit suicide at noon for all to see. But then some blue-eyed foreigner visits to the island and tells the entire tribe “how unusual it is to see another blue-eyed person like myself in this region of the world.”
• https://www.physics.harvard.edu/uploads/files/undergrad/probweek/prob2.pdf. Then you visit the island and on your departure you tell the dragons that at least one has beautiful green eyes.
• A mathematics department populated with arrogant mathematicians, each of whom think they are infallible but must resign if they find they have published a paper containing an error. One day, a visiting mathematician announces “Someone here has made a mistake.”
• A group of people eat barbecued spare ribs, some of whom have barbecue sauce on their faces. The cook says “At least one of you has barbecue sauce on her face. I will ring the dinner bell over and over, until anyone who is messy has wiped her face. Then I will serve dessert.”

In all of these examples, there is a trigger that creates common knowledge that starts a countdown. The final link is part of a very nice article on common knowledge at the Stanford Encyclopedia of Philosophy. This article clearly distinguishes between mutual knowledge and common knowledge.

 

[lukesfn]

Although, I am not sure everybody quite understood the point I was bringing up, I'm pretty comfortable with my understanding of the puzzle and the paradox now. If applying the same inductive logic, the monks may all decide to leave, but if applying detective logic, they may all decide to stay. I don't see how inductive logic can be seen as perfect logic, therefore, with the set of assumptions I would choose, all monks would stay. I think this puzzle is an example of the flaws of inductive logic and the paradoxes it can create.

 

[.Scott]

Although, I am not sure everybody quite understood the point I was bringing up, I'm pretty comfortable with my understanding of the puzzle and the paradox now. If applying the same inductive logic, the monks may all decide to leave, but if applying detective logic, they may all decide to stay. I don't see how inductive logic can be seen as perfect logic, therefore, with the set of assumptions I would choose, all monks would stay. I think this puzzle is an example of the flaws of inductive logic and the paradoxes it can create.

The logic they use is entirely deductive.
If there was only one blue-eyed monk and the (truthful) guru declares that there is a blue-eyed monk, that one blue-eyed monk would deduce it was himself by eliminating all other possibilities. I'm sure you can work out the problem with two blue-eye monks as well - using exclusively deductive reasoning.

 

[Heinera]

Many of the recursion statements in this thread about monks knowing about other monks are either wrong or irrelevant - and are effectively straw horses in the discussion.

I don't entirely agree that recursive statements are irrelevant in this problem. For instance, the guru could make the suicide moment happen one step earlier by saying "there is at least one monk with blue eyes, and everybody knew that", etc.

 

[lukesfn]

If there was only one blue-eyed monk and the (truthful) guru declares that there is a blue-eyed monk, that one blue-eyed monk would deduce it was himself by eliminating all other possibilities. I'm sure you can work out the problem with two blue-eye monks as well - using exclusively deductive reasoning.

What if there was only one blue-eyed monk and the guru didn't speak?

Anyway, I think we are going around in circles and I am not sure how to explain my self better then I already have.

 

[Andreas C]

What if there was only one blue-eyed monk and the guru didn't speak?

Anyway, I think we are going around in circles and I am not sure how to explain my self better then I already have.

Nothing would happen then. If the guru didn't speak, nothing would happen. But since he does speak, he triggers the events.

The problem is not a paradox. It's a simple application of deductive logic for 3 persons, I agree, it seemingly gets more complicated and counter intuitive with more, but that doesn't mean anything. Of course, it's not stated very well, because the monks/islanders may or may not choose the same strategy, if we are to accept this solution we have to determine if there are no other solutions.

 

[forcefield]

But if the priest makes a declaration, then he knows that on the second opportunity the "2" theory will be tested.

That's a bit vague. I agree that recursion like "everyone knows that everyone knows that everyone knows" is not needed but it is a simple way to express that "A knows that B knows that C knows" and it's permutations.

 

[stevendaryl]

This is obviously a mathematical problem (at least once you've clarified the assumptions and the reasoning), but from my messing around, it seems notoriously difficult to formulate mathematically. One way is to use modal propositional logic.

Let $B_1, B_2, ...$ be propositional variables with the interpretation that $B_n$ means "islander number $n$ has blue eyes". Let $K_1, K_2, ...$ be modal operators with the interpretation that $K_n P$ means "islander number $n$ believes $P$".

Then we would need to axiomatize how these modal operators work. Something along the lines of:

For $i \neq j$,
$B_i \leftrightarrow K_j B_i$ (Everybody knows whether or not everybody else has blue eyes)

And then there would be rules of inference of the form:

$(K_n A) \wedge (K_n (A \rightarrow B)) \rightarrow K_n B$

This seems enormously complicated. An alternative approach is to use graphs to represent possible worlds and their connections. Let a closed circle represent a possible world. Inside the circle, we list all the ID numbers of islanders with blue eyes. For each $j$, we draw an arrow from world $W_1$ to world $W_2$ if islander number $j$ in world $W_1$ believes that he might be in world $W_2$.

For a simple example, imagine a world with two islanders. Here are shown 4 possible worlds: (W1) No blue-eyed people, (W2) Islander #1 has blue eyes, (W3) Islander #2 has blue eyes, and (W4) Both have blue eyes. In world W1, islander #2 believes that he might be in worlds W1 or W3, and islander #1 believes he might be in worlds W1 or W2.

Now, to simplify things, I'm going assume that:

• All blue-eyed islanders are indistinguishable. They believe the same things (or analogous things).
• All non-blue-eyed islanders are indistinguishable.
• The beliefs are completely determined by the objective facts (how many people with what colored eyes there are). So there can't be two worlds with the same number of blue-eyed and non-blue-eyed people, but differ in what people believe is possible.
• There are the same number of islanders in every possible world.

In light of these assumptions, we can characterize a world by the number of blue-eyed individuals in it. For definiteness, let's assume there are 3 islanders. Then we can characterize the situation by a sequence of graphs, one graph per day. On day -1, nobody knows anything except what they can see (and what they can deduce about what other people can see). On day 0, all the people in all possible worlds are told that there is at least one blue-eyed person. In any possible world, if a blue-eyed person can deduce that he is blue-eyed, then he kills himself. On day 1, in every possible world, if someone sees that a blue-eyed person is still alive, he deduces that that person did not deduce that he had blue eyes. Etc.

To say that someone deduces some fact means that that fact is true in every world that he considers possible.

Since all blue-eyed people believe the same thing, we will just use blue arrows to represent what blue-eyed people believe, and brown arrows to represent what non-blue-eyed people believe. So here is the sequence of situations (where a situation is an entire connected set of possible worlds corresponding to a day)

• On Day -1, blue-eyed people in any possible world believe that they are either in their actual world, or one with one fewer blue-eyed person (because they consider it possible that their own eyes are not blue). Non-blue-eyed people believe that they are either in their actual world, or one with one more blue-eyed person.
• On Day 0, it is announced (in every possible world) that there is at least one blue-eyed person. This eliminates the possible world with 0 blue-eyed people. So the graph of possible worlds is changed so that there is no blue arrow out of the world with 1 blue-eyed person. So the blue-eyed person in that world knows what world they are in, and so know that they have blue eyes, and so they commit suicide.
  
• On Day 1, in the possible world in which there are 2 blue-eyed people, they can see that nobody committed suicide. So that means that they do not live in the world with 1 blue-eyed person. So that arrow is eliminated, and they know exactly what world they are in--the one with 2 blue-eyed people. So they commit suicide.
• On Day 2, in the possible world in which there are 3 blue-eyed people, they can see that nobody committed suicide, so that means there are 3 blue-eyed people. So they commit suicide.

 

[.Scott]

it seems notoriously difficult to formulate mathematically

I agree. Or as I said before, to try to make a step-by-step statement about what every monk knows about every other monk ...
But what's wrong with the logic in post #100?

Now, to simplify things, I'm going assume that:

• All blue-eyed islanders are indistinguishable. They believe the same things (or analogous things).
• All non-blue-eyed islanders are indistinguishable.

You can treat the blue-eyed islanders as equivalent, but they are absolutely not "indistinguishable". It is critical to the logic that they be absolutely distinguishable so that each blue-eyed can determine that he is dealing with the same group of individuals at every event.

The non-blue-eyed islanders are irrelevant. You can have as many as you wish without effecting the logic. As I said before, they are only "furnishings".

 

[.Scott]

I don't entirely agree that recursive statements are irrelevant in this problem. For instance, the guru could make the suicide moment happen one step earlier by saying "there is at least one monk with blue eyes, and everybody knew that", etc.

No. But he could make it happen one step earlier by saying that he sees at least 2 blue-eyed monks. The statement "there is at least one blue-eyed monk" is a very specific trigger to a very specific sequence.

 

[.Scott]

That's a bit vague. I agree that recursion like "everyone knows that everyone knows that everyone knows" is not needed but it is a simple way to express that "A knows that B knows that C knows" and it's permutations.

OK, how's this:
Let $T_n$ represent the theory that there are $n$ blue-eyed monks on the island.
Let "day" represent the passing of an opportunity to commit suicide (or leave the island, depending on the story).
Whenever there is the credible statement: $~T_0$, then on the next day, either there will either be a suicide ($T_1$) or not. If there is not, it will prove $~T_1$. This is because if $T_1$, then that only blue-eyed monk knows $T_0 or T_1$, so with $~T_0$ he can deduce $T_1$ and that he is that 1. If no one commits suicide after day 1, that proves $~T_1$.

This logic holds even if other information already demonstrates $~T_0$ because this new declaration allows all the blue-eyed monks to know that $~T_0$ was given to all monks on the same day in a way that makes $~T_1$ deductible on the next day.

 

[.Scott]

What if there was only one blue-eyed monk and the guru didn't speak?

Anyway, I think we are going around in circles and I am not sure how to explain my self better then I already have.

Using the notation in my previous post, that monk knows $T_0 or T_1$, all other monks know $T_1 or T_2$. Without new information, such as the statement $~T_0$, nothing happens.

 

[stevendaryl]

You can treat the blue-eyed islanders as equivalent, but they are absolutely not "indistinguishable". It is critical to the logic that they be absolutely distinguishable so that each blue-eyed can determine that he is dealing with the same group of individuals at every event.

Okay, well I'm assuming that the population is fixed (other than deaths by suicide).

The non-blue-eyed islanders are irrelevant.

Not quite. For the puzzle to work, a blue-eyed islander has to consider it possible that his eyes are non-blue. So in my possible-worlds semantics of the puzzle, every world has the same total number of islanders, but differ in how many are blue-eyed.

 

[256bits]

but differ in how many are blue-eyed.

The number of non-blue-eyed islanders should be irrelevant. In the puzzle given, the non blues could be 1, 10, 1000,...
( Oh that was already stated )
What one has to consider is YOU as an islander, who does not know his eye color, and the deductive process to go through while perceiving only the blue-eyed and determining if your color is blue or non-blue. All the other blue-eyed will go through the same process. If you are blue-eyed then you are included in the blue eyed deductive process. If you are non-blue then you become irrelevant to the blues. As a brown, You can keep on doing Case A but it does not get you off the island.

Case A You are brown, but you don't know it but are hoping for the chance to leave which never comes.
EX1 1 blue eyed Jane - Jane sees no other blue so she is it. You see her leave on Day 1 so you are non-blue
Ex 2 2 eyed blue - Jane sees 1 blue and Sally sees 1 blue. You see 2 blue. Jane, Sally leave on Day 2. You are non-blue.
etc

Case B You are Blue, but don't know it and are hoping. eventually your chance to leave will come.
Ex 1 Jane, You blue. You both see one blue. She doesn'y leave on Day 1, so you and her deduce you are both blue, and you both leave on Day 2
Ex 2 Jane, Sally, You blue. All see 2 blue. Nobody leaves on Day 1, or Day 2, so all deduce they are blue and leave on Day 3.
etc.

 

[lukesfn]

I realized I keep confusing my self. I've been suffering a cold, and my ability to think clearly keeps abandoning me, and I have difficult even explaining what I am trying to understand.

 

[stevendaryl]

The number of non-blue-eyed islanders should be irrelevant. In the puzzle given, the non blues could be 1, 10, 1000,...
( Oh that was already stated )
What one has to consider is YOU as an islander, who does not know his eye color, and the deductive process to go through while perceiving only the blue-eyed and determining if your color is blue or non-blue

Yeah, I went through it. The point is that there are various "depths" of statements. Letting the blue-eyed islanders be numbered 1, 2, 3, etc.

1. There are actually 100 blue-eyed individuals.
2. Islander #1 believes that there are either 99 or 100 blue-eyed individuals.
3. Islander #1 believes that islander #2 believes that there are 98, 99 or 100 individuals
4. Islander #1 believes that islander #2 believes that islander #3 believes that there are 97, 98, 99 or 100 individuals.

So the reasoning involves considering "possible worlds" in which there are between 0 and 100 blue-eyed individuals. But in every possible world, there are 100 individuals doing the reasoning, although they aren't all blue-eyed in all possible worlds. So the non-blue-eyed people are relevant in other possible worlds.

 

[Heinera]

No. But he could make it happen one step earlier by saying that he sees at least 2 blue-eyed monks. The statement "there is at least one blue-eyed monk" is a very specific trigger to a very specific sequence.

That is not correct (the "No"). If the guru says that "everybody knows there is at least one blue-eyed monk", a group of two monks would immediately (and independently) deduce they both had blue eyes, and could thus skip a time step. (Monk A reasons that if he had brown eyes, monk B couldn't know there was at least one blue-eyed monk, and same for B vs. A). The induction that takes us to n > 2 goes as before.

Furthermore, if the guru says "everybody knows that everybody knows there is at least one blue-eyed monk" (to a group of size n >= 3) he would move the suicide moment forward by two time steps, etc. This clearly shows that the nested levels of knowledge are relevant to the problem.

 

[Demystifier]

For a last couple of days, I have not been answering any questions addressed to me. I wanted to think about carefully about all this ones again. In the next post I will present my last conclusions, which, I hope, answer many questions and objections addressed to me. If not, please refer any new questions/objections to my next post, which is supposed to surpass all my previous posts.

 

[Demystifier]

Refined critique of the standard solution

I have found a simpler and sharper way to explain what exactly is wrong with the standard solution. In my explanation I will assume that the reader is already familiar with the standard solution, which will allow me to skip over some details.

First let me present some crucial correct results of the standard solution:

(1) The information given by the prophet is sufficient for all blue-eyers to eventually realize that they are blue-eyers.

(2) If there are n blue-eyers, they will realize that they are blue-eyers after n days, starting from the first day at which they acquire information equivalent to the information given by the prophet.

In addition, if one assumes

(3) No other source of information, except by the prophet himself, provides sufficient information for all blue-eyers to eventually realize that they are blue-eyers.

then one arrives at the final result

(4) If there are n blue-eyers, they will realize that they are blue-eyers after n days, starting from the first day at which the information was given by the prophet.

Note that (1) and (2) are not sufficient to get (4). To get (4), one also needs (3). In other words, (3) is tacitly assumed in the standard solution that leads to the final result (4).

But assumption (3) is wrong. Consequently, the standard solution is wrong as well.

Why is (3) wrong? Well, (3) is correct for n=1 and n=2. But (3) is wrong when n=3 or more. Let me only explain why is (3) wrong for n=3, because the generalization for higher n is trivial.

The prophet made the public statement:
"Some of you has blue eyes."
Clearly, this is equivalent to the public statement:
"At least one of you has blue eyes."

But now consider the following scenario. Instead of making a public statement, to each monk the prophet gives a separate private envelope with a letter. Each letter contains the same message reading as follows:
"At least one of monks has blue eyes. This message is sent to all monks."
Clearly, this scenario provides information equivalent to the public statement above. Even though the letter is not public, the second sentence in the letter makes the same effect as publicity of the one-sentence public statement above.

Next observe that the two-sentence message above is equivalent to:
"At least one of monks has blue eyes. Now all monks know that."

Now the crucial question is this. Is the information provided by the prophet new to the monks? Let us study case by case.

n=1: For this single blue-eyer, the first sentence in the letter "At least one of monks has blue eyes" is new.

n=2: In this case, the blue-eyers already know that "At least one of monks has blue eyes". They know it without the prophet. It is not new. But the second sentence "Now all monks know that" is something new.

n=3: In this case the first sentence is not new, similarly to the case n=2. In addition, for n=3, even the second sentence is not new. (For instance, the first blue-eyer knows two blue-eyers (the second and the third one), he also knows that the second blue-eyer knows at least one blue-eyer (the third one), and finally he knows that the third blue-eyer also knows at least one blue-eyer (the second one).) Therefore nothing in the prophet's message is new in the case n=3. In other words, assumption (3) is wrong for n=3. Q.E.D.

 

[maline]

But now consider the following scenario. Instead of making a public statement, to each monk the prophet gives a separate private envelope with a letter. Each letter contains the same message reading as follows:
"At least one of monks has blue eyes. This message is sent to all monks."
Clearly, this scenario provides information equivalent to the public statement above. Even though the letter is not public, the second sentence in the letter makes the same effect as publicity of the one-sentence public statement above.

Next observe that the two-sentence message above is equivalent to:
"At least one of monks has blue eyes. Now all monks know that."

No, the statement "This message is sent to all monks" includes the second sentence as well: Everyone knows that everyone knows that everyone knows etc. that at least one of monks has blue eyes. This is nontrivially stronger than "Everyone knows that at least one of monks has blue eyes".

See andrewkirk's post # 94, I think it is the clearest thus far.

Also note that before the prophet speaks, no one has reacted in any way to anyone's eye color, so it is clear that no one can deduce his eye color from anyone else's actions. After the prophet speaks, you have agreed that the deduction can be made. There remains to clarify how this change comes about, which several posters including andrewkirk have done.