Your favorite logic puzzles

[Antti]

Well, the title is quite self-explanatory. So, what are your favorite logic puzzles and why? (I'm running short and need new ones!)

 

My favorite so far is probably the blue-eyed islanders puzzle. It took me long enough to solve it, but I managed to do so without cheating. I like puzzles that seem counter-intuitive at first.

 

So here's a version of the puzzle:

There is an island of 1000 people, 100 of whom have blue eyes, and 900 of whom have brown. There are no mirrors, nor any other reflective surfaces on the island, and the local religion forbids all discussion of eye-colour. Furthermore, anyone who discovers their own eye-colour must commit suicide that same day.

One day, an explorer lands on the island, and is invited to speak before the whole population. The explorer, unaware of the local customs, commits a faux pas stating "How pleasant it's to see another pair of blue-eyes, after all these months at sea". The explorer doesn't direct his words to anyone in particular.

The question is: What happens next?

Assume that everyone on the island follows their religion unerringly and that all islanders are hyper logical; if there is some way by which someone can deduce their eye-colour, they will do so instantly.

And

here's the solution (shamelessly promoting my own blog).

[ydoaPs]

What about the brown-eyed islanders? After realizing what has happened, they will all commit suicide on the next day (assuming they knew that all islanders have either brown of blue eyes).

I don't think that holds. There's no reason they would find out that they have brown eyes if one of the at least one blue eyed islanders commits suicide.

 

However, on the second day, Johnny sees that Hugh hasn’t committed suicide, and therefor deduces that Hugh must also see a blue-eyed islander. Since Johnny can see only one, he concludes that he must be the blue-eyed islander that Hugh sees

The jump from here requires knowing exactly how many blue eye islanders there are.

[Antti]

I don't think that holds. There's no reason they would find out that they have brown eyes if one of the at least one blue eyed islanders commits suicide.

All blue eyed islander commit the suicide at the same day, thus all islanders that remain have to conclude that they have brown eyed (since there are only two possibilities either blue or brown eyes).

 

The jump from here requires knowing exactly how many blue eye islanders there are.

The only think Johnny needs to know is that Hugh must see a blue-eyed islander as he hasn't committed suicide. As he can see only Hugh having blue-eyed he must reason that he has blue-eyes. (And after this surely Johnny knows that there are two blue-eyed islanders, himself and Hugh who he can see).

Edited February 2, 2012 by Antti

[TonyMcC]

The explorer doesn't claim his own eyes are blue (he could have been talking about a shipmate, perhaps the only one on his ship with blue eyes. Alternatively he could have been on a ship where nobody had blue eyes and he was thinking of the blue eyed wife he left behind).

He doesn't inform any particular person of their eye colour, although everyone might wonder "does he mean me"?.

It seems the only action the islanders will take is to punish the explorer in a way not described for his faux pas (maybe excommunication) .

I feel instinctively that "nothing really" can't be the answer - or can it?

 

OK looked at the answer - I see that it is not assumed the explorer is not giving information about his own eye colour. Sorry!

Edited February 2, 2012 by TonyMcC

[CaptainPanic]

LOL!

Welcome to the forum, Antti.

 

This is quite normal behavior for this place... you ask for new puzzles, and post your own favorite, and instead your favorite puzzle will get ripped apart and nobody posts a new one.

 

You'll surely get enough brain exercises here, and we all mean to do well... we just don't always give the replies that somebody wants.

 

Anyway, while I think I understand the examples with only 1 or 2 people with blue eyes, I do not see how you can extrapolate that to four.

One person with blue eyes will think: "Ok, the newcomer said there are people with blue eyes. And I can see 3 of them. Those 3 individually will see only 2, and they have no way to realize that they themselves have blue eyes too."

And all 4 will have the same response.

Edited February 2, 2012 by CaptainPanic

[Phi for All]

This is quite normal behavior for this place... you ask for new puzzles, and post your own favorite, and instead your favorite puzzle will get ripped apart and nobody posts a new one.

Hey, I moved the thread from the Lounge to Brain Teasers & Puzzles, don't I get a cookie?

[Antti]

LOL!

Welcome to the forum, Antti.

 

This is quite normal behavior for this place... you ask for new puzzles, and post your own favorite, and instead your favorite puzzle will get ripped apart and nobody posts a new one.

Thank you. I don't mind at all; if anything it's helpful to think of ways to explain something to people, it only deepens one's understanding on the subject. And I like to defend my case so I think I will enjoy it here. I wouldn't mind discovering some new puzzles though.

 

Anyway, while I think I understand the examples with only 1 or 2 people with blue eyes, I do not see how you can extrapolate that to four.

One person with blue eyes will think: "Ok, the newcomer said there are people with blue eyes. And I can see 3 of them. Those 3 individually will see only 2, and they have no way to realize that they themselves have blue eyes too."

And all 4 will have the same response.

Oh, I might add this to enlighten the case with three blue-eyed islanders:

After 2 days, each blue-eyed person knows that a second blue-eyed person knows that a third person has blue eyes, but no one knows that there is a third blue-eyed person with that knowledge, until the third day arrives.

 

Okay, case with four islanders. Let's call them Andy, Bob, Cindy, Derek. After explorer speaks.

Andy, Bob, Cindy, and Derek will all see three islanders* with blue-eyes and reason "if I don't have blue eyes, there will only be three blue-eyed islanders and they will all commit suicide on the third day". Well, the third day comes and no one commits suicide as none of them yet has proof for themselves being blue-eyed.

 

After no-one commits suicide Andy must conclude that Bob, Cindy, and Derek all see three blue-eyed islanders. And since he can only see three (which would mean that each of them saw only two blue-eyed islanders) he must conclude that the third one they see is he himself.

 

*

Andy sees Bob, Cindy, and Derek.

Bob sees Andy, Cindy, and Derek.

Cindy sees Andy, Bob, and Derek.

Derek sees Andy, Bob, and Cindy.

 

See what I did there?

 

Hey, I moved the thread from the Lounge to Brain Teasers & Puzzles, don't I get a cookie?

Sure, you do. Here!

Edited February 2, 2012 by Antti

[ydoaPs]

All blue eyed islander commit the suicide at the same day, thus all islanders that remain have to conclude that they have brown eyed (since there are only two possibilities either blue or brown eyes).

 

The only think Johnny needs to know is that Hugh must see a blue-eyed islander as he hasn't committed suicide. As he can see only Hugh having blue-eyed he must reason that he has blue-eyes. (And after this surely Johnny knows that there are two blue-eyed islanders, himself and Hugh who he can see).

This breaks down after two. If the islander says "It's nice to see the exactly three pair of blue eyes in the native population here", it might work, but that's not what he said. He merely said that there exists at least two. Even if there are only two blue eyed islanders, since an exact number wasn't given and the islanders can't look at their own eyes, each of the brown islanders can logically think they have blue eyes or brown eyes. Likewise, if there are more than two blue eyed islanders and each sees at least two other blue eyed islanders, the traveler gave them no information from which they could deduce their own blue-eyedness.

 

Hey, I moved the thread from the Lounge to Brain Teasers & Puzzles, don't I get a cookie?

No cookies for you.....ever.

 

Oh, I might add this to enlighten the case with three blue-eyed islanders:

After 2 days, each blue-eyed person knows that a second blue-eyed person knows that a third person has blue eyes, but no one knows that there is a third blue-eyed person with that knowledge, until the third day arrives.

 

Okay, case with four islanders. Let's call them Andy, Bob, Cindy, Derek. After explorer speaks.

Andy, Bob, Cindy, and Derek will all see three islanders* with blue-eyes and reason "if I don't have blue eyes, there will only be three blue-eyed islanders and they will all commit suicide on the third day". Well, the third day comes and no one commits suicide as none of them yet has proof for themselves being blue-eyed.

 

After no-one commits suicide Andy must conclude that Bob, Cindy, and Derek all see three blue-eyed islanders. And since he can only see three (which would mean that each of them saw only two blue-eyed islanders) he must conclude that the third one they see is he himself.

 

*

Andy sees Bob, Cindy, and Derek.

Bob sees Andy, Cindy, and Derek.

Cindy sees Andy, Bob, and Derek.

Derek sees Andy, Bob, and Cindy.

 

See what I did there?

 

What you did there was have them using information they do not have. All the information that was given to them was that there was at least one islander with blue eyes. This isn't even new information to most of the tribe. All you have the traveler saying is "How pleasant it's to see another pair of blue-eyes, after all these months at sea". This indicates at least one, not the exact number. Your problem doesn't work.

[Antti]

This breaks down after two. If the islander says "It's nice to see the exactly three pair of blue eyes in the native population here", it might work, but that's not what he said. He merely said that there exists at least two. Even if there are only two blue eyed islanders, since an exact number wasn't given and the islanders can't look at their own eyes, each of the brown islanders can logically think they have blue eyes or brown eyes. Likewise, if there are more than two blue eyed islanders and each sees at least two other blue eyed islanders, the traveler gave them no information from which they could deduce their own blue-eyedness.

 

The explorer says that there exists one pair of blue eyes so at least one blue-eyed islander. Did you read my explanation, if you did, I would just be repeating myself, if you didn't, I suggest you do. Or I might just as well post it here. Here we go. Oh, before that, the reason why it doesn't break up is that the explorer introduces new knowledge, and it doesn't need to be directed. The thing is that everyone knows that everyone knows...

 

To get an idea of how the puzzle works let's start by first considering a much simpler case where there exists only one blue-eyed islander, call him Jack.

 

Jack knows from the explorer's words that there exists at least one blue-eyed islander. Since he can see none, Jack correctly concludes that he must be the blue-eyed islander and commits suicide on the first day.

 

Now suppose that instead of one there are two blue-eyed islanders, Johnny and Hugh. Johnny can see Hugh and so knows that there exists at least one blue-eyed islander. However, on the second day, Johnny sees that Hugh hasn't committed suicide, and therefor deduces that Hugh must also see a blue-eyed islander. Since Johnny can see only one, he concludes that he must be the blue-eyed islander that Hugh sees. They both commit suicide on the second day.

 

What about the brown-eyed islanders? After realizing what has happened, they will all commit suicide on the next day (assuming they knew that all islanders have either brown of blue eyes).

 

So the general statement is: If there are blue-eyed islanders, they will all commit suicide on the n^th day. And all brown-eyed islanders will commit suicide on the (n+1)^th day.

 

The answer to the original puzzle therefore is: The blue-eyed islanders will commit suicide on the 100^th day and the brown-eyed will do the same on the 101^st day.Proof by induction consists of two simple steps.

 

• Step 1. Showing that the statement holds when n is equal to the lowest value in question.
• Step 2. Showing that if the statement holds for some n, then the statement also holds when n+1 is substituted for n.

We've already worked out the first step. In the case that there is only one blue-eyed islander he will commit suicide on the first day.

 

Now then, if we suppose that n is larger than 1. Each blue-eyed islander will reason along the lines: "If I don't have blue eyes, there will only be n-1 blue-eyed islanders, and they will all commit suicide n-1 days after the explorer's blunder". When n-1 days pass no-one commits suicide as none of the blue-eyed islanders yet has proof for themselves being blue-eyed. However, after nobody commits suicide on the (n-1)^th day, each blue-eyed islanders has to conclude that they themselves must be blue-eyed, and so they will all commit suicide on the n^th day.

 

Quod erat demonstrandum.

 

There exists an argument against the solution I've offered. The argument states that, although the explanation works in the case that there exists only one blue-eyed islander, it will not do so when more than one blue-eyed islander are present because the explorer doesn't tell them anything they don't already know. That is to say, everyone on the island already knows that there exists at least one blue-eyed islander.

 

However this is not true! The explorer introduces new information.

 

To understand this, first consider the following example. There is a group of students sitting in a class room; each one may individually notice that the teacher isn't wearing any trousers, but they don't know whether the others have also noticed. Now then, if the teacher mentions the fact the information becomes common knowledge, also known as second-order knowledge. In other words, everyone in the class room knows that everyone knows that the teacher isn't wearing trousers.

 

So in a more general sort of way: If everyone in a group of people knows X, then X is said to be first-order knowledge. If everyone knows that everyone knows X, this is to say if everyone knows that X is first-order knowledge, then X is considered to be second-order knowledge. Generally, X is (n+1)^th-order knowledge, if everyone knows that it's n^th-order knowledge.

(i

 

When there exists only one blue-eyed islander, the explorer directly increases the stock of first-order knowledge.

 

When there are two blue-eyed islanders, Johnny and Hugh, everyone knows that there exists at least one blue-eyed islander, and so much is first order knowledge. However, it isn't second-order knowledge until the explorer speaks. This is because Johnny doesn't know if Hugh knows whether there exist any blue-eyed islanders, and likewise.

If this explanation doesn't do I found another by xkcd's Randall: http://xkcd.com/solution.html

And Wikipedia seems to use this in as an example in context of common knowledge: http://en.wikipedia....(logic)#Example

 

All the information that was given to them was that there was at least one islander with blue eyes.

No, the information the explorer gave to them is (in addition to what you said) that "everyone knows that there exists at least one blue-eyed islanders. See the difference.

Edited February 2, 2012 by Antti

[ydoaPs]

 

The explorer says that there exists one pair of blue eyes so at least one blue-eyed islander. Did you read my explanation, if you did, I would just be repeating myself, if you didn't, I suggest you do. Or I might just as well post it here. Here we go. Oh, before that, the reason why it doesn't break up is that the explorer introduces new knowledge, and it doesn't need to be directed. The thing is that everyone knows that everyone knows...

 

 

If this explanation doesn't do I found another by xkcd's Randall: http://xkcd.com/solution.html

And Wikipedia seems to use this in as an example in context of common knowledge: http://en.wikipedia....(logic)#Example

 

 

No, the information the explorer gave to them is (in addition to what you said) that "everyone knows that there exists at least one blue-eyed islanders. See the difference.

 

Ok, so there is only one blue eyed islander. They are told there is at least one blue eyed islander. This means the blue eyed islander knows there is only one, but each of the brown eyed islanders have only enough information to say that the number of blue eyed islanders is greater than one but less than three since they cannot see their own eyes.

 

Since the blue eyed islander cannot see any blue eyed islander, he kills himself. This means there are now zero blue eyed islanders, but the brown eyed islanders only have enough information to deduce that there are less than two blue eyed islanders. There is no information given to the brown eyed islanders at any point in the scenario such that they would be logically forced to kill themselves.

[Antti]

Ok, so there is only one blue eyed islander. They are told there is at least one blue eyed islander. This means the blue eyed islander knows there is only one, but each of the brown eyed islanders have only enough information to say that the number of blue eyed islanders is greater than one but less than three since they cannot see their own eyes.

 

Since the blue eyed islander cannot see any blue eyed islander, he kills himself. This means there are now zero blue eyed islanders, but the brown eyed islanders only have enough information to deduce that there are less than two blue eyed islanders. There is no information given to the brown eyed islanders at any point in the scenario such that they would be logically forced to kill themselves.

 

After the first suicidal event:

 

Each islander left will reason that if they had have blue-eyes the first suicidal event would not have taken place, as it did take place they, without any doubt, must have brown eyes.

 

I think I should maybe rename this thread...

 

"Arguing about my favorite logic puzzle"

 

LOL!

[ydoaPs]

After the first suicidal event:

 

Each islander left will reason that if they had have blue-eyes the first suicidal event would not have taken place, as it did take place they, without any doubt, must have brown eyes.

 

I think I should maybe rename this thread...

 

"Arguing about my favorite logic puzzle"

 

LOL!

Ok, I get the reasoning now, but there's still something off about it since they already knew there was at least one person on the island with blue eyes.

Edited February 2, 2012 by ydoaPs

[Antti]

My bad, it does work with only one actual blue-eyed person barring no clear pools of water on or surrounding the island. Ok, I got it now.

 

It takes time to think it out.

 

Now then, any new puzzles for me?

[ydoaPs]

It takes time to think it out.

 

Now then, any new puzzles for me?

 

Actually, I don't think the puzzle works. The whole island already knows that there is at least one blue eyed person before the traveler gets there since there are 100 of them and they can see each other. There's also the fact that everyone on the island already knows that there is at least one brown eyed person on the island. So, we can run the same solution for the brown eyed people. The problem, however, is that the solutions should be running simultaneously. Wouldn't the presence of one solution ruin the operation of the other?

[John Cuthber]

This looks a lot like the unexpected hanging to me.

http://en.wikipedia.org/wiki/Unexpected_hanging_paradox

 

All the people on the island can see some people with blue eyes.

The traveller doesn't add to that.

 

What would happen if someone (on the island) dreamed that the traveller turned up and said the bit about "I can see someone with blue eyes".

The dreamer would know that it was possible for a traveller to do so. After all, any traveller who got that would see people with blue eyes and anyone on the island would know that the traveller would see people with blue eyes.

Since they are perfectly logical they would deduce that a traveller might turn up and say that.

So they would be able to deduce the same logical string, even without having the traveller arrive and commit suicide. (Followed by the rest of the group)

 

But there's a problem.

What happens if they dream that the traveller says "I can see someone with brown eyes".

In that case the brown eyed people have to kill themselves first.

 

But both groups can't die first.

So there's a flaw in the logic.

I don't know for certain what it is, but there must be one.

[ydoaPs]

But both groups can't die first.

So there's a flaw in the logic.

I don't know for certain what it is, but there must be one.

The paths to solution run simultaneously interfere with each other and make neither work. And then there's the problem of how the population got that large in the first place given the fact that the traveler didn't give them any information they didn't already have.

[CaptainPanic]

Hey, I moved the thread from the Lounge to Brain Teasers & Puzzles, don't I get a cookie?

I have cookies disabled, but I pressed that green button on the post.

 

And then there's the problem of how the population got that large in the first place [...]

... given the fact that the people are incredibly suicidal.

 

It's like forever playing a combination of the game where you can't say "yes" or "no", and Russian roulette. You're not likely to be a winner... and the stranger who makes a remark about their eyes is probably the least of their worries.

 

Sorry to drift so far off topic.

Edited February 3, 2012 by CaptainPanic

[imatfaal]

Here is Randall XKCD's telling of the same puzzle

 

and here is his explanation.

 

The solution is sound and works - rec.puzzles used to regularly re-hash it, but annoyingly I cannot find any of the old threads

 

There is even a wikipedia page on the puzzle - common knowledge

[ydoaPs]

Here is Randall XKCD's telling of the same puzzle

 

and here is his explanation.

 

The solution is sound and works - rec.puzzles used to regularly re-hash it, but annoyingly I cannot find any of the old threads

I don't think it is. It assumes that they don't know that at least one brown eyed person exists whilst simultaneously using that information. Assuming for the sake of the argument that the solution does work, it works equally well if we swap the colors by having the tribe be told that at least one brown eyed islander exists. The problem comes in with the guru (per Randall's version, the traveler per the OP's version) doesn't give the tribe any new information. They already knew that at least one blue-eyed islander existed. They also already knew that at least one brown-eyed islander exists. It doesn't work if the scenario used for the solution is being tried for both colors simultaneously.

 

The answer is that all of the islanders are safe and stay on the island.

[Antti]

Once more, I try to explain this as patiently and simply as I can. ydoaPs, you seem to keep missing points that I have stated multiple times already. But it's probably because I don't state my case clearly enough...

 

imatfaal, thanks

 

The whole island already knows that there is at least one blue eyed person before the traveler gets there since there are 100 of them and they can see each other. There's also the fact that everyone on the island already knows that there is at least one brown eyed person on the island. So, we can run the same solution for the brown eyed people. The problem, however, is that the solutions should be running simultaneously. Wouldn't the presence of one solution ruin the operation of the other?

We cannot run the same solution for brown-eyed islanders the amount of information about the brown-eyed islanders is not equal to the amount of information about the blue-eyed islanders. Hence the solution should not be running simultaneously.

Wikipedia:

What's most interesting about this scenario is that, for k > 1, the outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge.

 

For k = 2, it is merely "first-order" knowledge. Each blue-eyed person knows that there is someone with blue eyes, but each blue eyed person does not know that the other blue-eyed person has this same knowledge.

 

For k = 3, it is "second order" knowledge. After 2 days, each blue-eyed person knows that a second blue-eyed person knows that a third person has blue eyes, but no one knows that there is a third blue-eyed person with that knowledge, until the third day arrives.

 

In general: For k > 2, it is "(k − 1)th order" knowledge. After k − 1 days, each blue-eyed person knows that a second blue-eyed person knows that a third blue-eyed person knows that.... (repeat for a total of k − 1 levels) a kth person has blue eyes, but no one knows that there is a "kth" blue-eyed person with that knowledge, until the kth day arrives. The notion of common knowledge therefore has a palpable effect. Knowing that everyone knows does "make a difference. When the outsider's public announcement (a fact already known to all) becomes common knowledge, the blue-eyed people on this island eventually deduce their status, and leave.

 

The paths to solution run simultaneously interfere with each other and make neither work. And then there's the problem of how the population got that large in the first place given the fact that the traveler didn't give them any information they didn't already have.

 

There is no reason whatsoever why there would be two solutions running simultaneously.

 

Assuming for the sake of the argument that the solution does work, it works equally well if we swap the colors by having the tribe be told that at least one brown eyed islander exists. The problem comes in with the guru (per Randall's version, the traveler per the OP's version) doesn't give the tribe any new information. They already knew that at least one blue-eyed islander existed. They also already knew that at least one brown-eyed islander exists. It doesn't work if the scenario used for the solution is being tried for both colors simultaneously.

You see the difference between everyone knowing something and everyone knowing that everyone knows something. First and second order knowledge there. The thing is this puzzle requires 100th-order knowledge. So it is not enough that "they already knew that at least one blue-eyed islander existed [and that] they also already knew that at least one brown-eyed islander exists."

 

So what happens is that the explorer's words increase the stock of 100th-order knowledge. Second-order knowledge is not enough. And as no-one increases the order of knowledge concerning brown-eyed islanders they can't reason as the blue-eyed islanders do.

 

 

[ydoaPs]

We cannot run the same solution for brown-eyed islanders the amount of information about the brown-eyed islanders is not equal to the amount of information about the blue-eyed islanders. Hence the solution should not be running simultaneously.[/size][/font]

Wikipedia:

What's most interesting about this scenario is that, for k > 1, the outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge.

 

That is false according to both Randall's formulation and your own. The islanders have the ability to see. They see more than one of each color and the outsider merely says there exists at least one of one of the colors. The outsider or the guru (depending on the formulation we're talking about) gives no new information.

 

You see the difference between everyone knowing something and everyone knowing that everyone knows something.

 

In both formulations, everyone knows that everyone knows that there exists at least one person of each eye color even before the fact was announced.

[Antti]

• http://terrytao.wordpress.com/2011/05/19/epistemic-logic-temporal-epistemic-logic-and-the-blue-eyed-islander-puzzle-lower-bound/

[md65536]

Ok, I get the reasoning now, but there's still something off about it since they already knew there was at least one person on the island with blue eyes.

If you're talking about only the case where there is one blue-eyed islander, then no: The brown-eyeds knew there was at least one blue-eyed, but the blue-eyed didn't know that. If the blue-eyed suicides, then the rest can deduce that there was only one blue-eyed.

 

The interloper's comment provides new information only to a lone blue-eyed. No one else thinks anything too shocking of the comment.

The blue-eyed's suicide provides new information to everyone else.

 

 

Sorry if I'm off due to skimming the thread.

 

 

[ydoaPs]

If you're talking about only the case where there is one blue-eyed islander, then no: The brown-eyeds knew there was at least one blue-eyed, but the blue-eyed didn't know that. If the blue-eyed suicides, then the rest can deduce that there was only one blue-eyed.

 

The interloper's comment provides new information only to a lone blue-eyed. No one else thinks anything too shocking of the comment.

The blue-eyed's suicide provides new information to everyone else.

 

 

Sorry if I'm off due to skimming the thread.

Indeed, but see my more developed reasoning regarding the actual case.

[md65536]

Indeed, but see my more developed reasoning regarding the actual case.

Oh yes. I think the XKCD link presents it slightly more easy to think about.

 

I think I see how it works, now.

 

 

The key is that if there are N blue, each of them can assume that there are N-1 blue,

and this will lead to a logical contradiction, so each knows the assumption is wrong and that they are blue.

 

So for an exemplary case that's not N=1 or N=2, suppose there are only 4 blues on the island.

Suppose I am blue, but let me assume that I'm not blue.

Assume there are 3 blues.

Assume also that the 3 other blues will have the same logic as me, and each will assume that there are only 2 blues.

On the first night, no one leaves, so everyone knows that there are at least 2 blues. But everyone already knew this. So perhaps they could skip this night?*

On the second night, no one leaves, so everyone knows that there are at least 3 blues. Now each of the 3 blues will know their assumption was wrong, and that they're blue. So they'll leave the next night.

On the third night, no one leaves, so everyone knows there are at least 4 blues. My assumption that I'm not blue is wrong, so I know I'm blue. I leave on the fourth night (and so do the other symmetric blues).

 

The questions posted on the XKCD link:

1. What info does the Guru give? None!??? I think the same argument above could be done with any color where N>3, but it appears not so...**

 

2. Why is the N=1 and N=2 case relevant?

Answer: Not sure...

 

3. Why do you have to wait 99 nights?

* Or in my example, why do we have to wait for the 3rd night, if the 1st night gives no information?

Answer: Suppose we skipped night 1, because everyone already knows there are at least 2 blues. So on night 1, any blue who thought there were only 2 blues could leave... but no one would. So on the first night no one leaves, whether there are 3 or 4 blue. If I skip any nights I already know and everyone else does as well, I still don't know if it's 3 or 4 and I know the 3 blues don't know if it's actually 2 (that I assume they see) or 3 (that I assume there are). So everyone can ignore the nights, but all the ignored nights leave more than one possibility open (3 or 4; I may or may not be blue). It is not until night 2 that I know for sure that the 3 blues know there are 3 blues (I knew all along that there were at least 3 blues, and they knew too, but I didn't know they knew!), and not until night 4 until I know there are 4 of us.

 

 

 

** As for other colors...

Suppose there are 2 purple-eyeds.

Everyone knows there is at least 1 purple-eyed. But each of the purple-eyed can assume the other purple is the only one, and not derive any contradictions. I know the other purple will never know if they're purple, and I'll never know if I'm purple (or perhaps I'm red).

 

Case P3: Suppose instead there are 3 purple.

I can assume that I'm not purple, and that there are only 2 purple, and that each of them can assume there are only 1 purple.

But then, if there are only 2 purple and each assumes there's only 1, they can each assume that the other sees no purple!

None of these assumptions will be contradicted when no one leaves the island night after night, so I never know that my assumption that I'm not purple is wrong.

In this case, without the guru, I don't know that the other purples knows that each other knows that any other purples exist! So again, I know there are at least 2 purple, but if there are 3 (i.e. me) I'll never know it.

 

So suppose instead there are 4 purple.

I will assume there are 3.

I assume each of the 3 assume there are 2 purple.

Suppose we treat this similarly to the blue case.

On the first night no one leaves, and everyone knows there's at least 2 blue (and I know everyone knows there's at least 2 purple but that's not news either).

On the second night no one leaves, so I and everybody know there's at least 3 blue. But I know from Case P3 that the 3 purple won't know that their assumption is wrong that there are only 2. So I don't know that everybody knows there are 3 purple.

 

So, even though everyone knows there's at least 1 purple, I can assume the wrong thing and not derive a contradiction, because I know that the other purples can assume the wrong thing and not derive a contradiction, because it's possible from the information that I have that there are only 3 purples and they each know the others can assume the wrong thing and not derive a contradiction... and so forth?

 

Confusing!

 

Edit:

I suppose the answer to XKCD's question #1 is:

After day N, I know that the assumption that there are only N blue eyed is wrong, based on induction, and knowing that the assumption that there are only N-1 blue is wrong. The induction relies on the N=1 case, where the contradiction is only possible with the guru?????? Still confusing.

 

 

Edited February 9, 2012 by md65536