Friday Fun: Classic Logic Puzzle

[albionmoonlight]

The Blue Eyed Islanders

n.b.: This is a logic puzzle, not a simulation of real life. In the real world, an island like this would probably not exist. In the real world, people would probably invent mirrors. In the real world, people would probably talk about their eye color. In the real world, the logic of this logic puzzle breaks down. This is not the real world. This is a logic puzzle. Accept its axioms and solve it on its terms. Thank you. Oh, and if you have seen this before, it might make it more fun if you let others try to puzzle through it.

The Setup:

Anyway, On an island, there are a certain number of people who have blue eyes, and the rest of the people have green eyes. There is at least one blue-eyed person on the island. If a person ever knows with 100% certainty that she has blue eyes, she must leave the island at dawn the next day. If she does not know with 100% certainty that she has blue eyes, then she stays on the island. Each person can see every other persons' eye color, there are no mirrors, and there is no discussion of eye color. At some point, an outsider comes to the island and makes the following public announcement, heard and understood by all people on the island: "at least one of you has blue eyes."

The Problem:

Assuming each and every person on the island
(1) Will leave at the dawn following the day that he obtains 100% certainity that he has blue eyes;
(2) Will stay if he does not have 100% certainity that he has blue eyes;
(3) Is completely truthful;
(4) Is perfectly logical; and
(5) Knows that everyone else on the island follows (1)-(4).

Then what is the eventual outcome?

For purposes of discussing a solution, it might make sense to use a common variable (X) to represent the number of people on the island with blue eyes.

[albionmoonlight]

The solution

http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29#Example

[st.cronin]

there is no discussion of eye color.

I'm not sure I understand this.

[Eaglesfan27]

I'm not sure I understand this.

Same here. If they never discuss eye color, then it would seem that there would never be 100% certainty that they have blue eyes or don't have blue eyes and the status quo would remain. Although, I'm sure there is something I'm overlooking and there is more to it than that.

[albionmoonlight]

I'm not sure I understand this.

No one mentions eye color. No one asks what their eye color is. And no one tells anyone else what their eye color is.

[Eaglesfan27]

Ahh, I just figured out the flaw in my logic.

[st.cronin]

No one mentions eye color. No one asks what their eye color is. And no one tells anyone else what their eye color is.

Then, why would anybody leave the island? The only way I see that happening is if only 1 person has blue eyes. That person, by seeing everybody else's green eyes, would eventually realize that they were the person the outsider was talking about. But if there are more than one person with blue eyes, and what you say is correct, why would anybody ever believe THEY had blue eyes?

[st.cronin]

The part that confuses me is (3) is completely truthful. Truthful about what?

[spleen1015]

Then, why would anybody leave the island? The only way I see that happening is if only 1 person has blue eyes. That person, by seeing everybody else's green eyes, would eventually realize that they were the person the outsider was talking about. But if there are more than one person with blue eyes, and what you say is correct, why would anybody ever believe THEY had blue eyes?

If they're is only 1 person, then they would see that everyone else has blues eyes and leave the first dawn. That is easy. The problem is if there is more than 1.

If jbmagic and HornsManiac had blue eyes, each would know that the other has blue eyes. If jbmagic is the only person that Horns sees with blue eyes, yet he doesn't leave on that first dawn, then Horns has to know that he has blue eyes.

This just increases with more folks. Let's say that jb, horns, and skydog all have blue eyes. jb and horns know Skydog has them. Horns and skydog knows jb has them. jb and skydog know that Horns have them. If no one leaves on the first dawn and no one leaves on the 2nd, the they each should know that they have blue eyes.

If you see X people with blue eyes and no one leaves in X dawns, then you know you have blue eyes.

[st.cronin]

If they're is only 1 person, then they would see that everyone else has blues eyes and leave the first dawn. That is easy. The problem is if there is more than 1.

If jbmagic and HornsManiac had blue eyes, each would know that the other has blue eyes. If jbmagic is the only person that Horns sees with blue eyes, yet he doesn't leave on that first dawn, then Horns has to know that he has blue eyes.

This just increases with more folks. Let's say that jb, horns, and skydog all have blue eyes. jb and horns know Skydog has them. Horns and skydog knows jb has them. jb and skydog know that Horns have them. If no one leaves on the first dawn and no one leaves on the 2nd, the they each should know that they have blue eyes.

If you see X people with blue eyes and no one leaves in X dawns, then you know you have blue eyes.

Knowing that somebody has blue eyes is not the same thing as knowing that somebody knows that they have blue eyes. Maybe I'm overthinking it, but taking your example:

If me and one other person has blue eyes, when do I leave the island? At what point do I logically know that I have blue eyes? What if there are 9 people with blue eyes, and none of them leave the next day?

[Warhammer]

Actually I think there is a flaw in the logic.

If only one person has blue eyes, and they look at everyone else and see green eyes, than everyone of those people will leave the island believing that they alone have the blue eyes.

If more than one person has blue eyes, no one will leave the island because there is no discussion of who has the blue eyes. All blue eyed people will see at least one other person with blue eyes and thus they will stay on the island waiting for the person they see with blue eyes to leave.

The key here is that there is no discussion. The important parts of the puzzle are items 1, 2, and 4. No one will have absolute certainty unless they see everyone else has green eyes. At that point, assuming the statement is true, they will then leave. Once more than one person has blue eyes, there is not a 100% certainty regarding what a person's own eye color is. Therefore, no one will leave because there is not 100% certainty that any individual blue eyed person has blue eyes.

[st.cronin]

Actually I think there is a flaw in the logic.

If only one person has blue eyes, and they look at everyone else and see green eyes, than everyone of those people will leave the island believing that they alone have the blue eyes.

If more than one person has blue eyes, no one will leave the island because there is no discussion of who has the blue eyes. All blue eyed people will see at least one other person with blue eyes and thus they will stay on the island waiting for the person they see with blue eyes to leave.

The key here is that there is no discussion. The important parts of the puzzle are items 1, 2, and 4. No one will have absolute certainty unless they see everyone else has green eyes. At that point, assuming the statement is true, they will then leave. Once more than one person has blue eyes, there is not a 100% certainty regarding what a person's own eye color is. Therefore, no one will leave because there is not 100% certainty that any individual blue eyed person has blue eyes.

That's how I see it, exactly.

[st.cronin]

But if they are all perfectly logical, then they will determine they have blue eyes. They can have absolute certainty once they realize, on the nth day, that they can see n-1 people with blue eyes, that they too have blue eyes.

You will have to explain that logic to me, because I don't see it. Somebody says "at least one of you as blue eyes." I see x number of blue eyed people. Why should I ever assume that I have blue eyes?

[Warhammer]

But if they are all perfectly logical, then they will determine they have blue eyes. They can have absolute certainty once they realize, on the nth day, that they can see n-1 people with blue eyes, that they too have blue eyes.

No, only if the same guy comes back day after day and tells them if there is a person with blue eyes still on the island.

Remember the original part of the puzzle:

At some point, an outsider comes to the island and makes the following public announcement, heard and understood by all people on the island: "at least one of you has blue eyes."


This is not a daily occurance, it only happens once. Remember, no one knows for sure how many people with blue eyes are on the island. If they knew, they would be able to figure out that if they saw N-1 people with blue eyes they must have blue eyes. But, all they know is that at least one person has blue eyes. Since there is uncertainty as to what N is, then as long as at least one other person has blue eyes, it is uncertain what color their own eyes are. The only time anyone can be certain what color their eyes are is when no one else has blue eyes, then they can be certain that they alone have blue eyes.

[Warhammer]

You will have to explain that logic to me, because I don't see it. Somebody says "at least one of you as blue eyes." I see x number of blue eyed people. Why should I ever assume that I have blue eyes?

EXACTLY! At that point, you cannot be certain that you have blue eyes.

[BrianD]

Actually I think there is a flaw in the logic.

If only one person has blue eyes, and they look at everyone else and see green eyes, than everyone of those people will leave the island believing that they alone have the blue eyes.

Can you explain this better? If only one person has blue eyes and he can't fine anyone else on the island with blue eyes, he will know he is the one. Everyone else with green eyes will be able to see the blue eyed guy and they will know that they have green which will keep them on the island.

If more than one person has blue eyes, no one will leave the island because there is no discussion of who has the blue eyes. All blue eyed people will see at least one other person with blue eyes and thus they will stay on the island waiting for the person they see with blue eyes to leave.

The key here is that there is no discussion. The important parts of the puzzle are items 1, 2, and 4. No one will have absolute certainty unless they see everyone else has green eyes. At that point, assuming the statement is true, they will then leave. Once more than one person has blue eyes, there is not a 100% certainty regarding what a person's own eye color is. Therefore, no one will leave because there is not 100% certainty that any individual blue eyed person has blue eyes.

Discussion isn't needed. Since everyone is perfectly logical, the single blue-eyed guy would figure it out and leave on the first day. If I have blue eyes and I only see one blue eyed person, I would expect that guy's perfect logic to have him gone on day 1. If he isn't gone (knowing his perfect logic), I have to know that there is a second blue-eyed person...and since I have looked at everyone and didn't see him...it must be me. The other guy would use the same logic I did, and we would both figure it out on day 2.

Same thing goes with 3 people. I see two blue-eyed people and know that neither will figure it out on day 1, but both should figure it out on day 2. If neither figures it out on day 2, there must be a third person...which I can see is nobody else so it must be me. Everyone will figure it out on day 3.

And so on.

[albionmoonlight]

The fact about truthfulness was in the original puzzle. It is there really just to stop anyone from saying "Well, person Y might just buy some sunglasses and never leave even if he knows he has blue eyes."

People seem to be debating between two choices here.

Let's say two people on the island have blue eyes. Joe and Dave. The guy comes to the island and says his piece. Joe thinks "Ha! Dave has to leave tomorrow because he will know that he must be the blue eyed person!"

What goes through Joe's head the next morning when he realizes that Dave didn't leave?

[BrianD]

It is also a necessary factor that everybody knows everybody on the island...or at least knows that there aren't people the haven't seen yet. People have to understand that they have seen everyone.

[albionmoonlight]

dola--

BrianD got it.

You can look at the spolier link in the second post for more discussion.

Feel free to keep discussing it, but I really have nothing new to offer that Brian has not presented. I think that he is right.

[albionmoonlight]

It is also a necessary factor that everybody knows everybody on the island...or at least knows that there aren't people the haven't seen yet. People have to understand that they have seen everyone.

Good point. I should have made that clear in the original post.

[Warhammer]

I get what everyone is saying...

On day 3, if no one leaves, then the assumption is that more than one person has blue eyes. If they see at least two blue eyed people, then you go to the next day, etc. Once it is one day greater than the number of blue eyed people you see, you realize that you have blue eyes and leave.

I made the mistake of assuming this was a one day thing, not that you would track this for days. I would figure that after 5 days or so, everyone on the island would kill and eat those with blue eyes.

[BrianD]

This sounds like a good place for an inductive proof. The x=1 situation is pretty easy to see, but it is the x>1 that is more difficult...unless you can step through x=2 and x=3 and see the pattern.

[BrianD]

The interesting thing about this puzzle (and possibly the tricky part) is that there is only one day when people will leave the island. Everyone will leave at the same time.

[BrianD]

As an aside, is it a necessary condition that an outsider inform the island that at least 1 person has blue eyes? It is necessary if there is only 1 person, but is it necessary if there are more than one? Can't use an inductive proof to say the outsider isn't necessary since it doesn't work when x=1. Thoughts?

[spleen1015]

If you see X people with blue eyes and no one leaves in X dawns, then you know you have blue eyes.

Doesn't get any simpler than this.