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

[damaless]

Wait, I thought the tribal meeting only happened once.

edit: Yeah, I went back and looked.

The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island.

Emphasis mine.

The Guru only needs to say this once for 100 people to leave on the 100th day.

Imagine you're a blue-eyed person on the island. The Guru has said, once, that she can see someone with blue eyes. You look around, see 99 people with blue eyes. Then, you know that the person she saw wasn't necessarily you, since it could easily have been one of those 99 other people. But 99 days later, when still no one has left, you realize that since everyone can reason just as well as you, all of those 99 people you can see with blue eyes must be seeing someone who has blue eyes, who you can't see. Which is you. Keep in mind every blue-eyed person has the exact same perspective as you. So on the 99th day all of those people realize that 99 people they can see with blue eyes see one extra person with blue eyes. So everyone with blue eyes realizes that they have blue eyes on the 99th day, and so they leave on day 100.

All this comes from the Guru saying once that she can see one person with blue eyes.

[Rat]

Wait, I thought the tribal meeting only happened once.

edit: Yeah, I went back and looked.

The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island.

Emphasis mine.

The Guru only needs to say this once for 100 people to leave on the 100th day.

Imagine you're a blue-eyed person on the island. The Guru has said, once, that she can see someone with blue eyes. You look around, see 99 people with blue eyes. Then, you know that the person she saw wasn't necessarily you, since it could easily have been one of those 99 other people. But 99 days later, when still no one has left, you realize that since everyone can reason just as well as you, all of those 99 people you can see with blue eyes must be seeing someone who has blue eyes, who you can't see. Which is you. Keep in mind every blue-eyed person has the exact same perspective as you. So on the 99th day all of those people realize that 99 people they can see with blue eyes see one extra person with blue eyes. So everyone with blue eyes realizes that they have blue eyes on the 99th day, and so they leave on day 100.

All this comes from the Guru saying once that she can see one person with blue eyes.

ah, right, it does say that.. anyway.. the answer still makes sense... and nonono icaruse... i says no hostility... i said no offense!!!!

basically the same idea though.. either way... well.. ok ignore most of my old answer... the actual answer still does make sense though...

bah im going back to the individual comic forum

[damaless]

I didn't mean to discourage you from trying to solve logic puzzles, I just wanted you to understand that the people still leave even if the Guru only says it once.

[Rat]

I didn't mean to discourage you from trying to solve logic puzzles, I just wanted you to understand that the people still leave even if the Guru only says it once.

im not big on logic puzzles anyway...

but i understand, thanks

[Icaruse]

Why would the other person leave immediately if they see no blue-eyed people, if the guru never gave the pronouncement? For all that one person knows, they could be the one blue-eyed person, or there may be no blue-eyed people, and that person's eyes are brown, or green, or fluorescent purple, or something else.

(et al. responses)

Indeed. Upon reflection of my answer and the explinations I read, I realized that I failed to make the base case, making my entire argument useless. I got so caried away with the synchronozation of the modelings that I did not realize that there was originally no basis with wich to model. Anyway, thanks.

I still have not entirely convinced myself that the information the guru gives is completely external to all the modelings (i.e. does not apply only to the first itteration down), however I know this is a subject already touched on in this topic and my intuition says that it, indeed, travels all the way to the bottom, so I will read more of the replies.

Great puzzle, btw. Like an onion.

[ringobob]

This is correct. However, let's say that town meetings stop. But instead, the guru goes around to each person in the tribe each day, reporting on who left and who didn't. Let's further suppose this is the only thing each person knows--that the guru is coming to that person specifically, and saying who left.

Now, nobody will leave. Why? Because they get no new information. But what's more, they will not leave on day n, day 2n, day 5n, whatever.

But if tribal meetings are held daily, they will leave as described in the general solution.

You're correct in saying that they do not learn new information that nobody would leave, because they already know this. But something else is happening at the tribal meetings.

I was going to disagree with you, but then in the course of my explanation proved to myself that you were correct. The fact that they see each other every single day is an important part of the induction, because if for even one day they do not see each other, the inductive chain breaks down.

Wait, I thought the tribal meeting only happened once.

I think some people are using "tribal meeting" to mean a time when the guru speaks (only happens once), and some people are using it to mean a guaranteed time that everyone on the island sees everyone else on the island (per the puzzle, this happens every day, though not necessarily in a formalized meeting).

Great puzzle, btw. Like an onion.

In many, many ways

[yy2bggggs]

I was going to disagree with you, but then in the course of my explanation proved to myself that you were correct.

What? I'm correct?

I'm offended! You're breaking protocol. Haven't you ever been in an internet debate?

You're supposed to disagree with me even if what I say is completely obvious and undeniable--it's your job to twist whatever I say to such a degree that I get completely confused and go off on a sabatical to think about it, and/or we're supposed to get into a heated debate over this and eventually drag Hitler or our family heritage into it.

But you agree? Just like that? No way! I feel severely gypped.

What the hell is wrong with this forum?

[bitwiseshiftleft]

No real information is gained each day until day n...

Your reasoning is correct, but your conclusion is wrong. There is real information gained each day. If there wasn't, why would a day matter?

I was using information in a technical sense, meaning, the negative base-2 log of the size of the (hidden) state space. There is exactly one relevant bit of information missing from every islander's knowledge: whether or not his eyes are blue. That is, from any islander's initial observations, there are exactly two relevant states that the island can be in: one in which his eyes are blue and one in which they are not. The mental states of the other islanders are hidden, but the relevant details depend only on the day and on the eye color of the observer.

Obviously, a predictable occurrence (that doesn't change eye color) cannot give any information, because one could just imagine that it had already happened and reason from there. Only an unpredictable observation can do that, and by induction hypothesis, we know that the only unpredictable which ever happens on the island (for n>1) is whether people leave on night n-1.

The tribal meetings (or ferry or whatever) are necessary for synchronization, and therefore for the chain of reasoning, but except on night n-1, they do not give information. In fact, since it is impossible to gain information without determining one's eye color (since that's the missing bit), if they did give information (in the sense that I'm using it), everyone would leave early.

[yy2bggggs]

I was using information in a technical sense, meaning, the negative base-2 log of the size of the (hidden) state space.

What a coincidence. So was I!

There is exactly one relevant bit of information missing from every islander's knowledge: whether or not his eyes are blue.

I disagree. There is a lot more going on here than your particular relevant bit of information, that's relevant.

The entire synchronization process works specifically because of information gained. Maybe you'll find out exactly what information is communicated if you work on this little side puzzle:

Let's say that not everyone shows up at tribal meetings after the guru announcement, for fear of discovering their eye color. But the meetings are still held. Instead, people show up somewhat arbitrarily. Figure out the minimum requirements, with specificity, for a particular person to discover his eye color in the minimum possible number of days.

[damaless]

This isn't a problem that takes into account people's fears and hesitations. The reason why "people" and "eye colour" is used is because it's a useful analogy to the abstract logic/mathematical problem this is.

If you want to come up with a new puzzle that does take into account that the people may or may not want to leave the island and will act accordingly, start a new thread, imo. That's more of a stats problem anyway.

[yy2bggggs]

This isn't a problem that takes into account people's fears and hesitations.

You aren't to take this into account. This is still a puzzle, and it's still part of the same thread because it's still about the puzzle.

See? That's what I was talking about, ringobob. Now here is a true internet denizen!

[damaless]

This isn't a problem that takes into account people's fears and hesitations.

You aren't to take this into account. This is still a puzzle, and it's still part of the same thread because it's still about the puzzle.

See? That's what I was talking about, ringobob. Now here is a true internet denizen!

No, here is someone who reads carefully.

Everyone can see everyone else at all times

[yy2bggggs]

No, here is someone who reads carefully.

But reads what carefully?

Threads should not be duplicated. If I were to create a new thread about this puzzle variant, I must first search to see if there's a thread already out there. Turns out, there is. Not only that, I created that thread!

Which leads to a second situation. If there's a separate thread about a subject, but people aren't using it, then it's more appropriate to talk about things in that same thread.

Finally, the issue is quite relevant to the discussion at hand. Using puzzle logic, you're allowed to do nothing extraordinary. Thus, in this particular variant (which is more specific than the variant I posted in the other thread), you're basically to minimize the number of people who show up, and specify exactly who shows up. In addition, you are to arrive at the same solution.

This is directly related to the original puzzle--it's conceptually no different than considering a different number of blue eyed people. In essence, tribal meetings where everyone shows up are sufficient to reveal a person's eye color in n-1 days, but the necessary conditions do not involve everyone showing up each day--only a minimal set. Determining this minimal set will betray what's going on.

[damaless]

Maybe you are too focused on assuming that I am just trying to twist your words and prove you wrong. I never said that the variant that you are considering is not worth discussion or consideration, I only said that it is a variant. That in the original blue eyes puzzle, the solution is clear, hesitations and fears of the human mind are irrelevant. All I'm saying is that the puzzle you are discussing now is a different puzzle than the original blue eyes puzzle, with a different solution.

[ringobob]

Let's say that not everyone shows up at tribal meetings after the guru announcement, for fear of discovering their eye color. But the meetings are still held. Instead, people show up somewhat arbitrarily. Figure out the minimum requirements, with specificity, for a particular person to discover his eye color in the minimum possible number of days.

Well, first it's necessary to specify that a person knows whether someone else is still on the island whether they see them that day or not... otherwise, it would be impossible for anyone to leave.

Maybe you are too focused on assuming that I am just trying to twist your words and prove you wrong. I never said that the variant that you are considering is not worth discussion or consideration, I only said that it is a variant. That in the original blue eyes puzzle, the solution is clear, hesitations and fears of the human mind are irrelevant. All I'm saying is that the puzzle you are discussing now is a different puzzle than the original blue eyes puzzle, with a different solution.

I think you're focusing too much on the "hesitations and fears" aspect of this... he's not really making any assumptions about why a person might not show up, he's just basically removing one rule, namely:

Everyone can see everyone else at all times

... so, what is the minimum necessary for someone to figure out their eye color? Sounds just as relevant to me as any of the sub questions that were asked in the "official solution".

[bitwiseshiftleft]

You know, when we're arguing about a puzzle, it's very annoying so say things like:

Maybe you'll find out exactly what information is communicated if you work on this little side puzzle:

Let's say that not everyone shows up at tribal meetings after the guru announcement, for fear of discovering their eye color. But the meetings are still held. Instead, people show up somewhat arbitrarily. Figure out the minimum requirements, with specificity, for a particular person to discover his eye color in the minimum possible number of days.

Because then, to continue the discussion, I have to go and work out your puzzle, work out exactly what you meant by "what information is communicated," and then "maybe" I'll have enough information to continue.

In any case, in your puzzle, nobody can figure out his eye color in the minimum number of days unless he shows up to every meeting, so the solution is something like, for all i, there exist at least i people who show up to the meetings 0..n-i, and this probably is off by 1 in some direction.

However, the difference is, in your puzzle, the meetings are optional, and therefore there is information gained by attending them. That is, some part of people's mental process is a function of whether they attended the meeting (extra hidden state space), and whether they attend cannot be predicted from the previous observations (information gained). In the one we've been discussing, the meetings are mandatory (no extra hidden state space), and while they change the state of the island, they do so in a predictable way. There are no new, relevant, unpredictable observations made at the meetings (no information gained) until night n-1. That doesn't mean that the meetings are unimportant, or that the puzzle works without them, just that there is no information gained.

And sure, if my eyes were brown (which they're not), then someone else would be making a new observation on night n-2, but that gives me no info (there are still exactly two possible relevant states of the island, it's just that one of them now involves n-1 people knowing their eye color and the other does not).

If you'd like to argue that there's more hidden information in this puzzle, that some of the observations are unpredictable, or that predictable observations can grant information, or that one of my assumptions or logical steps is wrong, then I'd like to hear your argument. I would not like to be told to go find it myself.

[skeptical scientist]

Let's say that not everyone shows up at tribal meetings after the guru announcement, for fear of discovering their eye color. But the meetings are still held. Instead, people show up somewhat arbitrarily. Figure out the minimum requirements, with specificity, for a particular person to discover his eye color in the minimum possible number of days.

Every blue-eyed person must see at least one other blue-eyed person every day. Furthermore, every blue-eyed person must know that every blue-eyed person sees at least one other person every day. Furthermore, every blue eyed person must know that every blue-eyed person knows that every blue-eyed person sees at least one other blue-eyed person every day. Etc. (We don't actually need infinitely many of these, but at least 100 or so.)

[yy2bggggs]

You know, when we're arguing about a puzzle, it's very annoying so say things like:

Sorry you feel that way, but please remember, this is a puzzle forum, not a debate forum. The rules are different; the delay is appropriate for this reason. Just show some patience.

skeptical: This being more about demonstrating necessary conditions, assume the only variable you're allowed to play with is who shows up at the meetings when--required implications must follow directly from this. Furthermore, the minimal set is smaller than what you propose anyway.

There's a different way to get at this, too. I'll present that some time this weekend (and, once again, I won't just blurt it out, and I refuse to apologize for that).

[bitwiseshiftleft]

You know, when we're arguing about a puzzle, it's very annoying so say things like:

Sorry you feel that way, but please remember, this is a puzzle forum, not a debate forum. The rules are different; the delay is appropriate for this reason. Just show some patience.

...

There's a different way to get at this, too. I'll present that some time this weekend (and, once again, I won't just blurt it out, and I refuse to apologize for that).

That's fine. However, understand that I presented a logical argument, and still don't see anything wrong with it (other than my initial misstatement of the induction direction). Last time, you said that there was something wrong with my argument and that I might figure out what it is by solving your puzzle. Well, I'm pretty sure I solved your puzzle, and I still don't understand what's wrong with my argument, so think carefully before trying this again. The Socratic method is hard to get right, particularly if you're not Socrates.

[skeptical scientist]

For some reason I was thinking everyone had to find out. If you're the only one who has to find out,

You need to attend a meeting with two other blue eyed people every day.

Nevermind, this is false. I stand by my original answer, and the only way that could happen in a single meeting is if

all of the blue-eyed people are at that meeting.

[yy2bggggs]

There's a different way to get at this, too. I'll present that some time this weekend.

That's fine. However, understand that I presented a logical argument, and still don't see anything wrong with it (other than my initial misstatement of the induction direction).

What I'm saying is wrong is that there's only one bit of relevant information. The particular piece of information you cited is indeed relevant, and is one bit of information, but there's information communicated at each tribal meeting.

The inductive argument of what would happen at day 1, day 2, etc is perfectly valid, and provides a solution to this puzzle, but it's not the whole picture. The tribe is in a completely distinct state after the first tribal meeting; after the second, it's in another completely distinct state.

Even the initial announcement by the guru gives more information that the content of the announcement. The guru, by announcing this to the whole tribe, starts the chain--but if the guru gave the same exact announcement, individually, person to person, to every member of the tribe, nothing would happen at all.

The tribe goes into a different state when the guru makes the announcement to the whole tribe, than it would be in if the guru just made the announcement individually. This is because in the former case, information is gained, but in the latter case, it is not.

This all points to the same thing--information gained depends upon other tribal members being present. So obviously, it involves other members; however, it's also obviously not just what other members know, because that's just a symmetric situation to what a particular individual knows.

That's as far as I'll dare go at the moment explaining this, but here's the different situation. Let's consider the original puzzle--this time, we're going to make variations on the state of the tribe.

Basic puzzle Guru announces to the tribe that the guru sees a blue eyed person. Given n blue eyed people, everyone knows their eye color by day n.
Variant Guru announces to each individual, one on one, that she sees a blue eyed person. Nothing ever happens.
Border case Guru announces to the tribe that she sees n blue eyed people. Everyone leaves the first day.
Border case Guru announces to each individual, one on one, that she sees n blue eyed people. Everyone leaves the first day.
Middle case Guru announces to the tribe that she sees (at least) k blue eyed people, 1>k>n. What happens?
Middle case Guru announces to a group of j blue eyed people (subgroup of the tribe), that she sees (at least) k blue eyed people (in the whole tribe). 1>j>k>n. What happens?
Middle case Same as above, 1>k>j>n. What happens?

[bitwiseshiftleft]

What I'm saying is wrong is that there's only one bit of relevant information. The particular piece of information you cited is indeed relevant, and is one bit of information, but there's information communicated at each tribal meeting.

I think we're talking about subtly different variants of the puzzle here, and that's leading to a long debate where we each thing the other guy is missing the point.

In the version I'm talking about, the rules are strict and laid down in advance, and every relevant event on the island is scripted ahead of time.

For example, in my understanding of the problem, everyone knows (from the rules) that the Guru will make a pronouncement of the form "I (do/do not) see someone with blue eyes" on day 0. If they did not know this ahead of time, they would indeed gain information by hearing the pronouncement, because they couldn't have predicted it. Everyone also knows that, with the exception of the Guru's original statement, nobody ever says anything about eye color; if this were not part of the rules, then the Guru telling people individually about eye color would give them information (though, as you say, not enough to work out their eye color).

Similarly, in my understanding of the problem, the islanders must always show up to meetings (or, as xkcd stated it, they can see each other all the time but there's a ferry that leaves at midnight). Otherwise, information is lost when they decide (nondeterministically) whether to show up, and gained again by everyone at the meeting (by observing who showed up).

If all the action is scripted in advance, then the only unpredictable observation (and therefore, the only information gained) is the meeting on day n-1. If it is not scripted in advance, then sure, the islanders' choices to show up at meetings gives information.

[ringobob]

I was going to disagree with you, but then in the course of my explanation proved to myself that you were correct.

What? I'm correct?

I'm offended! You're breaking protocol. Haven't you ever been in an internet debate?

You're supposed to disagree with me even if what I say is completely obvious and undeniable--it's your job to twist whatever I say to such a degree that I get completely confused and go off on a sabatical to think about it, and/or we're supposed to get into a heated debate over this and eventually drag Hitler or our family heritage into it.

But you agree? Just like that? No way! I feel severely gypped.

What the hell is wrong with this forum?

Fine. I retract.

I was going to disagree with you, but then in the course of my explanation proved to myself that you were correct.

----------------------------------------------------------------------------------

This is correct. However, let's say that town meetings stop. But instead, the guru goes around to each person in the tribe each day, reporting on who left and who didn't. Let's further suppose this is the only thing each person knows--that the guru is coming to that person specifically, and saying who left.

Now, nobody will leave. Why? Because they get no new information. But what's more, they will not leave on day n, day 2n, day 5n, whatever.

But if tribal meetings are held daily, they will leave as described in the general solution.

You're correct in saying that they do not learn new information that nobody would leave, because they already know this. But something else is happening at the tribal meetings.

This is incorrect. Only Hitler (or someone otherwise associated with the Nazis in word or deed) would believe such an argument.

---------------------------------------------------------------------------------

HAH.

[yy2bggggs]

I think we're talking about subtly different variants of the puzzle here, and that's leading to a long debate where we each thing the other guy is missing the point.

All of my variants are just meant to be hints of the bigger picture--they're all aimed at the original problem. In other words, yes, I'm spinning off variants left and right, but I'm really talking about the original problem, just like you. (Only for simplicity, I'm varying the details to the canonical puzzle, which involves tribal meetings each day, and I believe we're both treating total number of blue eyed people as a variable).

If all the action is scripted in advance, then the only unpredictable observation (and therefore, the only information gained) is the meeting on day n-1.

How is that unpredictable? We know exactly what happens.

[rhino]

How is that unpredictable? We know exactly what happens.

As an islander who sees n-1 blue-eyed people, you don't know whether or not they will leave on day n-1. You do know, however, that none of them can leave before that.

Note: I agree with bitwiseshiftleft here, but I'm beginning to suspect that this argument is nothing but semantics.

[yy2bggggs]

How is that unpredictable? We know exactly what happens.

As an islander

But you are not an islander!

There's an underappreciated symmetry here between you the puzzle solver and a tribal member--after all, this whole problem works only because everyone on the island is also a problem solver. So anything you do, a problem solver can do; anything you recognize or allow, a problem solver can recognize or allow.

Thus, if there's one bit of information, there's a lot more--and all of it is relevant, because the problem hinges on everyone recognizing everyone else as problem solvers (that is, the same symmetry applying between you and the tribal member, applies just as validly to the tribal member and other tribal members). If you don't allow for this recursion due to unpredictability, you must not allow it in the first place.

There's a valid perspective where there are 0 bits of information, but none where there's only one bit.
[Edit:]
Further clarification--if you say, "relative to person A, there's one bit of information that is not known", you're ipso facto allowing person A to say "relative to person B, there's one bit of information that is not known".

[Yakk]

Basic puzzle Guru announces to the tribe that the guru sees a blue eyed person. Given n blue eyed people, everyone knows their eye color by day n.
Variant Guru announces to each individual, one on one, that she sees a blue eyed person. Nothing ever happens.

Unless they know what the guru told other people. :)

Border case Guru announces to the tribe that she sees n blue eyed people. Everyone leaves the first day.
Border case Guru announces to each individual, one on one, that she sees n blue eyed people. Everyone leaves the first day.

Suppose the Guru said "I see at least n blue eyed people". Then all the blue eyed people leave on night 1, and all the brown eyed people leave on night 2.

Next, suppose the Guru says "I see at most X blue eyed people". This is equivilent to saying "I see at least 200-X brown eyed people", reverses the puzzle, and the brown eyed people leave first.

Saying "I see exactly X blue eyed people" is saying both "I see at least X blue eyed people" and "I see at most X blue eyed people". This is why both the Blue and Brown eyed people leave on the same night in your case, but the brown eyed people need another day if the Guru says "at least".

Middle case Guru announces to the tribe that she sees (at least) k blue eyed people, 1>k>n. What happens?

The induction arguement kicks in. In n-k+1 days, they leave.

Middle case Guru announces to a group of j blue eyed people (subgroup of the tribe), that she sees (at least) k blue eyed people (in the whole tribe). 1>j>k>n. What happens?

Middle case Same as above, 1>k>j>n. What happens?

Is k > n-j? If so, you can demonstrate that the induction can kick in, because you just gained "there are at least k-n+j blue eyed people in the subgroup". Showing that is it the only efficient method would be interesting, and must be done before you have a proof that this would actually happen.

Otherwise, I suspect you got nothing.

[rhino]

But you are not an islander!

So what? We're talking about what the islanders know.

You claim there is unpredictability in the events before day n-1. That means you should be able to give me an example of something that can happen before day n-1 that an islander cannot predict. If you can't, I don't understand what you mean by "unpredictability".

Of course all the tribal meetings have to happen or the induction doesn't work. That doesn't mean the event of a tribal meeting conveys information, since they're guaranteed to occur.

So yes, please give me an example of what is unpredictable before day n-1. I don't want a puzzle to think about- what I'm asking for is very concrete, it should be easy to give a concrete answer.

Edit: In fact, only hitler would claim there were any unpredictable events before day n-1!

[bitwiseshiftleft]

How is that unpredictable? We know exactly what happens.

As an islander

But you are not an islander!

There's an underappreciated symmetry here between you the puzzle solver and a tribal member--after all, this whole problem works only because everyone on the island is also a problem solver. So anything you do, a problem solver can do; anything you recognize or allow, a problem solver can recognize or allow.

Thus, if there's one bit of information, there's a lot more--and all of it is relevant, because the problem hinges on everyone recognizing everyone else as problem solvers (that is, the same symmetry applying between you and the tribal member, applies just as validly to the tribal member and other tribal members). If you don't allow for this recursion due to unpredictability, you must not allow it in the first place.

There's a valid perspective where there are 0 bits of information, but none where there's only one bit.
[Edit:]
Further clarification--if you say, "relative to person A, there's one bit of information that is not known", you're ipso facto allowing person A to say "relative to person B, there's one bit of information that is not known".

Yeah. There are 0 bits of information not known to the problem solver. There is 1 bit of information not known to any given islander, but these bits are orthogonal. A can certainly reason "there is one bit of information that B doesn't know" (and will do so in the course of the puzzle) but, as it happens, A knows B's bit (sort of; B's bit encompasses not just his eye color, but also things that depend on his eye color, some of which A doesn't know. But A isn't missing B's bit.). So yes. A certainly has to reason about how much information other people know, but there is still only one bit that A is missing.

[skeptical scientist]

Yakk, you seem to be assuming that the islanders know they have either blue or brown eyes, but mightn't they all suppose that their own eyes could be green, purple, orange, or puce?

[tendays]

Hello all,

I've been reading all this thread and feel an urge to say something :-) (yes, i'll post in the introductory thread very soon I promise)

I think using some formal notation should help doing formal reasoning on this so I suggest the following. At least it helps me solving this kind of problems. Sorry if it just ends up confusing people :-)

Bx where x is a number means "there are x blue eyed islanders". (In particular we know that B100 holds)

Then, because we are dealing with uncertainty I write A | B to mean "one of A or B is true".

So, in the riddle, the knowledge of blue eyed people, before the guru speaks, is B100 | B99 - there are either 99 or 100 blue eyed people (and people with non blue eyes know that B101 | B100 holds)

More generally, before the guru speaks, if Bx is true then blue eyed people will know that Bx | Bx-1. This includes the case x=1 and even x=0.

Finally, because we are only concerned about what blue eyed people think I'll write {X} to express "blue eyed people know that X".
To be totally rigorous we'd need to set a few axioms, like {X} => X, i.e. "If blue eyed people know that X is true then X is true" and {X} and {Y} => {X and Y}, i.e. "if blue eyes know that A is true and blue eyes know that B is true then blue eyes know that A and B is true".

So what I wrote above is Bx implies { Bx | Bx-1 }. We can go further and replace Bx-1, getting "Bx implies { Bx | {Bx-1 | Bx-2} }".

Because we, as riddle solvers, know that B100 holds, we also know that {B100 | {B99 | {B98 ..... {B2 | {B1 | B0}} ... }}} holds.
In other words (taking {X}'s definition above), before guru talks, blue eyed people know that B100 | {B99 | {B98 ..... {B2 | {B1 | B0}} ... }} holds.

On day one, when the guru speaks, she says "not B0". So as soon as she has spoken, {{{{{{{...not B0...}}}}}}} becomes true (it is true for any level of nesting. I explain below.) This is the actual information that she gives the blue eyed people, which they did NOT know before she speaks, and which, 99 days later, will allow blue eyed people to know they have blue eyes. Let me explain:
not B0 means there is at least one person with blue eyes. This was already true before she spoke.
{not B0} means blue eyed people know that there is at least one person with blue eyes. This too was already true before she spoke.
{{not B0}} means blue eyed people know that {not B0} is true, i.e. they know that all the other blue eyed people know that there is at least one blue eyed person. This was already true before she spoke, as well.
{{{not B0}}} means that blue eyed people know that {{not B0}} is true. Etc.
With ninty nine pairs of { - } you get a statement that was FALSE before the guru spoke, and becomes TRUE afterwards. (For reasons that have already been given a hundred times in this thread - I can give them again using this notation if anyone cares)

As soon as she is done and the islanders are done thinking about the consequences, the following expression becomes true: {B100 | {B99 | {B98 ..... {B2 | {B1}} ... }}}.

To prove this I need two axioms which are (A1) that "if blue eyed people know that X implies Y and know that X is true then they also know that Y is true". That is the "blue eyed people are perfect logicians" part. Using my notation this is written {X=>Y} and {X} imply {Y}. Additionally, I assume that they know first order logic, i.e. (A2) if B is a first order logic theorem then {B} holds.
We get the following:
(B1 | B0 and not B0) implies B1
( {B1 | B0} and {not B0} ) implies {B1}
Now if I know that X|Y is true and Y implies Y' then I also know that X|Y' is true.
I.e.
B2 | {B1 | B0} and {not B0} implies B2 | {B1}
i.e.
{B2 | {B1 | B0}} and {{not B0}} implies {B2 | {B1}}. You get the idea.

Now, the rule is "people who know their eye colour leave at the next ferry". Assuming Bx holds, this is true precisely if {Bx} is true as well. (In our B100 case, blue eyed people will all leave if and only if they know that there are 100 blue eyed people).
Therefore, when a ferry come and goes empty lets everybody in the island know that {Bx} is wrong (whatever x is).
So, we were at the following, just after the guru spoke:
{B100 | {B99 | {B98 ..... {B2 | {B1}} ... }}}
Night comes, the ferry comes and goes, and the next day people see no one has left. So {Bx} was wrong for all x on that night, i.e. in particular {B1} was wrong. The above expression reduces to
{B100 | {B99 | {B98 ..... {B3 | {B2}} ... }}}
This is on day 2.
Similarly, until day 99, were the expression which is true (but was wrong on day 98) is {B100 | {B99}}. In English, what blue eyes know is B100| {B99}, i.e. "either 1) we are a hundred to have blue eyes or 2) they are 99 to have blue eyes *and they know it*."
That night, when the ferry leaves empty, "not{B99}" is told to the islanders. So, using the same reasoning, the next day {B100} is true, and all blue eyes leave.
I have not expressed brown eyes knowledge in there, so briefly: before the blue eyes left their knowledge was B100 | B101. When the blue eyes left the came to know that {B100} was true (and therefore B100 also is). So all brown eyes know on day 101 that they don't have blue eyes (but they don't know if they are brown or green or anything else).

So in light of the above I'd say that bitwiseshiftleft is correct in saying that in an information theoretic sense people don't learn anything new until the day 99 (for blue eyes) or 100 (for brown eyed people). The knowledge for all blue eyes is B100|B99 until day 99, i.e. blue eyed people all get one extra bit of knowledge on day 99 and none until that day. However the state of the world (in the sense the set of true and false statements, as I explained above) is changing every day, as yy2bggggs says (yes I'll admit it - I am trying to make every one happy).

Compare it to the following situation: A train goes from one point to another, and needs a hundred day to complete its journey. On day 99 it is going to cross a big bridge.
Because it is the first time a train is sent over that bridge, everbody wonders if the bridge is going to break or not when the train passes.
No one learns *any* information about whether or not the bridge will hold while the train is approaching. Knowledge is only gained on that day the train attempts to cross the bridge. However the state of the system changes every day, in that every day the train is closer to the bridge, and there is no other way to know if the bridge will hold than wait for the train to do all the way to it. Same here - the mental/knowledge state of the islanders changes every day but that state is not gained by experiments or observations, hence they do not gain information in an information theoretic sense.

I hope I was understandable.

[skeptical scientist]

For some reason I was thinking everyone had to find out. If you're the only one who has to find out,

You need to attend a meeting with two other blue eyed people every day.

Nevermind, this is false. I stand by my original answer, and the only way that could happen in a single meeting is if

all of the blue-eyed people are at that meeting.

[yy2bggggs]

and the only way that could happen in a single meeting is if

all of the blue-eyed people are at that meeting.

How about at meeting n-1? There's either n-1 or n blue eyed people. Assuming you have blue eyes, only one has to show up--that's enough to reveal you have blue eyes. Check your reasoning.

The situation is different if you have brown eyes, where you must account for all blue eyed people you know exist daily, so that "blue eyed people didn't show up" doesn't simply mean they didn't come.

[phlip]

One thing people might not be seeing with the "things we don't know" stuff...

For simplicity, take the 4-blue-eyed-people case. Person A knows, as has been listed before:

• There are at least 3 blue-eyed people
• B knows there are at least 2 blue-eyed people
• B knows that C knows that there is at least one blue-eyed person
• B doesn't know if C knows if D knows if there are any blue-eyed people

However, after the guru's pronouncement, he also knows:

• B knows that C knows that D knows there is at least one blue-eyed person.
• Tonight, noone will leave. B will know that C knows there is at least 2 blue-eyed people
• Tomorrow night, noone will leave, and B will know that there is at least 3 blue-eyed people
• The night after, B, C and D may or may not leave. Whether they do or not will give me new information about my own eye colour.

That night, when noone leaves, we know that B knows that C knows that there are at least 2 blue-eyed people. But this is not new information that night... we knew this would happen as soon as the guru made the pronouncement – we knew then that B didn't have that knowledge yet, but would that night.

[Yakk]

Yakk, you seem to be assuming that the islanders know they have either blue or brown eyes, but mightn't they all suppose that their own eyes could be green, purple, orange, or puce?

I used "brown eyes" to denote the equivilence class of non-blue eyes.

[ringobob]

I used "brown eyes" to denote the equivilence class of non-blue eyes.

That's the thing, the non-blue eyed group is not known (by them) to be an equivalence class. Each individual in the brown eyed group thinks:

"I see 100 blue eyed people, 99 brown eyed people, and my eyes could be blue, brown, green, red, or chartreuse."

It does not follow that knowing you are not in one group means you are in the other group.

[Iskaral]

I admit I haven't read all replies here but it seems to me only mikolaj have written about the issues with this problem.

The information the inhabitants on the island get from the guru is a common starting point and which color of eyes to count. The information that someone has blue eyes is worthless. For example, the guru could have said just "blue!" and it would have had the same effect.

The solution to the problem requires that all the inhabitants understand that the mention of blue means they should start counting blue eyes. This might seem like the obvious choice but it's still not a totally logical problem. If the guru had said "purple" would they still start counting blue eyes because it's a close enough color? Because even when the guru says blue there might not be 100% consensus that this is THE event that should start the counting. What if someone waits for the guru to say "start counting blue now" instead?

[EDIT] Removed my bad example

[phlip]

For example, the guru could have said just "blue!" and it would have had the same effect.

No, it wouldn't have.

Consider if there was just one blue-eyed person. As far as that person can tell, there might not be any any blue-eyed people. In this case, clearly, the guru saying "I see at least one blue-eyed person" gives some information, that "Blue! Hahaha! Purple monkey dishwasher! Watch out for the flying pink elephants! Someone get these spiders off me!" does not.

Now, consider for two blue-eyed people. Each of them can see exactly one blue-eyed person. Now, if the guru comes out and says some gibberish, nothing happens. Both blue-eyers know that the other person won't leave, 'cause they have no reason to... so no new information is given when they don't. But if they guru comes out and says "I see at least one blue-eyed person"... even though both blue-eyers know that particular fact already, it still changes the situation. Now, both blue-eyers will expect the other one to leave, by the logic in the previous paragraph. When they don't, they'll realise that they must have blue eyes, and leave.

The pattern continues...
The inductive step of the proof holds no matter what the guru says, or even if the guru doesn't say anything, but the base case only holds if the guru specifically says "I see at least one blue-eyed person".
For an inductive proof to be true, both must hold.

[Iskaral]

No, it wouldn't have.

Consider if there was just one blue-eyed person. As far as that person can tell, there might not be any any blue-eyed people. In this case, clearly, the guru saying "I see at least one blue-eyed person" gives some information, that "Blue! Hahaha! Purple monkey dishwasher! Watch out for the flying pink elephants! Someone get these spiders off me!" does not.

Your sense of the induction proof is wrong. Consider that the guru hadn't said anything at all, but instead we just assume we have the knowledge that at least one person has blue eyes.

Assuming this knowledge, we can easily see that for N=1 (N being the number of blue-eyed persons) that person realizes right away his own color.

For N=100 we get that all blue-eyed persons realize on day 100 what color they have, provided very same assumption that at least one person has blue eyes is true. The induction proof says that for N=100 eveyone needs to know there is at least one blue-eyed person for it to hold, and this is true before the guru says anything.

It doesn't matter that in the N=1 case we wouldn't have the information because this is just a hypothetical case used to start the induction.

Also the guru never said anything about the case with one blue-eyed person. There is no guarantee he/she would have said the same thing if there only was one blue-eyed person on the island.

[jestingrabbit]

No, it wouldn't have.

Consider if there was just one blue-eyed person. As far as that person can tell, there might not be any any blue-eyed people. In this case, clearly, the guru saying "I see at least one blue-eyed person" gives some information, that "Blue! Hahaha! Purple monkey dishwasher! Watch out for the flying pink elephants! Someone get these spiders off me!" does not.

Your sense of the induction proof is wrong. Consider that the guru hadn't said anything at all, but instead we just assume we have the knowledge that at least one person has blue eyes.

Assuming this knowledge, we can easily see that for N=1 (N being the number of blue-eyed persons) that person realizes right away his own color.

For N=100 we get that all blue-eyed persons realize on day 100 what color they have, provided very same assumption that at least one person has blue eyes is true. The induction proof says that for N=100 eveyone needs to know there is at least one blue-eyed person for it to hold, and this is true before the guru says anything.

It doesn't matter that in the N=1 case we wouldn't have the information because this is just a hypothetical case used to start the induction.

Also the guru never said anything about the case with one blue-eyed person. There is no guarantee he/she would have said the same thing if there only was one blue-eyed person on the island.

I really do think that you have the wrong end of the stick on this one Iskaral.

What goes on isn't just simple counting, it just resembles that. What is really going on is people hypothesizing about people hypothesizing about people hypothesizing etc.

To see this its easiest to start at the case with 3 or four blue eyed people, but we can do it with 100 anyway, its just a lot more tedious and I wont be writing it all out.

To begin with, if people just started to arrive on the island, not knowing their eye color, I don't see how anyone could assert that they would spontaneously know it at some time, short of empirical evidence being provided, which is specifically denied by the puzzle.

Then the guru arrives, and the fun starts. Before the guru speaks, the blue eyed people know that there are at least 99 blue eyed people and at most 100. The brown eyed people know there are at least 100 blue eyed people and at most 101.

But, they don't know for certain what other people know. A person with blue eyes can hypothesize that another person with blue eyes knows that either there are at least 98 blue eyed people and at most 99, or they know that there are at least 99 and at most 100.

Furthermore, A blue eyed person doesn't know what a blue eyed person knows that a blue eyed person knows. A blue eyed person can hypothesize that a blue eyed person can hypothesize that a blue eyed person knows that there are at least 97 blue eyed people and at most 98 blue eyed people, or there are at least 98 blue eyed people and at most 99, or they know that there are at least 99 and at most 100.

Furthermore, A blue eyed person doesn't know what a blue eyed person knows what a blue eyed person knows that a blue eyed person knows. There are four entirely possible hypothetical perspectives that thrice hypothesized individual might hold.

What starts the count is the fact that a blue eyed person's 99th hypothesized individual, and a brown eyed person's 100th hypothesized individual, knows what the guru says and would act in a particular way.

I think that the puzzle is entirely logical, its just modal logic, which is reasoning about other people's reasoning. Normally, we don't really think like this to the degree that the problem requires that we think like this. We can possibly come to a determination that our opponent in chess is trying to do x, and maybe we can try to make them think that we are doing y whist actually doing z, which requires a fair bit of modal logic, but beyond that its a very confusing way to think.