Logic puzzle

[Mahone]

The answer to this puzzle is interesting in that it is quite simple yet until you read it, you probably wouldn't think of it in a million years. Neither me, my brother or work colleagues could work it out by ourselves.

The puzzle is at follows:

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."

Try and figure it out before you look at the answer, which can be found here.

[DigitalShadow]

The answer to this puzzle is interesting in that it is quite simple yet until you read it, you probably wouldn't think of it in a million years. Neither me, my brother or work colleagues could work it out by ourselves.

The puzzle is at follows:

Try and figure it out before you look at the answer, which can be found here.

Yeah, I saw that on the XKCD blag a while ago. Unfortunately I'm not patient enough; I thought about it for a little while and then looked up the answer because it was bugging me.

[Vort]

The answer to this puzzle is interesting in that it is quite simple yet until you read it, you probably wouldn't think of it in a million years. Neither me, my brother or work colleagues could work it out by ourselves.

The puzzle is at follows:

Try and figure it out before you look at the answer, which can be found here.

I haven't looked at the answer yet. Here's my reasoning:

***** SPOILER SPOILER SPOILER SPOILER SPOILER ******

***** SPOILER SPOILER SPOILER SPOILER SPOILER ******

***** SPOILER SPOILER SPOILER SPOILER SPOILER ******

Assume that this situation begins at the moment the Guru speaks; that is, no one has been seeing other people or counting days until that moment.

Suppose there were only one blue-eyed person on the island. Since he would not see any blue-eyed people, he would immediately know that he himself must have blue eyes, and would leave the island that same night (first night).

Suppose there were two blue-eyed people on the island. Each would see the other and know there was at least one blue-eyed person (not counting the possibility of himself or herself). If that other person saw no blue-eyed people, then the situation would be as above; that person would immediately know his eye color and would leave that night. So each blue-eyed person would watch the other to see if s/he left that night. When the other person did not leave that night, they each would know that they both had blue eyes, and would therefore leave the following night (second night).

Following this logic, we see that for N blue-eyed persons on the island, they will all deduce their eye color and leave after N nights. Therefore, all the blue-eyed people will leave the island after 100 nights, and all the brown-eyed people will leave the island the following night (unless they see the hundred blue-eyed people leaving the island, immediately deduce that all the rest are brown-eyed, and then go join them on the ferry).

[DigitalShadow]

SPOILER

It's too bad there isn't a spoiler tag in this forum. Kudos on your reasoning skills though.

[Mahone]

I haven't looked at the answer yet. Here's my reasoning:

***** SPOILER SPOILER SPOILER SPOILER SPOILER ******

***** SPOILER SPOILER SPOILER SPOILER SPOILER ******

***** SPOILER SPOILER SPOILER SPOILER SPOILER ******

Assume that this situation begins at the moment the Guru speaks; that is, no one has been seeing other people or counting days until that moment.

Suppose there were only one blue-eyed person on the island. Since he would not see any blue-eyed people, he would immediately know that he himself must have blue eyes, and would leave the island that same night (first night).

Suppose there were two blue-eyed people on the island. Each would see the other and know there was at least one blue-eyed person (not counting the possibility of himself or herself). If that other person saw no blue-eyed people, then the situation would be as above; that person would immediately know his eye color and would leave that night. So each blue-eyed person would watch the other to see if s/he left that night. When the other person did not leave that night, they each would know that they both had blue eyes, and would therefore leave the following night (second night).

Following this logic, we see that for N blue-eyed persons on the island, they will all deduce their eye color and leave after N nights. Therefore, all the blue-eyed people will leave the island after 100 nights, and all the brown-eyed people will leave the island the following night (unless they see the hundred blue-eyed people leaving the island, immediately deduce that all the rest are brown-eyed, and then go join them on the ferry).

Well done, you are the first person I have come across to have worked it out without looking at the answer. Though your bit at the end about the brown eyed people leaving is incorrect because they do not know that there is only blue and brown eyed people (and one green eyed) on the island, by this I mean are far each person is aware, he/she has red eyes and the rest have brown/blue/green.

Edited June 5, 2009 by Mahone

[pam]

Now how do we know he didn't REALLY look at the answer and just want us to think him so smart? hahahaha

[dazed-and-confused]

how do we know pam really wrote that response..............how do we know i'm really dazed-and-confused......................how do you know you are actually reading this right now..........or now...........or............................................NOW...........................i'm tired.

[pam]

dazed-and-confused are you feeling a little dazed and confused right now?

[beefche]

It doesn't bode well when I don't even understand the premise....

[bmy-]

It's much easier to figure out if you've taken higher level maths. The key to the entire puzzle are the words 'perfect logicians'.

I failed the first time

[MarginOfError]

I, for some reason, interpreted the problem as though one person left at a time...that really dampened my chances.

However, now that I think about Vort's thing about all the brown eyed people leaving and then Mahone's rebuttal about the green eyes, it makes me question the whole solution. In the presence of a third color, and on the assumption that the inhabitants did not know that there was only one person with that third color, wouldn't that mean the inhabitants never leave the island? For example, after 101 days, all of the non-brown-eyed inhabitants would know that they didn't have brown eyes, but they still wouldn't know if their eyes were green or if they were blue. Am I correct in thinking that this problem only works in the presence of exactly two eye colors?

Of course, the problem could still work if they knew that exactly one person had green eyes, but then they would all know who that is, and the Guru would have left long ago and all the inhabitants would still be on the island and starving because the Guru abandoned them instead of teaching them how to head hunt.

[Mahone]

I, for some reason, interpreted the problem as though one person left at a time...that really dampened my chances.

However, now that I think about Vort's thing about all the brown eyed people leaving and then Mahone's rebuttal about the green eyes, it makes me question the whole solution. In the presence of a third color, and on the assumption that the inhabitants did not know that there was only one person with that third color, wouldn't that mean the inhabitants never leave the island? For example, after 101 days, all of the non-brown-eyed inhabitants would know that they didn't have brown eyes, but they still wouldn't know if their eyes were green or if they were blue. Am I correct in thinking that this problem only works in the presence of exactly two eye colors?

Of course, the problem could still work if they knew that exactly one person had green eyes, but then they would all know who that is, and the Guru would have left long ago and all the inhabitants would still be on the island and starving because the Guru abandoned them instead of teaching them how to head hunt.

No, the solution does work, regardless of how many coloured eyes there are on the island.

Start off from thinking there is just one person on the island with blue eyes. When the guru says "hey, I can see someone with blue eyes", that person will look around and think "there is no-one I can see with blue eyes, by jove, it must be me", so he will leave that night. If there is you and someone else on the island with blue eyes, you will look at each other and each think "I can see one person with blue eyes, if he leaves tonight, I know that he believes he is the only person on the island with blue eyes as he cannot see anyone else with blue eyes, therefore I don't have blue eyes". If he doesn't leave that night, you know he can see someone else with blue eyes and as you can only see him with blue eyes, you know the other person must be you and so you both leave on the second night. They both think like this as they are "perfect logicians" as has been mentioned. You can take take the number up one at a time until it reaches 100 and the logic still works.

Edited June 6, 2009 by Mahone

[pam]

I, for some reason, interpreted the problem as though one person left at a time...that really dampened my chances.

However, now that I think about Vort's thing about all the brown eyed people leaving and then Mahone's rebuttal about the green eyes, it makes me question the whole solution. In the presence of a third color, and on the assumption that the inhabitants did not know that there was only one person with that third color, wouldn't that mean the inhabitants never leave the island? For example, after 101 days, all of the non-brown-eyed inhabitants would know that they didn't have brown eyes, but they still wouldn't know if their eyes were green or if they were blue. Am I correct in thinking that this problem only works in the presence of exactly two eye colors?

Of course, the problem could still work if they knew that exactly one person had green eyes, but then they would all know who that is, and the Guru would have left long ago and all the inhabitants would still be on the island and starving because the Guru abandoned them instead of teaching them how to head hunt.

Oh brother.

[Vort]

Well done, you are the first person I have come across to have worked it out without looking at the answer. Though your bit at the end about the brown eyed people leaving is incorrect because they do not know that there is only blue and brown eyed people (and one green eyed) on the island, by this I mean are far each person is aware, he/she has red eyes and the rest have brown/blue/green.

Yeah, you're right. I misremembered where the info about blue/brown eyes was given. The blue-eyed people could deduce their own eye color after 99 days, but the brown-eyed people would only know that they did not have blue eyes after all the blue-eyed folks left -- they wouldn't know if their own eyes were brown, green, or violet.

[ztodd]

The logic seems to be solid, but it's hard to shake the feeling that there's something wrong with it. Here's what's throwing me- each new level is based on what would happen in a hypothetical situation from the level beneath, but... it's already known that the very first hypothetical situation is not true (that there's only one person with blue eyes), so how can it even be used to build up further hypothetical situations?

As it says on the website-

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?

When I saw that question, I was like, yeah... how is it possible that the 1 and 2 person cases can even be considered? I gotta think about this some more. :)

[Mahone]

The logic seems to be solid, but it's hard to shake the feeling that there's something wrong with it. Here's what's throwing me- each new level is based on what would happen in a hypothetical situation from the level beneath, but... it's already known that the very first hypothetical situation is not true (that there's only one person with blue eyes), so how can it even be used to build up further hypothetical situations?

As it says on the website-

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?

When I saw that question, I was like, yeah... how is it possible that the 1 and 2 person cases can even be considered? I gotta think about this some more. :)

The hypothetical situation of one person has two results, one for if the situation is true and one for if it isn't true. If it is true, he leaves that night. If it isn't, it goes onto the next step (two people) and repeats over and so on and so forth. Finally it gets to 100 blue eyed people and that IS true, so they all leave on the 100th night.

So really, the first hypothetical situation isn't "wrong" as such, the result is just returned as false, so goes into the next one. It's all part of the same solution. Wow, I sound like I'm writing pseudo-programming code lol.

Edited June 7, 2009 by Mahone

[MarginOfError]

No, the solution does work, regardless of how many coloured eyes there are on the island.

Start off from thinking there is just one person on the island with blue eyes. When the guru says "hey, I can see someone with blue eyes", that person will look around and think "there is no-one I can see with blue eyes, by jove, it must be me", so he will leave that night. If there is you and someone else on the island with blue eyes, you will look at each other and each think "I can see one person with blue eyes, if he leaves tonight, I know that he believes he is the only person on the island with blue eyes as he cannot see anyone else with blue eyes, therefore I don't have blue eyes". If he doesn't leave that night, you know he can see someone else with blue eyes and as you can only see him with blue eyes, you know the other person must be you and so you both leave on the second night. They both think like this as they are "perfect logicians" as has been mentioned. You can take take the number up one at a time until it reaches 100 and the logic still works.

Yup, you're right...again, somehow I got stuck into a trap of thinking that the eye color wasn't a binary state when it really was (blue vs. not blue). That there is probably why I went into statistics and not pure math.

The hypothetical situation of one person has two results, one for if the situation is true and one for if it isn't true. If it is true, he leaves that night. If it isn't, it goes onto the next step (two people) and repeats over and so on and so forth. Finally it gets to 100 blue eyed people and that IS true, so they all leave on the 100th night.

So really, the first hypothetical situation isn't "wrong" as such, the result is just returned as false, so goes into the next one. It's all part of the same solution. Wow, I sound like I'm writing pseudo-programming code lol.

It's a process called mathematical induction. It's used in mathematics to prove the truth of a statement when a direct proof is either impossible or excessively complicated. The process is completed in two steps:

• Show that the statement is true for a base step (usually n=1).
• Assume that the statement is true for some n and show that it must also be true for n+1.

If both of these steps my be completed, then it follows that the statement is true for all n greater than or equal to the base step. A rather famous example of proof by mathematical induction is the Binomial Expansion Theorem, which states:

(a+b)^n = a^n + a^(n-1)*b + a^(n-2)*b^2 + ... + a^2*b^(n-2) + a*b^(n-1) + b^n

In this logic puzzle, the same process is used. We can show the solution for n=1, and then, assuming the solution for n, we can also show the solution for n+1. (In first developing a proof by mathematical induction, it is very common to start by working out the solution for 1, 2, 3, 4, ... until a clear pattern is noticed)

[Lbybug]

Oh my gosh i'm so confused

[pam]

(a+b)^n = a^n + a^(n-1)*b + a^(n-2)*b^2 + ... + a^2*b^(n-2) + a*b^(n-1) + b^n

Sheesh...why didn't you explain it that way earlier. It surely clarifies it for me.