In the 100 blue eyes problem - why is the oracle necessary?

Question

The riddle

Randall Munroe (of xkcd fame) has, a bit hidden on his site, a logic puzzle:

A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. 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. Everyone on the island knows all the rules in this paragraph.

On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.

The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

"I can see someone who has blue eyes."

Who leaves the island, and on what night?

There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."

And lastly, the answer is not "no one leaves."

He admits the puzzle isn't his:

I didn't come up with the idea of this puzzle, but I've written and rewritten it over the the years to try to make a definitive version. The guy who told it to me originally was some dude on the street in Boston named Joel.

The answer

He gives his solution:

The answer is that on the 100th day, all 100 blue-eyed people will leave. It's pretty convoluted logic and it took me a while to believe the solution, but here's a rough guide to how to get there. Note -- while the text of the puzzle is very carefully worded to be as clear and unambiguous as possible (thanks to countless discussions with confused readers), this solution is pretty thrown-together. It's correct, but the explanation/wording might not be the best. If you're really confused by something, let me know.

If you consider the case of just one blue-eyed person on the island, you can show that he obviously leaves the first night, because he knows he's the only one the Guru could be talking about. He looks around and sees no one else, and knows he should leave. So: [THEOREM 1] If there is one blue-eyed person, he leaves the first night.

If there are two blue-eyed people, they will each look at the other. They will each realize that "if I don't have blue eyes [HYPOTHESIS 1], then that guy is the only blue-eyed person. And if he's the only person, by THEOREM 1 he will leave tonight." They each wait and see, and when neither of them leave the first night, each realizes "My HYPOTHESIS 1 was incorrect. I must have blue eyes." And each leaves the second night.

So: [THEOREM 2]: If there are two blue-eyed people on the island, they will each leave the 2nd night.

If there are three blue-eyed people, each one will look at the other two and go through a process similar to the one above. Each considers the two possibilities -- "I have blue eyes" or "I don't have blue eyes." He will know that if he doesn't have blue eyes, there are only two blue-eyed people on the island -- the two he sees. So he can wait two nights, and if no one leaves, he knows he must have blue eyes -- THEOREM 2 says that if he didn't, the other guys would have left. When he sees that they didn't, he knows his eyes are blue. All three of them are doing this same process, so they all figure it out on day 3 and leave.

This induction can continue all the way up to THEOREM 99, which each person on the island in the problem will of course know immediately. Then they'll each wait 99 days, see that the rest of the group hasn't gone anywhere, and on the 100th night, they all leave.

Before you email me to argue or question: This solution is correct. My explanation may not be the clearest, and it's very difficult to wrap your head around (at least, it was for me), but the facts of it are accurate. I've talked the problem over with many logic/math professors, worked through it with students, and analyzed from a number of different angles. The answer is correct and proven, even if my explanations aren't as clear as they could be.

User lolbifrons on reddit posted an inductive proof.

If you're satisfied with this answer, here are a couple questions that may force you to further explore the structure of the puzzle:

1. What is the quantified piece of information that the Guru provides that each person did not already have?
2. Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?
3. Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

These are just to give you something to think about if you enjoyed the main solution. They have answers, but please don't email me asking for them. They're meant to prompt thought on the solution, and each can be answered by considering the solution from the right angle, in the right terms. There's a different way to think of the solution involving hypotheticals inside hypotheticals, and it is much more concrete, if a little harder to discuss. But in it lies the key to answering the four questions above.

The question

Everybody on the island could have come to the conclusion that 'There is at least one person with blue eyes', simply by looking around, seeing 100 people with blue eyes, and realising that everybody can see at least one person with blue eyes.

So why is it necessary for the Guru to say 'I see at least one person with blue eyes' to get the ball rolling?

Answer 1

The knowledge of each islander consists of:

• the color of the eyes of every other islander;
• any past pronouncement from the guru;
• the history of who left the island on previous days (including their eye color), which provides knowledge about others' knowledge (that either they did or did not know their own eye color on previous days).

At the beginning of the story, nobody has ever left the island and there is no past pronouncement. So the only information everyone has is the color of everybody else's eyes, and the fact that nobody has figured out their own eye color. This is a stable situation, which lasts forever. It is in fact quite intuitive that since nobody has any information that involves in any way the color of their own eyes, nobody can be certain of the color of their own eyes.

Let's say that the guru makes her pronouncement on day 0. Starting on day 0, each islander has extra information: up to n days after the pronouncement, nobody left, meaning that nobody could figure out the color of their own eyes.

Suppose that only Alice has blue eyes. Before day 0, she never knew anyone with blue eyes. On day 0, she learns that someone has blue eyes; since nobody else does, it has to be her and only her, so she takes the ferry that night.

Now suppose that only Alice and Bill have blue eyes. Before day 0, Bill already knew that there was someone with blue eyes, but he did not know that Alice knew. If Bill had had green eyes, Alice would have been the only blue-eyed person and would not have known. On the first night after the guru, Alice doesn't leave; this tells Bill that Alice did not know the color of her eyes, so Bill learns that she was not the only blue-eyed person. Since Bill knows that either Alice is the only blue-eyed person or Bill and Alice are the only two, Bill now knows that both he and Alice have blue eyes.

If Charlie also has blue eyes, then he follows the reasoning above. Since Alice and Bill do not leave on the second night, it follows that they are not the only two people with blue eyes, so Charlie figures out that he's the third and leaves the next night.

The information that islander X learns from the guru is not just “someone has blue eyes”, but also “Y knows that X knows that someone has blue eyes”, “Z knows that Y knows that X knows that someone has blue eyes”, etc. It's vital to the puzzle that the guru's declaration is public and known to be public. If some of the islanders didn't hear the announcement, the chain of deduction wouldn't work anymore.

Answer 2

Let's continue the induction, since the jump to 99 blue eyes does seem weird. After all, everyone knows that someone has blue eyes.

If there are 4 blue eyed-people, A will look at B,C,D, thinking :

Maybe I don't have blue eyes (only 3 blue eyes?). In this case B must be thinking, that he may not have blue eyes either, and B is looking at C and D, whom he perceives as being the only ones to have blue eyes (since I consider the option that I don't have blue eyes), and B thinks that C is having the same reasoning. C thinks he does not have blue eyes and only D has.

Now, the issue here is that I, being A, can see that B has blue eyes. Therefore I know that C sees at least D and B as having blue eyes. But this is the reasoning of B, who does not know that he has blue eyes.

When I project myself into the reasoning of the next person, I cannot use the knowledge I have of their eye color.

The same goes for 5 people and more. I see 4 blue-eyed people, each of which is possibly seeing only 3, and thinking that each of the other is possibly seeing only 2...

Answer 3

Every blue-eyed person sees 99 blue-eyed people. Since they don't know that they have blue eyes, they suspect it might be the case that every other blue-eyed person can only see 98 blue-eyed people, and if those people only see 98 blue-eyed people, they might think that each of them only see 97 blue-eyed people. And so it continues, until someone considers a hypothetical situation in which someone sees no blue-eyed people. Then the guru, in this hypothetical, really does make a difference.

So the essential piece of information the Guru provides is that everyone knows that everyone knows that everyone knows that [... etc. ...] everyone knows that there is someone on the island with blue eyes. This enables everyone to discard that nested hypothetical.

It might be easier if we assign everyone numbers. People 1 to 100 have blue eyes. Person 1 sees 99 people with blue eyes, so suspects that Person 2 might see only 98 people with blue eyes, in which case Person 2 would think that Person 3 might only be able to see 97 people with blue eyes, in which case they would think that Person 4 might only be able to see 96… all this speculating is unravelled when everyone finds out that if Person 100 could not see any blue eyes, then Person 100 would be able to leave, so if Person 99 could only see one set of blue eyes, Person 99 would be able to leave after they didn't, so… etc.

---

Perhaps this is enlightening: if the Guru went to each person individually, and told them each in secret that there was a person with blue eyes, then it would not help: they would truly have learned nothing. The Guru saying that someone has blue eyes does not change anyone's mind about whether or not anyone has blue eyes. But that's not all everyone gets from the situation: not only did everyone hear the announcement, everyone saw that everyone else heard the announcement, and everyone saw that everyone saw that etc. Everyone finds out something about other people's state of knowledge.

Answer 4

The whole process is inductive, so it needs a starting point. If there were only one blue-eyed person, he would never know that there is "at least one person with blue eyes," so he would not go the first night. If there are only two, neither of them can know whether the other doesn't go the first night because he only sees brown eyes, so they don't know if they should go the second night. A third wouldn't be able to know if the first two hadn't gone because they only see one each or two, and so on.

When the oracle makes his statement, it ensures that a hypothetical lone blue-eyed person would know he is the one, which allows the induction to begin.

Answer 5

The only explanation I've seen that's sufficiently precise to be satisfying is this answer to the corresponding question on math.SE. The key fact that the "oracle" (guru) gives you, that you didn't have before, is that "(everybody knows)^N there is at least one blue-eyed person" for any value of N. In particular, you need it to be true for N=100, but the "induction process" starting from direct observation only gives you the result up to 99 levels of "(everybody knows)". The guru really is giving additional information that you don't already know: not information about the existence of a blue-eyed person, but information about everyone's knowledge of what each other know.

In particular, explanations that claim the guru is just needed as a starting point for counting days are wrong. The guru's statement, and everyone's awareness of it, are really needed in order for anyone to draw a conclusion about their own eye color.

Answer 6

I think considering it backwards might actually be the easier way to understand it.

A given blue-eyed person does not want to leave, so he hopes he has brown eyes and assumes he has brown eyes. He sees 99 blue-eyed people. Because he has assumed he does not have brown eyes himself, he must assume all of those other blue eyed people see 98 other blue eyed people. (In his mind, he has removed himself from the set of blue eyed people.)

(The fact that all the blue eyed people actually see 99 other blue eyed people is separate from the belief the first person holds that those people see 98 others.)

The first person then goes on to reason that a given one of the 98 will see only 97 others. So, the first person believes there are 99 total, and in the mind of the first person is an imaginary second person who believes there are 98 total. And so on.

The entire stack of one mind thinking about what is in the mind of another person who is thinking about what is in the mind of another person exists entirely in the mind of the first person. That's how the state of imagined knowledge can get so far from the reality that everyone can physically observe.

The rest of the induction has been explained already, so I'll just amplify the two points I wanted to add to the discussion with this answer:

• Each person is in turn removing himself from the set of blue eyed people (until his hypothesis is contradicted on day 100). That's why the numbers go down 99, 98, etc.
• We are dealing with nested levels of imagined minds thinking about other imagined minds (like the nested dreams in Inception). The 2nd, 3rd, 4th, etc. levels are "virtual people" (like nested virtual machines) and that's how they see can differ from what is physically observed.

Answer 7

The colour of the guru's eyes is not relevant. The guru is allowed to speak about eyes and nobody else is. If any blue eyed person said "I can see someone with blue eyes" where everyone on the island could hear it, the same thing would happen. Also if any brown eyed person did. The moment a blue-eyed person hears that someone else can see some blue eyes, and those blue-eyed people know it, the clock starts ticking. Once I hear that and I see N blue eyed people, if they haven't left after N days it's because they are including me in their count of N. Therefore I have to leave on day N+1. It even works if they wake up one morning and find "at least one person has blue eyes" scrawled on the mirror in lipstick, except for them not having any mirrors.

Answer 8

There are a lot of explanations for this, and certainly also a lot of debate over this question as the problem is extremely counterintuitive. Therefore, no explanation I could give or anybody could give will come close to satisfying everyone, but I will try anyway.

---

Although every islander knows that there is at least one person in the island with blue eyes, the blue-eyed people do not know whether there are 99 or 100 people with blue eyes on the island.

The guru coming and saying there is a person on the island with blue eyes allows them to start the chain of inferences alluded to in the solution and conclude that if everybody does not leave in 99 days, they are a person with blue eyes as well.

The reason they cannot start this chain of inferences themselves boils down to the fact that although they see somebody with blue eyes, they cannot determine how many days to wait (either 98 and I am not blue-eyed, or 99 and I am blue-eyed) because they do not know the total number of blue-eyed people on the island. You need somebody outside their group to come and tell them that there is at least one person with blue eyes, so that you have the inductive base case of one blue-eyed person to build on top of and determine how many days to wait.

Answer 9

As you did, let's reduce it to the case of three people for clarity's sake.

Aaron, Bob, and Charlie have blue eyes. No guru says anything.

Aaron thinks: If Bob sees only Charlie with blue eyes, then Bob knows after the first night, viz after Charlie doesn't leave, that Bob has blue eyes.

Er, no. That'd be true if the guru said someone has blue eyes. But that's not true now: Charlie's not leaving doesn't mean anything, as no one has told him he has blue eyes. So (in Aaron's mind) Bob doesn't, even if he sees only Charlie with blue eyes, know after Charlie doesn't leave the first night that Bob has blue eyes.

Answer 10

Let's take the case where there are 3 blue eyed people. each blue eyed person sees two blue eyed people but that is not enough for him/her to realize they have blue eyes. for that fact to be inferred he needs to observe the two blue eyed people he sees not leaving after two days. and the only reason he would expect them to leave in two days is because he observed them listening to the remark that "there is at least one blue eyed person".

If the information was not shared to all at the same time there would be no reason for anyone to expect the group of blue eyed people to leave at any point.

If you see N blue eyed people around you expect them to all leave N days after the statement. if the information isn't shared there would be no reason for that expectation and therefore it would be impossible to infer your own eye color.

Answer 11

The oracle disproves a nested hypothetical.

I'll try to prove this from the top down without using induction.

First, a definition:

Person(n) is the n'th blue-eyed person. We number the blue-eyed people 1 to 100 without loss of generality, with each person being Person(1) from their own perspective. Those without blue eyes are not relevant to this proof and are ignored.

H(n) is the n'th nested layer of hypothetical worlds with each person assuming their own eyes are non-blue at every layer.

• H(0) is our perspective looking at the puzzle from the outside. It contains 100 people with blue eyes.

• H(1) is what we imagine Person(1) sees, and contains 99 people of blue eyes.

• H(2) is what we imagine Person(1) imagines Person(2) sees if Person(1) does not have blue eyes. It contains 98 pairs of blue eyes.

• H(3) is what we imagine Person(1) imagines Person(2) imagines Person(3) sees, if Person(1) and Person(2) both assume that they don't have blue eyes. It contains 97 pairs of blue eyes.

• H(100) is what we imagine Person(1) imagines Person(2) imagines Person(3) imagines... Person(99) imagines Person(100) sees, if Person([1, 99]) assume that their eyes are non-blue. It contanis 0 pairs of blue eyes.

• H(101) is what we imagine Person(1) imagines Person(2) imagines Person(3) imagines... Person(99) imagines Person(100) imagines that the Guru sees, if Person([1, 100]) assume that their eyes are non-blue. It contanis 0 pairs of blue eyes.

Prior to the Guru's statement, H(101) is conceivable to Person(1) - not that it is true, but Person(1) believes that Person(2) believes that Person(3) believes... ...that Person(99) believes that Person(100) believes that it might be true.

After the Guru's statement, H(101) is no longer conceivable. Since H(101) is no longer conceivable, Person(100) in H(100) would leave on the next night. Since they don't, H(100) becomes impossible. Since no one leaves the night after, H(99) becomes impossible. Each night, another layer of nested H(n) becomes impossible, until on the final night, H(1) becomes impossible and everyone simultaneously realizes that H(0) is the only possibility remaining.

The full definition of H(101)

Here is the fully expanded of H(101), which the Guru's statement renders impossible.

H(101) is what we imagine Person(1) imagines Person(2) imagines Person(3) imagines) imagines Person(4) imagines Person(5) imagines Person(6) imagines Person(7) imagines Person(8) imagines Person(9) imagines Person(10) imagines that Person(11) imagines that Person(12) imagines that Person(13) imagines that Person(14) imagines that Person(15) imagines that Person(16) imagines that Person(17) imagines that Person(18) imagines that Person(19) imagines that Person(20) imagines that Person(21) imagines that Person(22) imagines that Person(23) imagines that Person(24) imagines that Person(25) imagines that Person(26) imagines that Person(27) imagines that Person(28) imagines that Person(29) imagines that Person(30) imagines that Person(31) imagines that Person(32) imagines that Person(33) imagines that Person(34) imagines that Person(35) imagines that Person(36) imagines that Person(37) imagines that Person(38) imagines that Person(39) imagines that Person(40) imagines that Person(41) imagines that Person(42) imagines that Person(43) imagines that Person(44) imagines that Person(45) imagines that Person(46) imagines that Person(47) imagines that Person(48) imagines that Person(49) imagines that Person(50) imagines that Person(51) imagines that Person(52) imagines that Person(53) imagines that Person(54) imagines that Person(55) imagines that Person(56) imagines that Person(57) imagines that Person(58) imagines that Person(59) imagines that Person(60) imagines that Person(61) imagines that Person(62) imagines that Person(63) imagines that Person(64) imagines that Person(65) imagines that Person(66) imagines that Person(67) imagines that Person(68) imagines that Person(69) imagines that Person(70) imagines that Person(71) imagines that Person(72) imagines that Person(73) imagines that Person(74) imagines that Person(75) imagines that Person(76) imagines that Person(77) imagines that Person(78) imagines that Person(79) imagines that Person(80) imagines that Person(81) imagines that Person(82) imagines that Person(83) imagines that Person(84) imagines that Person(85) imagines that Person(86) imagines that Person(87) imagines that Person(88) imagines that Person(89) imagines that Person(90) imagines that Person(91) imagines that Person(92) imagines that Person(93) imagines that Person(94) imagines that Person(95) imagines that Person(96) imagines that Person(97) imagines that Person(98) imagines that Person(99) imagines that Person(100) imagines that the Guru sees, if Person([1, 100]) assume that their eyes are non-blue. It contanis 0 pairs of blue eyes.

After the Guru's statement, no one is imagining that hypothetical anymore (and this is common knowledge).

Answer 12

The Guru's information makes the blue-eyed-people special. It is a bit easier to understand if you imagine the Guru saying "those with blue eyes may go".

Then on day 1, you see nobody leaving, so you know nobody knows his own eyecolor, so you can conclude that at least 2 persons must have blue eyes.

Then on day 2, you see nobody leaving, so you know nobody knows his own eyecolor, so you can conclude that at least 3 persons must have blue eyes.

... Then on day 99, you see nobody leaving, so you know nobody knows his own eyecolor, so you can conclude that at least 100 persons must have blue eyes. But if you have blue eyes and you see that there are only 99 other blue-eyed persons, you know you are the lucky #100. So you'll leave at day 100.

If the Guru wasn't necessary, the people with brown eyes could also leave the island sooner or later. But there is no way for them to assure they don't have red eyes, or any other color. If only two colors existed, they could all go if the Guru only said which color should leave first.

Basically, the info given by the Guru is NOT "there is someone here with blue eyes". Everybody knows that already, since everybody sees two blue-eyed persons and everybody knows those two can see each other.

It is also NOT "everybody knows that there is someone here with blue eyes". It actually is "everybody knows, that everybody knows, that everybody knows, ... [repeat 99 times] that someone has blue eyes".

Answer 13

I started writing my definitive explanation for how everyone is actually wrong about the necessity of the Oracle's proclamation and in the process finally explained to myself why, in fact, it's essential.

Possibly not adding anything new to the list of answers (how ironic is that??) I'll throw in my explanation.

This is highly unintuitive, but the way that the eye logic is deduced starts with the accusation that someone has blue eyes. The immediate response to that accusation is "is it me?" (by everyone on the island).

As we know if we reduce this down to 2 people if they both have blue eyes they each say (to themselves) "I also see someone with blue eyes" and wind up sitting there for an extra day.

But their thought process is "what is the other person thinking? - they *know that there's a blue eyed person on the island and they know that I know that there's a blue eyed person on the island and therefore if I'm not moving it must be because they have blue eyes".

So, what happens if you don't have the announcement?

Well, with one and two people it's self evident that looking at no one or one other person offers no useful info.

However, with three people, intuitively you think "everyone MUST see a blue eyed person" but remember the issue isn't what they can see, it's what they can be sure EVERYONE else can see - so assume everyone is a pessimist and expects their own eye color to be non-blue...

A (think her eyes are brown) looks at B and thinks "B sees me (A) with brown eyes and thinks her(B's) eyes are also brown and so A assumes B assumes C is staring at 2 brown eyed people and expects that her own (C's) eyes are ALSO brown. And there's the rub... I was stuck for a while on the idea "but A knows for sure that C can see B's blue eyes!!!"... however, the issue isn't what A knows; The issue is what A knows B knows C knows. And when you walk the chain of deduction, assuming everyone is a pessimist (not wanting to think they have blue eyes) the inevitable conclusion is that every person must deduce that the last person in the he thinks she thinks chain will assume there are NO blue eyed people!

Quite counter intuitively, this progression can work for any number of people, so it doesn't matter if there are 3 or 3 million blue eyed people, it's still entirely logical and rational (actually inevitable) that A will come to the conclusion that person [number of blue eyed people on the island] can reasonably suspect that there are no blue eyed people on the island. And if there are no blue eyed people on the island then there's no place from which to start one's logical countdown.

If the last person in the logical chain has been informed that there is indeed a blue eyed person on the island then either they will leave (seeing no one else with blue eyes) or they will stay (because they themselves see someone else with blue eyes) and the entire deduction process begins.

Answer 14

Does the Guru's statement bring any new information?

The misleading thing here is that you might get tricked into the belief that the statement of the Guru just tells the people on the island that there is someone with blue eyes. But that is nothing new! The people already knew that by looking around.

The statement of the Guru says something deeper. It not only makes the people know that there is someone with blue eyes, it also makes them know that everybody else knows that there is someone with blue eyes.

Even deeper, it makes them know that everybody else knows that everybody else knows that everybody else knows (ad infinitum) that there is someone with blue eyes.

Now that is a strong statement, because the people themselves only knew this up to a certain point!

A small example

For instance suppose that we have 3 blue eyed people, A, B and C, and no Guru. A knows that there is someone with blue eyes. A knows that B knows that there is someone with blue eyes. But A does not know that B knows that C knows that there is someone with blue eyes, because A doesn't know his own eye color. For this to know, A needs the statement of the Guru.

Answer 15

I was able to more or less understand the solution only by imagining that this whole story is happening in Island 100 - our island, and there are another 99 islands in the ocean, each called Island 1, Island 2, Island 3, ..., Island 99, each of them named after the total number of people with blue eyes in them. The total number of people in each island is the same: 200.

None of the islanders knows anything at all about the other islands. Actually, for them the other islands might just be a mental construction in their imagination; but for the sake of our reasoning, let's consider them as real islands. Since the islands do not have any sort of communication between them, Island 100 is exactly the island of the original problem.

• Island 1: 1 blue eyed person, 199 brown eyed people.
• Island 2: 2 blue eyed people, 198 brown eyed people.
• Island 3: 3 blue eyed people, 197 brown eyed people.
• Island 4: 4 blue eyed people, 196 brown eyed people.
• Island 5: 5 blue eyed people, 195 brown eyed people.
• ...
• Island 99: 99 blue eyed people, 101 brown eyed people.
• Island 100: 100 blue eyed people, 100 brown eyed people.

The rules are equal in every island - people will leave when they find out their eye colour.

On a given day, the guru, travelling on a boat, does the same operation in every island.

On each day N, the N blue eyed people from Island N will leave.

The fact that the N-1 blue eyed people seen by any blue eyed observer on any island didn't leave the day before convinces that observer that they are actually in Island N, and not in Island N-1. (The only two possible islands they could be in, since each of them knows that there are either N-1 or N blue-eyed people on their island.)

Answer 16

The solution listed is correct, but it is the solution to a much harder problem than you might think, which is: There are 200 people on an island, where any person can have either blue or non-blue eyes. On Day 0, a Guru announces either that: a) I see at least one pair of blue eyes or b) I see no blue eyes.

Given this single datum, the standard algorithm would solve ANY number of blue eyes, from 0 to 200. Without this single datum, even though you can see N blue eyes (where N is from 0 to 199), you can never be certain what your eye color is, because you would never know if Total Blue Eyes = N or N+1.

Put another way, if you can see N blue eyes, and the guru tells you that Total Blue Eyes == 0 OR that Total Blue Eyes >= 1 on Day 0, you can determine your own eye color after N-1 days (if you have blue eyes) or N days (if you have non-blue eyes) according to the standard algorithm.

If, however, you were ONLY trying to solve the single case where exactly N people have blue eyes, then you can leave without the Guru on Day 0:

• On Day 0, if you see N blue eyes, your eyes are non-blue. Stay.
• On Day 0, if you see N-1 blue eyes, your eyes are blue. Leave tonight.

What is even cooler is that if you are willing to NOT solve any single case, such as "0 people have blue eyes", then you don't need the Guru to start the induction.

• On Day 0, you see N blue eyes, where N>=0. On day N, if no one has left yet, leave knowing you have blue eyes. If anyone ever leaves before you get a chance, you don't have blue eyes, leave the very next day.

Which is pretty cool considering that if odds of having blue eyes were, say 50%, then the odds of all having blue eyes = 1/2 ^ 200 ~ 10^-61. Pretty tolerable odds if you were lacking a Guru!

It would be cool to see a general algorithm that could be tuned with a variable cost for "days spent calculating" versus a cost for "getting the answer wrong". The default question basically assumes "cost of days spent calculating" == 0 or "cost of getting the answer wrong" == infinity.

Answer 17

If the oracle said nothing and there was one person, that person could never know if anyone at all had blue eyes, so could not leave.

If there were two, neither would know in the first day whether the other was the only one and should leave alone, or whether they themselves were the second, so neither can leave. Everyone who can see the two knows that those two should not leave.

On the second day, you cannot know if the other should have left yesterday alone or whether you and he should leave today with you. You know he should not leave tomorrow, as there are definitely only one (him) or two (him and you) but since you know he is only here today because he was as clueless as you on day one, you can't determine your own eye colour from this.

On the third day, the two of you know that the other should have left on one of the previous day's, but still do not know which. Everybody else has the same dilemma as you did on the third - you don't know if the two are waiting for you, or simply couldn't work it out the day before. Again there are either two who missed their day yesterday, or three including you.

By the 4th day, everyone knows they've all missed their chance, because they can only see one or two sets of blue, and their own (unknown) would make two or three

Answer 18

Accepted answer induces from 4 blue eyed people that without the Guru nobody can leave the island.

Although an old topic, I would like to add a bit of explanation.

Some answers postulate that the key information provided by the Guru is the fact that from now on, everybody knows that everybody knows that some people are blue eyed on the island.

Explain how this is news if there were say 100 blue eyed people on the island?? Some mistakenly apply the reasoning that among 100 blue eyed, someone with blue eyes only sees 99 and thinks that the other blue eyed may see only 98 who thinks there may be only 97, and so on down to 1.

The issue here is that people don't think in turn, but simultaneously. If there are 100 people with blue eyes, all blue eyed people see 99 others and know for a fact that everybody else sees at least 98.

So why on earth do we need the Guru??

If there are 100 blue eyed people on the island, for any person with blue eyes (who only sees 99 blue eyed people), they need to know it is possible for 99 to leave the island (i.e. if 99 didn't leave yesterday, it must mean that I have blue eyes too). However, for 99 people to leave the island, it needs to be possible for 98. And so on until 1.
So while for any N>3 blue eyed people everyone knows that everyone knows that the island has some blue eyed people, it is necessary to also know that people would be theoretically able to leave the island for any N even if <=3. And by induction this is only possible if 1 person is able to leave the island.

In conclusion
For any N>3 the Guru didn't provide any new information as to the presence of blue eyed people on the island.
However, the Guru's declaration makes it theoretically possible for N=1 to leave the island, which is necessary for N=2, and so on for any N.
The Guru's declaration actually triggers a chain of events or non events (people leaving or staying) that in itself bears an information that is critical for the strategy to take place.

I think some other answers and comments point in that direction, I hope mine does a slightly better job at clarifying the importance of the Guru's declaration.

Answer 19

With all this logic and chain of thought, one basic but key part of the puzzle is forgotten. The islanders need to know the color of their eyes to leave the island. At any point a blue-eyed person can see that there are 99 blue-eyed people and 100 brown-eyed people. And on the 100th day, when 99 blue-eyed people have not left the island, the islander has still not concluded the color of his eyes (maybe blue, brown or any other color). But, had he known there was at least one blue-eyed person on the island (as proclaimed by the guru), he could have concluded that his eyes had to be blue on the 100th day. When no one leaves on the 100th day as well(since no one can determine the color of their eyes yet), they are left with same information on the 101st day as they had on 1st day, i.e, a blue-eyed person can see 99 blue-eyed people and 100 brown-eyed people. Since all islanders are perfect logicians, no islander can come to a conclusion without the guru's proclamation.

Answer 20

Another side of this, instead of doing the induction from 1 person with blue eyes, it may be more intuitive to instead consider induction from the guru's statement.

Before any announcement, all brown-eyed people know that there are either 100 or 101 blue-eyed people on the island, and all blue-eyed people know that there are either 99 or 100 blue-eyed people on the island.

Consider the case that instead of saying she sees someone with blue eyes, she instead said: "I see at least 100 people with blue eyes".

Brown-eyed people learn nothing new from this. Blue-eyed people, who only see 99 others, immediately learn their own eyes must be blue, so can leave on the first night.

Next consider the case where the guru states "I see at least 99 people with blue eyes".

Now nobody learns anything new initially about their own eye colour. The brown-eyed people, however, had a 1 day information advantage. They also know that nobody will be leaving tonight, as they know that there are not exactly 99 blue-eyed people because they see 100.

After the first night, when all the blue-eyed people are still there, they all simultaneously learn that there are at least 100 blue-eyed people, the same information that the brown-eyed people had the day before, and the same as if the guru had delayed the announcement by a day, but then announced seeing 100.

Similarly, if the guru had stated "I see at least 98 people with blue eyes", everyone on the island now knows nobody will leave the first night, as they all see at least 99.

After the first night, the islanders all know that everyone is in the same position as if the guru had just announced "I see at least 99 people with blue eyes". Blue-eyed people now wait to see if the 99 other blue eyed people leave on the second night. Brown-eyed people already know nobody will leave on the second night.

Extending this to $N$, if the guru states "I see at least $N$ people with blue eyes", where $N < 99$, blue-eyed people initially know that nobody will leave for at least $99-N$ nights, and brown-eyed people initially know that nobody will leave for $100-N$ nights. In each case the person knows that nobody will leave for a number of nights equal to the difference between the guru's announcement of number of blue-eyed people, and the number of blue-eyed people they see.

After 1 night, everyone knows that nobody left (which for $N<99$ is not a surprise to anyone). This makes the following day equivalent to a day on which the guru had announced "I see $N+1$ people with blue eyes".

---

Returning to what the guru actually said "I see at least 1 person someone with blue eyes", everyone knows that:

• Nobody will leave the island tonight, or tomorrow night, or indeed for many more weeks.
• Tomorrow the situation will be the same as if the guru had, 1 day later, announced "I see at least 2 people with blue eyes"
• The day after tomorrow, the situation will be the same as if the guru had, 2 days later, announced "I see at least 3 people with blue eyes".

...

• After 98 nights the situation will be the same as if the guru had, 98 days later, announced "I see at least 99 people with blue eyes". The blue-eyed people will have marked this date on their calendar as the date on which they expect to see all the blue-eyed people leave.
• After 99 nights when the blue-eyed people did NOT leave, each blue-eyed person now knows that there are at least 100 blue-eyed people; the 99 they can each see, and by implication themselves. The brown-eyed people, who see 100 blue-eyed people would similarly have marked their calendar with this as they date they expect all the blue-eyed people to leave.
• After 100 days, the blue-eyed people have all left. The remaining brown-eyed people have a strong suspicion they all have brown eyes, but cannot know for sure that they are not the only other green-eyed person apart from the guru, or that they don't have another eye colour entirely (grey, red, purple) that they have never seen in anyone else.

---

A side-observation - if the guru states "I see someone with blue eyes and someone with brown eyes", everyone will be able to leave - each person would diarise two dates - the date on which all the blue-eyed people will leave unless their own eyes are blue, and the date on which all the brown-eyed people will leave unless their own eyes are brown. Only those with a colour specifically mentioned by the guru may leave.

On a similar island with 10 blue-eyed people, 20 brown-eyed and 20 green-eyed, and one grey-eyed:

• an announcement like "eyes of the following colours are present in our population: blue, brown, green, grey" (possibly amended if there are logical loopholes) would lead to the grey-eyed person leaving that very night, the blue-eyed people all leaving on the 10th night, and everyone else leaving on the 20th night.
• an announcement like "I can see someone with [colour] eyes" allows only those with that eye colour to leave, and only after sufficient nights have elapsed so that everyone with that eye colour expected everyone else with that eye colour to have left the previous night.

Answer 21

Not sure if this is the right answer but my wife and I thought everyone will leave the island the 201st day and here's why:

We assumed the Guru would either say " I see a blue eyed person" or " I see a brown eyed person" each day (alternating or randomly, doesnt matter). Since she's a logician too, she would accurately total up the number of brown and blue eyes on day#200. Let's say a person x has brown eyes, she will realize by day # 200 what her eye color is as she knows by now that there are 100 blue colored eyes and 99 brown eyed people. This logic will apply to every member too.

Very interested to see what the geniuses on this forum have to say!

Answer 22

Sorry, but there's a flaw in the riddle's question that is badly waved away with:

"Before you email me to argue or question: This solution is correct. My explanation may not be the clearest, and it's very difficult to wrap your head around (at least, it was for me), but the facts of it are accurate. I've talked the problem over with many logic/math professors, worked through it with students, and analyzed from a number of different angles. The answer is correct and proven, even if my explanations aren't as clear as they could be."

How did the islanders come into existance? When and how did they decide, they want to leave? Do they think alike and do they know so?

If they came to be on the island and/or decide to leave, all of them at the same time, they can all leave at the 100th night, because they figured out the even distribution (100 blue, 100 brown eyes) by the same argument as they do with the oracles pronouncement. The situation becomes stable only with some sort of non-beginning. The islanders were always there and didn't know, when the others would've started to count days. This non-beginning is at best implicit in the question.

They must also be thinking alike and know it. Plus they must be thinking in a certain way to come to this solution. The best way to argue this point is the numbering introduced by Ben Millwood: Person 1 might assume that there are only 99 blue eyed people. This is equivalent with the assumption that people 2-100 see 98 blue eyed people. Hence everyone can discard the possibility that there is someone seeing less than 98 blue eyed people. Since they discarded this 98 they can alos skip the nights to count them off. Everyone who sees 98 same colored eyes assembles to leave in night 1. Everyone who sees 99 same colored eyes assembles to leave in night 2. This solution is also valid, logically derivable and requires only another way of thinking alike and knowing the others do so, too. So to make the answer unique you would have to formulate if they want to leave urgently or want to know their own eye color urgently but stay as long as possible.

I'm not saying the solution is incorrect. I'm just saying it's not the only correct solution, because of implicit assumptions (thinking alike) and missing requirements (leave soon or stay long).

Long story short: You only need the oracle, if there is no other starting point for counting off the nights.

Answer 23

I would like to add an answer to one of the bonus questions:

Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

Let's break this down into logical reasoning from the perspective of a blue-eyed and a brown eyed person.

Blue-eyed person perspective

I can see 99 pairs of blue.

If I'm blue: blues can see 99 pairs, browns can see 100 pairs.

If I'm brown: blues can see 98 pairs, browns can see 99 pairs.

Brown-eyed person perspective

I can see 100 pairs of blue.

If I'm blue: blues can see 100 pairs, browns can see 101 pairs

If I'm brown: blues can see 99 pairs, browns can see 100 pairs.

All of this is immediately inferred by everyone else. Then we go down one more layer of reasoning.

Perspective of blue-eyed person seen by another blue-eyed person, who thinks they might be brown

I can see 98 pairs of blue.

If I'm blue: blues can see 98 pairs, browns can see 99 pairs.

If I'm brown: blues can see 97 pairs, browns can see 98 pairs.

And one more layer of inference...

Perspective of the hypothetical person who can only see 97 pairs

I can see 97 pairs of blue.

If I'm blue: blues can see 97 pairs, browns can see 98 pairs.

If I'm brown: blues can see 96 pairs, browns can see 97 pairs.

---

You get the idea. It seems absurd initially to wait the full 100 days, but because we must consider the full chain of inference for everyone involved, we eventually get down to the same recursive argument and are thus forced to wait for the full 100 days. Everyone knows that no one could possibly see less than 98 pairs of blue, but they need the full 100 days to figure out if they personally are blue-eyed or brown-eyed.

Answer 24

I got somewhat similar answer, but logically easier and relying on a "trick". When the Oracle is about to come all people come to the meeting unless they see that there is a blue eyed already present there. So: 1)If there are no people one goes to the meeting 1.a) if he sees anyone blue eyed coming, then he is brown eyed 1.b) if no one else comes then he is blue-eyed - the oracle will anounce at least him or anybody else blue-eyed and he can't be sure who the oracle is talking about. But if no one else comes, then he is blue eyed and leaves, knowing that. So all blue eyed will understand they are such in the steps mentioned and the rest that they will stay there forever :) The main reasoning is - "I won't go to the meeting if I see someone blue-eyed there, because if I'm also blue eyed we won't be able to make the distinction or at least we should fallback to the other solution" "Wait and see" action is present in both solutions, while in mine the oracle is there only for motivation for the meeting.

Answer 25

It seems that the oracle just tells everybody something they already know, so they seemingly shouldn't be able to deduce anything new from that.

Another way to resolve this is to consider which of the below statements are true:

B1: At least one native has blue eyes.
B2: Every native knows B1 is true.
B3: Every native knows B2 is true.
...
B_(k+1): Every native knows B_k is true.

And the answer is that, for n blue-eyed natives, statements B_1 through B_n will be true. And while B_n is true, only the non-blue-eyed natives will know it is true.

When the oracle made the statement, it's not just that everybody heard the statement, so they know B1 is true. Everybody knows that everybody was there and heard the oracle's statement, so everybody knows B2 is true. The fact that the statement was made in public makes all the B_k statements true, and B_n is something that some of the natives didn't already know was true.

Answer 26

The Guru's statement provides an arbitrary day that synchronizes everyone's starting point for counting days for blue-eyed people. She really can say anything she wants that will perform this function.

Taking this by cases works for any number of people, and only requires up to 4 days, because it accounts for the logical implications of the fact that the population of blue-eyed people cannot be fewer than the number of blue-eyed people that a blue-eyed person can see. Let me explain:

N = how many blue-eyed people there are. X = how many blue-eyed people I can see.

X = 0, N = 0

There are no blue-eyed people, so the Guru cannot honestly say that there are.

X = 0, N = 1

If I cannot see any blue-eyed people, but the Guru indicates that there are, then I know that I must be the only blue-eyed person, so I will leave the first day.

X = 1, N = 1 or 2

If I can see one person with blue eyes, then there are either 1 or 2 blue-eyed people, depending on whether I myself have blue eyes.

If I do not have blue eyes, then the blue-eyed person cannot see any other blue-eyed people and will know by the Guru's declaration that he himself is the only person with blue eyes, and so will leave the first day. If the blue-eyed person leaves the first day, then I must not have blue eyes.

If I do have blue eyes, then the other blue-eyed person can see only one other blue-eyed person and will expect me to leave the first day if he does not have blue eyes. But once neither he nor I leave the first day, we will know that we both have blue eyes and we will leave the second day.

X = 2, N = 2 or 3

If I can see two people with blue eyes, then there are either 2 or 3 people with blue eyes, depending on whether I myself have blue eyes.

If I do not have blue eyes, then any blue-eyed person (A) can see only 1 other blue-eyed person and knows that there are either 1 or 2 blue-eyed people. Person A also knows that the other blue-eyed person (B) can see either 0 or 1 blue-eyed people, so A knows that B knows that there are either (0 or 1) or (1 or 2) blue-eyed people. But A knows for a fact that there exists at least 1 person with blue eyes, so he can discount any situations where fewer than 1 blue-eyed person exist.

If I do have blue eyes, then another blue-eyed person can also see only 2 blue-eyed people and knows that there are either 2 or 3 blue-eyed people.

The actual options from any point of view include 1, 2, or 3 people with blue eyes. But since I can see 2 with blue eyes, I know that there cannot be only 1, so I can discount the N=1 situation.

On the first day, those who can see only 1 blue-eyed person will expect them to leave. But because I know that there are at least 2, I expect no one to leave.

On the second day, those who can see 1 blue-eyed person will have realized that they also have blue eyes and will leave. We who can see 2 will know that the N=1 situation can be discounted, but cannot discount the N=2 unless no one leaves the second day.

If no one leaves the second day, then I will know that I must also have blue eyes, and we will all leave on the third day.

X = 3, N = 3 or 4

If I can see three people with blue eyes, then there are either 3 or 4 people with blue eyes, depending on whether I myself have blue eyes.

If I do not have blue eyes, then any blue-eyed person (A) can see only 2 other blue-eyed people and knows that there are either 2 or 3 blue-eyed people. Person A also knows that a blue-eyed person (B) can see either 1 or 2 blue-eyed people, so A knows that B knows that there are either (1 or 2) or (2 or 3) blue-eyed people. But A knows for a fact that there exists at least 2 people with blue eyes, so he can discount any situations where fewer than 2 blue-eyed people exist.

If I do have blue eyes, then another blue-eyed person can also see only 3 blue-eyed people and knows that there are either 3 or 4 blue-eyed people.

The options from any point of view include 2, 3, or 4 people with blue eyes. As with the previous situation, everyone knows that there are at least 2 blue-eyed people, so I can dismiss the N=1 case.

On the first day, no one expects anyone to leave. I know that a blue-eyed person A (who knows that N=2 or N=3) knows that a blue-eyed person B (who knows that N=1 or N=2) doesn't know whether B should leave today.

On the second day, no one expects anyone to leave. I know that A knows that if B can see 1, then B will realize that he has blue eyes and leave today.

On the third day, I know that A would learn that B can also see 2 blue-eyed people, so A must have blue eyes, and A would leave today.

On the fourth day, I will confirm that A can also see 3 blue-eyed people, which means I must also have blue eyes, so I will leave today.

Those who can see 4 blue-eyed people will know that they themselves do not have blue eyes on the fifth day.

X = 4, N = 4 or 5

If I can see four people with blue eyes, then there are either 4 or 5 people with blue eyes, depending on whether I myself have blue eyes.

If I do not have blue eyes, then any blue-eyed person (A) can see only 3 other blue-eyed people and knows that there are either 3 or 4 blue-eyed people. Person A also knows that a blue-eyed person (B) can see either 2 or 3 blue-eyed people, so A knows that B knows that there are either (2 or 3) or (3 or 4) blue-eyed people. But A knows for a fact that there exists at least 3 people with blue eyes, so he can discount any situations where fewer than 3 blue-eyed people exist.

If I do have blue eyes, then another blue-eyed person can also see only 4 blue-eyed people and knows that there are either 4 or 5 blue-eyed people.

The options from any point of view include 3, 4, or 5 people with blue eyes. As with the previous situation, everyone knows that there are at least 3 blue-eyed people, so I can dismiss the N=1 and N=2 cases.

On the first day, no one expects anyone to leave. I know that a blue-eyed person A (who knows that N=3 or N=4) knows that a blue-eyed person B (who knows that N=2 or N=3) doesn't know whether B should leave today.

On the second day, no one expects anyone to leave. I know that A knows that if B can see 2, then B will realize that he has blue eyes and leave today.

On the third day, I know that A would learn that B can also see 3 blue-eyed people, so A must have blue eyes, and A would leave today.

On the fourth day, I will confirm that A can also see 4 blue-eyed people, which means I must also have blue eyes, so I will leave today.

Those who can see 5 blue-eyed people will know that they do not have blue eyes on the fifth day.

General case: X > 3

If I can see X blue-eyed people, then there are either X or X+1 blue-eyed people, depending on whether I myself also have blue eyes.

If I do not have blue eyes, then any blue-eyed person (A) can see only X-1 blue-eyed people and knows that there are either X-1 or X blue-eyed people. This person also knows that any (other) blue-eyed person (B) can see either X-2 or X-1 blue-eyed people and knows that there are either (X-2 or X-1) or (X-1 or X) blue-eyed people.

If I do have blue eyes, then any other blue-eyed person can also see only X blue-eyed people and also knows that there are either X or X+1 blue-eyed people.

I know that the full list of options from some blue-eyed person's point of view are X-2, X-1, X, or X+1. But I know that X-2 and X-1 are not actual options, because of my own knowledge that there are either X or X+1 blue-eyed people.

I also know that some blue-eyed person's knowledge of the options from his point of view, relative to my point of view, are X-2, X-1, or X. But he knows that X-2 is not an actual option, because of his own knowledge that there are either X-1 or X blue-eyed people.

If there were X-2 blue-eyed people, they should leave on the first day, but since I know there aren't that many, I do not expect anyone to do anything then. I know that a blue-eyed person A knows that a blue-eyed person B has to wait for no one to leave for B to be convinced that B has blue eyes, so A expects no one to leave, either.

If there were X-1 blue-eyed people, they should leave on the second day, but I know there aren't that many, so I do not expect anyone to do anything then, either. I also know that a blue-eyed person A knows that if a blue-eyed person B has been convinced that B has blue eyes, then B will leave today, so A has to wait to see whether B leaves before A will be convinced that A has blue eyes. Thus A will wait through the second day.

If there are X blue-eyed people, they should leave on the third day, and if they do, then I know that I do not have blue eyes. I know that if a blue-eyed person A has become convinced that A has blue eyes, then he would leave today.

If there are X+1 blue-eyed people, then no one will have left on the third day, so I will know that I have blue eyes, and I will leave the fourth day. I know that if a blue-eyed person A has not left yesterday, it must be because he can also see X blue-eyed people, which means that I must also have blue eyes.

Anyone who has another eye color will know that they do not have blue eyes by the fifth day, after all the blue-eyed people have left.

Without the Guru's synchronization, everyone's "day-counter" will be unknown to anyone else, so no one can know when to expect anyone else to leave.