My write-up of the "Blue Eyes" solution (SPOILER A

[t1mm01994]

I've always failed to understand how people could fill up 1000 posts arguing something that has been argued many times before... But hey, inductive reasoning is hard (a thing to google for anyone who whats a hint, as well)

[skullturf]

This may seem frivolous, but I believe it's relevant to the "blue eyes" puzzle.

Today I shared the following photo on Facebook:

http://www.vancouversun.com/5408477.bin?size=620x400s

and added the comment: But maybe the '"Rhino not for sale" sign not for sale' sign IS for sale!

Which, of course, is a little confusing. But it illustrates a point that's very similar to a crucial point about the blue eyes puzzle.

You can have a sign that says "Rhino not for sale". And then you can have a second sign saying that the first SIGN is not for sale. Then, if you wanted to try to be clever or confusing, you could add a THIRD sign saying that the SECOND sign is not for sale.

That may seem like a strange or confusing thing to do, and it probably is. But you could do it.

And importantly, EACH sign would be DIFFERENT -- and also, EACH sign is making a DIFFERENT assertion.

We who are not perfect logicians start to get confused when there are many "levels", and distinctions start to get blurred for us. But it's very important to realize that this blurring of levels ONLY occurs in our own imperfect subjective understanding.

Logic DEMANDS that we regard EACH of the following statements as DIFFERENT:

"A has blue eyes"
"B knows that A has blue eyes"
"C knows that B knows that A has blue eyes"
"D knows that C knows that B knows that A has blue eyes"
and so on.

No matter how much we might subjectively "feel" otherwise, two layers is different from three layers, which is different from four layers, which is different from seventeen layers, which is different from 99 layers, which is different from 100 layers, which is different from infinitely many layers.

[billiams]

There is a standard way to solve the problem. This solution uses mathematical induction, but ignores and thus fails to exploit the principle of shared knowledge at the heart of this puzzle. Take the 500 blue eyed five hundred brown eyed iteration.

Read below for spoiler:

Spoiler:

The traditional way of solving this problem results in the conclusion that the blue eyed people leave the island on day 500. This is essentially via induction. IFF on day one everyone sees other people with blue eyes, no one leaves. IFF on day 2, no person sees only 1 blue eyed person none leaves. and so one, till Day N, when the blue eyed see N-1 and they must leave must leave.

This method doesn't exploit common knowledge. The induction can start with pkn, the number commonly known of an eye color, ( in this case N-1, not the case when pk=1, of course) on day 1. No one leaves. But on day 2, pkn+1 will reveal the blue eyed people as they will only see 499 and have to skedattle. The same obtains with the brown eyed. The visitor adds nothing in this scenerio, but he would if n is less than 2.
it will never take more than two moves, if pkn is 1 or greater.

[phlip]

So, what you are saying is that no matter how many blue-eyed people there are, as long as it as at least 2, they will leave on day 2?

So, say, if there are 100 blue-eyed people and 100 brown-eyed people, then all 100 blue-eyed people will leave on day 2?
Or if there are 99 blue-eyed people and 101 brown-eyed people, then all 99 blue-eyed people will leave on day 2?

In that case, consider these two scenarios:
(1) There are 100 blue-eyed people and 100 brown-eyed people on the island, and I am one of the blue-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be blue, but I don't know this).
On day 1, nothing happens.
And then on day 2, all the blue-eyed people leave, and I go with them, knowing that my eyes are blue.

(2) There are 99 blue-eyed people and 101 brown-eyed people, and I am one of the brown-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be brown, but I don't know this). So far, everything I can see is identical to scenario 1.
On day 1, nothing happens, identically to scenario 1.
And then on day 2, all the blue-eyed people leave, same as scenario 1, except this time I stay behind, knowing that my eyes are not blue.

This is what you are claiming is happening. But how can I possibly learn different things on day 2 if everything I've seen in the two scenarios is identical?

Short version: common knowledge does not work that way.

[Gwydion]

But you fail to recognize just what is "shared knowledge". You are correct - if there were a giant sign that said "there are at least 499 blue-eyed people" which was visible to all the islanders at all times. This sign does not exist in the current statement of the puzzle.

In fact, the existing solution does exploit the fascinating properties of common knowledge and shared knowledge - which is why in your proposed scenario it takes 500 days to leave. The pool of things which are common knowledge changes every day someone fails to leave. From the perspective of a blue-eyed person on the island, there could be either 499 or 500. However, from the perspective of a brown-eyed person, there could be 500 or 501. Which one is the "number commonly known"?

[sarcasm] There must be at least 100 posts with correct solutions or refutations of your answer within this thread. If I come in and say "at least one of these is right, please read". how long does it take to convince you you're wrong? [/sarcasm]

[billiams]

But you fail to recognize just what is "shared knowledge". You are correct - if there were a giant sign that said "there are at least 499 blue-eyed people" which was visible to all the islanders at all times. This sign does not exist in the current statement of the puzzle.

In fact, the existing solution does exploit the fascinating properties of common knowledge and shared knowledge - which is why in your proposed scenario it takes 500 days to leave. The pool of things which are common knowledge changes every day someone fails to leave. From the perspective of a blue-eyed person on the island, there could be either 499 or 500. However, from the perspective of a brown-eyed person, there could be 500 or 501. Which one is the "number commonly known"?

[sarcasm] There must be at least 100 posts with correct solutions or refutations of your answer within this thread. If I come in and say "at least one of these is right, please read". how long does it take to convince you you're wrong? [/sarcasm]

Not long, I'm not stubborn, but even a blind squirrel finds a nut, now and then.


Picture it with smaller numbers. bbbggg, shared knowledge bb of b's the bbb who will use that too, but the b's will be gone and so will the G's pkd+1 won't give then the info required for them to leave with the blues. blues then start with two on day 1, no one leaves. They plug in pkn+1, 3 (remember for the greens it's 4, but they are also doing the same calculation with green, so they'll be gone too) and they see two blues and boom they leave.The same applies with 500, all b's will see 499 bs, and plug it in as the starting point for induction.

I appreciate the prompt reply.

I will try to be more clear, and would love to respond to questions and thoughts on this solution.

--

So, what you are saying is that no matter how many blue-eyed people there are, as long as it as at least 2, they will leave on day 2?

So, say, if there are 100 blue-eyed people and 100 brown-eyed people, then all 100 blue-eyed people will leave on day 2?
Or if there are 99 blue-eyed people and 101 brown-eyed people, then all 99 blue-eyed people will leave on day 2?

In that case, consider these two scenarios:
(1) There are 100 blue-eyed people and 100 brown-eyed people on the island, and I am one of the blue-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be blue, but I don't know this).
On day 1, nothing happens.
And then on day 2, all the blue-eyed people leave, and I go with them, knowing that my eyes are blue.

(2) There are 99 blue-eyed people and 101 brown-eyed people, and I am one of the brown-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be brown, but I don't know this). So far, everything I can see is identical to scenario 1.
On day 1, nothing happens, identically to scenario 1.
And then on day 2, all the blue-eyed people leave, same as scenario 1, except this time I stay behind, knowing that my eyes are not blue.

Yes, exactly what I'm saying. I surprised no one has gotten this before.

This is what you are claiming is happening. But how can I possibly learn different things on day 2 if everything I've seen in the two scenarios is identical?

Short version: common knowledge does not work that way.

Yes, that's what's I'm saying. 2 days. Try it out. Common knowledge, and it's modal operations are a work in progress, but yes, it does work this way.

Remember as a brown eye you are doing a calculation too, but the pkd for brown for blues starts one higher, so will not trick you, and your are doing your pkd with brown eyes for brown eyes too, and will not leave with the blues.

[ConMan]

So, what you are saying is that no matter how many blue-eyed people there are, as long as it as at least 2, they will leave on day 2?

So, say, if there are 100 blue-eyed people and 100 brown-eyed people, then all 100 blue-eyed people will leave on day 2?
Or if there are 99 blue-eyed people and 101 brown-eyed people, then all 99 blue-eyed people will leave on day 2?

In that case, consider these two scenarios:
(1) There are 100 blue-eyed people and 100 brown-eyed people on the island, and I am one of the blue-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be blue, but I don't know this).
On day 1, nothing happens.
And then on day 2, all the blue-eyed people leave, and I go with them, knowing that my eyes are blue.

(2) There are 99 blue-eyed people and 101 brown-eyed people, and I am one of the brown-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be brown, but I don't know this). So far, everything I can see is identical to scenario 1.
On day 1, nothing happens, identically to scenario 1.
And then on day 2, all the blue-eyed people leave, same as scenario 1, except this time I stay behind, knowing that my eyes are not blue.

Yes, exactly what I'm saying. I surprised no one has gotten this before.

This is what you are claiming is happening. But how can I possibly learn different things on day 2 if everything I've seen in the two scenarios is identical?

Short version: common knowledge does not work that way.

Fixed your quote attribution, so we can actually see what you said.

But you still haven't answered Phlip's question - if I see 99 blue-eyed people, and 100 brown-eyed people, should I leave the island or not?

[Dason]

So, what you are saying is that no matter how many blue-eyed people there are, as long as it as at least 2, they will leave on day 2?

So, say, if there are 100 blue-eyed people and 100 brown-eyed people, then all 100 blue-eyed people will leave on day 2?
Or if there are 99 blue-eyed people and 101 brown-eyed people, then all 99 blue-eyed people will leave on day 2?

In that case, consider these two scenarios:
(1) There are 100 blue-eyed people and 100 brown-eyed people on the island, and I am one of the blue-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be blue, but I don't know this).
On day 1, nothing happens.
And then on day 2, all the blue-eyed people leave, and I go with them, knowing that my eyes are blue.

(2) There are 99 blue-eyed people and 101 brown-eyed people, and I am one of the brown-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be brown, but I don't know this). So far, everything I can see is identical to scenario 1.
On day 1, nothing happens, identically to scenario 1.
And then on day 2, all the blue-eyed people leave, same as scenario 1, except this time I stay behind, knowing that my eyes are not blue.

Yes, exactly what I'm saying. I surprised no one has gotten this before.

This is what you are claiming is happening. But how can I possibly learn different things on day 2 if everything I've seen in the two scenarios is identical?

Short version: common knowledge does not work that way.

Fixed your quote attribution, so we can actually see what you said.

But you still haven't answered Phlip's question - if I see 99 blue-eyed people, and 100 brown-eyed people, should I leave the island or not?

That depends. Do you have blue eyes or not?
/sarcasm

[jestingrabbit]

Billiams, please seriously consider what phlip has said. People with the same information who are acting only on that information must act the same. Phlip has demonstrated that there isn't enough different information after two days for all the participants to differentiate between being in a situation where the number of blue eyed, n, is large (large is bigger than 2 here) and differs by only 1. Are they a blue eyed person who sees n-1 blue eyed, or are they a brown eyed person who sees all the n-1 blue eyed people? You would have them acting exactly the same, but they have different eye colours.

btw, just throwing variables at the problem without any information about what your variables mean isn't a very helpful communication strategy.

Also, please start using the edit button instead of making fresh consecutive posts. -jr

[billiams]

So, what you are saying is that no matter how many blue-eyed people there are, as long as it as at least 2, they will leave on day 2?

So, say, if there are 100 blue-eyed people and 100 brown-eyed people, then all 100 blue-eyed people will leave on day 2?
Or if there are 99 blue-eyed people and 101 brown-eyed people, then all 99 blue-eyed people will leave on day 2?

In that case, consider these two scenarios:
(1) There are 100 blue-eyed people and 100 brown-eyed people on the island, and I am one of the blue-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be blue, but I don't know this).
On day 1, nothing happens.
And then on day 2, all the blue-eyed people leave, and I go with them, knowing that my eyes are blue.

(2) There are 99 blue-eyed people and 101 brown-eyed people, and I am one of the brown-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be brown, but I don't know this). So far, everything I can see is identical to scenario 1.
On day 1, nothing happens, identically to scenario 1.
And then on day 2, all the blue-eyed people leave, same as scenario 1, except this time I stay behind, knowing that my eyes are not blue.

Yes, exactly what I'm saying. I surprised no one has gotten this before.

This is what you are claiming is happening. But how can I possibly learn different things on day 2 if everything I've seen in the two scenarios is identical?

Short version: common knowledge does not work that way.

Fixed your quote attribution, so we can actually see what you said.

But you still haven't answered Phlip's question - if I see 99 blue-eyed people, and 100 brown-eyed people, should I leave the island or not?

plug in the pkns, the blues start one below you, so it will never happen. You will also use 100 which as your staring point-day one says stay, but when raised to pkn+1 will tell you to zoom with the browns.

Sorry about the consecutive posts Jest. They were replies and fairly long. I tried to be clear about what I meant. Publicly known number. By that I mean what each group knows publicly, the number is used as the starting point for induction for each group, and would obviate the problem that Philip raises.

I'm psyched by the enthusiam on this thread.

[Gwydion]

So, what you are saying is that no matter how many blue-eyed people there are, as long as it as at least 2, they will leave on day 2?

So, say, if there are 100 blue-eyed people and 100 brown-eyed people, then all 100 blue-eyed people will leave on day 2?
Or if there are 99 blue-eyed people and 101 brown-eyed people, then all 99 blue-eyed people will leave on day 2?

In that case, consider these two scenarios:
(1) There are 100 blue-eyed people and 100 brown-eyed people on the island, and I am one of the blue-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be blue, but I don't know this).
On day 1, nothing happens.
And then on day 2, all the blue-eyed people leave, and I go with them, knowing that my eyes are blue.

(2) There are 99 blue-eyed people and 101 brown-eyed people, and I am one of the brown-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be brown, but I don't know this). So far, everything I can see is identical to scenario 1.
On day 1, nothing happens, identically to scenario 1.
And then on day 2, all the blue-eyed people leave, same as scenario 1, except this time I stay behind, knowing that my eyes are not blue.

Yes, exactly what I'm saying. I surprised no one has gotten this before.

This is what you are claiming is happening. But how can I possibly learn different things on day 2 if everything I've seen in the two scenarios is identical?

Short version: common knowledge does not work that way.

Fixed your quote attribution, so we can actually see what you said.

But you still haven't answered Phlip's question - if I see 99 blue-eyed people, and 100 brown-eyed people, should I leave the island or not?

plug in the pkds, the blues start one below you, so it will never happen. You will also use 100 which as your staring point-day one says stay, but when raised to pkd+1 will tell you to zoom with the browns.

Perhaps it's me, but what does pkd mean? Or pkn from your first post? It would be helpful if you defined your terms. Also, regardless of the starting point, Phlip's question is still unanswered - given a set of starting information (you see 99 blue eyes and 100 brown eyes, it is day 2), do you leave or not, and why? There was a nice proof earlier in this thread (page 6 maybe?) in which it is demonstrated that n days is the minimum possible solution for a situation involving n blue-eyed islanders - and it hasn't been disproved yet, despite your insisting that "plug it in, I swear it works".

Edit: Page 6 had a link to the actual proof, which was on page 3. My Rain Man-fu isn't perfect, I guess.

Call the situation where there are n blue eyed people out of N people (with n<=N) S(N,n). All the n people with blue eyes must leave on some day, as there is at least one line of reasoning which implies that they leave. Moreover, they must leave on the same day by symmetry. Let D(N,n) be the day on which the best reasoning dictates the n blue eyed people leave in situation S(N,n).

A blue eyed person in S(N,n) is in the same predicament as a non-blue eyed person in S(N,n-1). If D(N,n)<=D(N,n-1) then a non-blue eyed person in S(N,n-1) will leave on D(N,n) believing that they have blue eyes. Therefore D(N,n)>D(N,n-1) and D(N,n)>=n by induction.

[billiams]

So, what you are saying is that no matter how many blue-eyed people there are, as long as it as at least 2, they will leave on day 2?

So, say, if there are 100 blue-eyed people and 100 brown-eyed people, then all 100 blue-eyed people will leave on day 2?
Or if there are 99 blue-eyed people and 101 brown-eyed people, then all 99 blue-eyed people will leave on day 2?

In that case, consider these two scenarios:
(1) There are 100 blue-eyed people and 100 brown-eyed people on the island, and I am one of the blue-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be blue, but I don't know this).
On day 1, nothing happens.
And then on day 2, all the blue-eyed people leave, and I go with them, knowing that my eyes are blue.

(2) There are 99 blue-eyed people and 101 brown-eyed people, and I am one of the brown-eyed people.
So, I see 99 blue-eyed people and 100 brown-eyed people (and my eyes happen to be brown, but I don't know this). So far, everything I can see is identical to scenario 1.
On day 1, nothing happens, identically to scenario 1.
And then on day 2, all the blue-eyed people leave, same as scenario 1, except this time I stay behind, knowing that my eyes are not blue.

Yes, exactly what I'm saying. I surprised no one has gotten this before.

This is what you are claiming is happening. But how can I possibly learn different things on day 2 if everything I've seen in the two scenarios is identical?

Short version: common knowledge does not work that way.

Fixed your quote attribution, so we can actually see what you said.

But you still haven't answered Phlip's question - if I see 99 blue-eyed people, and 100 brown-eyed people, should I leave the island or not?

plug in the pkds, the blues start one below you, so it will never happen. You will also use 100 which as your staring point-day one says stay, but when raised to pkd+1 will tell you to zoom with the browns.

Perhaps it's me, but what does pkd mean? Or pkn from your first post? It would be helpful if you defined your terms. Also, regardless of the starting point, Phlip's question is still unanswered - given a set of starting information (you see 99 blue eyes and 100 brown eyes, it is day 2), do you leave or not, and why? There was a nice proof earlier in this thread (page 6 maybe?) in which it is demonstrated that n days is the minimum possible solution for a situation involving n blue-eyed islanders - and it hasn't been disproved yet, despite your insisting that "plug it in, I swear it works".

Typo, pkn, just publicly known number. It's not hard. I gave an example in my first reply. But it's the numbers that can be seen by any individual, and they will be the starting points for induction. for example, take Philip's. 99 blues and 101 brown: the Pkns for Blues will be 98 and 101 (that's what they see and they know everyone else see at least; the brown's Pkn's will be 99 and 100. The Blues (and they don't know yet they are blue) will plug in 98, which would mean they would have to see no more than 97 to leave. The next day they up the inductive point to 99, and when they see 98, they will know they are are blue and have to leave. The browns will use 99 on the first day, and 100 the second. Ahh.. I see said the blind man, if there is a difference of 1, it jams the gears because both inductive rules would tell them they are the brown eyed and blue eyed. There would have to be a sub rule to wait a day if this occurs. It is a tricky one. Then repeat using the same starting point, as the previous day, Unless they are aware that there are only two values. It would still save a lot of time.

[phlip]

You can say that that pkn number is different for the two scenarios, but that doesn't matter to me! All I can see is 99 blue-eyed people and 100 brown-eyed people. Nothing more. I certainly can't see any "the pkn is this number!" signs or anything.

Now, I know that if my eyes are blue then your pkn is 99, but if my eyes are not-blue then your pkn is 98. But since I don't know my own eye colour, I can't determine which of those two is correct. So I don't know what your pkn is.

How can you possibly call something "common knowledge" when I, a person in the situation, don't know what it is?

---

But let's try another simple question, for you. Let's say your explanation of what happens is accurate. Say you're on the island, and you can see, let's say, 58 people with blue eyes and 83 people with brown eyes. On day 1, nobody left, and it is now day 2. All the blue-eyed people you can see are preparing to leave. Should you leave, along with them? What colour are your eyes?
Bonus question: What is your "pkn" in this situation?

[billiams]

You can say that that pkn number is different for the two scenarios, but that doesn't matter to me! All I can see is 99 blue-eyed people and 100 brown-eyed people. Nothing more. I certainly can't see any "the pkn is this number!" signs or anything.

Now, I know that if my eyes are blue then your pkn is 99, but if my eyes are not-blue then your pkn is 98. But since I don't know my own eye colour, I can't determine which of those two is correct. So I don't know what your pkn is.

How can you possibly call something "common knowledge" when I, a person in the situation, don't know what it is?

---

But let's try another simple question, for you. Let's say your explanation of what happens is accurate. Say you're on the island, and you can see, let's say, 58 people with blue eyes and 83 people with brown eyes. On day 1, nobody left, and it is now day 2. All the blue-eyed people you can see are preparing to leave. Should you leave, along with them? What colour are your eyes?
Bonus question: What is your "pkn" in this situation?

Philip is correct. I screwed the pooch on this, the second day will lead to a both blue eyed and brown eyed. I was lazy, and only looked at one side of the problem. Sorry I wasted your time.

[The Mighty Thesaurus]

Turanga?

[jestingrabbit]

Turanga?

I think you mean David Bowie.

[billiams]

going to reedit

[splidge]

I really hate to be lame and say I didn't read all the posts, but I've only read the first 13 pages and this one.

I think billiams' posts illustrate a slightly different way of thinking about the problem which is equivalent to the accepted "nest of hypotheticals" scenario (I had thought about this independently reading the earlier parts of the thread but I will use his terminology since it is on this page and hence current):

Namely, if there is a "publicly known number" (pkn) of people with a particular eye colour, deductions can be made and people with that eye colour can (eventually) leave. But since it is common knowledge that everyone doesn't know the colour of their own eyes, everyone also knows that it is impossible to agree on any pkn value. So rather than having to think about the 99 (100?) level deep hypothetical, I can just use the fact that everyone is in the dark about their own eye colour to prove that there is no pre-existing pkn.

The guru's announcement sets pkn_blue=1 and the answer derives from there. If the guru instead said "I can see at least 99 blue-eyed people" it would set pkn_blue=99 and allow the blue eyed people to leave on the second night. The guru does not mention brown eyes so pkn_brown remains unset and the brown-eyed people are stuck.

Does that make any sense?

[jestingrabbit]

It makes a lot of sense to me. Specifically, trying to bootstrap some sort of pkn is always doomed to failure because of the fact that you mentioned: no one knows their own eye colour.

[t1mm01994]

An explanation that naturally fits in my head, rather than me spending 3 hours nesting hypotheses! Eureka!

EDIT: referring to the pkn explanation here.

[jestingrabbit]

I don't think the "pkn" explanation is that useful for answering questions like "what information does the guru add to the situation?" unless you already have a pretty strong understanding of the nested hypotheticals, to the point where you read "publicly known" as meaning "everyone knows that everyone knows that... (ad infinitum)... that everyone knows that" and that there's a difference between that statement and one where there are only a finite number of "everyone knows that".

[splidge]

Under the "pkn" explanation, the information the guru provides is pkn_blue=1 - this is a nice concise answer to the question.

Without resorting to the hypotheticals, I can argue that prior to the guru's statement there is no defined pkn_blue because it is impossible to agree on one (because it's common knowledge that no-one knows their own eye colour). I think I can answer "why don't they just choose 1 by themselves?" by pointing out that this would be superrational (why not 2 or some other integer in [2..98]?), rather than needing to invoke the nested hypotheticals.

[lightvector]

No. If "pkn = K" means "It is common knowledge that there are at least K blue eye islanders", then prior to the guru's announcement, pkn is exactly 0. (More precisely, the largest K for which "pkn = K" is true is 0). If you think it is undefined, or that it can't be determined merely because of the lack of a common way to agree on a number, then you still don't understand the problem.

[splidge]

OK, I agree that pkn_col=0 for all possible colours by default rather than "undefined"; in either case it does not allow islanders to draw inferences from the behaviour of other islanders.

However, I'm not sure I agree with the following:

If you think ... it can't be determined merely because of the lack of a common way to agree on a number, then you still don't understand the problem.

A common way to agree a number would be sufficient to establish a nonzero pkn value and allow the islanders to eventually leave. The definition of pkn means that any way of agreeing a number would necessarily establish the requisite common knowledge to allow the inferences to be drawn. For example, if a random blue-eyed islander were to say "raise your hand if you can see 95 or more blue-eyed islanders" and everyone raised their hands, this would set pkn_blue to 96 immediately (and all the blue-eyed islanders, including the one who made the pronouncement, would leave on the 5th subsequent night).

The depth of knowledge required is only equal to the depth of inference that is to be drawn anyway. If, for instance, the guru were to take two blue-eyed islanders to one side and say "There are at least 99 blue-eyed people on this island" then they would both leave on the second night.

[Guest?]

So I admit I didn't read all 26 pages on this topic, but after reading the first few it seemed the problems people were having were not the same as mine.

It seems to me that this problem is unsolvable without the additional clarification "The guru will always give new information" or something along those lines. Otherwise, in the case of 2 blue eyed people, on the second day the blue-eyed perfect logicians would think "Yes, you said the same thing yesterday, and we cannot infer that this is new information." Same for any number of blue-eyed people greater than two.

Am I missing something? Do the perfect logicians just assume that the guru would not bother repeating herself?

[t1mm01994]

So, let's take a small case: 2 blues, 2 browns, no guru. What will happen?

[Goldstein]

Guest, the Guru speaks once only, not once each day. On the first day she tells the crowd "I see someone with blue eyes" and then she never again speaks for the rest of her days. Additionally, she doesn't give indication of who she sees with blue eyes - only that one of the people she can see has blue eyes.

[Gwydion]

For clarification, if the guru *did* speak every day, there would be no new information gained after the first time. This helps to clarify the fact that she does communicate a single, quantifiable datum rather than serve as a theoretical "jumping-off point" for otherwise arbitrary decisions.

[Xias]

I think it would be beneficial to start a new thread. As much as my heart leaps for joy every time I see this thread bumped to the top, it's getting a little old seeing the same arguments, because let's face it - this many pages is pretty intimidating to sift through. With a new thread, we'd be able to arrange common complaints and their explanations in the first post, and reduce repetitive discussion:

"The induction steps falls apart after the X-person case."

"Nobody leaves because the Guru doesn't give them any information, since everyone already knows there is at least one person with blue eyes."

"They all leave 100 days after they arrive, without the Guru's help, since everyone already knows there is at least one person with blue eyes."

"Since they all know that everyone knows there's 98 blue eyed people, they leave on day 3."

"Nested hypotheticals are meaningless because they all know that everyone else sees at least 98 blue-eyed people."

What others am I missing?

[Cryft]

I've read and understand the question (and solution) and have tried to wade through this thread to see if this has been brought up before, but 26 is a lot of pages and I have little time tonight. The problem comes in the implications of the following part of the problem.

Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate.

The problem with this is that it seems to say that the only form of communication is seeing the eye color of others, and to draw attention away from the islanders' ability to notice when each other are leaving or staying. After all, remaining on the island is a declaration to the rest of the inhabitants that you do not know your own eye color, and is certainly a form of communication.

I realize that this is incredibly nit-picky and probably specific to only a few cases, but I feel that, with the goal of 100% clarity of problem presentation in mind, a phrase should be added to the problem stating specifically that the islanders notice exactly who has left and who has stayed at all times.

Perhaps something like

Everyone can see everyone else who is still on the island at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate.

This way it doesn't give any hints towards looking at meta-knowledge (thus spoiling the problem), but doesn't imply that the only information the islanders ever gain is from the guru.

[Xias]

I've read and understand the question (and solution) and have tried to wade through this thread to see if this has been brought up before, but 26 is a lot of pages and I have little time tonight. The problem comes in the implications of the following part of the problem.

Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate.

The problem with this is that it seems to say that the only form of communication is seeing the eye color of others, and to draw attention away from the islanders' ability to notice when each other are leaving or staying. After all, remaining on the island is a declaration to the rest of the inhabitants that you do not know your own eye color, and is certainly a form of communication.

I realize that this is incredibly nit-picky and probably specific to only a few cases, but I feel that, with the goal of 100% clarity of problem presentation in mind, a phrase should be added to the problem stating specifically that the islanders notice exactly who has left and who has stayed at all times.

Perhaps something like

Everyone can see everyone else who is still on the island at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate.

This way it doesn't give any hints towards looking at meta-knowledge (thus spoiling the problem), but doesn't imply that the only information the islanders ever gain is from the guru.

I think that's taken care of by the wording "keeps a count of". What significance does the count have if they aren't aware of any changes? I think it's established that seeing the number of people *is* how the communicate when someone leaves.

[Cryft]

I think that's taken care of by the wording "keeps a count of". What significance does the count have if they aren't aware of any changes? I think it's established that seeing the number of people *is* how the communicate when someone leaves.

It is established to those who have been discussing the problem for some time. However, when I think back to my first reading of the problem, it had given me the impression that they did not give each other any information by staying on the island.

The only reason I posted about it was to prevent it from reminding me of http://xkcd.com/169/ in any way. I was thrown off because of a specific understanding of the wording of the problem, and it can easily be prevented in the future. Considering the pains that were gone through to make the question as unambiguous as possible, I figured this change would be helpful.

[Xias]

I think that's taken care of by the wording "keeps a count of". What significance does the count have if they aren't aware of any changes? I think it's established that seeing the number of people *is* how the communicate when someone leaves.

It is established to those who have been discussing the problem for some time. However, when I think back to my first reading of the problem, it had given me the impression that they did not give each other any information by staying on the island.

I meant established by the problem, not established by consensus. By stating that

Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate.

I think it is clear that knowing the number of people that are on the island with each eye color is the only way to communicate. This, coupled with the assertion that they are all perfect logicians, any change (or lack thereof) in those numbers must necessarily transfer information to anyone who is both perfectly logical and able to count.

The only reason I posted about it was to prevent it from reminding me of http://xkcd.com/169/ in any way. I was thrown off because of a specific understanding of the wording of the problem, and it can easily be prevented in the future. Considering the pains that were gone through to make the question as unambiguous as possible, I figured this change would be helpful.

I can see that an addition like that would make the problem more unambiguous, but you're the first that I know of to have had that problem - even among the many, many people who have trouble with the riddle. I think this particular case is down to your misunderstanding of the problem. As you say, you had the impression that they did not give information by staying - did you think that anyone leaving would also convey no information? Alternatively, if your original understanding meant that they could not communicate (transfer information) by leaving (changing the number of people on the island) then why would that particular sentence exist in the problem at all?

It's a puzzle; it's intended to force you to consider exactly how they can find out what their eye color is. Further clarification and explanation would only serve to give the answer away.

[00melo00]

A friend introduced me to the puzzle via this website. For anyone that doesn't know it, here it is: http://xkcd.com/blue_eyes.html (can't find the url tag).

Here is mine solution:
I thought the answer was recursive but I couldn't find a mechanism that was doing the job, so I did it intuitively.
Presuppositions I needed a lot.
1. They are perfect logicians. This means if one person would figure out if he had blue eyes he would leave the island immediatly.

Then I got stuck so I started to construct things from the ground up.

X is our blue eyed person that is our perspective (and view sight) as well.

What if: N = 2
X knows he has blue eyes, because guru told him so. The guru waves.

What if: N = 3 --> 1/ 1/ 1
X knows he has blue eyes, the guru waves.

What if: N = 4 --> 1 / 2 / 1 (format: blue red green)
X knows he has blue eyes, the guru hosts a party

And then it got tricky. I knew this would be the 'induction step', but I suck at induction so I still had to do this intuitively, which is why this answer is different (and iterative) instead of inductive / recursive.

What if: N = 5 2 / 2 / 1 (blue red green)
X knows that 3 people don't have blue eyes.
The guru knows nothing extra, so he knows 2 persons that aren't cutting it. However, he must be VERY AWARE of the fact that everyone heard what he said.
The 2 brown eyed persons know that 2 persons aren't cutting it (like the guru).

This gives a chance distribution (I'll need this):
The people who have blue eyes put themselves at 50% chance that the guru saw him.
The other villages put themselves at 33%.

I knew I had to do something with this difference, a difference that always will be 1/n or 1/n+1 (in this case 1/2 or 1/3). But I felt something was missing, so I asked myself the question: can I do something with the time? Since it was also kind of suggested in the question: what day do they leave?

So instead of doing it recursively I decided to do it chance based. They are perfect logicians, so if someone knows they are it, they will leave and everything will be fine (because they can see him leave and check his eyes if he has blue eyes this whole thing stops, if he has brown eyes then something irrelevant to this case happened). Now since they are perfect logicians they know a way to think their way out of it if all else fails, and that's what my solution is:

If all else fails you will go on the day on which your chance is based. So if it's 1/2, you'll go on the second night, if it's 1/3, you'll go on the third night (in this case). If people already left the island (blue eyed) the algorithm stops. So this prevents the brown eyed people and the guru from going. They all know their chance of it being them.

So at the second night our person X sees the other person having blue eyes, which means HE must have blue eyes, the ferry waits and they know they should go on the ferry. Fast forward this to 100 blue eyed people and make up the chance distribution of 1/100 and 1/101. So all the blue eyed people will leave on day 100.

The difference between the solution posted on the blog: on the blog the chance distribution is implicit and less relevant than in my case. Furthermore, the chance is recursively defined. My solution is iterative. Funny thing that both algorithms can work alongside each other.

-------------- APPEND ----------------

Furthermore, I'd like to add that after this, the brown eyed people leave on day 200. Because of the following:

The brown eyed people get the news on day 101 that the blue eyed people have left. This starts the counter immediatly at one. They are perfect logicians and they know that there is one person with green eyes and the rest has brown eyes.

So our person Y (brown eyed guy) will think the following: the blue eyed people all left, that means I'm not a blue eye. I'm either green, brown or something else. He puts his chance of being brown at 1/100. Like every other brown eyed person does. However, the guru (green eyed person) will put his chance on 1/101 of being brown.

Nobody left on 1/99, because every brown eyed person put his chance on 1/100, which means that the brown eyed people will leave. The brown eyed people can do this, because in a way, the action of all blue eyed people leaving is akin for the guru to say: I see at least one brown eyed person.

Thus, the Guru will be left alone, knowing that he has neither brown or blue eyes. The only way for him to solve is problem is to promote his island and let all other eye colors come in as well.

[Xias]

A friend introduced me to the puzzle via this website. For anyone that doesn't know it, here it is: http://xkcd.com/blue_eyes.html (can't find the url tag).

Here is mine solution:
I thought the answer was recursive but I couldn't find a mechanism that was doing the job, so I did it intuitively.
Presuppositions I needed a lot.
1. They are perfect logicians. This means if one person would figure out if he had blue eyes he would leave the island immediatly.

Then I got stuck so I started to construct things from the ground up.

X is our blue eyed person that is our perspective (and view sight) as well.

What if: N = 2
X knows he has blue eyes, because guru told him so. The guru waves.

What if: N = 3 --> 1/ 1/ 1
X knows he has blue eyes, the guru waves.

What if: N = 4 --> 1 / 2 / 1 (format: blue red green)
X knows he has blue eyes, the guru hosts a party

And then it got tricky. I knew this would be the 'induction step', but I suck at induction so I still had to do this intuitively, which is why this answer is different (and iterative) instead of inductive / recursive.

What if: N = 5 2 / 2 / 1 (blue red green)
X knows that 3 people don't have blue eyes.
The guru knows nothing extra, so he knows 2 persons that aren't cutting it. However, he must be VERY AWARE of the fact that everyone heard what he said.
The 2 brown eyed persons know that 2 persons aren't cutting it (like the guru).

This gives a chance distribution (I'll need this):
The people who have blue eyes put themselves at 50% chance that the guru saw him.
The other villages put themselves at 33%.

I knew I had to do something with this difference, a difference that always will be 1/n or 1/n+1 (in this case 1/2 or 1/3). But I felt something was missing, so I asked myself the question: can I do something with the time? Since it was also kind of suggested in the question: what day do they leave?

So instead of doing it recursively I decided to do it chance based. They are perfect logicians, so if someone knows they are it, they will leave and everything will be fine (because they can see him leave and check his eyes if he has blue eyes this whole thing stops, if he has brown eyes then something irrelevant to this case happened). Now since they are perfect logicians they know a way to think their way out of it if all else fails, and that's what my solution is:

If all else fails you will go on the day on which your chance is based. So if it's 1/2, you'll go on the second night, if it's 1/3, you'll go on the third night (in this case). If people already left the island (blue eyed) the algorithm stops. So this prevents the brown eyed people and the guru from going. They all know their chance of it being them.

So at the second night our person X sees the other person having blue eyes, which means HE must have blue eyes, the ferry waits and they know they should go on the ferry. Fast forward this to 100 blue eyed people and make up the chance distribution of 1/100 and 1/101. So all the blue eyed people will leave on day 100.

The difference between the solution posted on the blog: on the blog the chance distribution is implicit and less relevant than in my case. Furthermore, the chance is recursively defined. My solution is iterative. Funny thing that both algorithms can work alongside each other.

-------------- APPEND ----------------

Furthermore, I'd like to add that after this, the brown eyed people leave on day 200. Because of the following:

The brown eyed people get the news on day 101 that the blue eyed people have left. This starts the counter immediatly at one. They are perfect logicians and they know that there is one person with green eyes and the rest has brown eyes.

So our person Y (brown eyed guy) will think the following: the blue eyed people all left, that means I'm not a blue eye. I'm either green, brown or something else. He puts his chance of being brown at 1/100. Like every other brown eyed person does. However, the guru (green eyed person) will put his chance on 1/101 of being brown.

Nobody left on 1/99, because every brown eyed person put his chance on 1/100, which means that the brown eyed people will leave. The brown eyed people can do this, because in a way, the action of all blue eyed people leaving is akin for the guru to say: I see at least one brown eyed person.

Thus, the Guru will be left alone, knowing that he has neither brown or blue eyes. The only way for him to solve is problem is to promote his island and let all other eye colors come in as well.

Your chance distribution thing is weird and I have no idea where it's coming from. But, given your append, I think you misunderstand the problem:

No brown eyed people leave the island. Not ever. Not unless the guru speaks again, or some other outside factor gives information.

Since you seem to think that they do, your logic is somehow flawed, and you should try to find out why.

EDIT: I looked over your post again and I think I understand your train of thought.

First off, the Guru never "saw" anyone in particular. There is no means of calculating the "chance that the guru saw them" because that's not what the guru means. The guru's statement can be changed to "There is no less than one person with blue eyes on this island" and the same information is passed.

Here's how the induction works:

First, we establish the n=1 case. That is to say, for ANY number of people on the island of any eye colors, there is ONLY one with blue eyes. When the guru speaks, this person sees no other person with blue eyes and figures out that he is the only one, and he leaves. When n=1, day=1.

Now we say that if the n=k case works, then the n=k+1 case works. We suggest that for any number of blue eyed people k, they will leave on day k. If that is true, then if there are k+1 blue eyed people on the island, they will see k blue eyed people. Each one figures out that there are either k or k+1 blue eyed people. When day k comes around and no one leaves, they know it is not k, and leave on day k+1. The induction holds.

You can see this in action if we go step by step. If there are 2 blue-eyed people, then each will see the other and figure there is either one, who will leave on day 1, or two, and they can both leave on day two. Since they both think this, neither of them leaves on day 1, so they both leave on day 2. Since 2 people would leave on day 2, if there are 3, they will know on day 3 after nobody leaves on day 2.

This holds no matter how many people are on the island, or what the distribution of colors is. There could be 100,000,000 blue eyed people, and a single brown eyed person; the blue eyed people leave on day 100,000,000 and the brown eyed person never leaves.

[phlip]

The guru's statement can be changed to "There is no less than one person with blue eyes on this island other than myself" and the same information is passed.

Fixed for important clause. The guru doesn't leave, regardless of her own eye colour.

[00melo00]

@Xias: thanks. My new post might not be right, but atm I'm examining why I got it wrong and it already proves to be really helpful

I have to note:
This was my answer before I looked up the solution on the internet. When I wrote the appends I knew the official induction answer (and understood it as well). Especially in the appends (but also quite a bit in the original post) I was thinking in a CS/programming style kind of way (ignoring induction when I wrote my appends). I've noticed today, my appends don't hold.

I see a funny line of thinking though. Could you debunk this logic (I can't).

When you take into account more problems of these in the following fashion: n / n / 1. Where n is a random number. And you take into account that the guru was talking about a specific person (I know the general solution, I'm looking for other ones).
The following interesting thing occurs, lets take a few examples to see the pattern.

Chance that the guru saw him.
1/1/1
Blue goes away.

2/2/1
Blue: 1/2
Brown: 1/3
Green: 1/3

The way how I derive this chance is to behave 'as if' you were a blue eyed person. So you take n - 1 people and add yourself up to it. So n chances.

3/ 3/ 1
Blue: 1/3
Brown: 1/4
Green: 1/4

4/ 4/ 1
Blue: 1/4
Brown: 1/5
Green: 1/5

The pattern is. People who are really blue will always count n. People who are not blue will always count n + 1. Since n < n + 1, the first group that leaves is blue. All people of the island can contrive these simple situations. So a real blue eyed person will assign himself as 1/100 and a brown eyed person as 1/101 if you'd follow this pattern.

Intuition would immediatly say, then leave at the nth day! Because if you leave earlier, you will meddle with things you don't know off, this value you do know, so leave on this day. I know for all he knows another could assign 1/99 or 1/50. He doesn't know what other people will do. Like I said this last paragraph is my intuition talking, not my logic Another intuition would say: this problem is inherently inductive, because it's posted on a computer science forum and almost every pattern is n +1. I know, a heuristic which would get me wrong many times, but it's a heuristic I used to solve this problem.

Now lets step out of reality and go into person X with the last situation.

4/ 4/ 1
BluePerson real: 1/4
BluePerson looking in BluePerson2's head, he could think: 1/3 (BluePerson = brown) or 1/4 (BluePerson = blue)
BluePerson2 real: 1/4
BluePerson2 looking in Blueperson2's head, he could think: 1/3 (BluePerson2 = brown) or 1/4 (BluePerson2= blue)

I know that if you would take the approach from BluePerson1 goes into BluePerson2's head and BluePerson1 goes from the perspective of BluePerson2 in BluePerson3's head.
Yea, then you'd arrive at induction.

The reason I'm still writing this is because this is my most intuitive construction, which eventually leads to the clue that induction is involved.

[Xias]

4/ 4/ 1
BluePerson real: 1/4
BluePerson looking in BluePerson2's head, he could think: 1/3 (BluePerson = brown) or 1/4 (BluePerson = blue)
BluePerson2 real: 1/4
BluePerson2 looking in Blueperson2's head, he could think: 1/3 (BluePerson2 = brown) or 1/4 (BluePerson2= blue)

I know that if you would take the approach from BluePerson1 goes into BluePerson2's head and BluePerson1 goes from the perspective of BluePerson2 in BluePerson3's head.
Yea, then you'd arrive at induction.

The reason I'm still writing this is because this is my most intuitive construction, which eventually leads to the clue that induction is involved.

That's actually a pretty important thought process to understand why the guru's statement conveys any information at all. We've been calling it "Nested hypotheticals", where person 1 imagines person 2 imagining person 3 imagining person 4 imagining... that person 100 doesn't see anyone with blue eyes. A lot of people get tripped up on the idea that this hypothetical person 100 can exist if everyone knows that everyone knows that there's 98 blue eyed people. But what does everyone know that everyone knows that everyone knows?

[Garrett]

I didn't read whole thread to see if something similiar was posted here so sorry if I repeat someones post.

There is another way to explain a solution to this puzzle. It's pretty much the same thing only longer because you're going from 99 to 1 and then back again to 99. This is how I solved this puzzle (I always seem to do things the hard way...).
Let's say I'm blue-eyed:

Spoiler:

I see 99 blue-eyed(be) dudes and 100 non-blue-eyed(bne). Let's say I'm nbe. Then the be dude next to me sees 98 be dudes and 101 nbe dudes. Then he thinks: "If I'm nbe then the be dude next to me sees 97 be dudes and 102 nbe dudes. Then he thinks"... and so on until be dude number one. If he doesn't leave island after day one, then that means that be dude next to him deduced he has be and they both leave on day two. If not, then the be dude next to be dude next to be dude deduced he has be and so all three of them leave on the third day. And so on back to me and we all leave on the 100th day.

I wouldn't solve this puzzle (or it would take me much longer) if not for a puzzle about three sages and their hats that I solved few years ago.

[t1mm01994]

That, in a slightly more rigorous version, is the solution posted in the OP, so congratulations on solving it!