My write-up of the "Blue Eyes" solution (SPOILER A

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Wed Oct 08, 2014 3:49 am UTC

kokevi wrote:The argument here is that the fact that there are Green eyes is mutual knowledge, not common knowledge. For it to be common knowledge all dragons must know there are green eyes (1), they must know the other dragons know that there are green eyes (2), and they must know the other dragons know they know (3).

Your definition of common knowledge is insufficient to solve the problem. Take the case of an island with three dragons. All 3 know there are green eyes. All 3 know the other two dragons know there are green eyes. And all 3 know that the others know that they know green eyes exist. However, none of the dragons knows their eye color with certainty, and in fact none can be sure that GEDs are common knowledge.

Put yourself in the mindset of one of the dragons - A sees 2 GEDs, so is sure that each of her fellow dragons can see a GED. However, in A's mind B might only see 1 (C), and also in A's mind, B might not know that C can see any GEDs. As outsiders, we know this isn't true because we know A's eye color, but A doesn't.

kokevi
Posts: 3
Joined: Tue Oct 07, 2014 11:32 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby kokevi » Wed Oct 08, 2014 6:27 am UTC

rmsgrey wrote:By the standard definition of common knowledge in logic, you need the infinite regress, or some equivalent condition (such as self-reference). Before the visitor says anything, all three of your conditions are met, but the knowledge is still only 99 levels deep - everyone knows1 that everyone knows2 that everyone knows3 that ... that everyone knows99 that there is at least one green-eyed dragon, but the green-eyed dragons don't know that - that's the crucial information that kicks everything off...

OK, got my head around it. Even though #100 knows that #99 knows that #100 knows ... etc and #100 knows that #98 knows that #100 knows.... #99 must still know that #98 knows that #99 knows....

I started thinking of it as the green spotted dragon problem. Each dragon has a green spot on the back of their head. They all line up with #100 at the back. #100 can see that all the dragons have green spots. #99 can only see the 98 dragons in front of it, which is what #100 can imagine #99 seeing. So from #100 point of view #99 can only see 98 GSD and so on. And then #1 can't see any. And it doesn't matter how you shuffle them round, the dragon at the back will always think the dragon at the front can't see any spots.

Thanks

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby jestingrabbit » Thu Oct 09, 2014 1:30 am UTC

chettski wrote:A few folks here have nailed it (especially OP Tipping), but most are missing the forest for the trees. Sure, you can work out the logic for n=1, n=2, and extend to n=100. But there's a clear fallacy here, in that the visitor/guru gives non-common information only in the case of n=1 or 2, but not 3 or higher. The entire system breaks down if the visitor/guru gives already known information. There is no "starting the clock" when he/she states previously known (and obvious) information!

Someone (I forget who) correctly observed that this is a faulty logic problem. I believe the true logic problem lies in recognizing the fallacy of the initial "logic problem," which most miss, since they're wrapped around extending n from 3 through 100. This reminds me of Marilyn Vos Savant (and a legion of mathematics professors and statisticians... including my late grandfather) getting the Monty Hall problem spectacularly wrong. The key in that problem (which most miss) is that the host gives new information 2/3rds of the time, leading to the "better odds if you switch."

The correct wording of a solvable version of the blue-eyed puzzle must have the "discovery" of everyone else's eye color on day one, such as dragons/islanders blindfolded at birth, then removing the blindfolds all at once. Only then will you have the magic happen on day 100. As it stands, it's unsolvable. 8-)


Nah.

Here's some fun questions for you to think about.
1. How can any of the islanders rule out having green eyes before the guru speaks?
2. Lets say there are 4 islands, with the first island having 1 blue eyed person, the second, having 2 blue eyed people, the third having 3, and the fourth having 4. And lets say four gurus go to these islands and announce that they see a blue eyed person. On which day do the different blue eyed people on the different islands leave?

Basically, there is a difference between "I know you know I know you know" and "I know you know I know you know I know you know" and "I know you know I know you know I know you know I know you know". It usually doesn't come up in real life, but its there.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Adam H
Posts: 1267
Joined: Thu Jun 16, 2011 6:36 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Adam H » Thu Oct 09, 2014 1:53 pm UTC

chettski wrote:Sure, you can work out the logic for n=1, n=2, and extend to n=100. But there's a clear fallacy here, in that the visitor/guru gives non-common information only in the case of n=1 or 2, but not 3 or higher. The entire system breaks down if the visitor/guru gives already known information.
I'm not smart enough to explain this entire puzzle well, but I think I can make you see that it works for N=3 or 4.

This clicked for me when I imagined being the third person on the island with 2 blue eyed people. I would assume I don't have blue eyes, so for the other two people I don't matter. I'm nothing more than a tree to them. For them it would be the same problem as the easy N=2 problem. So then when they don't solve it as if it's the easy two person problem, I know that it's not the easy two person problem.

So it's solvable with N=3. What about N=4? If I'm on the island with 3 other people who I see have blue eyes, I assume I don't have blue eyes. Therefore the other three people are ignoring me and they'll be able to solve it just like it was N=3 (following the logic in my last paragraph). And again, when they don't solve it for N=3, I know that it's not the three person problem so there must be four blue eyed people on the island.

So it's solvable with N=4. What about N=5? Same thing, it just gets harder to follow. If you want to say that it's only solvable with 1-4 people but not 5-100 people, I'll let someone else argue with you. But it definitely works with at least some N>2.
-Adam

jdoege
Posts: 2
Joined: Fri Apr 22, 2011 4:21 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby jdoege » Thu Oct 09, 2014 2:13 pm UTC

This question starts by assuming the answer is generally correct regarding how the people/dragons come to the conclusion that they must leave the island/transform into birds. Setting that aside for the moment, what is it, exactly, about the guru's/visitor's words that start the clock ticking? Why, by the same logical process, didn't the dragons transform 100 days after they were first all present and could all see and know that all others saw (minus personal eye knowledge) the same thing?

rmsgrey
Posts: 3616
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Thu Oct 09, 2014 2:26 pm UTC

chettski wrote:Someone (I forget who) correctly observed that this is a faulty logic problem. I believe the true logic problem lies in recognizing the fallacy of the initial "logic problem," which most miss, since they're wrapped around extending n from 3 through 100. This reminds me of Marilyn Vos Savant (and a legion of mathematics professors and statisticians... including my late grandfather) getting the Monty Hall problem spectacularly wrong. The key in that problem (which most miss) is that the host gives new information 2/3rds of the time, leading to the "better odds if you switch."


Actually, in the standard Monty Hall problem, the host gives new information 100% of the time - which of the two remaining doors he picks - once he's picked a door, his then opening it tells you nothing. My information is that Marilyn got the problem right - that you're better off switching (when you assume that the host knows where the car is, must open a door other than your chosen one, and deliberately chooses a goat - other assumptions can produce different results).

In this problem, if you argue that there is some cutoff - that, say, with 1 or 2 blue-eyed islanders, they get new information from the guru's announcement, and depart on the first and second days respectively, but with 3 or more, there's no new information, so nothing can happen - then you run into a problem just above the cutoff. In this example, if there are 3 blue-eyed islanders, they know that if there were only 2 blue-eyed islanders when the guru spoke, then they'd both leave on the second day, they know from their observations that there are either 2 or 3 blue-eyed islanders, but when the other blue-eyed islanders don't leave on the second day, they somehow fail to connect those three facts.

Conclusion: either something prevents the islanders from evaluating a simple syllogism (in which case you should really say what that something is) or the guru's statement does provide new information after all. With 3 blue-eyed islanders, the information comes not from the content of the guru's statement, but from each of the 3 knowing that each of the other 2 knows that the other 1 heard the statement.

Call the 3 blue-eyed islanders A, B and C. Before the guru's statement:

A knows that there's at least one blue-eyed islander (B and C).
B knows that there's at least one blue-eyed islander (A and C).
C knows that there's at least one blue-eyed islander (A and B).
A knows that B knows that there's at least one blue-eyed islander (C).
A knows that C knows that there's at least one blue-eyed islander (B).
B knows that A knows that there's at least one blue-eyed islander (C).
B knows that C knows that there's at least one blue-eyed islander (A).
C knows that A knows that there's at least one blue-eyed islander (B).
C knows that B knows that there's at least one blue-eyed islander (A).
In fact, A knows that B knows that A knows that B knows that A knows that B knows that A knows that B knows that A knows that B knows that A knows that B knows that there's at least one blue-eyed islander (C).

What A doesn't know is that B knows that C knows that there's at least one blue-eyed islander because the blue-eyed islander B and C both know about is A, and A doesn't know that there's anything to know about himself.

When the guru makes his statement, what A learns isn't the content of the statement, nor that B knows the content of the statement, but rather that B knows that C knows the content of the statement. That's new information to A, and that's what makes it work for 3 blue-eyed islanders. With 4 blue-eyed islanders, A knows that B knows that C knows, and B knows that C knows that D knows, but A only finds out that B knows that C knows that D knows when the guru speaks (and only finds out that it wasn't new information to B when B doesn't leave on the third day).

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby jaap » Thu Oct 09, 2014 3:55 pm UTC

I find this puzzle fascinating as it really shows how difficult the concept of common knowledge is.

100 blue-eyed islanders, two of which are labelled A and B.
A and B both see 99 blue-eyed people. It is obvious though that this is not common knowledge.
It is almost as obvious that it is common knowledge that they both see at least 98 blue-eyed people. You can imagine A and B standing together looking at the other 98, both seeing the same thing, and both knowing that the other sees the same thing.

Now with 3 islanders- A, B, and C.
From the above it is common knowledge between any two of them that they each see at least 98 blue-eyed people. These are however not the same 98 people for every pair, so the knowledge that one pair shares is not the same as the knowledge shared by another pair. You can however say that it is common knowledge amongst all 3 of them that they can all see at least 97 blue-eyed people, as you can imagine them all looking at the other 97 people simultaneously and knowing that they all see exactly the same thing.

It is all too easy to make the mistake here to assume that seeing 98 blue-eyed people is common knowledge amongst A, B, and C, but that is like some people agreeing that "Michael is a great basketball player" but all thinking of a different person called Michael. It is only illusory common knowledge.

I think this is why people often think it short-circuits once you get to three or four people.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Thu Oct 09, 2014 10:18 pm UTC

jdoege wrote:This question starts by assuming the answer is generally correct regarding how the people/dragons come to the conclusion that they must leave the island/transform into birds. Setting that aside for the moment, what is it, exactly, about the guru's/visitor's words that start the clock ticking? Why, by the same logical process, didn't the dragons transform 100 days after they were first all present and could all see and know that all others saw (minus personal eye knowledge) the same thing?

The question doesn't assume anything. All of the information we have been discussing can be deduced logically - rmsgrey did a great job two posts up explicitly stating all of the known information in the 2- and 3-person cases, and the specific fact that the guru's statement adds to the pool of known facts. Those of us who have been involved with this thread for years say things like "start the clock" but there really isn't one. We're not trying to say that there is a timer that begins when the guru speaks, and that everyone is just waiting until "their day". Rather, once the guru speaks every day that no one leaves sees the islanders eliminating additional hypothetical situations until they can conclude with certainty their own eye color. Granted, the islanders know that nobody will leave on days 1-98, but they can't be sure that all of the other islanders know the same...

Let's imagine an island on which everyone is brought together, blindfolded, and one day everyone's blindfold is removed. They can all see each other. No one speaks, and no tricky stuff happens. Can any of them ever deduce with certainty their eye color, without someone providing some more information? Imagine one of those islanders has red eyes - how would he ever know? Let's simplify even more - what if you had a single person on an island. Would he ever be able to deduce his eye color without more information? In a manner of thinking, this is the situation each of those 100 islanders faces, because his eye color might be independent of the eye colors of all of his neighbors. The guru must add new information in the one-person situation, and nobody seems to question the logical leap in the two-person situation. This is far less obvious when there are 100 people, and yet there is definitely a quantifiable datum being transmitted.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby jestingrabbit » Thu Oct 09, 2014 10:29 pm UTC

jdoege wrote:This question starts by assuming the answer is generally correct regarding how the people/dragons come to the conclusion that they must leave the island/transform into birds. Setting that aside for the moment, what is it, exactly, about the guru's/visitor's words that start the clock ticking? Why, by the same logical process, didn't the dragons transform 100 days after they were first all present and could all see and know that all others saw (minus personal eye knowledge) the same thing?


The answer is actually pretty tricky. Speaking only of the blue eyed people, they can say of one another "I know that you can see 99 blue eyed people" and "I know that you know that I can see 98 blue eyed people". And, as we keep adding "know" layers, we reduce the minimum possible blue eyed people. Well, there's a point where the number of blue eyed people hypothetically known to exist becomes 0. When the guru speaks, this lowest layer of hypothetical changes.

Gwydion wrote:The question doesn't assume anything.


I think they were just meaning that they were assuming the answer was mostly right, and they couldn't understand what information was being transmitted.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

rmsgrey
Posts: 3616
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Thu Oct 09, 2014 10:55 pm UTC

jestingrabbit wrote:The answer is actually pretty tricky. Speaking only of the blue eyed people, they can say of one another "I know that you can see 99 blue eyed people" and "I know that you know that I can see 98 blue eyed people". And, as we keep adding "know" layers, we reduce the minimum possible blue eyed people. Well, there's a point where the number of blue eyed people hypothetically known to exist becomes 0. When the guru speaks, this lowest layer of hypothetical changes.


Your numbers are a little inconsistent - for me to know that you can see 99 blue-eyed people, there must be 99 other blue-eyed people, and you and me (101 total), but you would also know that I can see those 99 other people, so I know that you know that I can see 99 people, not just the 98 you credit me with knowing you know I can see - you have to bring a third person into the chain to reduce the number of people known to have blue eyes by the person at the end of the chain...

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby jestingrabbit » Fri Oct 10, 2014 4:16 am UTC

rmsgrey wrote:
jestingrabbit wrote:The answer is actually pretty tricky. Speaking only of the blue eyed people, they can say of one another "I know that you can see 99 blue eyed people" and "I know that you know that I can see 98 blue eyed people". And, as we keep adding "know" layers, we reduce the minimum possible blue eyed people. Well, there's a point where the number of blue eyed people hypothetically known to exist becomes 0. When the guru speaks, this lowest layer of hypothetical changes.


Your numbers are a little inconsistent - for me to know that you can see 99 blue-eyed people, there must be 99 other blue-eyed people, and you and me (101 total), but you would also know that I can see those 99 other people, so I know that you know that I can see 99 people, not just the 98 you credit me with knowing you know I can see - you have to bring a third person into the chain to reduce the number of people known to have blue eyes by the person at the end of the chain...


Ah, right you are. But the point about eventually not being able to assume that a hypothetical person hypothesizing a person who is hypothesizing a person... can see a blue eyed person stands. It just happens one level earlier than I wrote.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

GrandOpener
Posts: 3
Joined: Sun Oct 19, 2014 6:05 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby GrandOpener » Sun Oct 19, 2014 6:40 pm UTC

Hey guys and gals. Forgive me if I say some silly things here, since I am new to this puzzle. I have read the objections and responses thread and I think I agree with everything there. There is still one little thing that is bothering me. I've probably made a mistake considering how long you guys and gals have been discussing this, but I can't figure it out.

For the inductive solution to work, the last two sentences of the first paragraph establish that it is common knowledge that every islander has performed an accurate count of visible eye colors. As an islander, if your eyes are blue, you will know that anyone who performs a count of eyes will know that there are between 98 and 100 blue eyed islanders. If your eyes are non-blue, you know that everyone who counts will count between 99 and 101. The first paragraph also establishes that it is common knowledge that everyone is a perfect logician, thus it is common knowledge that everyone has made this same conclusion. Thusly, it is common knowledge that there are at least 98 blue eyed islanders.

I suspect someone will tell me I'm misunderstanding "common knowledge" and that this situation cannot recurse infinitely. However, for you--as an islander--it is common knowledge that everyone has counted, and you know with absolute certainty that it is not possible for anyone to count less than 98, so it seems to me that should mean everyone counted at least 98 is common knowledge. Everyone does know that everyone knows, ad infinitum, because the perfect logicians know that it is not possible to come up with any other count. Induction is not required for that particular conclusion, because it is immediately available. I keep coming back to the fact that it is common knowledge that everyone has performed an accurate count, and I can't figure out how to get around that to make the island a steady state prior to the guru speaking.

(For the sake of clarity, I am not debating the inductive solution. I think it is both clever and correct. I just cannot figure out how the island could be in a steady state prior to the guru speaking.)

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby jestingrabbit » Sun Oct 19, 2014 11:26 pm UTC

GrandOpener wrote:(For the sake of clarity, I am not debating the inductive solution. I think it is both clever and correct. I just cannot figure out how the island could be in a steady state prior to the guru speaking.)


(Its not really induction, or it needn't be, but lets try to answer your question.)

You don't know your eye colour. You arrive on an island and see some people with blue and brown eyes, with the island rules being shown to you on a pamphlet as you arrive. Later, more people arrive on the island, some with blue eyes, and some with brown, all given the pamphlet.

At what point, or under what circumstances, would you feel that you can conclude that you don't have green eyes?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

GrandOpener
Posts: 3
Joined: Sun Oct 19, 2014 6:05 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby GrandOpener » Mon Oct 20, 2014 2:27 am UTC

jestingrabbit wrote:You don't know your eye colour. You arrive on an island and see some people with blue and brown eyes, with the island rules being shown to you on a pamphlet as you arrive. Later, more people arrive on the island, some with blue eyes, and some with brown, all given the pamphlet.

At what point, or under what circumstances, would you feel that you can conclude that you don't have green eyes?


Okay, let me try to disprove my own theory then. First, let's suppose that the blue eyed people show up first. My reasoning would have been this:
GrandOpener wrote:1. Person A shows up. He can't see anything, so he sticks around.
2. Person B shows up. They both end up in the same situation: they each see one person with blue eyes, but don't know what the other person sees. Each of them knows that there is at least one blue eyed person, but they can't be sure the other knows that, so they stick around.
3. Person C shows up. Each person now sees two blue eyed people. Each person can conclude that even if their own eyes are non-blue, it is now guaranteed that every person on this island sees at least one person with blue eyes. Person C knows without a doubt that person B knows that person A knows that person C knows that there is at least one person with blue eyes, because it is not possible for anyone on this island to see less than one person with blue eyes and because it is common knowledge that everyone will make a conclusion that can be made with available facts. Three days later, if no one else shows up, they all leave together.


But having worked through it just now, I realize that's not exactly right. If we suppose now that Person C has brown eyes, Person C's observations are exactly the same as above, however Person A and Person B each only see one blue-eyed person, and thus they cannot conclude that everyone sees a blue eyed person. So in actuality, Person C doesn't know that Person A knows that Person B can definitely see a blue eyed person. Person C can't assume that "the timer" has been started for A and B, so he won't leave on day three. Persons A and B, with slight rearrangements of the letters, will make exactly the same conclusions and also stay.

So three blues can be steady state, but what happens with Person D shows up?

He knows that Person C can see either 2 or 3 blue eyes. He knows that Person C knows that Person B can see at least 1-2 blue eyes, but he doesn't know what Person C knows that Person B knows about his own eyes.

Okay, nevermind then, I get it. I see where that is going. I guess I didn't originally understand objection #2 as well as I thought I did. Thanks for making me work it out. :)

rmsgrey
Posts: 3616
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Mon Oct 20, 2014 1:33 pm UTC

GrandOpener wrote:For the inductive solution to work, the last two sentences of the first paragraph establish that it is common knowledge that every islander has performed an accurate count of visible eye colors. As an islander, if your eyes are blue, you will know that anyone who performs a count of eyes will know that there are between 98 and 100 blue eyed islanders. If your eyes are non-blue, you know that everyone who counts will count between 99 and 101. The first paragraph also establishes that it is common knowledge that everyone is a perfect logician, thus it is common knowledge that everyone has made this same conclusion. Thusly, it is common knowledge that there are at least 98 blue eyed islanders.

I suspect someone will tell me I'm misunderstanding "common knowledge" and that this situation cannot recurse infinitely. However, for you--as an islander--it is common knowledge that everyone has counted, and you know with absolute certainty that it is not possible for anyone to count less than 98, so it seems to me that should mean everyone counted at least 98 is common knowledge. Everyone does know that everyone knows, ad infinitum, because the perfect logicians know that it is not possible to come up with any other count. Induction is not required for that particular conclusion, because it is immediately available. I keep coming back to the fact that it is common knowledge that everyone has performed an accurate count, and I can't figure out how to get around that to make the island a steady state prior to the guru speaking.


Yeah, the mistake here is that you're not taking account of what people don't know about what other people do know - if I know that you see 98-99 blue-eyed islanders, so know the true count is 98-100, I don't know whether you see 98 and think that blue-eyed Fred over there might only see 97. The common knowledge you, me and Fred share is that the other 97 all have blue eyes, but, by including Fred, we're already below 98. If we then add Barney (who also has blue eyes) to our group, the common knowledge among the four of us is that the other 96 have blue eyes. And so on...

GrandOpener
Posts: 3
Joined: Sun Oct 19, 2014 6:05 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby GrandOpener » Mon Oct 20, 2014 11:42 pm UTC

There are two things that made it harder for me to understand the explanation that I think could be stated more clearly. (Or perhaps just more in line with my own thinking patterns.) Regardless, I'll leave them here with the hope that my contributions add something to the conversation.

The "everyone knows [repeat]" phrasing is correct, but mind bending. Stating that people are interchangeable, and thus I only need an individual chain of I know person X knows that person Y knows..., rather than a full web of everyone, everyone, everyone, makes it much easier to think about. (And then whatever conclusion about that single chain can be made about every possible chain, since people are interchangeable.)

Secondly, thinking about the problem in terms of common knowledge is very difficult. It's like reasoning what happens after the guru speaks coming from the direction of the situation with 100 rather than the situation with 1. Instead, it was much more useful for me to think about the "contagion of uncertainty" than about the knowledge. Specifically, when I consider what people know, I cannot be certain about my eye color. When I consider what I know person X knows, I cannot consider my eye color since I don't know what it is, and I cannot consider his color, since he doesn't know what it is. This creates a very straight-forward iterative chain, very similar in concept to starting with what would happen on the island after the guru speaks if only one islander had blue eyes. Once you understand the "contagion of uncertainty," it's fairly straightforward to see that there will be uncertainty about everyone's eye color when considering what is common knowledge among all islanders.

Thanks again for the lively discussion.

islandcolumbo
Posts: 3
Joined: Tue Oct 21, 2014 2:46 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby islandcolumbo » Tue Oct 21, 2014 3:26 am UTC

Hi guys, I'm totally new here and just seriously engaged with this puzzle a few days ago although I had seen the page at xkcd some time ago. I finally understood the top-down solution of nested hypothetical (I believe) at least, almost, I am sure the answer to my question can be found someplace in this massive thread but I just hope someone can explain this point to me or link me to the correct page or reply.

so, there's just one more thing

1.) The moment after The guru has spoken, after all the islanders have resolved to wait for day N+1 where N = the number of blue eyed persons they directly observe. They have convinced themselves that this is valid in part because there can be no fewer than N and more then N+1 blue-eyed islanders present.

2.) Every blue eyed person present knows the possible totals of blue-eyed persons are 99 and 100 depending upon their own eye color.

3.) Any person present who sees only 98 blue eyed persons must themselves have blue eyes.

Therefor any person present who sees only 98 blue eyed persons knows his own eyes are blue and will leave at once.

This of course does not happen, but the 100 leave the 2nd day.

brenok
Needs Directions
Posts: 507
Joined: Mon Oct 17, 2011 5:35 pm UTC
Location: Brazil

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby brenok » Tue Oct 21, 2014 11:06 am UTC

Why would someone see only 98 blue eyes?

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby phlip » Tue Oct 21, 2014 12:32 pm UTC

islandcolumbo wrote:2.) Every blue eyed person present knows the possible totals of blue-eyed persons are 99 and 100 depending upon their own eye color.

3.) Any person present who sees only 98 blue eyed persons must themselves have blue eyes.

The thing is, we only know these because we can see 99 blue-eyed people. Any hypothetical person who sees 98 blue-eyed people would not know this, and therefore would not be able to deduce that their eyes are blue. Thus the fact that no-one leaves immediately does not tell us that everyone else sees a 99th blue-eyed person.

Generally speaking, if you're going to try to argue that they should leave on day 2, or any other time earlier than day 100, then answer this:
(1) According to your logic, if there are 100 blue-eyed people on the island, what should happen?
(2) According to your logic, if there are 99 blue-eyed people on the island, what should happen? Are they leaving on the same day as in the 100-person case?
(3) If there are 100 blue-eyed people on the island, and I am one of them (so I can see 99 blue-eyed people) then what should I be thinking? How do I deduce my eye colour and leave?
(4) IF there are 99 blue-eyed people on the island, and I am not one of them (so I can see 99 blue-eyed people) then what should I be thinking? How do I not incorrectly deduce that my eye colour is blue, given I see the same thing as the previous case?

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

islandcolumbo
Posts: 3
Joined: Tue Oct 21, 2014 2:46 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby islandcolumbo » Tue Oct 21, 2014 2:31 pm UTC

so we have an islander

1.) I reasoned from the top down, I determined that anyone who sees N blue-eyed persons is now equipped to leave on ferry number N + 1, trusting that the hypothetical who saw one would leave on the first, the hypothetical who saw 50 would leave on the 50th etc. I myself need only wait for the 100th (or 101st) and then I can depart.

2.) But I can not just go ahead and create a hypothetical tonight, who knows all that I know, and seeing only 98 (or 99 in the case of the browns) would leave tonight.

so somehow, and this is what i'm stuck on, they all know they can not fully trust their own hypotheticals, and yet they do fully trust hypotheticals created by the othres.

* 1 should read *who saw zero would leave on the 1st *who saw 49 would leave on the 50th a typo

islandcolumbo
Posts: 3
Joined: Tue Oct 21, 2014 2:46 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby islandcolumbo » Tue Oct 21, 2014 3:46 pm UTC

Nevermind, I think I finally get it:

A hypothetical copy of islander 2 is created by islander 1 with only the information that islander 1 is certain is true and is certain that islander 2 has access to.

Islander 1 is aware that islander 2 never has access to any accurate upper bound, even tho islander 1 always has access to an accurate maximum, he never passes that information to his hypothetical copies of a person who may not know that information.

However he does know that islander 2 will indeed have access to an accurate lower bound equal to the 1 blue-eyed islander the guru has told them all exists plus the number of ferries that have departed since, and so he does pass that accurate lower bound to his hypothetical copies of islanders.

So on the first night no islander will create a hypothetical who is aware of any maximum, he will only tell them what they can see and that the lower bound is 1.

The hypothetical trusted to leave on the 50th ferry is not doing so because he is aware that the maximum is N + 1, he is doing so because he is aware the minimum is 1 plus 49.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby douglasm » Thu Oct 23, 2014 4:59 am UTC

It sounds like you've already figured it out, but here's another thing to consider for any conceivable shortcutting scheme:
If N blue-eyed people would leave on day D where D is not 1, it must be because N-1 people would leave on day D-1, as that's the only way for waiting a day to eliminate the N-1 case from consideration. Plug N-1 and D-1 in for N and D, and you get that N-2 people would leave on day D-2. Repeat enough times, and you'll eventually get that N-D+1 people would leave on day 1. If D < N, then this means that the Guru's statement is enough for a group larger than 1 to leave immediately without waiting at all, which is clearly absurd. Thus, no shortcut scheme is possible and D must at least equal N.

Skittles3074
Posts: 1
Joined: Fri Oct 24, 2014 5:15 am UTC

Blue Eyes: The Hardest Logic Puzzle...

Postby Skittles3074 » Fri Oct 24, 2014 5:20 am UTC

One thought on this puzzle. One item that led me astray was the part that says they could not communicate. Therefore, if no one could hear the guru's assertion, no one would leave the island. It's a silly little thing, but perhaps the clarification that the logicians can make use of the guru's claims would be helpful.

elwood
Posts: 12
Joined: Thu Sep 13, 2012 11:03 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby elwood » Fri Oct 24, 2014 2:06 pm UTC

So, I've been reading this entire thread for some time. I love this puzzle, I was familiar with it and the inductive solution before, and thanks to the xkcd version (and the discussion around here) I also managed to appreciate the "common knowledge" or "nested hypotheticals" explanation. Now, I'm about 15 pages into the thread mining for further insights, and ran into this gem:

Back in 2009, Tomace wrote:Suppose the guru had said "I see at least one person with blue eyes: that person there <points>, he has blue eyes". In this case I think the only person who would leave the island would be the person at whom the guru pointed. Yet it is still common knowledge that at least one person has blue eyes. This seems rather paradoxical to me, that by providing more information, the guru would actually allow fewer islanders to deduce their own eye colour.

Am I correct? If so, what is the best way of describing the quantifiable piece of information that the guru imparts (and how that information is changed under my scenario)? If not, why not?


Here is the thing: in the original puzzle, every islander thinks, after the Guru's statement,

Spoiler:
"There is one person with blue eyes that she is talking about, and that person could be me."


And in addition, everyone knows [that everyone knows etc.] that everyone else is thinking the same. In Tomace's version, we lose that emphasised bit. The Guru's statement is more specific, but it is less informative*. What's important is that the Guru's statement cannot any longer be used for inference. Another way to view it is that the base case of the induction no longer works.

[EDIT: Ha! the base case works, it is actually the inductive step that fails!]

The funny thing is that the existence of blue eyes does become common knowledge among islanders after the Guru's announcement. It is still the case that everyone knows [that everyone knows... to any level] that there is at least one person with blue eyes. But when you work out the nested hypotheticals, you need that statement spoilered above, which is implicit in the original version, and missing in Tomace's variant.

And for completeness, from the point of view of the person the Guru pointed to: he cannot assume that his eyes may not be blue (and everyone knows that he can't), so the chain of hypotheticals breaks down when it reaches him.

* Actually, can we say whether it is more or less informative? I don't think you can render a proposition less informative by adding clauses to a conjunction. Right?

(and well, you know, I apologise for having read only half of the thread before commenting, someone might have made the same remarks before)
Last edited by elwood on Fri Oct 24, 2014 3:19 pm UTC, edited 1 time in total.

Ralp
Posts: 25
Joined: Sat Dec 16, 2006 9:44 am UTC
Location: internet
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Ralp » Fri Oct 24, 2014 2:36 pm UTC

The guru's statement is more informative in that case, but in the original problem, most of the villagers' information comes from observing every night whether anyone has left or not (or rather, knowing that everyone now knows that everyone knows [...] that everyone has observed whether anyone has left). I think every night that passes gives them just as much new information as the guru's initial statement. But when the guru points to THAT dude, he winds up leaving immediately just by the special rule of the puzzle's premise, so the rest of the villagers don't get the opportunity to gain more info through the whole process.

elwood
Posts: 12
Joined: Thu Sep 13, 2012 11:03 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby elwood » Fri Oct 24, 2014 3:12 pm UTC

Ralp wrote:I think every night that passes gives them just as much new information as the guru's initial statement.


I don't know if that's easily quantifiable, but you're right, in the original we have:

Guru speaks: "At least one blue-eyed person" becomes common knowledge.
Next day: "At least two blue-eyed people" becomes common knowledge.
Third day: "At least three blue-eyed people" becomes common knowledge.
Etc.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Yakk » Fri Oct 24, 2014 3:15 pm UTC

Look at the situation with one blue eyed person, Bob, and two blue eyes people, Bob and Alice.

"I see someone with blue eyes". If Alice has brown eyes, Bob looks around, realizes he has blue eyes, and leaves the first night. Everyone else now knows Bob saw no blue eyes, so leaves the second night.

If Alice has blue eyes, Bob does not leave the first night. The second night both Bob and Alice know that the other party saw someone with blue eyes. And it must be them. So they both leave the second night. And everyone else follows on night 3.

"I see someone with blue eyes, and it is Bob right there". Bob leaves the first night regardless of if Alice has blue eyes, so no information is passed to Alice by Bob leaving the first night. So Alice cannot leave the second night.

By telling Bob he has blue eyes (and not just "someone"), the rest of the island learns less from Bob's behavior than they would by Bob learning "someone has blue eyes".

Bob gets more information from "Bob has blue eyes", but the rest of the island does not.

Amusingly, if the Guru told Bob and everyone else "someone has blue eyes" and then in secret told everyone else "that someone I'm talking about is Bob"... I think the recursion works. Except that the possibility of secret communication opens up a whole new can of worms.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

rmsgrey
Posts: 3616
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Fri Oct 24, 2014 3:30 pm UTC

Yakk wrote:Look at the situation with one blue eyed person, Bob, and two blue eyes people, Bob and Alice.

"I see someone with blue eyes". If Alice has brown eyes, Bob looks around, realizes he has blue eyes, and leaves the first night. Everyone else now knows Bob saw no blue eyes, so leaves the second night.


So when do the green-eyed people leave?

elwood
Posts: 12
Joined: Thu Sep 13, 2012 11:03 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby elwood » Fri Oct 24, 2014 3:42 pm UTC

Yakk: brown-eyed people never leave. They would have to know that brown is the only alternative, and they don't know that.

Otherwise, yeah, I agree.

Ralp
Posts: 25
Joined: Sat Dec 16, 2006 9:44 am UTC
Location: internet
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Ralp » Fri Oct 24, 2014 8:49 pm UTC

elwood wrote:
Ralp wrote:I think every night that passes gives them just as much new information as the guru's initial statement.


I don't know if that's easily quantifiable, but you're right, in the original we have:

Guru speaks: "At least one blue-eyed person" becomes common knowledge.
Next day: "At least two blue-eyed people" becomes common knowledge.
Third day: "At least three blue-eyed people" becomes common knowledge.
Etc.


Exactly, thank you. I wasn't completely comfortable with my "as much as" claim either, but the list you have there perfectly expresses the concept I was trying to get at.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Fri Oct 24, 2014 9:47 pm UTC

Yakk wrote:Amusingly, if the Guru told Bob and everyone else "someone has blue eyes" and then in secret told everyone else "that someone I'm talking about is Bob"... I think the recursion works. Except that the possibility of secret communication opens up a whole new can of worms.
This is definitely not the case. If the Guru told the whole island that someone had blue eyes, and then told n-1 islanders that Bob was the one she was talking about, none of the n-1 islanders have learned any new facts about the island. Among those n-1 islanders, it was already common knowledge that Bob has blue eyes; this has not changed. Bob was not privy to that information, so he also has not learned anything new. However, the inductive step also fails.

The existence of secret information is fairly straightforward - if secret information is a possibility, then the fact that people leave or don't fails to communicate data to the other islanders. The puzzle needs the statement that all of the given information about the puzzle is common knowledge, or else it is impossible to conclude anything with certainty about the behavior of the other islanders. If someone can directly deduce from the secret information available to them that they have blue eyes (for example, being told that they have blue eyes, being told that a blue eyed person exists in a group containing themselves and only brown eyed people), they leave. If not, they can not use another islander's failure to leave as a source of new information, because they can't perfectly put themselves in the mind of another islander.

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby phlip » Sat Oct 25, 2014 1:42 am UTC

No, I think the recursion still works... The base case is still the same (if there's only one blue-eyed person, then a "Secret announcement to all the other blue-eyed people" is vacuous and changes nothing), and the inductive case still works (if n blue-eyed people would leave on night n, then n+1 blue-eyed people must be able to leave on night n+1, by seeing no-one leave on night n and ruling out that case).

Gwydion wrote:Among those n-1 islanders, it was already common knowledge that Bob has blue eyes; this has not changed.

Sure, but the existence of blue-eyed people wasn't common knowledge among all n blue-eyed islanders before, and it is after... this still isn't different to the original puzzle.

Gwydion wrote:The existence of secret information is fairly straightforward - if secret information is a possibility, then the fact that people leave or don't fails to communicate data to the other islanders.

Not quite. Information is cumulative. If A and B implies Z, then if you know A and B and C you can still deduce Z. If you know A and B and C and D, you can still deduce Z. And so, if I know you know A, and I know you can't deduce Z, then I must be able to deduce you don't know B, even if you could possibly know C or D.

And so, people failing to leave does still communicate information... as the puzzle states, if any person is able to deduce their eye colour, they will leave. The possibility of secret information prevents people from deducing things from people actually leaving, but people failing to leave still communicates information.

It's why I hold that, even if you added to the puzzle that it's common knowledge that everyone's eyes are either blue or brown, the brown-eyed people still wouldn't leave immediately after the blue-eyed people do... they can't deduce that their eyes aren't blue because they don't know for certain that the other blue-eyed people don't have additional info... the puzzle says that the islanders don't have additional info, but that's not in the "this is common knowledge" paragraph. But even with people taking into account the possibility that other islanders have additional information, the main solution still works, and the blue-eyed islanders still leave.
Last edited by phlip on Sat Oct 25, 2014 2:00 am UTC, edited 2 times in total.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Yakk » Sat Oct 25, 2014 1:43 am UTC

However, Bob does not know what the rest of the island knows. So Bob leaves the island on day N, where there are N-1 other blue eyed people -- Bob follows the logic that everyone else would have, absent the "Bob is the one with blue eyes".

On day N-1, if Bob is present and you see N-2 other blue eyed people plus Bob, you know your eyes are blue, so you can leave on day N. On day N-1, you see N-1 other blue eyed people and Bob, you are not surprised Bob did not leave.

When Bob and every other blue eyed person leaves on day N, you now know your eyes are not blue.

In short, the other islanders can extract the needed information from Bob, so long as Bob does not know that Bob is the one with blue eyes, even if they themselves are privy to the fact that Bob is the one with blue eyes.

This, however, requires deception: Bob must not know that the other islanders where told something in secret, so Bob is reasoning incorrectly about the other islander's state of mind.

Admitting the possibility of such secret knowledge breaks the inductive step. So Bob must be absolutely deceived with regards to what the rules are somehow.

And the possibility that Bob was deceived, and yet is certain that he was not, means that the rest of the islanders must presume that their certainty that they themselves are knowing everything about what is going on and Bob's mental process must be limited by the fact that an otherwise identical islander was deceived, and yet was certain that they where not.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

narrativium
Posts: 9
Joined: Fri Sep 12, 2014 11:18 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby narrativium » Sat Oct 25, 2014 2:10 am UTC

A given blue-eyed person, called X, sees 99 blue-eyed people. X doesn't know if X is blue-eyed, but they know the minimum number of blue-eyed people is at least 99. This is true of all X.
A given blue-eyed person that X can see, called Y, sees either 98 blue-eyed people if X isn't blue-eyed, or 99 if X is. This is true for all Y.
If X isn't blue-eyed, Y will be determining what a given next person - called Z - can see, which is 97 if Y isn't blue-eyed and 98 if Y is. Or, if X is blue-eyed, Z can see 98 blue-eyed people if Y isn't blue-eyed, and 99 if Y is.
If X has blue-eyes, as Y does, they are seeing the same information and would leave on the same day, but they have to be able to agree on the same minimum number of blue-eyed people there could be to do so. A non-blue-eyed person sees one more blue-eyed person than a blue-eyed person does, so if a blue-eyed person leaves then they'll know the day after that they can stay... but they'll never know when to leave unless there's a consensus on how many blue-eyed people everyone can see at minimum.
So what minimum number of people can everyone know that everyone knows has blue eyes, without communicating?

What everyone's doing, by waiting until the 100th day, is counting up to the minimum number of people with blue eyes. If on the nth day blue-eyed people are still around, everyone reaches the consensus that the minimum number of blue-eyed people is at least n. On the morning of day 100, every blue-eyed person will simultaneously know that the consensus is more than the number it would be if they didn't have blue-eyes, so it's time to go.

If, on day 101, no blue-eyed person had actually left, each brown-eyed person would assume the set of blue-eyed people now included them, and they would all leave.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Sat Oct 25, 2014 5:34 am UTC

phlip wrote:No, I think the recursion still works... The base case is still the same (if there's only one blue-eyed person, then a "Secret announcement to all the other blue-eyed people" is vacuous and changes nothing), and the inductive case still works (if n blue-eyed people would leave on night n, then n+1 blue-eyed people must be able to leave on night n+1, by seeing no-one leave on night n and ruling out that case).

Gwydion wrote:Among those n-1 islanders, it was already common knowledge that Bob has blue eyes; this has not changed.

Sure, but the existence of blue-eyed people wasn't common knowledge among all n blue-eyed islanders before, and it is after... this still isn't different to the original puzzle.

Gwydion wrote:The existence of secret information is fairly straightforward - if secret information is a possibility, then the fact that people leave or don't fails to communicate data to the other islanders.

Not quite. Information is cumulative. If A and B implies Z, then if you know A and B and C you can still deduce Z. If you know A and B and C and D, you can still deduce Z. And so, if I know you know A, and I know you can't deduce Z, then I must be able to deduce you don't know B, even if you could possibly know C or D.

And so, people failing to leave does still communicate information... as the puzzle states, if any person is able to deduce their eye colour, they will leave. The possibility of secret information prevents people from deducing things from people actually leaving, but people failing to leave still communicates information.

It's why I hold that, even if you added to the puzzle that it's common knowledge that everyone's eyes are either blue or brown, the brown-eyed people still wouldn't leave immediately after the blue-eyed people do... they can't deduce that their eyes aren't blue because they don't know for certain that the other blue-eyed people don't have additional info... the puzzle says that the islanders don't have additional info, but that's not in the "this is common knowledge" paragraph. But even with people taking into account the possibility that other islanders have additional information, the main solution still works, and the blue-eyed islanders still leave.

An island with a single islander is not a valid base case for induction, when discussing "another islander". This is the flawed logic behind the famous inductive proof that all horses are the same color. However, this still works out for the two person case so it doesn't take away from your point. That's a nice illustration about the cumulative nature of information - helps to clarify things. Objection withdrawn.

rmsgrey
Posts: 3616
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Sat Oct 25, 2014 1:49 pm UTC

Gwydion wrote:An island with a single islander is not a valid base case for induction, when discussing "another islander". This is the flawed logic behind the famous inductive proof that all horses are the same color.


Actually, the version of that which I know relies on a faulty induction step rather than a faulty base case:

Base case: For each set of 1 horse, all horses in that set have the same coloration.

Induction step: Assume that for some n, for each set of n horses, all horses in that set have the same coloration. Take any set of n+1 horses. Removing any one horse, Silver, from that set gives you a set of n horses, all of which (by assumption) have the same coloration. Add Silver back into the set and remove a different horse, Beauty. The n horses including Silver all have the same coloration. Since both Silver and Beauty have the same coloration as the rest of the horses in the set, they must have the same coloration as each other, so, since this logic applies to any set of n+1 horses, each set of n+1 horses must contain only horses of the same coloration.

The trick here is that the highlighted portion is only valid when "the rest of the horses in the set" is a non-empty subset - everything up to that point is entirely true and/or valid, but when Silver and Beauty are the only two horses in the n+1 set, the logic fails - the base case is n=1; the induction step is only valid for n>1.

Okay, if you state the domain of validity for the induction step, then it stops being a faulty induction step, and becomes a mismatch between induction step and base case - which doesn't make the base case invalid for induction, merely for that particular induction step.

elwood
Posts: 12
Joined: Thu Sep 13, 2012 11:03 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby elwood » Wed Oct 29, 2014 1:22 pm UTC

phlip wrote:If A and B implies Z, then if you know A and B and C you can still deduce Z. If you know A and B and C and D, you can still deduce Z. And so, if I know you know A, and I know you can't deduce Z, then I must be able to deduce you don't know B, even if you could possibly know C or D.


What is seemingly paradoxical in the version where the Guru points specifically to Bob, is that apparently the implication is no longer valid. Say, for instance, A is "all prior knowledge of the islanders", B is "the Guru announced she can see someone with blue eyes" and C is "that someone is Bob". So A and B implies all that stuff that eventually gets the blue-eyed people off the island, whereas A and B and C does not.

The explanation being that B and C are not independent propositions (e.g. see that "someone" used in both - but it's not just a matter of wording) and there are some implicit conditions that hold for B alone but not for "B and C". In math terms, you need variables, quantifiers and predicates to express things unambiguously, and you are introducing ambiguity if you just try to move from predicate to propositional logic by using complex propositions without being careful.

EDIT: and by the way, philip, I notice you're around guarding sanity in the thread with people going "lololol why is everyone an idiot it obviously doesn't work with more than 5" every couple of pages? For, like, eight years now? Dude, you're awesome :D

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Yakk » Wed Oct 29, 2014 2:29 pm UTC

jestingrabbit wrote:Here's some fun questions for you to think about.
1. How can any of the islanders rule out having green eyes before the guru speaks?
2. Lets say there are 4 islands, with the first island having 1 blue eyed person, the second, having 2 blue eyed people, the third having 3, and the fourth having 4. And lets say four gurus go to these islands and announce that they see a blue eyed person. On which day do the different blue eyed people on the different islands leave?

Basically, there is a difference between "I know you know I know you know" and "I know you know I know you know I know you know" and "I know you know I know you know I know you know I know you know". It usually doesn't come up in real life, but its there.

This is a beautiful way to approach it.

There are 1001 islands, each with 1000 people.

You cannot see the islands from each other.

Each island has a number, but nobody knows what it is. The number goes from 0 to 1000.

On island #0, there are 0 people with blue eyes.
On island #1, there is 1 person with blue eyes.
On island #N, there are N people with blue eyes.

Islanders can see each other, but may not communicate with each other in any way. They all know each other to be perfectly rational, and they all know they are all playing the same game.

The Islanders, if they learn how many blue eyes there are on the island, are permitted to go to the dock at midnight and get on the boat and leave the island.

One day, 1001 gurus appear, one on each island. On island #1 to #1000, the guru says "I see at least one person with blue eyes on the island", then disappears.

On island #0, the guru says "I see nobody with blue eyes on the island" and disappears.

The islanders can completely trust the guru, and know what the guru would have said on each island by number, and that the guru visited every island.

The question is: can the people of island #100 ever leave, and if so, when? To work it out, work out if/when the people of island #1 can leave, and #2 and #3 etc.

---

Everyone on island #0 can leave the first night, as they now know there is nobody with blue eyes.

The blue eyed person on island #1 can leave the first night, as they can see they must have blue eyes. The brown eyed people can leave the second night.

On island #2, each of the blue eyed people do not know if they are on island #1 or #2. When the first night passes and the other blue eyed person does not leave, they now know they are on island #2, which means they have blue eyes! They leave the 2nd night. The rest of the island on the 3rd night.

On island #3, each of the blue eyed people do not know if they are on island #2 or island #3. On the second night, nobody has left. So on the 3rd night, they know they are on island #3, so the blue eyed people leave.

We can continue:

On island #N, N >1, each of the blue eyed people do not know if they are on island #N-1 or #N. Up to and including the N-1th night nobody leaves, which rules out them being on island #N-1, so they must be on island #N, which means they have blue eyes. So on night N they leave the island.

You can ask "why did it start the timer", but your inability to understand explanations does not mean it is invalid. The blue eyed people of island #N know that they are on #N or #N-1 by looking around (as they do not know if they have blue eyes, and can count). They can demonstrate that the blue eyed islanders on #N-1 would have left on night N-1 through a simple, finite argument (it does get long for large N, but it remains both simple and finite). So on day N, they have eliminated all other possibilities, thus they must have blue eyes, and can leave on night N.

It can be shown (though not that easily) that they could not figure out such a solution without the guru's aid, even through the guru said something seemingly useless to them.

The next step is to destroy all the islands but your own immediately after the guru speaks. Can the islanders on island #100 still leave?

The next step is to destroy all the islands but your own before the guru speaks. Can the islanders on island #100 still leave?

The next step is to make the other islands never have existed. Can the islanders on island #100 still leave?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby phlip » Thu Oct 30, 2014 11:12 am UTC

elwood wrote:What is seemingly paradoxical in the version where the Guru points specifically to Bob, is that apparently the implication is no longer valid. Say, for instance, A is "all prior knowledge of the islanders", B is "the Guru announced she can see someone with blue eyes" and C is "that someone is Bob". So A and B implies all that stuff that eventually gets the blue-eyed people off the island, whereas A and B and C does not.

That's my point though... it still does. At least, in the right conditions (ie, Bob doesn't know C).

In the normal puzzle, A and B and "B is common knowledge among all islanders" and "I can see 99 blue-eyed people (including Bob)" and "No-one left on night 99" implies "my eyes are blue".

In this variant, A and B and "B is common knowledge among all islanders" and C and "C is common knowledge among all non-Bob islanders" and "I can see 99 blue-eyed people (including Bob)" and "No-one left on night 99" still implies "my eyes are blue".

Adding extra information doesn't change the implication... (A -> B) |- ((A & X) -> B). What is relevant is whether those other conditions (particularly "No-one left on night 99") will still hold with the changed situation.

The short version is: given the structure of the proof (specifically the recursive "n-1 people would leave on night n-1, they didn't, so I must have blue eyes making it n people, and I'll leave at the next opportunity which is night n" proof), changing the situation by merely revealing additional information to the islanders (be that direct information in "Bob's eyes are blue" or meta-information in "I told Alice Bob's eyes are blue" or "the 'someone' I was talking about in my previous statement was Bob") can potentially make the islanders leave earlier (at which case the whole house of cards falls down), but it can't make them leave later, or not at all.

elwood wrote:EDIT: and by the way, philip, I notice you're around guarding sanity in the thread with people going "lololol why is everyone an idiot it obviously doesn't work with more than 5" every couple of pages? For, like, eight years now? Dude, you're awesome :D

Yeah... I'm not the only one who keeps coming back to this thread like a moth to a flame, but there's something about this particular brand of "wrong on the Internet" that keeps me coming back to beat my head against it again. But the very occasional "Oh, I get it now!" responses make it all worthwhile... I hope...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

marzis
Posts: 29
Joined: Fri Oct 17, 2014 5:19 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby marzis » Thu Oct 30, 2014 1:55 pm UTC

Hello everyone. I just want to quickly get out of the way the fact that I completely understand the common-knowledge based solution, the inability to know for certain that anyone on the island other than one's self that anyone else on the island knows for certain that there is at least 1 person on the island with Blue eyes, and how the Guru's statement "I can see at least one person with Blue eyes" leads to the establishment of a common-knowledge basis of 'at least 1' which then leads to all of the Blue eye'd people leaving on the 100th night (1st night is the one of the Guru's speaking). So, please don't bother trying to explain the common-knowledge aspect of things. My solution has nothing to do with it at all, and I'm fairly certain that if you try to use the common-knowledge solution to disprove mine, well, I won't get any further in understanding why my solution isn't correct (if it isn't) than I have so far on my own.

Here goes.

Initially, lets split the people on the island into three generic groups. A, B, and C. These groups are defined by their eye color, and everyone within the groups has the same eye color. I won't bother using Blue or Brown or Green anymore, because those are just arbitrarily chosen colors and can have no fundamental impact on the problem or solution.

Now, instead of bothering to assume to know what anyone else on the island can possibly know, we are going to look purely at what any one, single, individual can know, based entirely on their own eyes. This has nothing to do with common-knowledge, perfect-knowledge, or anything of that sort. It is simply looking at any one individual, wholly separate from everyone else on the island, and working out what that one individual can logically surmise based on what said individual can see. That is all.

What they can see:
Person A: 99 A, 100 B, and 1 C.
Person B: 100 A, 99 B, and 1 C.
Person C: 100 A, 100 B.

What they know:
Person A: 99 A, 100 B, 1 C, and one unknown (themselves).
Person B: 100 A, 99 B, 1 C, and one unknown (themselves).
Person C: 100 A, 100 B, and one unknown (themselves).

To reiterate the above: The line for Person A does not in any way assume to bother attempting to know or see, what the line for Person B will read. They are wholly uninterested with what anyone else on the island may or may not know or see.

What they can surmise:

Person A1: 99 A, 100 B, 1 C, and they themselves have eyes of A, thus 100 A, 100 B, 1 C.
Person A2: 99 A, 100 B, 1 C, and they themselves have eyes of B, thus 99 A, 101 B, 1 C.
Person A3: 99 A, 100 B, 1 C, and they themselves have eyes of X, thus 99 A, 100 B, 1 C, 1 X. (X in this case can be C, the function here is that X is NOT A or B).

Person B1: 100 A, 99 B, 1 C, and they themselves have eyes of A, thus 101 A, 99 B, 1 C.
Person B2: 100 A, 99 B, 1 C, and they themselves have eyes of B, thus 100 A, 100 B, 1 C.
Person B3: 100 A, 99 B, 1 C, and they themselves have eyes of X, thus 100 A, 99 B, 1 C, 1 X. (again, X is simply NOT A or B).

Taking, again, only what person A and B can surmise above, we can now take one further step, which does not depend on knowing with certainty that anyone on the Island can see anything, but rather, based on the above hypothetical situations that either person A or B have created, what can person A or B surmise about the other various participants in this hypothetical world?

I.e.,:
Person A1: Knows that if there are 100 A, 100 B, and 1 C, then: Every A will see: 99 A, 100 B, 1 C, and every B will see: 100 A, 99 B, and 1 C.
Person A2: Knows that if there are 99 A, 101 B, and 1 C, then: Every A will see: 98 A, 101 B, 1 C, and every B will see: 99 A, 100 B, and 1 C.
Person A3: Knows that if there are 99 A, 100 B, and 1 C, and 1 X, then: Every A will see: 98 A, 100 B, 1 C, and 1 X, and every B will see: 99 A, 99 B, and 1 C and 1 X.

Person B1: Knows that if there are 101 A, 99 B, and 1 C, then: Every A will see: 100 A, 99 B, 1 C, and every B will see: 101 A, 98 B, and 1 C.
Person B2: Knows that if there are 100 A, 100 B, and 1 C, then: Every A will see: 99 A, 100 B, 1 C, and every B will see: 99 A, 99 B, and 1 C.
Person B3: Knows that if there are 100 A, 99 B, and 1 C, and 1 X, then: Every A will see: 99 A, 99 B, 1 C, and 1 X, and every B will see: 100 A, 98 B, 1 C and 1 X.

No one in the situation above knows if they have A, B, or X, individually, just how 201 people on an island can be distributed based on a breakdown of 100/100/1 or 101/99/1/1.

As far as I can tell, so far, nothing in the above relies upon common-knowledge, as no one is attempting to know, with any ounce of certainty, that anyone else on the island knows anything else, since we are only working within a series of hypothetical compositions of the members of the island.

It is very important, I feel, to say that at this stage, no one on the island is any closer to leaving the island, nor at knowing which of the A1, A2, A3, or B1, B2, B3 situations above they fall into. But what they DO know, is this:

Person A: IF they have eye color X OR B, then: Everyone in group A can see 98 A.
Person B: IF they have eye color X OR A, then: Everyone in group B can see 98 B.

They know that they themselves are not members of said hypothetical group A or B listed above who can only see 98 A or 98 B, as they can see at least 99 of either A or B, but this still does not put them any closer to knowing their eye color, only what would be the reality of the distribution of the island based on their possible eye colors.

But what each islander individually knows, is relayed above. They should each, individually, be able to come to this conclusion on their own, without having to know with any certainty that anyone else on the island can come to that same conclusion. They don't care about what anyone else thinks, as they aren't of one mind or anything, they're just individuals observing and making conjectures about how the island might be distributed. So far I can't see how these assumptions above can depend on common-knowledge.

Smaller Island example: Three people on an island, 2 A (A' and A") and 1 B.
A' can see 1 A", 1 B. B can see 1 A' and 1 A".
If B has A, then A' and A" can see 2 A. If B has B, then A' can see 1 A" and 1 B. If A' has A, then A" can see 1 A' and 1 B. If A' has B, then A" can see 2 B. If A" has B, then A' can see 2 B. This may not be complete, but this is just to illustrate a point. They are not attempting to know anything, they are just laying out the various ways in which 3 people, of which they themselves are an unknown, can populate an island, and what each member of said island might see if any one of those combinations was the case.

Ok, onto the Guru.

If the various members of A and B can make the above conjectures about the distribution of the 201 members on the island, then it is logical to assume that, as they do so, so does the Guru (being a perfect logician as well).

And this is where I run into trouble with the common-knowledge solutions: They believe that the Guru's statement (as interpreted for the common-knowledge solution) is a logical one. [if the problem was built to be a common-knowledge exercise, then that's fine. but I don't know that]

If my above conjectures about the ways in which the respective A and B members of the island can surmise they are distributed is accurate, then our C would know those various ways as well, owing to the fact that she can see the 100 A and 100 B, and knows that any one of them doesn't know the color of their own eyes, and would subsequently surmise the various A1, A2, A3, and B1, B2, B3 possibilities that each respective A or B individual could. She would know also that she can speak, can speak only once, and that no one else on the island can speak, and of course, knows that she herself is a perfect logician, along with everyone else on the island.

So the Guru, knowing all this, decides to provide information only to one group of people (in the original: the Blue eyed people)? Decides, somehow, to choose A and not B? How is this logical? She has chosen to give information that, while being applicable to every Blue eyed person, is wholly irrelevant to every Brown eyed person. Every Brown eyed person can do nothing with the information she gives, AS INTERPRETED, in the common-knowledge solutions. And to me, this feels wrong, since I cannot find a logical way in which to say 'A' instead of 'B'.

And so we come to my interpretation of the Guru's statement, given all that she can see, and all that she has surmised along with the various members of A and B.

The Guru can provide, as referenced by either an A, or a B, person, 3 pieces of information.

Information 1: They have A color eyes.
Information 2: They have B color eyes.
Information 3: They have X color eyes. (This is equivalent to: 'They do not have A or B color eyes' as X is defined as not A or B)

These are the three possibilities that everyone on the island knows to be the case. Each person on the island can see everyone else, so, individually, they know that the only piece of information they need is their OWN eye color. They don't need to know that everyone else on the island knows what everyone else on the island knows. They just need the answer to their own, individual, selfish, isolated question, which is: What color are my eyes?

The Guru knows this, and says "I can see at least one person with Blue eyes."

The members of A and B instantly start to process this information relative to their three questions. Has the Guru provided Information 1? Information 2? Information 3? No. She has answered a question they were uninterested in, if they have Brown eyes, according to the common-knowledge solution.

My analysis of the Guru's statement is as follows:

The Guru is incapable of an illogical action, being a perfect logician, she just wouldn't ever conceive of it. Therefore she could never choose to provide information to A over B, since A is = to B in terms of number (100 vs 100) and we don't have any sort of history of the island or a valuation system against which to draw any sort of bias towards a particular group or individual. Therefore any statement she makes cannot be focused on only group A or group B, and similarly, cannot be provided to and kept isolated to only one member of group A or group B. Her statement must be equally applicable to every member on the island, since she is a perfectly logical machine.

Since the Guru must provide information to A and B equally, as any other option would be providing arbitrary preferential treatment, which is not a logical process, when she says "I can see at least one person with Blue eyes" her statement must be read as being equivalent to "I can see at least one person with Brown eyes" which must be read as being equivalent to "I cannot see anyone who does not have Blue or Brown eyes".

Once she says this, everyone has received the answer to Information 3, which is: "I do not have X color eyes" i.e., "I must have A or B color eyes".

[of special note: everyone on the island of either A or B has conceived the following possible results before the Guru speaks, and therefore, the Guru knows that everyone of A and B knows the possible results before she speaks, as they are all perfect logicians, the above hypothetical distributions upon the island are logical and do not depend on anyone other than themselves knowing anything, and rely entirely on what they can see, only]

Everyone of color A will say: If I have color B, then color A will see 98 A, 101 B, and now knowing they have either A or B, will know they have A, and will leave the island on the first night, as no one on the island can see fewer than 99 of either A or B. After the first night, if they see that the 99 A have left, they will know that each of them saw 98 A, and 101 B, and then on night 2 the 101 B will leave the island.
Everyone of color B will say: If I have color A, then color B will see 98 B, 101 A, and now knowing they have either A or B, will know they have A, and will leave the island on the first night, etc etc etc.

Everyone on the island will know also, that if NO ONE leaves the island on the first night, then NO ONE saw 98 of either A or B, and therefore the distribution is 100/100, (see above) and everyone will leave the island on night 2. (this lines up with the 'everyone of color A will say: If I have color A, then....' and 'everyone of color B will say: If I have color B, then....'

And so, that's it. The Guru's statement has to be perfectly logical, and I cannot see how a perfect logician can choose to provide information that is irrelevant to 1/2 of a group of recipients (i.e., common-knowledge solution)

Have at me.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: Google Feedfetcher and 12 guests