[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:

Quote

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]

Quote

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.

Quote

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]

 ydoaPs, on 2 February 2012 - 02:10 PM, said:

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

 ydoaPs, on 2 February 2012 - 02:10 PM, said:

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

This post has been edited by Antti: 2 February 2012 - 02:49 PM

[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!

This post has been edited by TonyMcC: 2 February 2012 - 04:04 PM

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

This post has been edited by CaptainPanic: 2 February 2012 - 03:08 PM

[Phi for All]

 CaptainPanic, on 2 February 2012 - 03:06 PM, said:

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]

 CaptainPanic, on 2 February 2012 - 03:06 PM, said:

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.

 CaptainPanic, on 2 February 2012 - 03:06 PM, said:

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?

 Phi for All, on 2 February 2012 - 03:16 PM, said:

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

Sure, you do. Here!

This post has been edited by Antti: 2 February 2012 - 03:39 PM

[ydoaPs]

 Antti, on 2 February 2012 - 02:47 PM, said:

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.

 Phi for All, on 2 February 2012 - 03:16 PM, said:

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

No cookies for you.....ever.

 Antti, on 2 February 2012 - 03:28 PM, said:

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]

 ydoaPs, on 2 February 2012 - 03:37 PM, said:

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

Quote

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

Quote

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.

This post has been edited by Antti: 2 February 2012 - 03:54 PM

[ydoaPs]

 Antti, on 2 February 2012 - 03:50 PM, said:

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]

 ydoaPs, on 2 February 2012 - 04:00 PM, said:

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]

 Antti, on 2 February 2012 - 04:21 PM, said:

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.

This post has been edited by ydoaPs: 2 February 2012 - 05:40 PM

[Antti]

 ydoaPs, on 2 February 2012 - 05:15 PM, said:

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]

 Antti, on 2 February 2012 - 05:40 PM, said:

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

 John Cuthber, on 2 February 2012 - 09:27 PM, said:

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]

Phi for All, on 2 February 2012 - 03:16 PM, said:

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.

ydoaPs, on 2 February 2012 - 11:06 PM, said:

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.

This post has been edited by CaptainPanic: 3 February 2012 - 02:39 PM

[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]

imatfaal, on 3 February 2012 - 03:15 PM, said:

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

Quote

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.

Quote

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.

Quote

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.