Midweek Logic Brain Teaser

Posted by Matt Robson on August 24, 2010, 05:48 PM | #

Q: So what piece of information is the guru providing that logically enables the blue-eyed people to leave the island on the 10th night?  For if the guru had not spoken no one would ever be able to leave the island.

A: Gives them knowledge that everyone knows this information. (which they know already in the non-trivial case), but, also that they know that everyone knows (in the case of 2 individuals), or, that everyone knows that everyone knows that everyone knows, that everyone knows….etc.

Posted by Guessedworker on August 24, 2010, 06:17 PM | #

Notus,

Since I am widely credited with a paucity of logic I shall admit to puzzlement and ask:

What deduction enables the first blue-eyed person to leave the island?  What is to stop all the brown-eyed people leaving when the number of blue-eyed people is reduced to two?

Posted by Rusty on August 24, 2010, 07:07 PM | #

I cannot understand how the popular solution to this type of puzzle is correct.  For one or two specified islanders, the logical sequence of events would occur.  But for three or more the popular solutions do not compute. 

Here is the problem.  The solutions continue adding blue-eyed people in the solution.  However, in the set up of the problem, we start off with a larger number of semi-ignorant islanders.  None of them know the exact tally of blue-eyed people.  If an islander sees at least two others with blue eyes and yet does not know the total, no new information is gathered after the first day of nothing happening, and nothing ever happens at all.

Posted by Steve on August 24, 2010, 07:37 PM | #

There has to be an intermediate exchange of information such as upon hearing the guru, nobody initially moves because they all see at least one blue eyed person, prompting each and every single blue eyed person to know that they MUST have blue eyes, since the others aren’t moving only because they see a blue eyed person.

Posted by Matt Parrott on August 24, 2010, 07:45 PM | #

You know you’re struggling when you look up the answers and explanations and still don’t get it. It seems as if the answer relies on the additional and unavailable facts that he is both referring to a different blue-eyed person on each iteration and that the islanders know that. I also didn’t get how one could conclude that the guru’s stunt was even iterative or truthful in the first place.

Since the islanders are perfectly logical and know the rules in that paragraph, they’re forced to conclude that he is not communicating information about anybody’s eye color - since that would be against the rules.

Or perhaps the islanders kill the guru for breaking the rules in their sacred paragraph, and his corpse gets to leave the following midnight because all is revealed in the afterlife.

Maybe they all waded offshore, save for a different one who remained on the island at noon each day to receive his eye color determination.

Posted by Rusty on August 24, 2010, 07:55 PM | #

To continue:  None of the perfectly logical 10 islanders would have a logical reason for thinking that any other to go through the “if there were x islanders he would leave on the x day” routine.  They start out with more than two blue-eyed people.   It is perfectly logical for each to (also) assume that he has insufficient info to act on the x day or any other.

Posted by Rusty on August 24, 2010, 08:24 PM | #

About the Guru:

Judy: Hey, Dad, what’s brown, has a tail, four legs, can fly a helicopter, and barks?

Dad: Uh, I don’t know.

Judy: A dog.

Dad: But dogs don’t fly helicopters.

Judy: Oh, I know, I just threw that in to make it harder.

Seriously, the guru adds only a “trigger point” of sorts.  It is also here in the explanations where many propound that the guru is the necessary catalyst which turns “something everybody already knows” into “common knowledge,” which is the supposed dynamic which makes all the islanders figure out what each other is thinking.  These complicated explanations for the guru’s effect “work” only because there are many more unstated premises behind the puzzle.  As a thinking exercise in logic, this puzzle is about as helpful as Schroedinger’s cat, soul-mate photons, or string theory, id est, it is actually more confusing to a serious thinker than a help.  Meiner Meinung nach, natürlich.

Posted by Notus Wind on August 24, 2010, 08:46 PM | #

I am glad to see that several people are having fun with this

Posted by Rusty on August 24, 2010, 09:18 PM | #

NW, I understand the popular solution just fine.  But it says that because the islanders are perfectly logical, they would use the “x leave/die on day x” argument without satisfactorily explaining WHY they would do that.  The “x leave/die on day x” inductive reasoning, is logical per se, but the adoption of it by three or more blue-eyed islanders is not.  If you are in a group of three or more blue-eyed islanders, it is more logical to assume that you will never have enough information to know for sure, and that you would do nothing, on day 1, x, or any other.

Someone named Jim (http://higherlogics.blogspot.com/2008/02/blue-eyed-islander-puzzle-analysis.html) might explain it better:

On an island with one blue eyed person the N=1 case works fine. On an island with N=2, induction also works fine.

However on an island with 3 or more blue eyed people the induction never gets started. There is no one on the island who imagines anyone will commit suicide on the first night. Reference to other islands where there are 1 or 2 blue eyed people is irrelevant to an island with 3 or more blue eyed people. When the number gets to 4 blue eyed people not only is there no one worrying about the first night but everyone knows that everyone else knows this. In fact the islanders could talk about this openly without giving away anyone’s eye color. They could say “Hey, we all know that there are at least two blue eyed and two brown eyed people so we all know that there is no way to get Sandro Magi’s weird logic going, right?

If you consider, say, the first hundred proof by induction problems you ever did, you will notice that this one is different from all the others. In all those when you get to the N+1th stage the Nth stage is embedded in the objects you are considering, be they equations, geometric objects, or even imagined situations like the present. The mistake lots of people online have made with this problem is thinking that what happens on an island with 1 or 2 blue eyed people has anything to do with an island with 100 blue eyed people. On an island with 100 blue eyed people no one for even a moment imagines that anyone else on the island is thinking he might be on an island with only one blue eyed person. So the induction never gets going for N=1. In order for your scheme to work the induction has to work on the actual island in question, not other islands with fewer blue eyed people.

The wildly popular solution is wrong unless one buys into the circular reasoning and special logical assumptions about “knowledge everyone already knows” being different than “common knowledge.”

Posted by Tanstaafl on August 24, 2010, 10:50 PM | #

If the guru had said, “10 people on the island have blue eyes” the induction argument would make sense.

The phase transition between 2 and 3 is reminiscent of the N-body problem in physics.

The guru knows who he is because he doesn’t see anyone else with green eyes.

Posted by Lurker on August 25, 2010, 12:20 AM | #

I see how it works for N=1, if the guru said blue eyed people plural, then it also works for N=2.

Day one, everyone looks around, each blue eye sees 9 others and 10 browns plus one green. Each brown eye sees 10 blues, 9 browns and one green. The green sees ten of each.

That night no-one leaves.

Next day the situation is the same. That means no-one left the island. That means that each person will assume that they themselves are the blue eyed person in question and therefore leave on night two.

So everybody leaves the island on night two.

Posted by Notus Wind on August 25, 2010, 12:29 AM | #

Rusty: In fact the islanders could talk about this openly without giving away anyone’s eye color.

The islanders can’t communicate with each other in accordance with the first paragraph.

Rusty: Reference to other islands where there are 1 or 2 blue eyed people is irrelevant to an island with 3 or more blue eyed people.
...
Tan: The phase transition between 2 and 3 is reminiscent of the N-body problem in physics.

The induction argument doesn’t suddenly break down in this way.

Rusty: The wildly popular solution is wrong unless one buys into the circular reasoning and special logical assumptions about “knowledge everyone already knows” being different than “common knowledge.”

There is no circular reasoning.  If there are 3 blue-eyed people then everyone knows that everyone knows that there is at least one blue-eyed person as a matter of fact, but the blue-eyed people themselves don’t know that everyone knows that everyone knows because they only see 2 blue-eyed people.

Posted by Notus Wind on August 25, 2010, 01:02 AM | #

GW and Matt P,

I’ve substantially revised my argument for the solution to the puzzle in the main entry.  Unfortunately, the closer I get to a complete proof the more unreadable it gets, which is a sign of just how feisty this little brain teaser really is.

Anyway, if you give up on my solution in the main entry you might have better luck here: http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29#Example

Posted by Tanstaafl on August 25, 2010, 01:29 AM | #

I think I understand. Even not knowing exactly how many blue-eyed people there are, but seeing 9 others with blue eyes, on day 9+1, since nobody has yet left, each perfect-logic blue-eyed person would conclude that they must have blue eyes.

Posted by Lewis on August 25, 2010, 01:46 AM | #

In the n1 case:

19 brown-eyed islanders live their days thinking “Bob has blue eyes, but he’ll never know! I wonder if I have blue eyes? I guess I’ll never know.”
Bob the blue-eyed islander lives his days thinking, “There aren’t any blue-eyed people on my island, unless it’s me. Guess I’ll never know.”

So when the guru says, “Someone has blue eyes!”:
19 islanders roll their eyes and think “No shit sherlock. I wonder if that includes me? Guess I’ll never know.”
Blue-eyed Bob, on the other hand, receives the shock of his life and leaves the island.

In the n2 case:

18 brown-eyed islanders live their days thinking “Bob and Jim both have blue eyes, but they’ll never know! I wonder if I have blue eyes? I guess I’ll never know.”
Bob lives his days thinking “Jim has blue eyes. I wonder if I have blue eyes? I guess I’ll never know.”
Jim likewise lives thinking “Bob has blue eyes. I wonder if I have blue eyes? I guess I’ll never know.”

So when the guru says “Someone has blue eyes!”:
All the islanders roll their eyes and think “No shit sherlock. I wonder if that includes me? Guess I’ll never know.”

—-
n2 is dead in the water. The induction never gets off the ground. Therefore, the correct answer is, in fact, “no one ever leaves the island.”

Posted by Lewis on August 25, 2010, 02:08 AM | #

Ok, n2 retake:

If, after the guru made his announcement, Bob looked around and saw 18 brown-eyed people, and blue-eyed Jim, and Jim did not leave the subsequent day, Bob would have to infer that Jim saw another blue-eyed person, and therefore Jim did not know whether the guru was referring to himself. Since, from Bob’s perspective, everyone else save Jim has brown eyes, Bob would be forced to conclude that the other blue-eyed person was himself, and both would leave the next day.

So n2 is definitely valid. Ignore the previous.

Posted by Lurker on August 25, 2010, 06:23 AM | #

Following on from Lewis. Yes, I see how it works for 1 & 2 but how beyond that?

Why doesnt everybody leave?

When the next day dawns and no-one has left why doesnt everyone assume that they themselves are the blue eyed person?

Posted by Rusty on August 25, 2010, 08:13 AM | #

First, an island with 3 or more blue-eyed people never expects anyone to leave on the first night; the induction process can never get started. 

Second, there is no logical reason to for a n=3 island to reason like a n1 or n2 island, id est, to begin their reasoning process as if they were.

All the razmataz and circular reasoning about common knowledge and induction is irrelevant at n=3+. 
The reason no one can explain clearly and simply why the popular solution “works” past n2 is because it has a faulty assumption: that there is only one logical solution for n3+ islands and that all the islanders would choose it.  But beginning at n=3, there is at least one other logical conclusion that each islander could come to and that is that A) at n=3, none of them will have any new information (the induction process has no way to get started) and B) that it is illogical to reason like an n1 or n2 island because they are an n3 island.  None can be sure of which logical conclusion has been reached by his fellow n3 islanders. 

This puzzle and its answer must surely classify as an urban mathematical legend.

Posted by danielj on August 25, 2010, 08:48 AM | #

Who cares about a bunch of white devils stuck on an island anyway?

All you white people care about is Lost and logic…

Posted by Rusty on August 25, 2010, 09:04 AM | #

Nitpicky perhaps, but something else about this puzzle annoys me.  The setup tells us that everyone is perfectly logical and knows that everyone else is, too.  The popular solution says that the guru adds new information: that once he speaks, he gives confirmation of something that the islanders were unsure of.  But on such an n3 island, all logical islanders would already know that everyone else knows that everyone else knows, et cetera.  The guru is important on an n1 island, and maybe on an n2 island, but not on an n>2 island. 

I know setups are tricky and I’m not picking on yours, NW, just making a general observation about the puzzle.

Posted by Notus Wind on August 25, 2010, 09:06 AM | #

Rusty,

All the razmataz and circular reasoning about common knowledge and induction is irrelevant at n=3+.

The razzmatazz works!

Consider the case of N=3 blue-eyed people.  Then each blue-eyed person sees 2 other blue-eyed people and reasons as follows, “If I am not a blue-eyed person then the two blue-eyed people that I can see will leave on the 2nd night.”  All the other blue-eyed people will reason similarly, and after 2 nights go by without anyone leaving the island then each blue-eyed person will be able to identify his eye color and leave on the 3rd night.

But on such an n3 island, all logical islanders would already know that everyone else knows that everyone else knows, et cetera.

In the case of N=3 blue-eyed people.  It is a true statement that “everyone knows that everyone knows that there is at least one blue-eyed people”.  But the blue-eyed people themselves don’t know that “every knows that every knows that there is at least one blue-eyed person” for they only see 2 other blue-eyed people!  The guru’s statement fixes all this.

I know setups are tricky and I’m not picking on yours, NW, just making a general observation about the puzzle.

No problems.

Posted by Rusty on August 25, 2010, 10:04 AM | #

Consider the case of N=3 blue-eyed people.  Then each blue-eyed person sees 2 other blue-eyed people and reasons as follows, “If I am not a blue-eyed person then the two blue-eyed people that I can see will leave on the 2nd night.”

No, they wouldn’t.  And no one would would wait until the second night, in any event.  On an island with 3 blue-eyed people, everyone already knows that there are at least two blue-eyed people.  The solution builds on the assumption that here is a possibility of someone leaving the first or second night.  On an n1 or n2 island this is true.  But everyone on the 3 blue-eyed island already knows that this will not happen.

I think what makes the popular solution sound logical is the “If we started out with an n1 island ...”  Although each islander could, there is no logical reason for anyone on an n3 island to necessarily conclude that everyone else would reason like that.

Posted by Lurker on August 25, 2010, 11:46 AM | #

and after 2 nights go by without anyone leaving the island then each blue-eyed person will be able to identify his eye color and leave on the 3rd night.

Why doesnt everybody on the island leave? Why dont they all assume they are the other blue eyed person?

Posted by Rusty on August 25, 2010, 12:45 PM | #

Each has to know for sure.  The same reason that keeps the brown-eyed islanders planted on n2 is the same reason which keeps anyone at all from leaving on an n3 island: everyone who sees two or more pair of blue eyes knows he has no way of knowing is own for sure.

Posted by Notus Wind on August 25, 2010, 01:29 PM | #

Lurker: Why doesnt everybody on the island leave? Why dont they all assume they are the other blue eyed person?

In the case of there being N=3 blue-eyed people on the island the brown-eyed people will see 3 blue-eyed people while the blue-eyed people will only see 2 other blue-eyed people.  This is the difference that explains why the logic plays out differently for the brown-eyed people than it does for the blue-eyed people.

Rusty: No, they wouldn’t.  And no one would would wait until the second night, in any event.

You are one relentless fellow!

Lets return to the case of there being N=3 blue-eyed people on the island.  By your own admission, if there were only 2 blue-eyed people on the island then they would leave the island together on the 2nd night.  Now, a blue-eyed person on an island with a total of 3 blue-eyed people will see the 2 other blue-eyed people and he will know that, “If I am not a blue-eyed person then the 2 blue-eyed people that I see will leave together on the 2nd night.” he will know this because he is a perfect logician (as stipulated in the first paragraph of the puzzle).  So if no one leaves the island for the first 2 nights then he will be able to conclude that it’s because he is blue-eyed and then leave the island on the 3rd night, along with all the other blue-eyed people who would go through the same logical train of thought.

But how do we know that no one will leave the island for the first 2 nights?  I demonstrate this claim in the second major paragraph of my induction argument in the main entry.

Posted by Notus Wind on August 25, 2010, 03:24 PM | #

The proof in the main entry is now completely rigorous!

Posted by Rusty on August 25, 2010, 03:31 PM | #

OK, I do see it working for n=3, good, thank you.  Each of the 3 who see 2 blues is blue-notblue until the two blues which he sees doesn’t leave on day 3, at which point each all three can self-identify himself at the same time.  Those who see 3 blues are forced to wait because they never have enough info

But what about n=4?  Would anyone who sees three blues expect that the chain could ever get started?

Posted by Rusty on August 25, 2010, 03:45 PM | #

OK, I got it.  At n=4, each blue-eyed person is seeing only three and knowing that it is possible for them to figure it out by day 3.  If they haven’t, and he sees no more, then he must be it.  And so on and so on.  The brown-eyed people are always one logical step behind because they see one more blue-eyed person.

Now that I understand it, the solution seems pretty simple; I can’t see how I didn’t see it before.  Way cool puzzle, thanks.

Now, what about n=5? 

Posted by Notus Wind on August 25, 2010, 03:49 PM | #

Rusty,

OK, I got it.  At n=4, each blue-eyed person is seeing only three and knowing that it is possible for them to figure it out by day 3.  If they haven’t, and he sees no more, then he must be it.  And so on and so on.  The brown-eyed people are always one logical step behind because they see one more blue-eyed person.

You got it!

Now that I understand it, the solution seems pretty simple; I can’t see how I didn’t see it before.  Way cool puzzle, thanks.

You’re welcome.  I would encourage you to share the puzzle with others now that you understand it.

Posted by Rusty on August 25, 2010, 04:31 PM | #

So, what is the significance of the guru’s remark, other than to get the whole ball rolling?

Posted by Dasein on August 25, 2010, 04:33 PM | #

Interesting puzzle.  It’s easy enough to see how, when there are only 1 or 2 blue-eyed people on the island, that a single blue-eyed person could figure it out on his own.  For N > 2, there seems to be the assumption that everyone is agreeing to this N-day procedure, perhaps because it’s the only solution to the problem.  In that case, I understand how it works.  But I still don’t see why the guru’s announcement is necessary when N > 2.  Everyone can see that there are at least 2 blue-eyed people who can see each other.  If you weren’t sure that each person knew everyone else’s eye colour, the pronouncement could be signficant, but I understood the following bit from the post to mean that everyone has a complete tally:

Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color

Or maybe the guru’s annoucement is necessary to set N=1 and put the solution in motion.

Posted by Wanderer on August 25, 2010, 04:42 PM | #

Couldn’t everyone get off the island within three days at most?

—Day One. Every islander says to the clerk on the ship “I think I have brown eyes”. Some are let on, others are sent back because their eyes are not brown.
—Day Two. Every islander remaining says to the clerk on the ship “I have blue eyes”. Some are let on, others are sent back because their eyes are not blue.
—Day Three. Any remaining islanders say to the clerk on the ship “I have green eyes”. Any remaining are let on.

Posted by Notus Wind on August 25, 2010, 05:04 PM | #

Rusty: So, what is the significance of the guru’s remark, other than to get the whole ball rolling?
...
Dasein: But I still don’t see why the guru’s announcement is necessary when N > 2

It’s difficult to fully communicate how the logic works but I’ll try my best.

Before the guru speaks, the basic knowledge that the islanders can gather is essentially visual, the eye colors of the people that they can see.  However, none of this knowledge is commonly known by everyone (i.e. not everyone knows that person X has blue eyes because person X doesn’t know that he has blue eyes).  The islanders may deduce propositional knowledge from all this visual data (i.e. “we all know that someone has blue eyes”) but they cannot conclude by virtue of their private deductions that everyone else can make the same deductions because none of their basic knowledge is commonly known.

It is only when the guru speaks proposition P that the islanders gain access to a piece of propositional knowledge that they know is commonly known.  And because they know it is commonly known they know that “everyone knows P” and that “everyone knows that everyone knows P” and that “everyone knows that everyone knows that everyone knows P” etc.

The puzzle highlights the subtlety of “common knowledge” as a logical concept.

Posted by Notus Wind on August 25, 2010, 05:35 PM | #

One more thing.

The guru gets the ball rolling by making it commonly known that, “Someone on the island has blue eyes.”  Because this statement is now commonly known it allows the islanders to extract further logical information from whatever happens at night, even if nothing happens and no one leaves the island.

Posted by Dasein on August 25, 2010, 05:46 PM | #

Interesting stuff, thanks for sharing this.  Another question: is there a reason the guru can’t have brown eyes, or even blue eyes if he qualified it as ‘someone else on this island has blue eyes’? 

A compendium of racialist brain teasers would be fun.  There’s that one I remember from childhood about the fox, chicken, and bag of grain that a man needs to get across a river.  You could make it a UN worker who can’t leave a Bantu and a pygmy alone for fear the latter would be eaten.

Posted by Notus Wind on August 25, 2010, 05:56 PM | #

Dasein,

Interesting stuff, thanks for sharing this.  Another question: is there a reason the guru can’t have brown eyes, or even blue eyes if he qualified it as ‘someone else on this island has blue eyes’?

I am not sure why the guru’s eyes have a unique color in this puzzle.  You could probably make the guru’s eyes blue or brown and not change anything else (including the guru’s proclamation that “Someone on the island has blue eyes”).

Posted by Wanderer on August 25, 2010, 06:03 PM | #

Notus Wind wrote:
It is only when the guru speaks proposition P that the islanders gain access to a piece of propositional knowledge that they know is commonly known.  And because they know it is commonly known they know that “everyone knows P” and that “everyone knows that everyone knows P” and that “everyone knows that everyone knows that everyone knows P” etc.

The puzzle highlights the subtlety of “common knowledge” as a logical concept.

“There are known knowns. These are things we know that we know.
There are known unknowns. That is to say, there are things that we know we don’t know.
But there are also unknown unknowns. There are things we don’t know we don’t know.”
—Donald Rumsfeld, expert logician


Wouldn’t the Guru’s message be an “unknown known” then?

Posted by Guessedworker on August 25, 2010, 06:30 PM | #

Rummy has green eyes!

http://unconfirmedsources.com/nucleus/media/21/20060803-rumskull.jpg

Posted by uh on August 25, 2010, 09:06 PM | #

Now see—isn’t this all much superior to PIG RIDDLES?

Posted by Silver on August 27, 2010, 09:32 PM | #

Notus,

The puzzle highlights the subtlety of “common knowledge” as a logical concept.

Maddeningly subtle.

I recall a version of this puzzle that had monks with red dots on their foreheads.  The statement of common knowledge that at least one monk had a red dot was accompanied by the order to commit suicide on learning that one had a red dot, which considerably simplifies the problem. In contrast, the eye-color puzzle would be confounded by the concomitant statement of common knowledge that at least one islander has brown eyes.

Dase,

A compendium of racialist brain teasers would be fun.

This particular brain teaser bears exquisite relevance to racialism.  “Everyone” can see that “racial differences are real”, or that “whites exist” and that most of them continue to behave as though they considered other whites valuable or important.  Yet it seems to require an explicit statement to that effect before the procession of racial logic that culminates in politicized whites can commence.