• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

The blue eyes problem

 
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The blue eyes problem is a version of a common logic problem involving inductive reasoning. The setup is something like this: there are 100 people living on island, 50 with blue eyes, and 50 with brown eyes. They are all very intelligent and expert logicians, but totally unable to communicate with each other. They can see each other, so know the color of everyone's eyes, but don't have mirrors or still water so they don't know their own eye color. They would all like to leave the island, but have no way to get off. A guru comes to the island who is able to communicate with the islanders, and makes them this offer. Anyone who can tell me what color his/her own eyes are can leave this island on my ship. He ends by saying that at least one person has blue eyes. For the purposes of simplicity, let's say the guru's eyes don't count. He doesn't have eyes, or isn't on the island. Whatever.

So what happens? On the 50th day, the 50 blue eyed islanders present themselves at the ship, state that they have blue eyes, and sail away. Why? If there had been just one islander with blue eyes, he would have left immediately since the guru said at least one person had blue eyes, and the islander would know it had to be himself, since he can see it's no one else. If two people had blue eyes, they would each be expecting the other to leave on the first day, and when that didn't happen, would be able to deduce that they must have blue eyes as well. Through induction, we get 50 people leaving on the 50th day, because they each know of 49 people with blue eyes, and yet no one left on the 49th day.

OK, that's all well and good. It's a bit hard to follow at first, and also a bit strange because the guru's information that at least one person has blue eyes is something that of course they all knew already, and yet it does in some way provide information that allows them to escape the island. However, I started thinking on these lines. What if there were 40 islanders with blue eyes and 60 with brown eyes? My contention is that the 60 people with brown eyes would also be able to leave the island on the 60th day by simply pretending the guru had also said at least one person on the island has brown eyes, something that everyone on the island also knows to be true. So far I haven't been able to convince anyone of this, or found anyone to convince me I'm wrong either. So I thought I'd refer it to the super-smart community of JavaRanch!
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The whole thing doesn't quite make sense to me either. Each person with blue eyes can easily tell that there are either 49 or 50 blue-eyed islanders, and they can easily tell that the other islanders can draw the same conclusion. Likewise each person with brown eyes can tell that there are either 50 or 51 blue-eyed islanders. So the hypothesis "There is 1 blue-eyed islander" can never be entertained by any islander at any time.

Presumably part of the scheme is that the boat arrives once a day to pick up the islanders who have figured out their ocular status. No islanders show up for the first boat, nor do they expect any other islanders to show up either. And nobody gains any information from that, since everybody already knows there are at least 49 blue-eyed islanders. The idea that now they know there are at least two blue-eyed islanders doesn't make sense.
 
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't understand why it's the 50th day. What do days have anything to do with it?

If two people had blue eyes, they would each be expecting the other to leave on the first day, and when that didn't happen, would be able to deduce that they must have blue eyes as well. Through induction, we get 50 people leaving on the 50th day, because they each know of 49 people with blue eyes, and yet no one left on the 49th day.


I don't understand any of this. Again with the days. Huh?
 
Sheriff
Posts: 67746
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I really hope this wasn't an interview question.
 
Rancher
Posts: 2759
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hmm.. This also assumes that all the islanders have to present themselves at the boat at the same time and without the knowledge of the other islanders. If I'm a brown eyed islander, and I see all the 50 blue eyed islander walk towards the boat, I know that I have brown eyes. So, by that reasoning, all 100 islanders should be able to leave the island.

Dennis Deems wrote:I don't understand why it's the 50th day. What do days have anything to do with it?

If two people had blue eyes, they would each be expecting the other to leave on the first day, and when that didn't happen, would be able to deduce that they must have blue eyes as well. Through induction, we get 50 people leaving on the 50th day, because they each know of 49 people with blue eyes, and yet no one left on the 49th day.


I don't understand any of this. Again with the days. Huh?



See, if there were only 1 person with blue eyes in the group of 100, then that blue eyed person sees al brown eyed people, and can hence deduce that s/he is the only blue eyed person, and would leave on the first day. All the other brown eyed people don't know whether they themselves have blue or brown eyes.
So, by that logic, if no one tried to leave on the first day, it means that atleast 2 people have blue eyes. Let's say only 2 people had blue eyez. Then both the blue eyed persons will see 1 person with blue eyes and 48 people with brown eyes and deduce that they have blue eyes. The 48 people don't know if there 2 people with blue eyes or 3 people with blue eyes. So, if there are 2 people with blue eyes, both of them will try to leave in second day
Again by that logic, if no one tried to leave on second day means there are atleast 3 people with blue eyes. Let's say only 3 people had blue eyes. Then all 3 blue eyed people will see 2 people with blue eyes and 47 people with brown eyes and deduce that they have blue eyes. The 47 people don't know if there 3 people with blue eyes or 4 people with blue eyes. So, if there are 3 people with blue eyes, both of them will try to leave in third day

And so on.. if there are N people with blue eyes, they will all try to leave on the Nth day.
 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ah, yes. That's an important detail. The boat leaves once a day. If the no one leaves on day n, then that can provide information that perhaps allows people to leave on day n+1. Good catch there.

@Paul, I'm not sure what you mean by the hypothesis that there is one blue-eyed islander. The guru states there is at least one blue-eyed islander, and this is meant to be understood as an absolute truth to us and to the islanders. That is, the guru is, to the islanders, an infallible and completely honest being.

OK, with those corrections, does everyone get why the blue-eyed islanders can leave on the 50th day? If so, then am I right about the brown-eyed islanders? Actually, my theory for a generalization is that if there are n different eye colors, and if the count of islanders with eye color i (let's notate it as C(i)) follows C(i) >= 3 and abs(C(i) - C(j)) >= 3, for all i, j, then all the islanders can eventually leave the island no matter what color the guru says initially. I'm not positive about the 3s there. It might work with one or both of them being 2.
 
Jayesh A Lalwani
Rancher
Posts: 2759
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It can work with multiple eye colors too if the guru tells them that there is atleast 1 person with each eye color. They would just leave in waves grouped by color
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Greg Charles wrote:@Paul, I'm not sure what you mean by the hypothesis that there is one blue-eyed islander.



The hypothesis that there is exactly one blue-eyed islander? All of the islanders already know this is false. So none of them would consider it possible that somebody would leave on the first boat. Likewise they already know that there are more than two blue-eyed islanders, so they would likewise expect that nobody will leave on the second boat. And so on.

The only thing they have to decide is whether there are 49, 50, or 51 blue-eyed islanders. And as far as I can see, boats arriving and departing provide no help at all in making that decision.
 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Paul, it quantizes the decision process. Otherwise the induction doesn't work. In the specific example I gave, all islanders would either see 49 people with blue eyes, or 50. No one leaves on the 49th day, which would tell each of the blue-eyed islanders that there are 50 people with blue eyes, and since I (one of the 50) can only see 49, that means I'm one of them. When they all leave on the 50th day, the brown-eyed islanders would realize that they don't have blue eyes, but still wouldn't know what color their eyes are, so they would be stuck.

@Jayesh, yes certainly if the guru said there are is at least one brown-eyed person, one blue-eyed person, and one green-eyed person, and given my assumptions about the C(i)s as stated above, then they'd all get to leave, albeit on different days. My contention is that they would anyway, even if the guru just said there's at least one blue-eyed person.
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Greg Charles wrote:@Paul, it quantizes the decision process. Otherwise the induction doesn't work. In the specific example I gave, all islanders would either see 49 people with blue eyes, or 50. No one leaves on the 49th day, which would tell each of the blue-eyed islanders that there are 50 people with blue eyes, and since I (one of the 50) can only see 49, that means I'm one of them. When they all leave on the 50th day, the brown-eyed islanders would realize that they don't have blue eyes, but still wouldn't know what color their eyes are, so they would be stuck.



But the induction doesn't work anyway, because there's nothing to start it off. An islander could say after the first day "Okay, if there was exactly one blue-eyed person here then they would have known it and left today, but nobody left today so there must be at least two blue-eyed persons", but only if they hadn't already noticed the existence of 49 or so blue-eyed persons. But the islanders are observant and logical, so they couldn't say that. They couldn't deduce anything from the first day.
 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you don't believe the original induction, and certainly there are a lot of people who don't, you can see many online discussions of it ranging from informal appeals to logic to formal mathematical proofs. XKCD is a good jumping off point: problem statement and solution. So far I haven't seen a definitive solution of what happens to the brown-eyed people though.

@Bear -- I just saw one cite of Google using this problem (though a different formulation) in their interviews.
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Never mind... I was wrong. The statement "If exactly one person has blue eyes then he will leave on the first day" is true, regardless of the fact that everybody knows that "exactly one person has blue eyes" is false. And then the inductive statement "If exactly N persons have blue eyes then they will leave on day N" is also true.

So back to your original question: Why can't the brown-eyed people use the same logic? Well, consider the statement "If exactly one person has brown eyes then he will leave on the first day". And suppose that exactly one person has brown eyes. Then that person cannot deduce that. Sure, he doesn't see any other brown-eyed people, but then he doesn't know whether there are any brown-eyed people at all because he hasn't been told of the existence of brown-eyed people. So he can't leave on the first day.
 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
OK, now we're making some progress. Let's say we're the island had 40 blue-eyed islanders and 60 brown-eyed islanders. It's the 40th day, and the blue-eyed islanders are leaving. We've agreed that the information given by the guru enabled this, even though his statement that there was at least one blue-eyed islander was already known by every single islander. That's the tricky bit. It's information, but paradoxically it's not. The math goes beyond me, but it's based on the idea of common knowledge.

Now if you're one of the 60 islanders remaining, you now know your eyes aren't blue, but you don't know what color they are. You might be thinking damn, I wish that guru had said there's at least one person with brown eyes, then at least I'd have had a chance. If he had, then all those 59 other people could leave on the 59th day if I have some other color eyes, or on the 60th day with me if I have brown eyes. Hey, they must also be able to deduce this, because I know they can all see multiple people with brown eyes and they know I can see multiple people with brown eyes. Why couldn't we all pretend the guru did say at least one person has brown eyes? That doesn't violate the premise that the guru is truthful, because I know it's true, and I know everyone else knows it's true. That gives us a chance we wouldn't have otherwise, so it's logical to pretend.

So, does the guru have to speak a fact that everyone already knows for it to become common knowledge, or is it more like flipping on a switch?
 
author
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The other question I have about the guru is this: What's the guru's motivation? Is his motivation to provide the thinnest clue he can come up with, that still provides enough info to solve the problem?
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No, that's the motivation of the person who made up the problem. To produce a mathematical structure requiring the smallest number of assumptions, or free variables, or inputs or whatever you like to call them.
 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
His motivation depends on the formulation of the problem. In one, he's not a guru at all, but a well-meaning foreigner who just happens to let slip at tidbit that leads to mass suicides on the island. In another he's the queen of a village and wants the women to assassinate their cheating husbands. I don't think his motivation enters into the logic of the puzzle though. You could also get distracted with questions like why can't the islanders communicate, can't they see themselves reflected somewhere, who determines fixed eye colors from a continuous spectrum, what about people who have two different colored eyes, what if some of the islanders don't want to leave the island, how do they know the guru isn't lying to them? None of these things are relevant. You have to take the premise of the puzzle as read.
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Paul Clapham wrote:The whole thing doesn't quite make sense to me either. Each person with blue eyes can easily tell that there are either 49 or 50 blue-eyed islanders, and they can easily tell that the other islanders can draw the same conclusion. Likewise each person with brown eyes can tell that there are either 50 or 51 blue-eyed islanders. So the hypothesis "There is 1 blue-eyed islander" can never be entertained by any islander at any time.



Yeah, I'm stuck on that bit too. Why does the Guru's statement that "there is at least one blue-eyed" person matter? Everybody on the island already knows this, and everybody on the island already knows that everybody knows this, and, though it wasn't mentioned, the same can be said of brown eyes.

The only reason I can think of is that as the islanders work back to day one, they need the information that there's at least one blue-eyed person for that person to have been able to leave on day one. But I still don't see how the Guru telling them what they already know now can kick-start that situation.

My head hurts.
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:Yeah, I'm stuck on that bit too. Why does the Guru's statement that "there is at least one blue-eyed" person matter? Everybody on the island already knows this, and everybody on the island already knows that everybody knows this


what if there was only one person on the island with blue eyes? How would he know? All he knows is that 99 people have brown eyes. If he isn't told "There is at least one person with blue eyes", how does he know if his eyes are blue or brown?"
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, it's like this. (I think.) You have to look at the problem as if there is an archipelago of islands which have various numbers of people with various eye colours, who sit around thinking logically while they aren't harvesting their coconuts. And these people can only act based on theorems which are true on all islands (what we called "analytic" in my long-ago predicate logic course). And one of the theorems applicable in this question is:

(1) If a person discovers that there is at least one person with eye colour X, but cannot see any people with eye colour X, then that person can conclude that their eye colour is X.



That's the basic theorem on which the tower of induction is built which causes the 50 blue-eyed people to leave on day 50. The next one up in the tower is:

(2) If nobody can conclude that their eye colour is X after the first day, then there must be at least two people with eye colour X. (And so if a person only sees one such person, they can conclude their eye colour is X.)



And so on by induction until the 50th day.

Now yes, it's true that on this particular island everybody can discover for themselves that there is at least one person with blue eyes and at least one person with brown eyes. But does this count as "discovery" for the purpose of Theorem 1? You think that it does. But for the premises of Theorem 1 to hold, that person must have learned of the existence of the person with eye colour X from some outside source, rather than from personal observation. So that implies that it doesn't.

 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That's an interesting take on it. It is clear to me that the guru's statement is the impetus allowing blue-eyed people to leave the island, but is it really because he tells them something (that they already know) or just because it gives them a common starting point? Looking at it in another way, if my logic is faulty, and yet all 60 brown-eyed people make the same blunder, then they can all leave the island on the 60th day after correctly identifying their eye color as brown. Even if one of those islanders had pink eyes, the other 59 would identify their eyes as brown on the 59th day and only he would be stuck there. If making an assumption helps people reach a correct conclusion, then how can it be faulty logic?
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
But from the math and logic point of view, just because you make an assumption and it leads to a correct conclusion, that doesn't mean that making the assumption was justified.
 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'd accept that if the correct conclusion was reached by lucky chance. For example, a couple has five daughters, so I assume that they are biologically incapable of bearing sons, and conclude that their next child will be a girl as well. I might be turn out to be right about the next child, but that doesn't mean I made a good assumption. So, if you could show how the brown-eyed islanders by assuming that the guru also could have said there was at least one brown-eyed islander might be led into making an incorrect conclusion in this scenario, or any scenario that is possible based on their observations, then I could agree that they could not logically make that assumption.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

fred rosenberger wrote:

Jeff Verdegan wrote:Yeah, I'm stuck on that bit too. Why does the Guru's statement that "there is at least one blue-eyed" person matter? Everybody on the island already knows this, and everybody on the island already knows that everybody knows this


what if there was only one person on the island with blue eyes? How would he know? All he knows is that 99 people have brown eyes. If he isn't told "There is at least one person with blue eyes", how does he know if his eyes are blue or brown?"



Yeah, I get that. However, everybody already knows that there are at least 49 people with blue eyes and at least 49 people with brown, and everybody knows more than that, depending on their specific eye color.

So how does G saying something that adds no information affect anything?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Paul Clapham wrote:Well, it's like this. (I think.) You have to look at the problem as if there is an archipelago of islands which have various numbers of people with various eye colours, who sit around thinking logically while they aren't harvesting their coconuts. And these people can only act based on theorems which are true on all islands (what we called "analytic" in my long-ago predicate logic course). And one of the theorems applicable in this question is:

(1) If a person discovers that there is at least one person with eye colour X, but cannot see any people with eye colour X, then that person can conclude that their eye colour is X.



Right. And we already know that on this island there is nobody who "cannot see anybody with eye color X", and, furthermore, everybody knows this fact.

That's the basic theorem on which the tower of induction is built which causes the 50 blue-eyed people to leave on day 50. The next one up in the tower is:

(2) If nobody can conclude that their eye colour is X after the first day, then there must be at least two people with eye colour X. (And so if a person only sees one such person, they can conclude their eye colour is X.)



And so on by induction until the 50th day.



Yup, got all that.

Now comes the part that makes me reach for the scotch..

Now yes, it's true that on this particular island everybody can discover for themselves that there is at least one person with blue eyes and at least one person with brown eyes. But does this count as "discovery" for the purpose of Theorem 1? You think that it does. But for the premises of Theorem 1 to hold, that person must have learned of the existence of the person with eye colour X from some outside source, rather than from personal observation. So that implies that it doesn't.



I'm gonna have to mull that over for a while.
 
Jayesh A Lalwani
Rancher
Posts: 2759
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok so I was googling about this problem, and Wikipedia has a good explanation . This problem illiustrates the concept of Common Knowledge For something to be Common Knowledge, everyone should know that thing exists AND everyone should know that everyone knows that the thing exists.

So, in this example, on the first day, everyone can see a certain number of blue-eyed people, the problem is that they do not know that everyone can see the same amount of blue-eyed people. So, the number of blue-eyed people is not common knowledge. Once the Guru comes in and makes the declaration which really everyone knows, it becomes common knowledge, because now everyone knows that everyone knows.

 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:
Now comes the part that makes me reach for the scotch..

Now yes, it's true that on this particular island everybody can discover for themselves that there is at least one person with blue eyes and at least one person with brown eyes. But does this count as "discovery" for the purpose of Theorem 1? You think that it does. But for the premises of Theorem 1 to hold, that person must have learned of the existence of the person with eye colour X from some outside source, rather than from personal observation. So that implies that it doesn't.



I'm gonna have to mull that over for a while.



Here's my point of view: this puzzle was obviously invented by somebody considerably smarter than me (it has Smullyan written all over it but I haven't searched out its provenance). And therefore they would surely not have overlooked the obvious things which people are saying in this thread. Therefore those obvious things are most likely wrong. And so I'm going to look for reasons why they are wrong. So far that's the best I can come up with.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Paul Clapham wrote:
Here's my point of view: this puzzle was obviously invented by somebody considerably smarter than me (it has Smullyan written all over it but I haven't searched out its provenance). And therefore they would surely not have overlooked the obvious things which people are saying in this thread. Therefore those obvious things are most likely wrong. And so I'm going to look for reasons why they are wrong. So far that's the best I can come up with.



Agree 100%. When I ask, "Why does something which adds no information affect the puzzle?" it's not to criticize or pick apart the puzzle. It's 99% "What am I missing here?" and 1% "Or could that have been left out?" but even that 1% is mostly just to help my own understanding of what the overall framework is.

Your explanation may be spot-on, but I haven't been able to get my head around it yet. (Granted, I haven't really given it that much thought.)
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:

Paul Clapham wrote:Well, it's like this. (I think.) You have to look at the problem as if there is an archipelago of islands which have various numbers of people with various eye colours, who sit around thinking logically while they aren't harvesting their coconuts. And these people can only act based on theorems which are true on all islands (what we called "analytic" in my long-ago predicate logic course). And one of the theorems applicable in this question is:

(1) If a person discovers that there is at least one person with eye colour X, but cannot see any people with eye colour X, then that person can conclude that their eye colour is X.



Right. And we already know that on this island there is nobody who "cannot see anybody with eye color X", and, furthermore, everybody knows this fact.

That's the basic theorem on which the tower of induction is built which causes the 50 blue-eyed people to leave on day 50. The next one up in the tower is:

(2) If nobody can conclude that their eye colour is X after the first day, then there must be at least two people with eye colour X. (And so if a person only sees one such person, they can conclude their eye colour is X.)



And so on by induction until the 50th day.



Yup, got all that.



Well I sure don't. I can't see what is suddenly known on day 50 that wasn't known on day 1. And I can't see how the fact of no one boarding the boat on day two means anything different than the fact of no one boarding the boat on day one.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dennis Deems wrote:
Well I sure don't. I can't see what is suddenly known on day 50 that wasn't known on day 1. And I can't see how the fact of no one boarding the boat on day two means anything different than the fact of no one boarding the boat on day one.



If nobody boarded the boat, that means nobody was able to deduce his own eye color. So that means he saw enough eyes of a given color that he didn't need to add himself to the set of eyes of that color to meet the minimum.

The Guru (G) informs the islanders "There is at least one blue-eyed person on the island. A boat will come once a day. When the boat comes, if you know your eye color, you can get on the boat and leave."

Imagine there's only one blue-eyed person on the island. The boat comes the first day. Everybody looks around and sees a bunch of brown-eyed people (BR) and one blue-eyed person (BL). Except that BL sees only BRs. Since he knows there's at least one BL, he knows he must be it, so he leaves.

Now imagine the same scenario with 2 BLs on the island. Day 1, the boat comes, and most people see a bunch of BRs and 2 BLs, except that the 2 BLs each see a bunch of BR and 1 BL. Nobody knows his own eye color, because the one piece of information that's known--that there's at least one BL--is satisfied by somebody else that he can see, so unlike with the 1 BL case, nobody can deduce his own eye color.

Now, remember that everybody is an excellent logician, and everybody knows that everybody else is an excellent logician. So, because nobody left on D1, everybody knows that there must be at least [b]two[b] BLs. If there were only one, they all know he would have figured it out and left.

On D2, the boat comes again. Everybody knows there are at least 2 BLs. (It turns out there are exaclty 2, but nobody knows that yet--only that there are at least 2.) The people look around at each other's eyes, and the 2 BLs each see a bunch of BRs and one BL. So each BL knows that he must be the remaining BL. So both BLs board the boat on day 2.

If there are 3 BLs, then, on D2, everybody knew there were at least 2 BLs, as before, but this time, everybody sees at least 2 BLs (and the BRs see 3 BLs). So nobody can leave on D2, because the information they have is met by what they see--nobody needs to add himself to the set of BLs to make up the known minimum number.

So D3 rolls around, and, since nobody left on D2, everybody knows that everybody else saw at least 2 BLs. So the 3 BLs that are there look around, and they each see only 2 BLs, so they each know that they must be the third, so all 3 BLs leave on D3.

And so on.

 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:
So D3 rolls around, and, since nobody left on D2, everybody knows that everybody else saw at least 2 BLs. So the 3 BLs that are there look around, and they each see only 2 BLs, so they each know that they must be the third, so all 3 BLs leave on D3.

And so on.



I think we can amend this somewhat. Rather than, "On day N, nobody leaves, so then on day N + 1 they all know..." day by day, I think it goes more like this:

Consider a case of 5 BR and 5 BL. Everybody knows from the get-go that there are at least 4 BL, because everybody can see at least 4 BL. All the BLs know that everybody else knows that there are at least 3 BL. BL1 sees 4 BLs (BL2, 3, 4, 5) but he doesn't know if BL2 is seeing 3 BLs (3, 4, 5) or 4 BLs(3, 4, 5 plus BL1 himself). This I think is the key part.

Everybody knows on D0, before the ship ever even comes for the first time, that nobody is going to leave on D1 and nobody is going to leave on D2, or on D3. Being excellent logicians, they'll all know right off the bat that there are at least 4 BL and that therefore everybody is seeing at least 3 BL. (Each BL's logic is: "I see 4 BL, so I know that there are either 4 BL or 5. I know that those BLs see either 3 BL or 4, so up through D3, nobody can conclude that he himself is the remaing BL.")

So there's no need for them to even observe the boat for D1-D3, since everybody already knows that nobody is getting on. It's what happens on D4 that sets things in motion.

D4 comes along, and everybody sees at least 4 BL, and, more importantly, since nobody got on the boat, everybody knows that everybody else saw at least 4 BL. So now the 5 BLs think, "A ha! Those BLs saw 4 BL, not 3, so that must mean that I'm a BL, so there are exactly 5 BL, and know we all know it."
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And now I'm starting to think that it can't actually work, that it's circular or something.
 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No, fight that feeling. The question I'm really interested in answering is does it matter what the guru says, or can he just say, "Go!" with the same effect.
 
Ranch Hand
Posts: 56
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


X people have blue eyes
Y people do not have blue eyes

Does it matter what X + Y is?
I don't think so.

if X=1, the person with blue eyes knows that X=1. Everyone else has to consider that X=1 or X=2.

If X=2 then those with blue eyes know that either X=1 or X=2 (those without blue eyes also have to consider that X might = 3).
If they do not observe X=1 behavior on day 1, they can conclude that X=2 on day 2

If X=3 those with blue eyes would know that either X=3 or X=2.
If on day 2 they did not observe the expected behavior for X=2, they could conlclude that X=3

etc ...
 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

eileen keeney wrote:
if X=1, the person with blue eyes knows that X=1.


And this is ONLY true if the Guru says "at least one person on the island has blue eyes". If he doesn't say that, then the one person with blue eyes doesn't know if X=1 or 0. Therefore, he can't know if he should go to the boat on the 1st day or the X+Y day.
 
eileen keeney
Ranch Hand
Posts: 56
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

fred rosenberger wrote:

eileen keeney wrote:
if X=1, the person with blue eyes knows that X=1.


And this is ONLY true if the Guru says "at least one person on the island has blue eyes". If he doesn't say that, then the one person with blue eyes doesn't know if X=1 or 0. Therefore, he can't know if he should go to the boat on the 1st day or the X+Y day.



Now I am starting to doubt the whole problem, because even before the Guru said that at least one person has blue eyes, everyone knew this fact.
So why did the Guru have to say this?

Lets speed the process up, and pretend the Guru didn't mention that at least any number of people had any specific eye color.

Everyone knows that everyone (themselves and everyone else) knows that at least X-2 people have blue eyes.
It doesn't matter what the Guru says or does not say, everyone already knows this.

So why does it take more than 3 days for everyone to get on the boat?


Suppose the Guru said that at least 48 people have blue eyes (which he does not need to say since not only does everyone know this is true, but everyone knows that everyone else knows this to be true).


 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

fred rosenberger wrote:

eileen keeney wrote:
if X=1, the person with blue eyes knows that X=1.


And this is ONLY true if the Guru says "at least one person on the island has blue eyes". If he doesn't say that, then the one person with blue eyes doesn't know if X=1 or 0. Therefore, he can't know if he should go to the boat on the 1st day or the X+Y day.



But since X is not 1 or 0, and since everybody knows that it's not 1 or 0, and since everybody knows that everybody else knows that it's not 1 or 0, I don't see how it can matter.

So let's say it's 3 and 3, and G says nothing except the rules about the boat.

D1, everybody knows:
  • There are at least 2 people with color P and at least 2 with color Q.
  • Everybody can see at least 1 person with color P and at least 1 person with color Q.


  • So if my eyes are P, I see 2P and 3Q. And I know that everybody else is seeing at least 1P and at least 1Q. (And I actually know everybody is seeing at least 2Q, but I don't think that's relevant.)

    I can't deduce my eye color, so I can't leave today. And if G had said, "There is at least 1P," I would know nothing that I don't already know.

    Now, IF I had been the only P, AND G had said, "There is at least 1P," then I could go. But, whichever color my eyes are, I'm not the only one, and I know I'm not the only one. This is true for all of us.

    Without G saying anything, I can see both P and Q, so I know that whether my eyes are P or Q, there are at least 3 of us. I also know that everybody else knows that there are at least 2 of their own eye color. I know that the other Ps each see at least 1 more P and 3 Qs. What I don't know is if they see 2P + 3Q or 1P + 4Q.

    So now D2 rolls around. G hasn't said the magic words. We all not have one additional piece of information: Nobody left on D1.

    Can we use that information to increment the number of people there must be with our eye color, and hence get the ball rolling for our eventual escape? My gut says no. And it says no even if G had said the magic words. I need to think about it some more to formulate an actual defense or refutation of this posture, and my brain is too fried for that right now.
     
    eileen keeney
    Ranch Hand
    Posts: 56
    1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Ok,

    I was thinking about this while I was taking a nap, but the answer to my one dilemma (related to this problem) actually came to me while I was in the shower.

    It is not that they all need to be told that at least one person has blue eyes, because they all know this (just as they know that at least 49 people have blue eyes and they each know that everyone else knows that at least 48 people have blue eyes).
    Needing to be told something you already know was just very illogical to me.

    There is a lot of information that they all know to be true, and all know that everyone one else on the island also knows to be true.

    What they needed, is to be aware that everyone else is, at some same point in time, considering this specific piece of information and acting logically on this specific piece of information.

    Now if they could all have concluded that everyone acted on day one, with the knowledge that at least 48 of them had blue eyes, they (all of those with blue eyes) could have gotten off of the island faster. So what stopped them from drawing this conclusion if they were all so smart?
    The lack of knowing that everyone else was also considering this information?










     
    fred rosenberger
    lowercase baba
    Posts: 13089
    67
    Chrome Java Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    This is basically a recursion problem. The question boils down to "Is it possible for the population of BL people I can see to determine their own eye color or not?". That new sub-population recursively asks the same question, until you eventually get down to "Can a population of one person I see with BL determine if he has BL or not" - and this can only happen if the Guru tells them this fact.

    If there are X people with BL, then each would think this:

    I know there are (x - 1) people on the island with BL, but I don't know my own eye color. If that (x - 1) group of people can figure out if they all have BL, they will either all get on the boat on day (x-1), or they will know I have BL, and they will all know to get on the boat on day x. I'll wait and see if they get on the boat on day (x-1), and if not, we should all get on the boat on day x. But can they figure it out? well...let's call (x - 1) by the name y. each person in that group of y would think like this:

    I know there are (y - 1) people on the island with BL, but I don't know my own eye color. If that (y - 1) group of people can figure out if they all have BL, they will either all get on the boat on day (y-1), or they will know I have BL, and they will all know to get on the boat on day y. I'll wait and see if they get on the boat on day (y-1), and if not, we should all get on the boat on day x. But can they figure it out? well...let's call (y - 1) by the name z. each person in that group of y would think like this:

    I know there are (z - 1) people on the island with BL, but I don't know my own eye color. If that (z - 1) group of people can figure out if they all have BL, they will either all get on the boat on day (z-1), or they will know I have BL, and they will all know to get on the boat on day z. I'll wait and see if they get on the boat on day (z-1), and if not, we should all get on the boat on day z. But can they figure it out? well...let's call (z - 1) by the name q. each person in that group of y would think like this...

    This keeps going until you get to:

    I know there is 1 other person on the island with BL, but I don't know my own eye color. If that 1 person can figure out if he has BL, they he either all get on the boat on day 1, or he will know I have BL, and will know to get on the boat on day 2. I'll wait and see if he gets on the boat on day 1, and if not, we should both get on the boat on day 2. But can he figure it out? well...let's see what would happen if only one person had BL.

    He would know that nobody else has BL, but how would he know if only he did, or if everybody had BR? THE GURU TOLD US THAT AT LEAST ONE PERSON HAS BL. This is the part that lets us unwind the recursion call stack. He would know he was the only person with BL. So he should get on the boat on day 1. If the Guru has not said that, he would not know whether to get on the boat or not.

    So, the population of 2 had assumed that only 1 person (the other one) had BL, and they knew he would know to get on the boat on day 1. When he didn't, they knew their assumption was wrong, so they both have to have blue eyes. They should both get on the boat on day 2.

    When they don't on day 2, the three people who assumed there were only two know their assumption was wrong. Therefore, all three must have blue eyes...

    When they don't get on the boat, the four people who assumed there were three know they were wrong, so all four must have blue eyes.

    and so it unwinds back up the stack.



     
    Jayesh A Lalwani
    Rancher
    Posts: 2759
    32
    Eclipse IDE Spring Tomcat Server
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    "there are atleast 48 blue eyed people" is common knowledge as soon as the problem starts. All the blue eyed people see 49 other blue eyed people, and they know that the other blue eyed people see atleast 48 other blue eyed people. So, IMO, the blue eyed should have started the chain of reasoning at 49, not at 1. On the first day, if no one left, all the blue eyed people should have deduced that they themselves are blue eyed and left on the second day.
     
    Sheriff
    Posts: 3837
    66
    Netbeans IDE Oracle Firefox Browser
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Jayesh A Lalwani wrote:On the first day, if no one left, all the blue eyed people should have deduced that they themselves are blue eyed and left on the second day.


    How exactly should they deduce it? I'd say you should be more explicit in step two:



    (I don't like the puzzle. The logic is impeccable, but it does not feel like human reasoning.)
     
    Where does a nanny get ground to air missles? Protect this tiny ad:
    a bit of art, as a gift, that will fit in a stocking
    https://gardener-gift.com
    reply
      Bookmark Topic Watch Topic
    • New Topic