Monday, February 11, 2008

Blue-eyed Islander Puzzle - an analysis

Many people find themselves stumped by the so-called Blue-Eyed Islanders puzzle. There is also much controversy over its supposed solution. I'm going to analyze the problem and the solution, and in the process, explain why the solution works.

To begin, let's modify the problem slightly and say that there's only 1 blue-eyed islander. When the foreigner makes his pronouncement, the blue-eyed islander looks around and sees no other blue eyes, and being logical, correctly deduces that his own eyes must be blue in order for the foreigner's statement to make sense. The lone blue-eyed islander thus commits suicide the following day at noon.

Now comes the tricky part, and the source of much confusion. Let's say there are 2 blue-eyed islanders, Mort and Bob. When the foreigner makes his pronouncement, Mort and Bob look around and see only each other. Mort and Bob thus both temporarily assume that the other will commit suicide the following day at noon. Imagine their chagrin when they gather in the village square at noon the next day, and Mort and Bob both look at each other in surprise because Mort thought Bob was going to commit suicide, and Bob thought the same of Mort! Now both Mort AND Bob know their own eye colour is blue, and they will both commit suicide on day 2.

The very same argument can be extended to 3 blue-eyed islanders, Mort, Bob and Sue, who will commit suicide on the third day at noon. The day of the pronouncement, the three of them see each other, and Sue assumes Mort and Bob see only each other. Being logical, she thus deduces that they will commit suicide on the second day, by the above argument. Mort and Bob each see the same number of blue eyes as Sue, and thus reach the very same conclusions.

Imagine Sue's chagrin, when she gathers in the village square on the second day, and Mort and Bob are both surprised that she's not committing suicide! She now knows that her eye colour is also blue, and all three of them will kill themselves on the third day.

This inductive argument can be generalized to N blue eyed islanders, where all N of them will suicide on the Nth day after the pronouncement. QED.

40 comments:

Marius said...

I recently stumbled upon many versions of this puzzle and every time i read it i was sceptical of the solutions given.
Why? Because such a system(of people) cannot exist in the first place!
Let's say that the brown eyed persons don't matter and they don't leave the island if they founf out their eyes colour.Only the blue ones leave.
If only one person was blue eyed the scenario is ok and the person will leave the first day.
The argument for 2 blue eyed persons is also correct.
The problem comes with 3 or more blue eyed persons because in this scenario there is no trigger!All persons knew already that everyone knew that "there are blue eyed persons in the village".
The very same argument descried by you can be followed in the case with 3 blue eyed persons without the intervention of the outsider.

Sandro Magi said...

It is hard to quantify precisely what information is added using an informal language like English, but rest assured that additional information is provided by the outsider. See the actual mathematics involved.

jim said...

I believe Marius is correct and Sandro Magi and many others have made a logical error.

The simplest argument to show that nothing will happen on the island is to look at four cases:
1. The foreigner remarks on seeing blue eyes.
2. The foreigner remarks on seeing brown eyes.
3. The foreigner remarks on seeing brown and blue eyes.
4. The foreigner asks everyone to deduce his/her own eye color without making any remark about what he sees. Assume there is a taboo about thinking about one’s own eye color until he arrives or some such detail.

Clearly one can’t both deduce in case 1 that all the blue eyed people commit suicide on the 100th day and in case 2 deduce that the brown eyed people do the same. That's silly. In both cases no new information is given. If that isn’t sufficient argument then surely case 3 should give one pause. Do they all commit suicide or none of them or what? If that case doesn't let one know that the logic is incorrect consider case 4 where no information at all is given but only a starting time for people to think logically. In this case people have absolutely no reason to believe anything about their own eye color.

So where does the inductive argument fail? On an island with one blue eyed person and some brown eyed people clearly something happens if the foreigner claims to see blue eyes. Likewise an island with two blue eyed people.

However, as Marius says, nothing at all happens on an island with three blue eyed people. This is because everyone deduces, regardless of one’s own eye color, that nothing will happen on the first day. Hence no new information will be gleaned from observing events on the first day. Since no new information is acquired by waiting one day how can there be any information acquired on any subsequent day?

If you don’t like the inductive argument blowing up that fast consider an island with four blue eyed people where not only does everyone know that nothing will happen on the first day but everyone knows that everyone else knows it as well. So what is everyone waiting for? They can even discuss this without giving away anyone's eye color.

For the induction to get going there must be in at least one person's mind the possibility that another person might commit suicide the first night. So for three or more blue eyed people there is no induction at all.

Sandro Magi said...

Jim, you contradict yourself. First you say that case 1 and 2 provide no new information, then you admit that when there are 1 or 2 blue eyed on the island, something does change when the foreigner speaks. If no new information is provided, then why does anything at all change? The results should be invariant on the number of people available if truly no new information is provided.

This is the danger of informal reasoning, and I'm afraid that your intuition will not help you here. The only way to think about this problem clearly is a rigourous, formal approach. If you want to attack the description I provide in this post, then you will have to point out an actual logical flaw in the induction argument from 2 to 3 people. Appealing to the "information" available is not such an attack because you have not quantified "information", and so you cannot make rigourous claims about the information available.

However, mathematicians and logicians have precisely quantified information in such puzzles. This puzzle falls under "Common Knowledge" in logic (this link was in the post I linked to in the first sentence). Suffice it to say, the informal description I tried to provide in this post is precisely the accepted, formal result in logic.

I'm not sure how I could describe the generalization to 3 people any clearer, so I'm open to suggestions. I framed the informal descriptions with each agent making assumptions, but that was just for simplicity of presentation; no assumptions are actually necessary.

I'd appreciate an update on what manages to finally convince you of this result, or perhaps what you misunderstood in my explanation or those you read elsewhere, but I assure you that the result is formally sound.

jim said...

Hi Sandro Magi,

There is nothing logically inconsistent with useful information being supplied to a person who is told there are blue eyes when he has never seen them compared to a person who has been seeing lots of them all his life. I'm not sure why you expect the same words to be equally valuable in all situations.

One suggestion that might clear up your thinking is to tell us what you would expect to happen in the cases 2-4 described above.

Additionally here are a few more thoughts to consider. The failure of induction to work in the case of an island with 3 or more blue eyed people is, surprisingly, in the N=1 case. On an island with one blue eyed person the N=1 case works fine. On an island with N=2, induction also works fine.

However on an island with 3 or more blue eyed people the induction never gets started. There is no one on the island who imagines anyone will commit suicide on the first night. Reference to other islands where there are 1 or 2 blue eyed people is irrelevant to an island with 3 or more blue eyed people. When the number gets to 4 blue eyed people not only is there no one worrying about the first night but everyone knows that everyone else knows this. In fact the islanders could talk about this openly without giving away anyone's eye color. They could say "Hey, we all know that there are at least two blue eyed and two brown eyed people so we all know that there is no way to get Sandro Magi's weird logic going, right?

If you consider, say, the first hundred proof by induction problems you ever did, you will notice that this one is different from all the others. In all those when you get to the N+1th stage the Nth stage is embedded in the objects you are considering, be they equations, geometric objects, or even imagined situations like the present. The mistake lots of people online have made with this problem is thinking that what happens on an island with 1 or 2 blue eyed people has anything to do with an island with 100 blue eyed people. On an island with 100 blue eyed people no one for even a moment imagines that anyone else on the island is thinking he might be on an island with only one blue eyed person. So the induction never gets going for N=1. In order for your scheme to work the induction has to work on the actual island in question, not other islands with fewer blue eyed people.

Here is a real fast way to turn around your thinking. Strip away all the tropical island romance and suicide pacts, taboos and dancing hula girls, and consider a completely equivalent, albeit quite boring, problem. You put four blue hats and four brown hats on eight people and ask them to guess their hat color and require that no one give anyone else any information that might help them guess. I hope you will agree that nothing can be deduced.

Tell them that at the end of every minute they should declare their hat color if they know it. Nothing happens, right?

Assume of course that the eight people are perfectly logical and brilliant. They all know that each of them sees at least two blue and two brown hats. They even tell each other this while passing the time away waiting for you to come up with a better game, and since they all know all this there is no harm in talking. Still nothing happens.

Now you say to them that you see a blue hat. "So what", they all say, "we all noticed that and we even talked about it, didn't you hear?" Nothing happens at all.

(I hope you will think about this rather than assuming the Wikipedia reference to common knowledge makes you right. Whoever posted this problem to that page is in error also.)

Sandro Magi said...

Jim, it should be quite straightforward from the arguments that I already presented that case 1 is already answered, case 2 is obvious by symmetry with case 1, case 3 is is clear by symmetry with case 1 and 2, and case 4 adds no information whatsoever since nothing is added to the pool of common knowledge.

And I don't need to "clear up my thinking", since the argument I've presented is the accepted mathematical argument. Your reference to "my weird logic" implies that you are seriously confused on the subject you are debating. If you're seriously debating this conclusion, then take it up with the logicians that solved this problem over 30 years ago.

As for how the inductive argument works for N=3, it's already explained in the blog post, but I'll rephrase since you're having trouble understanding: Bob, Mort and Sue have blue eyes. Each of them sees only 2 people with blue eyes, and do not know their own eye colour.

When the foreigner says he sees blue eyes, each person on the island has two mutually exclusive possibilities to consider:

1. I too have blue eyes.
2. I do not have blue eyes.

Let's say we argue from Bob's perspective, keeping in mind that by symmetry the exact same argument applies to Sue and Mort, and in fact everyone else on the island.

Bob reasons as follows:
I see 2 people with blue eyes, so I know that if those 2 blue-eyed people kill themselves on the second day, then we are in case N=2, which you have agreed is valid, and my eyes are not blue.

However, if those 2 blue-eyed people do not kill themselves on the second day, then we must be in case N=3 since the only person's eye colour I don't know is my own, and therefore, my eyes too must be blue. Thus, I must kill myself tomorrow, on the third day.

Now replace 2 with K-1 and 3 with K in the above paragraph and you have your induction for K blue-eyed people. It's pretty clear from this description that the induction works perfectly well, despite your unsubstantiated claims to the contrary.

Now, I'm just going to conclude by saying that your posts are a little presumptuous. You don't know me, or how long I've spent on this puzzle, and your casual and non-rigourous dismissal of the solution that formally trained mathematicians have derived and that I have explained here frankly casts your whole position in doubt. Your attempts to shift the discussion to alternate problems and avoid actually pointing out a logical flaw in the argument I've described just makes it harder to take you seriously.

Just stick to the blue-eyed islanders. The problem statement and the logical solution is clear and simple. I have now explained it multiple times in very clear language, so understanding is now up to you.

jim said...

Hi Sandro Magi,

You think that if the foreigner says he sees blue eyes the blue eyed people kill themselves in 100 days, and if the foreigner says he sees brown eyes the brown eyed people kill themselves in 100 days, and if he says he sees blue and brown eyes everyone kills themselves in 100 days, yet in all cases he is not telling anyone anything they don't already know. But if he says nothing no one kills him/herself.

You cannot defend that. Perhaps you should bring in one of those old timey logicians you are leaning on for support and get him/her to justify that conclusion.

The explanation you just posted for N=3 fails to start the induction at N=1. Try writing it again without mentioning islands with 1 or 2 blue eyed people (which have nothing to do with an island with 3 blue eyed people) and you will see the problem. Describe the thought processes of the three people as regards the island they are actually on and you will see that they can't get started.

The hats problem would clear up everything if you would acknowledge that it is the same problem without the suicides and taboos.

Sandro Magi said...

Jim, N=1 is the base case on which the induction depends. Even N=2 follows from the base case + the argument I posted. The base case is trivial: when the foreigner makes his pronouncement, the only bue eyed person looks around, and seeing there are no other blue eyed people, concludes his eyes are blue, and so he must kill himself the following day.

All other N follow from this + the argument I already posted. If you still can't follow this, then I'm afraid I can't help you.

As for the foreigner adding knowledge, he IS. Even you agreed he adds knowledge for N=1 and 2, and your only difficulty is grasping the kth order knowledge required for case N=k. This is all on the common knowledge wiki page if you'd bothered read it.

jim said...

(part 1, to fit your size restriction)

Over the years this problem has come up a number of times in my classroom. This year when a student brought it in I looked online and was not happy to see the level of discourse in discussion groups and blogs like yours.

In my classes all students find the "correct" solution immediately because they can all solve problems inductively and have solved many of them already in the course. So we do not talk about understanding the logic but about whether the logic applies to the story line. The conversation we have, I feel, is important for their careers whereas the mindless browbeating people take online from self appointed experts just widens the disconnect between computer literati and the rest of humanity and makes it that much harder for people to do their jobs well.

The original problem as you know is one of how automata increase common knowledge. There the definition of being logical can be defined in the software. If the automata share information synchronously the problem is easily stated and the conclusion is inevitable, a tautology.

The problem breaks down in many ways as a puzzle about actual humans, for humans reason on a higher level than computers. These nuances are generally of no interest to those who have difficulty seeing the difference between computers and humans but are interesting to others. Hence the intriguing questions one finds online from those who don't accept the premises and who may seem stupid to people like you.

For example, can the islanders make dresses with a blue and brown eye pattern? Well, not without ruining the problem, so the problem has to be reworded. How about blue/brown art at all? After all, there is a taboo involving death, which would be of obsessive interest. Can the taboo be addressed in the culture at all? One finds that, as these "silly" questions arise, in order to preserve the puzzle the imagined islanders have to be restrained more and more in their thinking until, ultimately, they must be redefined as computers and the problem has to be stated as in the original 1969 paper.

jim said...

(part 2)
As a further example, when a native is taught the taboo it can be argued that this is equivalent to being told there are blue and brown eyed people on the island. So the clock starts for this individual at that moment. If everyone is told the rules simultaneously then the clock starts then, but if separately then there is no synchronous behavior.

As one restricts the behavior of the islanders more and more one must ask whether they should be permitted to think or act at all. If they are perfectly logical then they deduce from the moment they are told the taboo that they will all die if any mention of eye color is made to the assembled populace at any time. So they all know the consequences of a stranger's words long before he comes to the island.

Why wouldn't they leave notes around for each other at random times reading "I see blue eyes' so that their thinking is not in lockstep. This saves them. Hmmm, more restrictions on the problem, even less room for human ingenuity.

If all the interest is wrung out of the problem by addressing its myriad faults the islanders still have the option of killing the visitor before he speaks. If they fail in this they can still guarantee their escape. The moment he speaks they will simply ask each other "What are we all waiting for?" The attempt to program their thinking over the next 99 nights, when none of them expects anything to happen anyway, breaks down and they are saved.

I wonder if the original problem has any actual application in computer networking or whether it is just a cute puzzle in that domain as well. As clever as it is, it is not much removed from the firing squad problem, where students are asked to calculate the time it takes n synchronously operating automata, arranged in a line and communicating only with their neighbors, to all fire their guns simultaneously after a signal to fire is given to a single "soldier" at one end of the line.

Sandro Magi said...

If the automata share information synchronously the problem is easily stated and the conclusion is inevitable, a tautology.

It's not a tautology any more than any other proof in mathematics is a tautology. The conclusion is inevitable and follows necessarily from the premises, as would any result in any formal system, but this does not make it a tautology.

for humans reason on a higher level than computers

This is an ambiguous and unjustifiable assertion. What does "higher" mean? Computers can currently solve problems humans cannot, and vice versa. Furthermore, there is little evidence implying that human cognition is non-deterministic, and so a function that mimics the human cognitive process is theoretically possible and realizable on future computers.

In any case, this is immaterial to present discussion.

in order to preserve the puzzle the imagined islanders have to be restrained more and more in their thinking until, ultimately, they must be redefined as computers and the problem has to be stated as in the original 1969 paper.

The puzzle was always a pure logic puzzle, and any ambiguity is projected on it by people to escape thinking about the dilemma on purely logical grounds. The puzzle is obviously contrived, and intentionally to, as it's meant to clearly illustrate a seemingly counterintuitive result obtained via pure logic.

If you want to address sociological questions then you'll have to make your own puzzles.

As for applications, the Wikipedia page lists a few:
http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29#Applications

Rusty Mason said...

Jim is correct. The solutions to this popular puzzle add islanders in the solution. However, the puzzles starts off with many more blue-eyed islanders, let's say 10. But the islanders don't know the exact number, and after the first day have no new information, nor would they expect any, seeing 9 or 10 other blue-eyed islanders. There is no logical reason for them to assume that the others will go through the "n islanders will leave on day n" thinking process and suicide/leave on the nth or any other day.

Sandro Magi said...

There is no logical reason for them to assume that the others will go through the "n islanders will leave on day n" thinking process and suicide/leave on the nth or any other day.

Yes there is, because the puzzle specifies that they are perfectly logical, and the logical thought process they must follow has been detailed many, many times in this thread. Please read the thread. Jim is wrong, and the posted solution is correct.

Rusty Mason said...

Your solution is fatally flawed because it assumes the addition of one islander, step by step in the solution. But the islanders don't start out with one blue-eyed person then add one more at a time. They start out with several.

If you are one of several blue-eyed people, why would you expect that all the other islanders would go through the exact same "x islanders will leave on day x" thinking? There's no reason to. It is just as logical to assume that you, being one of several among several blue-eyed people, should start off day one assuming that you will never receive any more information, and logically, do nothing at all.

Rusty Mason said...

Sandro, You are saying that because the islanders are perfectly logical, they would use the "x leave/die on day x" argument but you do not explain why they would do that. The "x leave/die on day x" reasoning, per se, is logical, but the adoption of it by three or more blue-eyed islanders is not. It is more logical to assume that you will not have enough information to know on day 1, much less on day x.

Sandro Magi said...

But the islanders don't start out with one blue-eyed person then add one more at a time. They start out with several. The "x leave/die on day x" reasoning, per se, is logical, but the adoption of it by three or more blue-eyed islanders is not.

In fact it is perfectly logical, as explained many times in this thread. I have explained in step by step the induction proof that demonstrates why this is so. This is perhaps the most detailed explanation.

Sandro Magi said...

Just noticed I provided a broken link. This is the correct link to the most detailed explanation.

Lars said...

@jim, and @rusty, I just want to put in a word that I was in precisely your shoes a few hours ago... I was sceptical of the "solution", thinking that when the number of blue-eyed people is more than 2, no new information is being added when the outsider announces "I see blue eyes."

But Sandro is right... in fact new information *is* being added: after the announcement, everybody knows that everybody knows that (repeat n times) there is at least one pair of blue eyes. This is the technical meaning of "common knowledge". Although everyone already knew that at least one person had blue eyes, it was not common knowledge in this sense.

It was the wikipedia article Sandro linked to that helped me understand this, along with the Randall Munroe's explanation.

Brian said...

It's nice to know I'm not taking crazy pills.

I stumbled across this puzzle and I also see precisely the error being identified by Jim and Rusty. Rusty's way of explaining the error is the best articulation of it, in my opinion: the logical formulation assumes that people are being added in a sequence, when in fact no such thing is occurring, so no new information arises.

Further to the "common knowledge" argument, that also makes no sense. Five people with brown hats, five people with blue hats. Everyone knows there is at least one brown and at least one blue hat. If they are perfectly logical, they also know based on the number of people, that everyone else knows this too.

It blows my mind how widely accepted this puzzle and solution is alleged to be. Seems to me like a case study in groupthink. I understand the solution, and people can only attack my objection by trying to suggest that I do not actually understand the solution.

I guess when people relax their skepticism too much, and put too much faith in authority, anything is possible.

Sandro Magi said...

Brian, the point is that a person does not know their *own* hat colour. The argument hinges on this fact. His hat could be brown or blue, and the rule that they must kill themselves if they figure out their own hat colour is what establishes the induction.

If there are only two people, one blue hat and one brown hat, someone declaring they see a blue hat means that person dies the next day. If there are 2 blue hats, they each assume that the other will kill themselves the following day. When the other person doesn't do so, they infer that they too must have a blue hat, and they both die the following day. And 3 people die on day 3, and 4 on day 4, and so on.

The argument is subtle, but very simple. Even Jim and Rusty in the end acknowledged that this solution is correct. You need to think about this some more.

Brian said...

Thanks for the reply.

I am open to the possibility that I need to think about it more, but having spent so much time thinking about it already, I wonder whether I'll get a solid return on my time investment. Maybe I'll just shrug my shoulders and be okay with the fact that I may disagree with the majority on a certain logical puzzle.

Brian said...
This comment has been removed by the author.
Lenoxus said...

In a sense, I'm inclined to agree with what Jim had been saying earlier about humans vs computers. The many, many discussions I've read on this suggest that humans cannot intuitively think on more than 2 layers of recursive knowledge, ergo, no set of islanders could be "perfect logicians" like that in the first place. Most people think that

"Everyone knows that everyone knows X"

Is tha same hing as:

"Everyone knows that (x infinity) everyone knows X."

If our brains worked differently, we would have the same trouble with puzzles that required counting. "But when the library recieved another book, the total number of books can't possibly change – there were already more than 2, and more than 1 more than 2, etc! Effectively, numbers greater than 2 are equal."

Sandro Magi said...

@Lenoxus, I don't see how people's ability to reason is relevant to the logic puzzle. If we replaced people with robots in this puzzle, the same solution applies.

The point of logic puzzles is to create a scenario and determine precisely what logic tells us should happen.

Lenoxus said...

Sand Magi – I totally agree. I was being more facetious/cynical with my last comment. In fact, this is probably my favorite puzzle! I even wrote a long piece dealing with common objections to the solution, here:

http://forums.xkcd.com/viewtopic.php?t=80149&p=2874552

It's just interesting how it doesn't translate into real human behavior due to some stumbling blocks about meta-reasoning we call seem to share.

Craig Schnabel said...

Sorry to dredge up this old post, but I stumbled upon it, and I think I have something to add.

Jim was onto something, but he failed to follow it through. It's not that there is no solution, but that, depending on the conditions, it either doesn't require an explorer, or only requires him to set a "day 0."

With sufficient blue eyed people, there will be a "floor" for the real minimum of people anyone can see with blue eyes.

Let's say there are 100 blue 100 brown. I have blue eyes. That means I see 99 blue eyed people.

This tells me a few important things. I know there are blue eyed people, I know that everyone must know there are blue eyed people, and I know the minimum number of blue eyed people anyone can see is 98.

So let's say I assume I don't have blue eyes. That means anyone with blue eyes will see 98 blue eyed people, and know that there are blue eyed people, that everyone else knows that there are blue eyed people, and that the minimum number of blue eyed people anyone can THINK THERE ARE is 97.

This is the key: I, a blue eyed person, am now reasoning as another blue eyed person, and finding the floor because of it. The floor is 97, because they could see one less than me, if I'm not blue eyed, and could assume they don't have blue eyes. But no one will ever see less than 98 people with blue eyes, because I see 99, and they can only exclude themselves.

That means the minimum number of people there can be with blue eyes is n-1, and the minimum anyone could think there were is n-2, where n=the number of blue eyed people the reasoner is seeing. As long as n-2 > 3, you can know that blue eyed people are common knowledge, and that everyone else can too.

Then, you just leave on day n+1, provided all the blue eyed people haven't already left. They may leave one day before, at which point you'd know your eyes aren't blue.

Then you can do the same for every other color (you'd start with the lowest number you can see) and as long as everyone else doesn't leave before you, you can figure out your eye color.

Sandro Magi said...

Craig, we're agreed that when there are only 1, 2 or 3 blue eyes on the island, the foreigner adds important new information, correct?

For n=1 blue eye, the foreigner states the existence of blue eyes, which the only blue eyed person then infers must be his own eye colour.

For n=2, anybody seeing 1 blue eye provisionally assumes they're in n=1 until that's disproven on day 1, in which case they know they're in n=2.

For n=3, anybody seeing 2 blue eyes provisionally assumes they're in n=2 until that's disproven on day 2, in which case they know they're in n=3.

Now your conjecture is that when there are n>=4, the existence of blue eyes is already common knowledge. And yet, the template for induction is already established by this point, and you provide no reason to invalidate it. In order for your counterargument to work, this inductive argument must somehow be flawed, so you'll have to point out that flaw to convince me.

Note that the amount of knowledge being added by the foreigner's statement becomes progressively more convoluted the more blue eyes there are, so while it might seem "obvious" to you that the knowledge is already present, you haven't proven it. Given how subtle the information is, I don't accept your informal argument at face value.

Finally, others have posted precisely your counterargument, but they also describe the additional information which causes ultimately your argument to fail.

Craig Schnabel said...

It is pretty difficult to prove the lowest possible case (for me at least, I have no formal training). That being said, I'm almost certain my argument requires n>5, but I don't think that will convince you. :)

Say we go to n=10. the number of other islanders and their eye colors are irrelevant.

I see 9 blue eyed people.

Because I know that no one else can see less than 9, this must be common knowledge. There is no scenario where anyone can see few enough blue eyed people to reasonably assume it cannot be known by everyone else that there are blue eyed people.

Even if I don't have blue eyes, I know that anyone who does will be able to see 8 blue eyed people. They can make the same inference, because no one can see less than 7 (same logic) and therefore everyone must know that everyone else knows.

But I don't have to go any further, as a 9 seer (one who sees 9 blue eyed people,just to be clear), because I know no other scenario exists.

The 8 seers, if any exist, won't have to go further than 6 seers, and 7 seers cannot exist, because I see 9, so no one, in reality, will ever use 7 as a starting point.

Maybe I should add that the proof for why they leave is still the same, I'm just saying it's impossible to make"blue eyed people exist" common knowledge if it must necessarily be so with sufficient blue eyed people.

The reason I think n > 5 is the lower bound is basically this: I see 5. I know they see ate least 4, so I know it's commons knowledge, they can't not see a blue eyed person.

Their n becomes 5 essentially, and they can say, at worst, I know no one sees less than 3. Therefore no one can think there are less than 3. With three everyone sees blue eyed people, and everyone can see that everyone can see blue eyed people.

But I am still reasoning as an n=6, so I know no one will ever see less than 4. I can rule out all scenarios after that as impossibilities, so while the 1 blue eyed person scenario is important to find the ideal day to leave, no one could possibly think the real life scenario is less than 3 blue eyed people, which would have blue eyed people as common knowledge.

I'm going to stop myself here, as if I'm not explaining clearly enough yet why I think the lower bound is 6 I don't think I'm going to make it any better right now, and I'm also starting to convince myself it might be 7 :/

It's definitely not higher than ten. Getting the ideal answer might be a bit out of my league though. I think it rests on whether 3 or 4 is necessary as a floor for common knowledge if no one can think there are less.

Lenoxus said...

Craig: One problem is that you are using the term "common knowledge" to mean "everyone know that everyone knows". However, it doesn't; it actually means "everyone knows that everyone knows that everyone knows that everyone knows..." ad infinitum. And that makes a major difference, just like there's a big difference between just one and two layers ("everyone knows" vs "everyone knows that everyone knows").

There is no reason to treat two layers as a logical "stopping point". Instead, when we add another layer in our consideration, we have to subtract one from the "commonly" known number. For example, say there are six blue-eyed people. In that case:

Everyone knows that there are at least five blues.

[Everyone knows] x 2 that there are at least four blues.

[Everyone knows] x 3 that there are at least three blues.

[Everyone knows] x 4 that there are at least two blues.

[Everyone knows] x 5 that there is at least one blue.

[Everyone knows] x 6 that there are at least zero blues. (A logically necessary statement under all circumstances anyway; you can't have a negative number of blue-eyed people).

The human mind has a really hard time working past two layers here, which is why this puzzle is so famous.

Craig Schnabel said...

Ok, I'm beginning to see the problem, especially since common knowledge has such a well defined meaning.

The hump I can't get over is, why, when I know that everyone definitely sees a blue eyed person, and everyone will definitely know that everyone sees a blue eyed person, or more importantly, multiple blue eyed people, is it not optimal to assume you have blue eyes up unless everyone leaves the day before you would if it were true. If they don't leave, can't you be sure you do have blue eyes?

Lenoxus said...

You wondered why "is it not optimal to assume you have blue eyes up unless everyone leaves the day before you would if it were true". In fact, that is entirely correct.

If it is the case that, were you not blue yourself, all the blues you see would leave on a given day, then when you don't see them leave on that day, you can correctly conclude that you are a blue.

The trick is establishing that if. I originally had a whole spiel that basically repeated stuff I said before about working from the top down, but it's easier to get this if we build up from the bottom up.

Consider the case of 4 blues total. We agree that, absent the words of a foreigner, they won't ever leave, right? It's a stable situation. No one will leave an island of 4 blues "because it's Day 4", or for any other day afterward.

Now consider the case of 5 total. Each of them knows there are either 4 or 5 blues. In the case of 4, then no one will leave on Day 4 (established in the previous paragraph). So observing other islanders not leaving provides zero information. Therefore, the 5 blues each have no reason to leave. Hence, 5 is just as stable as 4.

Now consider the case of 6 blues. Each of them sees 5, and knows that 5 is stable. Thus, no information is gained by seeing nobody leave on Day 5. Because of this, the 6 blues will have no reason to deduce themselves to be blue, and they will not leave on Day 6. Hence, 6 is also stable.

And so on for 7, 8, 9, 10…

===========================

Let's say someone (I'll call him Alex) disagrees with some step of this. For example, Alex agrees that 5 is stable, but that 6 blues would deduce their eye color and leave on Day 6.

There's a very simple way to test this assertion. We give Alex a new randomly-chosen eye color and put him on the island. He sees 5 blues. On Day 5, none of those blues leaves. Should Alex leave on Day 6?

Remember, this situation is logically consistent with there being 6 blues (including Alex). So his answer should be "Yes, having seen no one leave yesterday, I will leave today." But the situation is also consistent with there only being 5 blues, because 5 is stable. So if he left, he could very well be making a mistake.

This basic argument can be re-applied by increasing the numbers by one. We've just established that 6 is stable, and can therefore repeat the argument to show that 7 is stable, and 8, and 9, and so on.

Schroedinger's Bull said...

On An island with 1 blue eyed person, given the scenario, the person leaves/dies/walks into a volcano. Immediately.

N=2:

Day 1:

Nobody leaves. They are expecting the other person to leave.

Day 2:

Since he other didn't leave, they can each surmise that they each also have blue eyes. From each viewpoint. (I think this is the critical flaw in the puzzle as posed. Not the inductive argument, nor the underlying logic. Just the puzzle. As posed.)

N=3:

DAY 1:

A observes B&C; B observes A&C; C observed A&B. none can be certain of their own eye color.

Day 2:

Since none were certain on day 1; none have left. They continue to observe the other islanders, but can gain no further certainty.

Day 3:

Repeat day 2.

the solution isn't valid for the specific situation described in the puzzle. I accept that it's meant to teach logic. Your inductive argument doesn't codify each islander's viewpoint. No islander can gain any more certainty from successive days because there is no additional certainty from waiting unless the islanders can communicate. Since they are forbidden to do so, their lack of exit is due to a lack of certainty from their viewpoint which is never resolved.

I believe this is a failure of the puzzle to reflect the intended logical problem, or a failure of the logic to properly codify the problem as stated.

Logic is useless in this context if it can't reflect the English expression of the problem.

In my view.



Sandro Magi said...

Schroedinger, you are incorrect as has been elaborated thoroughly in this thread. This mistake is pretty common, but the blue eyed islander is a very thoroughly analyzed mathematical problem and the posted solution is correct.

On day 3, each blue eyed islander realizes that the other two blue eyed islanders themselves see 2 blue eyes, and thus their own eyes must also be blue. Every brown-eyed islander sees 3 blue eyes, so they remain.

Ang Ee Yang said...

And what if all 100 of them kill themselves, but then since the rest of the villagers know all the blue eyed villagers are gone, the rest of them must have brown eyes, then all of them will commit suicide the next day?

Sandro Magi said...

Assuming you use the variant with only two eye colours, the islander's don't actually know that the island features only two eye colours, so your scenario can't happen.

CitizenJ said...

There are cases of "false induction". Here is one puzzle with false induction: A professor tells his class on a Friday that there will be an exam next week, but before the following weekend, and also that the exam will occur in the morning. He further adds that they won't know the day of the exam until the day it occurs. From this one student concludes, by the rules just given, that the exam cannot be given at all !

His reasoning is that the exam cannot occur on Friday, since by Thursday afternoon the students will know the exam must be on Friday, contradicting the rule that they will not know until the exam day. Since Friday Was ruled out, Thursday becomes the last day the exam can be given. But the same reasoning now applies to Thursday, and it is eliminated as an exam day also. Continuing this way each day is eliminated. Yet obviously the students could be taken by surprise when the exam is suddenly given Tuesday morning.

Does the blue eye puzzle entail a form of false induction?

CitizenJ said...

In the (exam induction) case I gave earlier, an absurd conclusion results. This is at least a warning that induction processes must be looked at critically. In the case of the blue eyes induction, a seemingly absurd result is also reached, I.e., that 100 blue eyed people can deduce their own eye color from the guru's statement that she merely sees blue eyes. The problem implies that the 100 arrived on the island all at once. Otherwise, a population of 100 could not have accumulated, since a lesser number would already begun leaving or left (according to the arguments given by the solution). The guru only speaks once, not during an accumulation process. The induction process itself is a counter factual-something that never happened. There was no actual n=1 case, or n=2 case or any case except n=100. It is questionable to say that the guru actually communicates new information when 100 blue eyed are plainly visible, and based on an imaginary inductive process.

All this being said, I don't have strong convictions about my objections. But I think the failure of induction to give a reasonable result in one case should give pause about it in other cases, especially when an absurd seeming result occurs.

Sandro Magi said...

Does the blue eye puzzle entail a form of false induction?

The scenario you describe is called the unexpected hanging paradox. It's not a case of "false induction", whatever that may be. The problem with that paradox is in faithfully formalizing the judge's informal statements. No one yet knows how to do this, and so the apparent paradox is not yet resolved.

This is not the case with the Blue Eyed Islanders puzzle. As I've detailed thoroughly in the comments here, the induction is simple and sound, and founded on the well-accepted principle of "common knowledge".

CitizenJ said...

I used the term "false induction" because that example (the unexpected exam or hanging paradox) leads to a false result--a contradiction. Although the "blue eyes" induction may not be structurally identical to the hanging paradox, can we rule out some other problem where the seeming soundness of that induction creates an absurd result? It is a much more complex case than the unexpected hanging case. Complexity usually gives a flaw more hiding places. As you noted yourself, the hanging paradox has not yet been resolved (despite being much simpler.)

Sandro Magi said...

The unexpected hanging paradox is not simpler, that's the point. It requires a formalization of natural language and its interpretation under temporal modalities. It's absurdly complex by comparison.

Like I said, the blue eyed islanders solution is well accepted by the mathematical community as an instance of the common knowledge. I don't see any benefit in belaboring this point more than I already have.