Your favorite logic puzzles

[md65536]

"It specifically states "assorted eye colors" "

 

The xkcd version does. The OP version does not.

 

I stand by my statement that no one (not islanders nor puzzle solver) needs to know how many possible eye colors there are and what those colors are, in order for the puzzle to work (ie. that all N blue leave on day N).

 

As I interpreted John Cuthber's example, there would suddenly be common knowledge from a God.

 

Yes, but John Cuthber's statement says that the common knowledge given by a God is "perfect logic". In other words, the God sets the puzzle's rules, and makes those rules common knowledge.

 

His example specifically excluded giving common knowledge of the existence of blue-eyed islanders. His point is that the puzzle is the same without that knowledge.

His example is flawed. It is not the same as the original puzzle, and to claim so indicates a complete misunderstanding of the solution, and of the importance of the common knowledge given by the visitor in the original puzzle.

 

The start time is needed, if everyone don't start acting on the same day, no islander can derive anything on his own counting.

Yes, but the start time is a part of the common knowledge. The start time is needed, but the start time alone (without the common knowledge of a blue-eyed islander) is not enough for anyone to deduce their eye color.

 

I think the quiz in the OP assumes only two eye colours and in the OP's answer those with brown eyes commit suicide the next day.

 

That's true, I should have stuck to the topic and used OP's version.

 

OP is incorrect. It must be common knowledge that the only two colors are brown and blue, in order that the brown also deduce their eye color. This is not stated in the puzzle. If the answer relies on assuming that things are common knowledge, then the point of the puzzle kind of falls apart. One might falsely assume all sorts of different common knowledge, as John Cuthber does in assuming that the existence of a blue eyed islander is already common knowledge, and that they could have deduced their eye color a year ago.

 

Technically, OP's puzzle also omits the important information of the rule that "every islander knows the rules". We are told that everyone follows the religion, so we might assume that the islanders know that too. But to be fair, we really can't, because it is an assumption of common knowledge. Then the puzzle doesn't work, even for the blue-eyed islanders.

 

I'd been using the xkcd version because it doesn't leave such ambiguities, but I should have stuck to OP's version.

 

 

I will concede, that in OP's version, unless the islanders know something more that we don't know they do, nothing will happen.

 

 

Ironically enough, in that case, the common knowledge of a blue-eyed islander, though essential, is not enough! And then the god-given common knowledge of "Oh by the way, everyone knows the rules" would start the countdown on the day of the new knowledge.

[Spyman]

Yes, but John Cuthber's statement says that the common knowledge given by a God is "perfect logic". In other words, the God sets the puzzle's rules, and makes those rules common knowledge.

 

His example specifically excluded giving common knowledge of the existence of blue-eyed islanders. His point is that the puzzle is the same without that knowledge.

His example is flawed. It is not the same as the original puzzle, and to claim so indicates a complete misunderstanding of the solution, and of the importance of the common knowledge given by the visitor in the original puzzle.

While looking back at John Cuthber's example I might have misinterpreted him when he said: "As far as I can see they all suddenly become aware that everyone knows that lots of people have blue eyes and that starts the destruction.", I thought he ment that the god gave them this knowledge...

 

Either way, I agree that John Cuthber's example changes the original quiz in the OP to something else.

 

 

Yes, but the start time is a part of the common knowledge. The start time is needed, but the start time alone (without the common knowledge of a blue-eyed islander) is not enough for anyone to deduce their eye color.

Yes, I agree, the start time is only one piece that is needed and does not suffice alone.

 

 

OP is incorrect. It must be common knowledge that the only two colors are brown and blue, in order that the brown also deduce their eye color. This is not stated in the puzzle. If the answer relies on assuming that things are common knowledge, then the point of the puzzle kind of falls apart. One might falsely assume all sorts of different common knowledge, as John Cuthber does in assuming that the existence of a blue eyed islander is already common knowledge, and that they could have deduced their eye color a year ago.

I think the quiz in the OP can be interpreted as that the two eye colours are common knowledge, firstly there are only two colours mentioned and secondly this island is far away enough that it is an explorer that finally arrives there after several months at sea, so the islanders might very well never have seen or heard of any other possible eye colour than the two they can see.

(Since he is invited to speak to the whole population it might even be the first non-islander they meet.)

 

So I think John Cuthber is correct about that the existence of a blue eyed islander is already common knowledge, if there is more than two islanders with blue eyes and everyone know everyones eye colour except their owns, then everyone would know that there is at least one blue eyed islander, but I don't agree with him that they can deduce their own eye colours since they lack a common syncronization.

 

 

Technically, OP's puzzle also omits the important information of the rule that "every islander knows the rules". We are told that everyone follows the religion, so we might assume that the islanders know that too. But to be fair, we really can't, because it is an assumption of common knowledge. Then the puzzle doesn't work, even for the blue-eyed islanders.

It is a quiz after all, we are supposed to assume some sensible stuff not mentioned in exact details.

 

 

I will concede, that in OP's version, unless the islanders know something more that we don't know they do, nothing will happen.

Agreed.

 

 

Ironically enough, in that case, the common knowledge of a blue-eyed islander, though essential, is not enough! And then the god-given common knowledge of "Oh by the way, everyone knows the rules" would start the countdown on the day of the new knowledge.

No, I don't think "Oh by the way, everyone knows the rules" is enough even if the two eye colours are common knowledge, the syncronization must include a direction too, they must have a common thought of what to deduce, otherwise one might think of blue, another of brown, while a third think of the forced suicide, the fourth thinks of forbidden communications and so on, in short all need to know what they are trying to figure out.

[md65536]

While looking back at John Cuthber's example I might have misinterpreted him when he said: "As far as I can see they all suddenly become aware that everyone knows that lots of people have blue eyes and that starts the destruction.", I thought he ment that the god gave them this knowledge...

 

I agree, but that's not enough.

I don't think that John Cuthber understands the full meaning of common knowledge in logic.

 

To quote the wikipedia link given 3 or so times already, "There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum."

 

Every order of knowledge, from 1st to (k-1)th, is necessary in order for the knowledge to be common knowledge.

 

The puzzle is an example of how every order can be important. In the puzzle, the islanders are explained to not have common knowledge of the existence of a blue eyed islander, until the outsider provides it. It shows how even with (k-2) orders of knowledge of what everyone knows, that (k-1)th order can make a difference.

 

 

 

So I think John Cuthber is correct about that the existence of a blue eyed islander is already common knowledge, if there is more than two islanders with blue eyes and everyone know everyones eye colour except their owns, then everyone would know that there is at least one blue eyed islander, but I don't agree with him that they can deduce their own eye colours since they lack a common syncronization.

I think we'll have to have the OP weigh in on this.

I disagree about the OP's intentions, because the given solution explains it like it's the standard blue-eyed islander puzzle, which relies on it not being common knowledge that there exists a blue-eyed islander. I'm pretty sure that is OP's intentions, because the whole point of the visitor's statement is that it provides the common knowledge.

 

I believe that OP meant to give a fairly standard "blue-eyed islander" puzzle, but accidentally skipped some details, leaving it ambiguous.

 

 

 

It is a quiz after all, we are supposed to assume some sensible stuff not mentioned in exact details.

Yes, but the islanders are "hyper logical", and we can't assume that they would assume anything.

It is definitely not a safe assumption that the existence of a blue-eyed islander is common knowledge before the visitor's statement.

 

If you were on an island of 1000 where everyone around you has purple eyes, would you deduce that you have purple eyes? (And do you have purple eyes? So would you be wrong? Would it be flawed logic?)

If you were in a forest where everyone around you was a tree, would you deduce that you were a tree, if there was no way to directly determine it?

 

 

 

No, I don't think "Oh by the way, everyone knows the rules" is enough even if the two eye colours are common knowledge, the syncronization must include a direction too, they must have a common thought of what to deduce, otherwise one might think of blue, another of brown, while a third think of the forced suicide, the fourth thinks of forbidden communications and so on, in short all need to know what they are trying to figure out.

 

No, they don't need a common plan of what to do. All they need is the understanding that everyone else is acting "hyper logically".

 

The islanders don't need a plan, to know that if day k passes and no one is gone, it is common knowledge that there are at least k blue.

If I'm blue, and I see 99 blue, and all the blue go on day 99...

BUT if it's allowed that they can kill themselves, then I don't know for sure if they all spontaneously decided to kill themselves, or if they suicided because they found out they were blue.

 

The xkcd versions prevents this ambiguity in the rules, with "Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay."

The wikipedia version currently has some ambiguity.

[Spyman]

I agree, but that's not enough.

I don't think that John Cuthber understands the full meaning of common knowledge in logic.

I think it is enough that I rejected John Cuthber's example already in post #45, as something different that the quiz in the OP.

 

 

I think we'll have to have the OP weigh in on this.

I disagree about the OP's intentions, because the given solution explains it like it's the standard blue-eyed islander puzzle, which relies on it not being common knowledge that there exists a blue-eyed islander. I'm pretty sure that is OP's intentions, because the whole point of the visitor's statement is that it provides the common knowledge.

 

I believe that OP meant to give a fairly standard "blue-eyed islander" puzzle, but accidentally skipped some details, leaving it ambiguous.

I don't know what the *standard* blue-eyed islander puzzle is, this is the first time I heard about this puzzle, but both this one in the OP and the one in the xkcd link relies on that they can all can know how many blue eyed there are except themselves and know that they all know this.

 

From the xkcd link where it is worded better:

 

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

 

The puzzle simply won't work if they don't know each others colours and know that the others also know.

 

 

Yes, but the islanders are "hyper logical", and we can't assume that they would assume anything.

It is definitely not a safe assumption that the existence of a blue-eyed islander is common knowledge before the visitor's statement.

 

If you were on an island of 1000 where everyone around you has purple eyes, would you deduce that you have purple eyes? (And do you have purple eyes? So would you be wrong? Would it be flawed logic?)

If you were in a forest where everyone around you was a tree, would you deduce that you were a tree, if there was no way to directly determine it?

The quiz in the OP is not worded such that we can to one hundred percent conclude that every islander can know that every one have seen and counted every one except their own eye colour. But I think it is sensible to assume that they had, they have lived their entire lives on the same isolated island, they all are extremly religious and eye colour is very important in their religion.

 

How certain are you that gravity works as normal somewhere on Earth were you had not been yet? Granted we can never know until we test but after lots of tests the probability increases and we can start to assume that gravity acts normal everywhere.

 

If I never had seen anyone with a different eye colour and everyone I had ever seen had the same colour, then I would be very certain. Further on in the context here I think if I where the only one with a different eye colour than the entire population with such a morbid religion, I would likely notice others treating me differently unless they all are extremly good actors.

 

I don't think trees have much deducing powers, whether they are alone or in a forest...

 

 

No, I don't think "Oh by the way, everyone knows the rules" is enough even if the two eye colours are common knowledge, the syncronization must include a direction too, they must have a common thought of what to deduce, otherwise one might think of blue, another of brown, while a third think of the forced suicide, the fourth thinks of forbidden communications and so on, in short all need to know what they are trying to figure out.

No, they don't need a common plan of what to do. All they need is the understanding that everyone else is acting "hyper logically".

 

The islanders don't need a plan, to know that if day k passes and no one is gone, it is common knowledge that there are at least k blue.

If I'm blue, and I see 99 blue, and all the blue go on day 99...

I did not say *a common plan*, I did not mean that they gathered together and took a collective decision, what I tried to say is that they all need to know what everyone else is using their *hyper logically* ability to try to figure out. If the explorer would have mentioned brown eyes instead the outcome would have been different because everyone would try to find out if they have brown eyes.

 

IMHO the common knowledge of the task at hand, including a syncronisation time, is the essential spark that starts the purge of blue eyed.

[md65536]

The puzzle simply won't work if they don't know each others colours and know that the others also know.

I think we're in agreement but just splitting hairs.

 

Yes, before the visitor's statement everyone already knows about the existence of a blue-eyed islander, but it isn't common knowledge.

 

 

The quiz in the OP is not worded such that we can to one hundred percent conclude that every islander can know that every one have seen and counted every one except their own eye colour. But I think it is sensible to assume that they had, they have lived their entire lives on the same isolated island, they all are extremly religious and eye colour is very important in their religion.

 

 

There's no need to assume that, because the OP stated, "if there is some way by which someone can deduce their eye-colour, they will do so instantly." As long as we assume it's possible, we don't need to consider how likely.

 

 

If I never had seen anyone with a different eye colour and everyone I had ever seen had the same colour, then I would be very certain. Further on in the context here I think if I where the only one with a different eye colour than the entire population with such a morbid religion, I would likely notice others treating me differently unless they all are extremly good actors.

The puzzle doesn't rely on any such educated guesses or assumptions about eye color, even "very probable" ones.

 

I did not say *a common plan*, I did not mean that they gathered together and took a collective decision, what I tried to say is that they all need to know what everyone else is using their *hyper logically* ability to try to figure out. If the explorer would have mentioned brown eyes instead the outcome would have been different because everyone would try to find out if they have brown eyes.

 

IMHO the common knowledge of the task at hand, including a syncronisation time, is the essential spark that starts the purge of blue eyed.

 

No, they don't need to know what everyone else is using their logic to figure out.

All they need to know is that the others are following the rules. If that's a "task at hand", then I agree with you.

 

You could say that the islanders are trying to figure out if they have blue eyes. You could equally say they're trying to avoid it (because they don't want to die), but that they accidentally find out anyway. All that matters is that eventually, the blue will deduce their eye color and die. Yes, they do need common knowledge of this fact in order to deduce their own eye color. They do need common knowledge that everyone is following the rules, from which they can deduce that the blue will all leave on day N, from which they can deduce that N is greater than k after day k passes without the blue leaving, from which they can (and by the rules, must) deduce if they have blue eyes.

[Spyman]

I think we're in agreement but just splitting hairs.

 

Yes, before the visitor's statement everyone already knows about the existence of a blue-eyed islander, but it isn't common knowledge.

The OP might not be as clear as the xkcd link but I think those parts are sensible to assume, however at the xkcd site they explicitly state that:

 

"Everyone on the island knows all the rules in this paragraph."

http://www.xkcd.com/blue_eyes.html

 

Which makes it common knowledge that there exists blue eyed islander before the explorer arrives.

 

If everyone knows that everyone counts then it is common knowledge that there are at least 98 and at most 101 blue eyed islanders:

 

"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),"

http://www.xkcd.com/blue_eyes.html

 

Anyone of the one hundred blue eyed can see 99 blue eyed islanders and knows that:

If he has blue eyes then any blue eyed can see to 99 blue and any brown eyed can see 100 blue

If he has brown eyes then any blue eyed can see 98 blue and any brown eyed can see 99 blue

Conclusion, everyone knows that everyone knows that there are at least 98 blue eyed islanders.

 

Anyone of the nine hundred brown eyed can see 100 pairs of blue eyes and knows that:

If he has blue eyes then any blue eyed can see 100 blue and any brown eyed can see 101 blue

If he has brown eyes then any blue eyed can see 99 blue and any brown eyed can see 100 blue

Conclusion, everyone knows that everyone knows that there are at most 101 blue eyed islanders.

 

If I can figure this out then surely any *hyper logical* islander can too.

 

 

No, they don't need to know what everyone else is using their logic to figure out.

All they need to know is that the others are following the rules. If that's a "task at hand", then I agree with you.

 

You could say that the islanders are trying to figure out if they have blue eyes. You could equally say they're trying to avoid it (because they don't want to die), but that they accidentally find out anyway. All that matters is that eventually, the blue will deduce their eye color and die. Yes, they do need common knowledge of this fact in order to deduce their own eye color. They do need common knowledge that everyone is following the rules, from which they can deduce that the blue will all leave on day N, from which they can deduce that N is greater than k after day k passes without the blue leaving, from which they can (and by the rules, must) deduce if they have blue eyes.

But they do need to have common knowledge of what the others are trying to figure out, everyone knows and follows the rules and everyone knows that everyone counts all islanders of each different eye colour before the spoken words.

 

Consider what would happen if the explorer says: "How pleasant it's to see another pair of brown-eyes, after all these months at sea" ?

Edited February 23, 2012 by Spyman

[imatfaal]

I am not sure of the common knowledge aspect - I agree with Spyman's post above about everyone knowing, and knowing that everyone else knowing before the explorer arrives. I have always got around this point by assuming - perhaps naively - why the process of inductive reasoning can only start with the explorer's announcement.

 

Before the announcement

Person A cannot deduce his eye colour. He wonders if he might show it though induction.

He starts with the initial case: one islander - no chance.

The first sensible case - one blue eyed islander, any number of browns. What do these islanders know - they know the other islanders eye colour AND nothing else. The blue eyed islander DOES NOT know of the existence of blue eyed islanders. The brown eyes do - but cannot act on is as their own is still unknown.

The induction has failed to take off - there is no deductive logic that can get the simple case going. You cannot impute the knowledge of the existence of (a) blue-eyed islander(s) to the simplest case - that is a piece of knowledge that is only gained in the more complex cases with lots of blue eyed islanders. Without an initial deductive case the induction cannot start

 

When the announcement is made

The first sensible case - there is knowledge of the existence of a blue eyed islander; bad luck for that guy - he is able to deduce that he must have blue eyes (at least one islander has blue eyes, no one else has blue eyes, therefore I must have blue eyes.)

The second case - first night, each blue eyed islander thinks "I can see a poor guy with blue eyes - through deductive logic he will leave the island tonight" ..."Oh Bugger. he didn't leave he must be able to see a second - which must be me"

The third...hundredth now follow through induction

 

edit - appalling grammar

Edited February 23, 2012 by imatfaal

[md65536]

I am not sure of the common knowledge aspect - I agree with Spyman's post above about everyone knowing, and knowing that everyone else knowing before the explorer arrives.

Yes... but once again that's not common knowledge.

 

Read and understand the wiki entry on common knowledge (logic) and you should see why the existence of a blue-eyed islander is not common knowledge before the visitor's statement.

 

 

 

-----

 

I'll try to explain this one more time and then I'm giving up, because I'm obviously failing at communicating anything effectively here.

 

 

Consider a smaller case of 7 islanders: 3 blue, 3 brown, and me with unknown-color eyes.

 

 

I see 3 blue.

IF my eyes are not blue, then the 3 blue each see only 2 blue. They will think it possible that there are only 2 blue.

If the blue that I see think that there are only 2 blue (which I know to be incorrect), they may think that each of those 2 blue

see only one other blue.

 

That is, the blue I see might think the blue they see might think there is only one blue... and that this sole blue might then see

no blues and so might think that there are no blues.

 

No one thinks that there are no blues. No one even thinks that anyone else thinks there are no blues.

But it's possible to think that the blue I see think

A: that there are only 2 blue, and

B: that the 2 blue each think there is only one blue, and

C: that the 2 blue each think that the one blue that they see thinks there are no blues.

 

 

Once the visitor gives the common knowledge of the existence of a blue-eyed islander, it is no longer possible for me to assume that

the 3 blue I see can assume that there are 2 blue who can assume that there is only 1 blue who can assume that there are no blue.

 

The existence of 1 blue-eyed islander is only truly common knowledge on day 1.

The existence of 2 is common knowledge on day 2, deduced from the common knowledge that if there was only 1 blue she would have determined her eye color and suicided by then.

The existence of 3 is common knowledge on day 3, etc.

 

I see 3 blue. On day 3 it is common knowledge that there are 3 blue. IF the 3 blue I see, each see only 2 blue and try to assume there are only 2 blue, they will deduce the contradiction and know that they have blue eyes. They will suicide on day 3.

 

ELSE If they're still around on day 4 I know that there are at least 4 blue. I now know that my eyes are blue.

 

 

Edit: Note that the whole time, it's possible to assume without contradiction that each of the 3 brown I see, each see only 2 brown and can assume that those 2 see only 1 brown, and can assume that the 2 can assume the one brown sees no browns. The existence of a brown-eyed islander is never common knowledge (unless we assume some additional amount of common knowledge about eye color that isn't specified in the puzzle).

Edited February 23, 2012 by md65536

[imatfaal]

Mr Eraserhead - you managed to explain common knowledge well, no need to give up!

 

My point was rather that common knowledge is a logical concept that allows a flow of induction to appear as deduction. There is an accessible inductive model to answer the blue-eyed islander problem, which both explains why people leave when they do and does not fall foul of the claim they leave straight away (it merely requires that the rules and knowledge is carefully monitored). This has already been discussed

 

 

But many people will distrust induction. John Cuthber earlier in this thread rightly mentioned how easy it is to misuse induction (the execution date/ surprise exam problem) - deduction does not suffer from this ( or more realistically it is much easier to spot the false logic). But the idea of common knowledge is in fact the the necessity to be scrupulously careful in invoking an inductive process neatly packaged

[md65536]

My point was rather that common knowledge is a logical concept that allows a flow of induction to appear as deduction. There is an accessible inductive model to answer the blue-eyed islander problem, which both explains why people leave when they do and does not fall foul of the claim they leave straight away (it merely requires that the rules and knowledge is carefully monitored). This has already been discussed

 

 

But many people will distrust induction. John Cuthber earlier in this thread rightly mentioned how easy it is to misuse induction (the execution date/ surprise exam problem) - deduction does not suffer from this ( or more realistically it is much easier to spot the false logic). But the idea of common knowledge is in fact the the necessity to be scrupulously careful in invoking an inductive process neatly packaged

Well now we're talking.

 

I agree. After writing the reply below I've decided that my reply is a rambling nit-picking of details that is an unnecessary diversion from the point of the puzzle.

 

----

 

Many people will distrust division. One may rightly mention that division can be misused to incorrectly prove that 0=1. So if division---or induction---is being misused one need only point out the error. One need not "explain why division by 0 doesn't work" in order to use division. Yes, we must be careful not to misuse any mathematical or logical reasoning, but we only need to distrust it when we don't know how to use it properly and precisely.

 

The induction proof for this puzzle "hides" the deductive reasoning that an islander might do, but that's okay because the puzzle specifically avoids the requirement that the islanders each think it through, with their magical logic abilities ("if there is some way by which someone can deduce their eye-colour, they will do so instantly."). So, yes, all that is needed is to be scrupulously careful.

 

I think that a confusing trick in this puzzle is that we mix up what we as omniscient puzzle solvers know and reason about the situation, and what the islanders know and reason. And I think it also tricks a puzzle writer, as in the case here where OP has made it an assumption that since we know that all the islanders follow the rules, that the islanders themselves know that too.

 

For the induction proof to be water-tight, it must not make any uncertain assumptions. The funny thing is, it is reasonable to argue that there's a flaw in the induction proof in this case (and with any other way of solving the puzzle)... The argument that if there was one blue, the other islanders would know the lone blue would deduce her eye color relies on the assumption that the islanders know that the other islanders know and obey the rules. WE know that they do, but we're meant to assume that it's common knowledge for the islanders.

 

Of the 3 versions mentioned herein (OP's, wikipedia's, and xkcd's) I think that only the xkcd version is specified precisely enough that the intended solution need not rely on such assumptions about the islanders.

[Spyman]

I'll try to explain this one more time and then I'm giving up, because I'm obviously failing at communicating anything effectively here.

I am glad you didn't give up since you were right, sorry for being so thickheaded, +1 for you.

[md65536]

I am glad you didn't give up since you were right, sorry for being so thickheaded, +1 for you.

Thanks No apologies necessary. If the details were easy to get, I would be able to explain it more easily.

[John Cuthber]

Thanks folks.

You are all clearly brighter than me (at least at this sort of thing).

I'm still wondering how little information the traveller has to impart to cause an effect.

It seems that "I see blue eyes" has an effect, and as far as I can work out "I see brown eyes" has a comparable effect.

 

What happens if he turns up and says "I see eyes which have a defined colour but I am not stating what that colour is"?

In particular, what happens in the case where the islanders know (as part of their creed), that all eyes are either blue or brown?

Similarly (I think) what if he says "I see a pair of eyes and their colour is ..." and then dies of a heart attack?

As far as I can tell the islanders think "he was going to say blue or he was going to say brown" and they consider each possibility.

[Spyman]

In the simplest case with only ONE islander, would any of the examples above provide enough clues for him to conclude his own eye colour?

 

Would it help that ONE if he was not alone and could see another islander with blue or brown eyes?

 

Would it help that ONE if he was not alone and could see several islanders with blue or browns eyes?