wood burning stoves 2.0*
The moose likes Meaningless Drivel and the fly likes The blue eyes problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "The blue eyes problem" Watch "The blue eyes problem" New topic
Author

The blue eyes problem

Stan Eads
Greenhorn

Joined: Apr 08, 2013
Posts: 6
The induction logic is good, but they all leave out the brown eyed people, who also wish to leave the island. Since their logic is just as powerful as that of the blue-eyed ones, all will realize on day one that they have either brown or blue eyes (or a third color). They will see the logic that will free the blue-eyed, and they want to be among them. "But," they may think, "if I have brown eyes, then I will not get to go home. I wish to go home whether I have brown or blue eyes." So, using their perfect logic, they all use the Guru's words as an initiating event for both the blue-eyed and brown-eyed case, not knowing which they are (if either).

If there are 50 of each, then they all depart on night #50. If there is a red-eyed outlier, then 49 depart on night #49, 50 depart on night #50, and one poor red-eyed schmuck stays on the island with the Guru.
Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2274
    
  28

There is only 1 ship
Stan Eads
Greenhorn

Joined: Apr 08, 2013
Posts: 6
Perhaps there is only one ship, but that is not relevant. Nowhere in the problem is the departure restricted to a single trip. The Guru's word is truth. If Guru says that those who can state their eye color correctly can leave on the ship, then getting the ship back for the second batch of eye-color-identifiers is the Guru's issue to resolve. The other islanders have only the eye issue to resolve. If they correctly do so, then they have earned their reward.
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 557
    
    7

Greg, 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


I disagree slightly on day 40, the 40 blue eyed and the 60 brown eyed would board the boat
Stan Eads
Greenhorn

Joined: Apr 08, 2013
Posts: 6
After day 40, the brown-eyed persons know only that there are either 60 brown-eyed persons or else 59 brown-eyed and one other-eyed person - themselves. They cannot leave until day 60 arrives and the 59 have not departed, demonstrating that they also have brown eyes.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11169
    
  16

I would say that on day one, 100 people come to the guru and say "I have <whichever> eyes". Approx. half would be right, and would get to leave the island.

The next day, everyone who was left would come back and say "I have <the other color> eyes", and they'd leave.

So by the end of day 2, everyone is off the island.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Stan Eads
Greenhorn

Joined: Apr 08, 2013
Posts: 6
Fred is correct, of course, due to a slightly deficient problem statement. There is no penalty for incorrect guesses, so anyone can simply guess colors until they get it right. They can all leave on the first day by naming colors until they state their own.

Since the point of this exercise is to create an extreme case of induction, there would properly be a penalty for incorrect guesses. If an incorrect guess would disqualify one from ever leaving the island, these master logicians would prefer a near-certain exit over a 50-50 shot from a guess. (It is not 100% certain because each person knows that they may have a third color of eyes. Even if that proves to be the case, they have a much better chance at a correct guess by eliminating blue and brown as possibilities.)
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4446
    
    5

I don't get it. I basically was asking the same questions as these (source= http://xkcd.com/solution.html):
1. What is the quantified piece of information that the Guru provides that each person did not already have?
2. Each person knows, from the beginning, that there are no less than 99 49 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?
3. Why do they have to wait 99 49 nights if, on the first 98 48 or so of these nights, they're simply verifying something that they already know?

I kind of get the concept of common knowledge (logic) in that they needed the Guru to explicitly state that there was at least one person with blue eyes such that each of them knew that everyone knew what the facts of the matter was but still, you'd think that it was pretty obvious from just observing. Being as I have brown eyes, I guess it doesn't matter much to me... I would have been left on the island to rot with the rest of the hopelessly unsure


Junilu - [How to Ask Questions] [How to Answer Questions]
Stan Eads
Greenhorn

Joined: Apr 08, 2013
Posts: 6
Junilu, I know that you understand the case with a single person with blue eyes (call it Case 1).That's a special case, of course, because the blue-eyed person sees no others with blue eyes. You probably also understand Case 2, where there are two people with blue eyes, and they know their status on day 2 since the other person didn't leave.

Case 3, with three persons works the same way: on day three, all three depart. Imagine yourself as a blue-eyed person under Case 3. You see two persons with blue eyes. They may be the only two - so they may each see only one with blue eyes. You, being a master logician, know that they will be watching to see if the other leaves that day, and expect that, when that does not happen, that both will leave the next day. When they do not, then it hits you - I MUST HAVE BLUE EYES ALSO! Day 3, you are all on the boat. These three could have ruled out the one-person case immediately and gone no further, but that would have been illogical of them!

All of the brown eyed persons were watching the Case 3 drama play out, just the way they knew that it would, master logicians that they are. BUT - what if day 4 arrives and the three have not left? Why, that means that there is one more person with blue eyes. There must be four of them, and #4 is me! This is Case 4. On day 4, all four of you depart the island. These four could have ruled out the Case 1 and Case 2 scenarios immediately, but that would also have been an illogical act.

You can see where this is going. You can describe the proof for Case 5 next (where Cases 1 - 3 can be ruled out immediately), and so on. At which Case number do you believe that the process breaks down? These are master logicians - they think it all through! Induction is continuing the process to its logical conclusion: the departure of all of the brown-eyed and blue-eyed persons from the island.

NOTE #1: The Guru provided the initiating event for the induction process. That was enough.

NOTE #2: You would still get off of the island with your brown eyes. See my post about the brown-eyed islanders, above.
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4446
    
    5

I understand the 1-, 2-, 3-, etc. person cases but it isn't helping me much because the fact of the matter is, the conditions for these scenarios are not present for them to play out. Each blue-eyed person sees exactly 49 people with blue eyes and 50 people with brown eyes from day one. With no basis to argue any of the lower-number cases, how can a blue-eyed person make any conclusion for the higher number cases that follow from the lower-number cases? All the "if there were only X people with blue eyes, they would all leave on day X but since they didn't, then I must have blue eyes too" (where X < 49) lines of reasoning don't seem relevant because they already know that, in fact, there are at least 49 people with blue eyes.

Here's my line of thought:

On the first day, nobody leaves because...
- All the brown-eyed people see 50 blue-eyed people and 49 brown-eyed people.
- All the blue-eyed people see 49 blue-eyed people and 50 brown-eyed people.
- Nobody can say for certain if they have blue eyes.

On the second day, nobody leaves because...
you have the same conditions as on the first day
so still, nobody can say for certain if they have blue eyes.

On the third day, nobody leaves because...
you have the same conditions as on the first and 2nd day and
so still, nobody can say for certain if they have blue eyes.

And so on...

So, I'm not quite getting how all of a sudden, on the 50th day, everything becomes crystal clear to the 50 blue-eyed people. I don't see "the miracle" happening. Although now that I think of it more maybe in the deep recesses of my mind, I might be getting an inkling of how this works. I don't know, it's still feels like one of those "right at the tip of my tongue" moments for me.

My thinking about the brown-eye people getting stuck on the island: because the Guru said "there is at least one blue-eyed person" and not "there is at least one brown-eyed person" then a brown-eyed person can't make the assumption that there are no more than two eye colors in play -- they could be red- or green-eyed for all they know; but they don't, so they can't leave the island, even after all the blue-eyed people leave. There just isn't enough "common knowledge" to say for certain if brown is the only eye color left. And since nobody can communicate, they'll never know...
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2840
    
  11

It's good to see this thread pop back up on (nearly) its first anniversary. Stan is the first person who's ever agreed with my reasoning that the brown-eyed people can also escape the island. I feel vindicated!

I guess I can see the 50/50 case, though it's not as easy to make as the 40/60 case, and even that hasn't been an easy case to make so far. I guess I do see it though. The brown-eyed people would see that the other brown-eyed people didn't leave, and reason, "Hey, they would have left on day 49 if they had seen 48 people with brown eyes. That means I must have brown eyes. I no longer have to wonder if I have blue eyes and would leave with those 50 other guys on day 51, or have some other colored eyes and be stuck here forever. I have brown eyes, and everybody is leaving tomorrow!"
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 557
    
    7

OK, we needed at least 1 blue eye to separate from 0 to 1. there is also a major issue with the timing, i.e. when there are x blue come aboard. My problem is that how long does it take for first person to walk to the retrieval vehicle ?

While this can be based in theory, how can this be done in a real environment?
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4446
    
    5

Steve Fahlbusch wrote:
While this can be based in theory, how can this be done in a real environment?

1. Put the participants in some kind of enclosure with only one door. The door will be opened for 10 minutes every hour, at which time only those who are absolutely sure of their eye color can exit.
2. Threaten grave bodily harm for anyone who attempts to exit but is wrong about their eye color -- and they only get one chance to get it right.
3. Threaten grave bodily harm if any participant communicates in any way or does something that would make it possible for anyone to come to a conclusion by any means other than logical reasoning alone

Goes to show you don't ever want to put me in charge of anything like this...
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

you can also reason backwards why it would take 50 iterations.

say I have blue eyes. i dont know it, but i do know there are 49 people with blue eyes. if i have blue eyes, then there are 50. so the possibilities are 49 or 50.
but lets also look at person A. A also has blue eyes, but doesnt know it. He sees either 48 blue eyed people or 49, if i have blue eyes. so taking his uncertainty and mine together, there could be 48, 49, or 50. lets assume i have brown eyes, that means A sees 48 people with brown eyes, and knows there may be 49.
but A is also a logician, he would also consider the perspective of B, who has blue eyes. naturally, A will come to realize that B wouldnt know he has blue eyes. A doesnt know either, so A from Bs perspective there could be 47 or 48 people with blue eyes. combining My uncertainty with As and Bs, the range is now from 47 to 50. To simplify the range, A would do the same thing I did, assuming he had brown eyes. So, assuming I have brown eyes, knowing A will do the same, then B will look at C...

etc...

so each person assumes they have brown eyes, then considers the two scenarios from someone else`s perspective. at a certain point they know it is wrong: i know there are 49 blue eyed people, so when A, with his doubt, begins to consider B's perspective I know that B won't see 47, he'll see 48 or 49. but my construct of A won't know that, and so assuming I am brown eyed, 47 is a possible expectation my construct of A might have of his construct of B, so on down the line. Eventually the constructed person at the bottom (call him Z) might hypothetically see one, or no blue eyed people. if Z sees none Z would leave right away. if Z sees one and that one doesnt leave, then Z would leave on day 2 with the only other blue eyed person he saw. if Z doesn't leave then whoever constructed Z (Z-1) would leave with Z and the other blue eyed guy on day 3. etc... up the line of constructs.

I know the day of reckoning is day 49. If everyone leaves then I am stuck, if not I go home day 50. But for person A, that day of reckoning might be day 48, and from his perspective, B's day of reckoning might be day 47... so the only logical thing to do is wait out the 49 days so everyone is on the same page.



Steve
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

fred rosenberger wrote:I would say that on day one, 100 people come to the guru and say "I have <whichever> eyes". Approx. half would be right, and would get to leave the island.

The next day, everyone who was left would come back and say "I have <the other color> eyes", and they'd leave.

So by the end of day 2, everyone is off the island.


We know the guru's word is stone, but we don't know anything about what he doesnt say. Assuming there is no punishment for guessing wrong is not a safe thing to do just because he didnt say there was.
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2840
    
  11

Steve Luke wrote:
We know the guru's word is stone, but we don't know anything about what he doesnt say. Assuming there is no punishment for guessing wrong is not a safe thing to do just because he didnt say there was.


If we allow for guessing, the problem is reduced to an absurdity. It's also unanswerable, since we don't know what colors the islanders would guess and in what order. I think we have to assume that the intent is that an islander can only leave the island when he can state his eye color with certainty. If anyone feels a need to devise punishments into the problem statement to make this work, then have at it!
Stan Eads
Greenhorn

Joined: Apr 08, 2013
Posts: 6
To Steve Fahlbusch: Creators of logic problems generally do not expend a lot of energy trying create scenarios that would correspond exactly to reality. They present a hypothetical situation with a problem to solve, along with the constraints under which you are working. When the intention is to present a challenging case requiring mathematical induction, it may be interesting to point out aspects of the problem that were not well-formed, but try to solve the problem itself if you can. That is also interesting.

To Greg Charles: If the 50/50 case seems murky, try the 5/5 case. By the priciples of induction in play here, it is exactly the same thing. Each person wants off of the island, and none know whether or not their eyes are blue or brown (or some other color, for that matter). Since the Guru's words serve as an initiating event to start the counting, and each person there wants to leave, they (as master logicians) start the day count for both blue and brown. After all, it is perfectl clear at that moment that the guru also saw someone with BROWN eyes and could just as well have said brown instead of blue.

To Junilu Lacar: Do you see how Case 3 (with 3 blue-eyed persons) has all three leaving on day 3? They do so, even though on day 2 they have the same conditions as on the first day, and on day 3 they have the same conditions as on the first two days. Same applies to Case 4. And since Case4 works, Case 5 also works. And since Case 5 works, Case 6 also works, and so on. This is induction.
Regarding the brown-eyed persons leaving, I addressed your question in my response to Greg, above. If there was a third eye-color there for one unfortunate islander say - 50 blue, 49 brown, one red - then the browns would simply leave on day 49 and the poor red-eyed schmuck would be hoping that the blues do not depart the next day (hoping for a 51-49 split). When they actually do depart, then it's a lonely island!
Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2274
    
  28

IMO, the way this problem is worded, it's not really a "problem". Rather it's an illustration of a particular way of thinking. It illustrates the concept of "common knowledge". It is trying to illustrate that there are things that you can infer B only when you know that everyone knows A. Once, you infer B, and you know everyone can infer B, A+B becomes common knowledge. Once A+B becomes common knowledge, you can infer C, and so on.

You can find thousand ways of circumventing this solution, but it breaks the "common knowledge" component of the problem, which makes it less interesting.
 
permaculture playing cards
 
subject: The blue eyes problem
 
Similar Threads
Only fun forwards for fun ...
Taming the Technology Tidal Wave ... thank you, everyone!!!
Heh, another good reason to vote Democrat this year
Static
Does Man have free will?