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

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Prelates, Moderators General

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

Postby xkcd » Sat Apr 08, 2006 8:26 am UTC

My write-up of the solution is available at http://xkcd.com/solution.html

And the problem is available at http://www.xkcd.com/blue_eyes.html

Edit 08/02/2012: A discussion of typical objections is available at viewtopic.php?f=3&t=80149 -jr
User avatar
xkcd
Site Ninja
 
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC

Postby jmuwolf » Mon May 08, 2006 10:24 pm UTC

If there were 3 people on the island... and the first day passed and no one left then the 2nd day passed and no one left... don't you think they would wonder why no one was leaving? OR! do they get fed up with the guru build a raft out of bamboo, post a wilson volley ball on a stick as their first mate and GtFout of there?

ConFr0zlEd!
jmuwolf
 
Posts: 3
Joined: Mon May 08, 2006 5:27 pm UTC
Location: Mineral, Va

Postby James » Mon May 08, 2006 10:58 pm UTC

Point of Order:

What in eff's sake are you talking about?
This is a block of text that can be added to posts you make. There is a 255 character limit.
James
 
Posts: 74
Joined: Sun Apr 09, 2006 9:28 pm UTC

Postby jmuwolf » Tue May 09, 2006 1:23 am UTC

did someone say "sake?" I'm thirsty!
jmuwolf
 
Posts: 3
Joined: Mon May 08, 2006 5:27 pm UTC
Location: Mineral, Va

Postby jmuwolf » Tue May 09, 2006 3:11 am UTC

I finally get it!... yay the whole "they're perfect logicians" thing helped me on that one. lol. My head hurts. you do this for a living?
jmuwolf
 
Posts: 3
Joined: Mon May 08, 2006 5:27 pm UTC
Location: Mineral, Va

Postby Shoofle » Tue May 09, 2006 10:52 am UTC

He does not... yet.
User avatar
Shoofle
 
Posts: 409
Joined: Sun Apr 09, 2006 9:28 pm UTC
Location: Location, Location.

Postby BlueEyes » Wed Jun 14, 2006 10:44 am UTC

RE: What is the quantified piece of information that the Guru provides that each person did not already have?

Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. Furthermore, everybody knows that everybody knows that there are at least 98 blues. And, everybody knows that everybody knows that everybody knows that there are at least 97 blueys....etc...etc...

But not everyone knew that everyone knew that last statement that can be inferred (involving the at least 1 person case) until the Guru spoke up.

Is this answer kinda on the right lines?
BlueEyes
 
Posts: 1
Joined: Wed Jun 14, 2006 10:29 am UTC

Postby xkcd » Wed Jun 14, 2006 3:39 pm UTC

Yeah, that's pretty much the idea.

There are two ways of looking at it -- the bottom-up inductive and the top-down layered hypotheticals. The latter version, which is what you are describing, more literally matches what's going on, and i like it more. The former version, which starts with the small cases and builds up, is easier to explain but less satisfying, I think. The questions were to try to force people to consider the more difficult/interesting hypotheticals version.
User avatar
xkcd
Site Ninja
 
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC

Postby Sven » Wed Jun 21, 2006 2:22 pm UTC

I think it may be worth mentioning on the page describing the puzzle itself, or somewhere else, that everyone on the island knows everyone else is a perfect logician. The solution doesn't work otherwise. Not really a big deal, but I thought it worth bringing up.
Sven
 
Posts: 1
Joined: Wed Jun 21, 2006 2:17 pm UTC

Postby xkcd » Thu Jun 22, 2006 6:43 pm UTC

I think it may be worth mentioning on the page describing the puzzle itself, or somewhere else, that everyone on the island knows everyone else is a perfect logician.

Hmm, yeah. Revised slightly. I'm trying to avoid making it too wordy.

But what you suggest isn't technically enough -- you must also say that they all know that they all know. And you have to define that recursively about 100 times :)
User avatar
xkcd
Site Ninja
 
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC

Postby Gozer » Wed Jun 28, 2006 9:35 pm UTC

My first intuitive response was the correct answer. Having not read the answer yet, I still had to work it out. Then I had to prove it to myself that it was correct.

Now, two days later, I don't believe the answer even though I know if I spend the time to work it out again, I'll convince myself again. Very interesting puzzle!
User avatar
Gozer
 
Posts: 18
Joined: Wed Jun 28, 2006 9:22 pm UTC
Location: West Lafayette, IN

Postby Enzo Dragon » Tue Jul 04, 2006 7:23 am UTC

Brilliant answer. I didn't have any problems understanding it.
Enzo Dragon
 
Posts: 4
Joined: Tue Jul 04, 2006 7:16 am UTC
Location: Charon, Pluto's Moon

Postby Gozer » Tue Jul 04, 2006 9:24 pm UTC

One interesting thought occurs, but it's a bit of a spoiler, so highlight below only if you already know the answer to the puzzle.


SPOILER:
======
My coworker thought this was a clever way for the guru to get people off the island. But then I realized that the guru is taking a rather substantial risk of leaving the island herself! If the Nth day wound up with an empty ferry, she would be joining the exodus the very next night!
======
User avatar
Gozer
 
Posts: 18
Joined: Wed Jun 28, 2006 9:22 pm UTC
Location: West Lafayette, IN

Postby mheard » Thu Jul 06, 2006 7:23 am UTC

Thanks for the great puzzle! I've been running it over in my head for about three days. I was totally on board with your solution until I explained it to two people, but now I can't convince myself I haven't fallen for a hand-waving proof.

The one- and two-man cases seem trivially true, and I can convince myself that the three-man case works as well. (Each blue-eyed person looks at the two others and thinks, "Hee, hee! Look at those suckers! They both think they have brown eyes, but tomorrow, they're gonna figure it out!" But then they all wake up on the third day and they all realize that no one has left, and OH SWEET IRONY!!!)

The three-man case works because the two-man case works, and the two-man case works because the one-man case works. I totally agree up to this point. But that's not enough for a proof by induction. I have to show that in general, the k-man case works because the k-1-man case works, and I can't convince myself that that's true.

It's tempting to say, "1 man the first day, 2 the second, 3 the third, therefore 4 the fourth and so on QED", but we haven't really given ourselves any reason to think that yet, in my opinion. 1, 2, and 3 are all concrete cases, but we never really showed "k-1 because k", just "3 because 2" and "2 because 1".

Can you give me a nudge in the right direction here?


EDIT: I've worked out what's bugging me the most.

The 2-man case works because each blue-eyed person can see one blue-eyed person, and the 1-man case works.

The 3-man case works because each blue-eyed person can think that each blue-eyed person can see one blue-eyed person, and the 1-man case works.

In the 4-man case, each blue-eyed person knows that each blue-eyed person can see at least two other blue-eyed people. The reason that the 2- and 3-man cases worked has completely evaporated.
mheard
 
Posts: 3
Joined: Thu Jul 06, 2006 6:45 am UTC

Postby xkcd » Thu Jul 06, 2006 7:12 pm UTC

It's not just hand-waving. The inductive portion of the proof is as follows:

Given: the K case works. That is, if there are K blue-eyed people, they will all leave on the Kth night.

Suppose there are K+1 blue-eyed people.

Each blue-eyed person can tell by observation that there are either K or K+1 blue-eyed people, depending which they themselves are.

Since they know that K blue-eyed people will leave the Kth night, if they wait through the Kth night and no one leaves, they know there are not K blue-eyed people. The only other possibilitiy is that there are K+1, so they know it includes them. Therefore, they leave the next ((K+1)th) night.

Therefore: If there are K+1 blue-eyed people, they all leave on the (K+1)th night.

So, we've shown that if it's known that K blue-eyed people will leave by the Kth night, then K+1 blue-eyed people will leave by the (K+1)th night. Now start with your base case K=1 or whatnot and go along with the induction.
User avatar
xkcd
Site Ninja
 
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC

Postby RealGrouchy » Fri Jul 07, 2006 2:01 am UTC

Wow, thanks for that doozey of a puzzle! (and more importantly, for the solution, without which I wouldn't have "solved" :P the puzzle)

Some people have suggested that on day 101 the brown-eyed people would all leave, but that is impossible. Below is my explanation, as well as my analysis of other potential holes/redundancies (which may well be intentional, so I'll just call them "quirks").

If I made an error (including spelling or formatting), please pm me or reply and I'll edit this post so it is clearer. I used the male gender because it's complex enough already.

BROWN-EYED PEOPLE CAN'T LEAVE:

After the blue-eyed people leave, it's not possible for any brown-eyed person to deduce that their eyes are brown without a second statement from the Guru, no matter how long they wait. This is because to each person, his or her eyes can either be brown or not-brown (-and-not-blue). Even though there are no longer any blue-eyed people around, it doesn't matter. If they could figure it out by only seeing 99 other brown-eyed people, then the blue-eyed people could have done it without the Guru's statement, which is key in closing the inductive loop (see below).

ALTERNATE WAY OF THINKING ABOUT THE BROWN-EYES:

This puzzle, and the inductive reasoning behind it, makes much more sense if you treat each person individually, rather than as a group with similar characteristics, even though they are all interchangeable. Let's name them X~001, X~002, ... , X~099, and X~100 (much to the dismay of their parents). In addition, the brown-eyed people have no more information on day 100 than they did on day 1. So I'll count the brown-eyed problem from day 100, not day 200.

For X~100 to know on day 100 that his eyes are brown, he would have to observe the 99 brown-eyed people he sees not leave on day 99. However, person X~099 doesn't know his own eye colour, and X~100 knows that X~099 doesn't know his own (X~099's) eye colour.

As far as X~100 is concerned, X~099 would leave on day 99 only if X~100 was not brown-eyed, and if the 98 brown-eyed people that X~099 sees did not leave on day 99. However, person X~098 doesn't know his own eye colour, and both X~100 and X~099 know that X~098 doesn't know his own eye colour. This repeats until we get to X~001, where, as far as X~100's hypothesis-within-a-hypothesis-times-100 is concerned, nobody knows their own eye colour (or, people are only logically aware of the eye colour of people with smaller-number names).

The crux is twofold:
- Each brown-eyed person plays this situation out in their minds with themself as person X~100
- Each brown-eyed person X~100 knows that even though he sees 99 other brown-eyed people, he doesn't know whether those people see 99 other brown-eyed people (if X~100 is brown-eyed) or 98 brown-eyed people (if X~100 isn't brown-eyed).

(this is where I get a bit fuzzy on the logic)

Therefore, Person X~100 knows that person X~099's knowledge of his own eye colour depends on person X~098's knowledge of his own eye colour ... which depends on person X~002's knowledge of his own eye colour, which depends on person X~001's knowledge of his own eye colour, which person X~001 simply cannot know*. That is why the brown-eyed people cannot know their own eye colour.

However, the blue-eyed people, who go through the exact same logic process, know that for each blue-eyed person playing the role of X~100 in his own mind, there exists at least one X~001 whose eyes are blue. Because of the Guru's statement, this hypothetical X~001 can be assumed to know his eyes are blue on the first day (even though this one person can actually be any of the 99 or 100 people who have blue eyes, as far as X~100 is concerned). X~100 knows that if on day one that person X~001 doesn't leave, then person X~002 will have figured out his eye colour (because persons X~003 to X~100 haven't figured out their own eye colour according to the hypothesis). If on day two persons X~001 and X~002 don't leave, then person X~003 would know his eye colour.

Although it seems obvious that nobody will leave on the third day, since X~100 knows that there are at least 99 people with blue eyes, it becomes necessary to follow this process to the 99th day, because X~100 doesn't know his own eye colour. Even though each person plays out the situation as X~100, they know that if their eyes are also blue, they could just as well be somebody else's hypothetical person X~001 or X~099.

[* Especially if it depends on the Guru knowing her own eye colour :P]

"QUIRKS"

It's possible that Randall overlooked these points, but it is equally possible that he decided to leave them in after careful consideration.


the puzzle wrote:1. A group of people live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly.

2. No one knows the color of their eyes.

3. Every night at midnight, a ferry stops at the island. If anyone has figured out the color of their own eyes, they [must] leave the island that midnight.

4. On this island live 100 blue-eyed people, 100 brown-eyed people, and the Guru.

5a. The Guru has green eyes,

5b. ...and does not know her own eye color either.

6a. Everyone on the island knows the rules and the properties stated above

6b. ...(except that they are not given the total numbers of each eye color)

6c. ...and is constantly aware of everyone else's eye color. Everyone keeps a constant count of the total number they see of each (excluding themselves).

7. However, they cannot otherwise communicate.

8a. So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes, but that does not tell them their own eye color; it could be 101 brown and 99 blue. Or

8b. 100 brown, 99 blue, and the one could have red eyes.


Unitalicized sentences/clauses are not contentious to the problem of brown-eyed people leaving.

Sentence 2's quirk is a mere editing point on technicality. They don't know their eye colour to start, but the blue-eyed people will be able to deduce it, and arguably "know" their own eye colour. I think it can be combined with clause 5b; see comments two paragraphs down. Also, I'd clarify by saying they don't know the colour of their own eyes.

In Sentence 3 (actually two sentences), I would replace "figured out" with "deduced", and "they [must] leave" to something more like "they can and will leave." There seems to be no mechanism for them to prove that they know, other than the fact that they are perfectly logical, which has been stated.

Sentences 4-8 are quirky. Specifically, sentence 4 and clause 5a are quirky because of the quirk in clause 6a, but is implicitly (though quirkily) unquirked by clause 8b. Um... I meant that seriously. See next paragraph.

The quirks lie in how much each person knows about eye colour. Sentence 6 doesn't clearly state how much information is retained regarding eye colours after clause 6b is factored out. It tends to imply that the islanders know the only eye colours are blue and brown (and green). Sentence 8b clarifies this, but if sentences 4-6 were clearer, sentence 8 could be unnecessary.

Specific rules that need mentioning in sentences 4-8 are:
- Eye colours include blue, brown, and green.
- Eye colours do not necessarily exclude any other colour
- Sentence 6c: Everyone on the island is aware of everyone else's eye colour, and keeps a constant count (also a red herring, as it implies that some islanders may leave before/after others--good one!) of the number they see of each (excluding themselves).
- None of the islanders--not even the Guru--knows his or her own eye colour (implied from this is that they don't know exactly how many people of each eye colour there are)
- Nobody on the island can communicate another's eye colour in any way.
- Everyone knows the above rules
- There are 100 blue-eyed islanders, 100 brown-eyed islanders, and the guru, whose eyes are green.

Another quirk with sentence 5 is that the guru's eye colour doesn't matter at all. If her eyes were blue, everyone would know that, and the other blue-eyed people would leave in no lesser or greater number of days; if her eyes were not blue, well we know the solution to that. Stylistically, it provides an explanation for why she is the one person who gets to speak, and adds another variable for the solver to consider. However, I think Randall is being generous: the title to the "hardest logic puzzle in the world" would go to this puzzle, but with the guru's eye colour left vague to the reader (but clearly not a member of the original 200). For this reason, the Guru can never leave.

A quirk throughout is that the inhabitants (except for the Guru) are always referred to in the plural form (likely to avoid copious repetitions of "he and she" while remaining Basically Decent, or otherwose choosing between calling them all males or all females). This adds to the difficulty because the inductive reasoning requires you to think of the situation from the individual's standpoint. Sentence 8 relieves this difficulty a bit, and could be removed if the points that it addresses are clarified.

I think the timing should be changed and clarified, in such a way that the guru makes his claim on the first day, before the ship comes (dawn and dusk; noon and midnight; 2:40 and 4:20; it doesn't matter). This way, it is clear for the purposes of confirming the answer to denote when the "100th day" comes in relation to the day the guru makes his statement.

ENDNOTES:

...Since Randall is the author of the puzzle, I will leave it to him to decide whether to incorporate any of these suggestions in future versions of his puzzle. Either way, I wouldn't have been able to solve it on my own.

...Also, as a clarification, I don't usually use the word "quirk" in my day-to-tday life, I just wanted to avoid calling them "problems", "unclarities", "weaknesses," or "inefficiencies," because they are not necessarily so.

...Also, this post took me four hours to write. Phew!

- RG>
Jack Saladin wrote:etc., lock'd
Mighty Jalapeno wrote:At least he has the decency to REMOVE THE GAP BETWEEN HIS QUOTES....
Sungura wrote:I don't really miss him. At all. He was pretty grouchy.
User avatar
RealGrouchy
Nobody Misses Me As Much As Meaux.
 
Posts: 6697
Joined: Thu May 18, 2006 7:17 am UTC
Location: Ottawa, Ontario, Canada

Postby Pyrthas » Thu Jul 13, 2006 1:52 am UTC

mheard wrote:In the 4-man case, each blue-eyed person knows that each blue-eyed person can see at least two other blue-eyed people. The reason that the 2- and 3-man cases worked has completely evaporated.
This reply's coming a little late, but I just found the forum. I came up with the solution in a minute or two, but I sort of cheated in that I'm somewhat familiar with this sort of situation. Anyway, here's an attempt to make the reasoning of each individual blue-eyed person a little more explicit.

In the following cases, let A, B, C, D be blue-eyed (B, C, and D only if there are enough blue-eyed people).

Take the case with only one blue-eyed person. That person (A) thinks to himself, "Suppose that I have non-blue eyes. Then, since I can see nobody with blue eyes, the guru lied. But the guru didn't lie [this is not actually explicitly stated in the statement of the puzzle, but let's assume it], so I cannot have non-blue eyes." A then leaves that night.

Two blue-eyed people: On day 1, A thinks to himself, "Suppose that I have non-blue eyes. Since I can see one person (B) with blue eyes, this must be the one-person case. Thus, B, seeing nobody with blue eyes, will leave tonight." But B doesn't leave that night, so on day 2, A thinks to himself, "Well, B didn't leave, so B must not have seen nobody with blue eyes. That is, B must not have gone through the reasoning I was expecting her to go through. Thus, the supposition that led to that expectation must have been wrong, and I must have blue eyes." B does the same thing with A, and they both leave on day 2.

Three blue-eyed people: On day 1, A thinks to himself, "Suppose that I have non-blue eyes. Since I can see two people with blue eyes (B and C), this must be the two-person case. Thus, each of them is going to go through the thought process mentioned above, and leave on the second night. (That is, B will suppose that she has non-blue eyes, in which case it's the one-person case, and expect C to leave on the first night. C does not leave on the first night, so B knows that she has blue eyes and leaves on the second night. C goes through similar reasoning about B's behavior, also leaving on the second night.)" But nobody leaves on the second night, so on day 3, A thinks to himself, "Well, B and C didn't leave, so they must not have gone through the reasoning I was expecting them to go through. Thus, the supposition that led to that expectation must have been wrong, and I must have blue eyes." B and C do the same thing with the appropriate pair, and they all leave on day 3.

Four blue-eyed people (the case that was giving you trouble): We do precisely the same thing, only it takes more steps. Hopefully by now, the steps are apparent. On day 1, A thinks to himself, "Suppose that I have non-blue eyes. Since I can see three people with blue eyes, this is the three-person case. Thus, each of them is going to go through the thought process outlined in the three-person case above, and they'll all leave on day 3." Nobody leaves on day 3, though, so A knows that his supposition was wrong, and thus that he has blue eyes.

The important thing to realize (and I think that this is where you were getting hung up) is that this is all what A expects to happen based on his supposition that his eyes aren't blue. He supposes that it's the three-person case and thus expects B, C, and D to each suppose that it's the two-person case (and thus expects B to expect C and D to suppose that it's the one-person case, and expects C to expect B and D to suppose that it's the one-person case, and expcets D to expect B and C to suppose that it's the one-person case; phew). What he finds, though, is that B, C, and D don't do that, since if they did, they'd all leave on day 3 (and of course they don't: they all see three people with blue eyes, including A). Thus, A is able to conclude that the supposition that led to those expectations, viz., that his eyes aren't blue, must be false.

Put another way, on day 4, A knows that they didn't actually suppose that it's the two-person case (because if they had, they all would have left the previous night). The only reason they wouldn't have done that is that they saw three people with blue eyes. The only way they could have seen three people with blue eyes is if A had blue eyes. Thus, on day 4, A knows that he has blue eyes.

And that's the four-person case.

To be clear, A doesn't actually expect these things. A more accurate description of the situation would be that A knows, "If I have non-blue eyes, then <what I've been saying A expects>." This is the hypothetical that keeps getting mentioned. But it's incredibly cumbersome to talk in all those hypotheticals, so the supposition-expectation talk will have to stay for now. Just for reference, though, here's the hypothetical that A knows on day 1 in the three-person case.
Code: Select all
If I have non-blue eyes, then
    it's the two-person case, so
    B and C will each see one blue-eyed person, and
    they will each know on day 1,
    "If I have non-blue eyes, then
        it's the one-person case, so
        the other person will each see no blue-eyed people, and
        will leave on day 1."
    That is, B and C will both know that if they have non-blue eyes,
        then the other one will leave on day 1.
    But nobody will leave on day 1, so
    on day 2, they will both know that they have blue eyes and leave.

In short, A knows:
If I have non-blue eyes, then
    B and C will leave on day 2.
Since nobody leaves on day 2, A knows that he has blue eyes.

The one for the four-person case is long and ugly, and even if I wrote it out, I don't think that it would be particularly instructive.

This was written up a little hastily, and while I rewrote things a bunch, I'm quite certain that it's still not as clear as it could have been. I apologize; if something isn't clear, let me know.

I know that there are other fun cases involving needing to know that everyone knows that everyone knows that... something (technical term for something that's known by everyone to be known by everone to be known by everyone...: common knowledge), but I can never remember them (probably because I don't really work in this field).

In any event, it's pretty nice to find a forum that has this sort of thing on it.
Pyrthas
 
Posts: 21
Joined: Thu Jul 13, 2006 12:01 am UTC

Postby DaveFP » Fri Jul 21, 2006 12:04 am UTC

Fantastic puzzle, I liked it a lot. My Girlfriend didn't, but then again she is an arts major.

The puzzle took me about 10 minutes to solve, the givaway for me was that it mentions on the puzzle page that it involves 'serious inductive logic'. I then began constructing the base case (one blue-eyed person) and the rest followed fairly quickly. It looks like those Discrete Maths courses weren't a waste of time after all :D
DaveFP
 
Posts: 76
Joined: Thu Jul 20, 2006 11:43 pm UTC

Postby dveteran » Fri Jul 21, 2006 12:53 am UTC

Good puzzle, anyway I was thinking what would happen if, as well as the people noted before, if there were a blind person, who had blue eyes? Now this person can count how many people are on nthe island, he just doesn't know what colour their eyes are.
I have an idea of what happens, but I want to hear your ideas, especially because I'm not sure if it is right.
dveteran
 
Posts: 4
Joined: Fri Jul 21, 2006 12:07 am UTC

Postby Charodei » Fri Jul 21, 2006 9:19 pm UTC

I took a different approach to the problem. We are told that at least one person leaves. If one person can deduce their eye color, everyone with that eye color will use the same logic, so they will all leave at once. Since the guru provides information about blue eyes, all the blue-eyed people leave. (The brown-eyed people can't leave, because if they could deduce their eye color, the guru wouldn't be necessary, and they all would have left the first time the ferry came.)

Unfortunately, I think you need to use the islanders' logic to find out when they leave.
User avatar
Charodei
 
Posts: 86
Joined: Fri Jul 21, 2006 8:29 pm UTC

Postby Pyrthas » Sat Jul 22, 2006 2:10 am UTC

Charodei wrote:Since the guru provides information about blue eyes, all the blue-eyed people leave.
This, I think, is a little too quick. At least, to prove that only people who have the same color eyes as the color that the guru talked about leave would, I think, take a bit of doing.
Pyrthas
 
Posts: 21
Joined: Thu Jul 13, 2006 12:01 am UTC

Postby Charodei » Sun Jul 23, 2006 12:33 am UTC

I admit that my logic isn't entirely rigorous. However, given that this is a logic puzzle rather than a riddle, it's hard to think of another solution that wouldn't involve an unexpected twist in thinking. So it is jumping to conclusions a bit, but to a not unreasonable conclusion.
User avatar
Charodei
 
Posts: 86
Joined: Fri Jul 21, 2006 8:29 pm UTC

Postby Westacular » Wed Aug 02, 2006 6:59 pm UTC

You can, I believe, generalize this:

On an island with N blue-eyed people and M brown-eyed people and K green-eyed people, etc., if the Guru made a statement on the first day saying:

"I see a blue eyed person, a brown-eyed person, a green-eyed person, ..." etc., then each group would leave en masse on the day corresponding to the size of their group. There are, I believe, no constraints on the number of different colours or the relative sizes of the groups.
Westacular
 
Posts: 44
Joined: Wed Aug 02, 2006 5:53 pm UTC
Location: Waterloo, ON, Canada

Postby Axolotl » Thu Aug 03, 2006 8:24 am UTC

It'd be very much appreciated if someone could explain to me the answer to the question:
What is the quantified piece of information that the Guru provides that each person did not already have?


I've tried to glean this from all the write-ups that have been posted so far, but to no avail.
User avatar
Axolotl
 
Posts: 107
Joined: Fri Jul 21, 2006 5:15 am UTC
Location: Melbourne

Postby Westacular » Thu Aug 03, 2006 10:11 pm UTC

I didn't understand it until reading this thread, either, but I'll take a stab at explaining it:

The Guru provides an end case to the ridiculously recurrent hypothesis of what people know.

Suppose you have blue eyes: you ('A') look around and see 99 people with blue eyes. You know that one of those people with blue eyes ('B') will see either 98 or 99 people with blue eyes, depending on whether or not you have blue eyes.

BUT! You suppose that if B sees 98 blue-eyed folk, then HE will think, well, this other blue-eyed dude ('C') might only see 97 people with blue eyes.

(You, personally, know that this cannot be the case, but you don't know that B knows that, because B doesn't know that he has blue eyes.)

And so A thinks that B thinks that C thinks that it's possible that D only sees 96 people who have blue eyes.

This chains onward indefinitely. What the Guru provides is a base case at the end of that chain: "... thinks that Y thinks that it's possible Z sees 0 people who have blue eyes, but if that's the case he'll leave the island tonight."

The bold text could not be placed at the end of the hypothetical before the Guru's statement, because prior to the statement a person seeing no blue eyes would not be able to conclude that he must be the one with blue eyes. The Guru's statement provides a starting point with which to test this overwrought hypothesis; as each day passes, one step of it is proven impossible until the day arrives when you KNOW that all the other blue-eyes see same thing as you, and therefore you all have to leave that night.

The fact that everyone is acting identically in parallel waiting for the results of the 99th night works because they don't all collectively know that everyone else knows that they're all waiting for that.
Westacular
 
Posts: 44
Joined: Wed Aug 02, 2006 5:53 pm UTC
Location: Waterloo, ON, Canada

Postby Axolotl » Fri Aug 04, 2006 2:03 am UTC

Thanks- I think I partially understand what you're getting at, but I'm afraid I still can't get past the stumbling block that the guru told the islanders something they all already knew, already knew that everyone else knew, already knew that everyone else knew that everyone else knew, and so on all the way down. I think I see the point made about the implications for the hypothetical case, but I still can't grasp the fact that this piece of information could have any effect on the situation.
User avatar
Axolotl
 
Posts: 107
Joined: Fri Jul 21, 2006 5:15 am UTC
Location: Melbourne

Postby Torn Apart By Dingos » Fri Aug 04, 2006 10:34 am UTC

I can't explain quite what information the Guru gives them either. But I know the argument that he tells them something they already know doesn't work:

Consider the case of two blue eyes. Then "everyone already knew" what the Guru told them. Yet, if you had blue eyes, and assume that you don't, you'll expect the other guy to leave tonight, but if he doesn't, you know you're the other one and can leave as well.

So in the case of two people with blue eyes, the quantified piece of information you get is that you know that the other guy will know he can leave, assuming you don't have blue eyes yourself.

Whereas in the case of only one guy with blue eyes, you'll know first-hand that you can leave.

So I can imagine it's sort of a tower of "you know that they know that they knew that ..." statements... but it still feels silly because it will only reach the base case if each person assumes he does not have blue eyes, even though you know they do. This is an evil problem.
User avatar
Torn Apart By Dingos
 
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Postby RealGrouchy » Fri Aug 04, 2006 4:41 pm UTC

dveteran wrote:Good puzzle, anyway I was thinking what would happen if, as well as the people noted before, if there were a blind person, who had blue eyes? Now this person can count how many people are on nthe island, he just doesn't know what colour their eyes are.
I have an idea of what happens, but I want to hear your ideas, especially because I'm not sure if it is right.


It would depend.

Assuming one blind person:

Case 1: if the others knew who he/she was (or at least that there was one blind person with eye colour X), then each eye-colour group could exclude that person from their group (e.g. the blue eyes can treat the blind person as a non-blue eyes).

Case 2: If the others don't know who the blind person is (or at least don't know what group the blind person belongs to), then they would not be sure either way.

There could be any number of case-1 people, but the presence of any case-2 people would strand them all forever. If there is an unknown number of blue-eyed blind people, then they would fall into case 2.

Since they are all perfectly logical, I would like to assume that seeing people would realize "the guy who keeps bumping into me is the blind person", and would be able to exclude them, indpendent of their eye colour. :P

- RG>
Jack Saladin wrote:etc., lock'd
Mighty Jalapeno wrote:At least he has the decency to REMOVE THE GAP BETWEEN HIS QUOTES....
Sungura wrote:I don't really miss him. At all. He was pretty grouchy.
User avatar
RealGrouchy
Nobody Misses Me As Much As Meaux.
 
Posts: 6697
Joined: Thu May 18, 2006 7:17 am UTC
Location: Ottawa, Ontario, Canada

Ah

Postby Guest » Thu Aug 10, 2006 10:50 pm UTC

Ah, I finally looked at this logic puzzle, again, months after you first presented it to me in IHOP, and came to the conclusion in about five minutes of thinking through it using the clue you had given me of "Think in smaller ratios." That, and after having glanced at the old logic puzzle about the prisoners being executed wearing hats, I was already thinking in terms of using others inactivity as indicative of what the others see, it made quick sense. It's not that hard given the right experience with similar scenarios, I imagine.
Guest
 

Postby Westacular » Thu Aug 10, 2006 11:25 pm UTC

RealGrouchy wrote:Case 1: if the others knew who he/she was (or at least that there was one blind person with eye colour X), then each eye-colour group could exclude that person from their group (e.g. the blue eyes can treat the blind person as a non-blue eyes).


Wrong. If there's a blind, blue-eyed person and everyone knows he's blind, then no one will ever leave.

Let's start small: Two blue-eyed people, one of them blind. Guru says he sees blue eyes. Other blue eyes sees Ol' Blindy there and thinks, "well, it's definitely him, but it could be me, but Blindy will never leave since he can't deduce anything, so his inaction is inevitable -- his not leaving on the first night proves nothing, and I have no reason to ever think I have blue eyes."

And that's it. A blue-eyed blind person cannot be excluded, because he satisfies the Guru's statement, but his guaranteed, perpetual inaction blocks everyone else from doing anything.

IF, say, Blindy was told each day how many people left the night before, AND he thought he was the only blind person on the island, then after a number of days had passed equaling the population of the island, he would leave, having had absolute evidence that he was blocking the standard solution -- which would only be the case if he had blue eyes. The following day, the scenario would restart as if the Guru had just made his statement.
Westacular
 
Posts: 44
Joined: Wed Aug 02, 2006 5:53 pm UTC
Location: Waterloo, ON, Canada

Postby posiduck » Fri Aug 11, 2006 6:28 am UTC

I think my favorite part of the puzzle is that if they know that one person on the island is not a perfect logician they don't leave.
blistering guitar solo
posiduck
 
Posts: 136
Joined: Fri Aug 11, 2006 4:47 am UTC
Location: Geography City, CA

Postby RealGrouchy » Fri Aug 11, 2006 2:23 pm UTC

Westacular wrote:
RealGrouchy wrote:Case 1: if the others knew who he/she was (or at least that there was one blind person with eye colour X), then each eye-colour group could exclude that person from their group (e.g. the blue eyes can treat the blind person as a non-blue eyes).


Wrong. ...


Ah, touché.

- RG>
Jack Saladin wrote:etc., lock'd
Mighty Jalapeno wrote:At least he has the decency to REMOVE THE GAP BETWEEN HIS QUOTES....
Sungura wrote:I don't really miss him. At all. He was pretty grouchy.
User avatar
RealGrouchy
Nobody Misses Me As Much As Meaux.
 
Posts: 6697
Joined: Thu May 18, 2006 7:17 am UTC
Location: Ottawa, Ontario, Canada

Postby alextrebek » Thu Aug 31, 2006 9:33 pm UTC

Westacular wrote:You can, I believe, generalize this:

On an island with N blue-eyed people and M brown-eyed people and K green-eyed people, etc., if the Guru made a statement on the first day saying:

"I see a blue eyed person, a brown-eyed person, a green-eyed person, ..." etc., then each group would leave en masse on the day corresponding to the size of their group. There are, I believe, no constraints on the number of different colours or the relative sizes of the groups.

When I first started this post, I was going to say that I think problems would arise if the three groups were equivalent, but now that I think about it, there wouldn't be. If there were 33 of each, they would all see 33 of the two groups they aren't and 32 of the one they are, and they'd all leave on the 33rd day. So yeah, that sounds good to me.

Somebody earlier said that the guru was taking a risk by pointing out the blue eyes, because she doesn't know that she doesn't have blue eyes; since she is the one who stated that she could see somebody with blue eyes, the islanders know to only look among the ranks of their fellow islanders, since the guru could not see her own eyes and still be on the island. They'd still leave on day 100, and she'd stay, blue eyes or not.

And I have to say this is an amazing puzzle.
alextrebek
 
Posts: 2
Joined: Thu Aug 31, 2006 9:20 pm UTC

Postby Vesio » Sun Sep 03, 2006 4:17 pm UTC

edit: I was wrong!
Vesio
 
Posts: 1
Joined: Sun Sep 03, 2006 3:42 pm UTC

Postby Cirne » Wed Sep 13, 2006 7:16 pm UTC

Gozer wrote:One interesting thought occurs, but it's a bit of a spoiler, so highlight below only if you already know the answer to the puzzle.


SPOILER:
======
My coworker thought this was a clever way for the guru to get people off the island. But then I realized that the guru is taking a rather substantial risk of leaving the island herself! If the Nth day wound up with an empty ferry, she would be joining the exodus the very next night!
======


Not quite! Since it is the Guru herself who makes the statement, everyone knows she does not know her own eye color, and so she will never factor into their solutions. And so, she will never be able to figure out her own eye color from her own statements. The problem would not change even if the Guru's own eyes were blue.
Cirne
 
Posts: 2
Joined: Wed Sep 13, 2006 7:10 pm UTC

One thing I can't figure out

Postby Larissa » Wed Oct 04, 2006 11:41 pm UTC

All you smart people will have to help me, because I get caught up in circular logic at 3 people with blue eyes. If there are 3 people with blue eyes, there will be no two-person case, because the two-person case says that the person sees only one other person with blue eyes, and that would never occur with 3 blue-eyed people, right? Each one would look around and see 2 other blue-eyed people.

You'll have to forgive me; my logic experienced a critical error while being installed in my brain. Sorry if I missed something obvious.
Larissa
 
Posts: 9
Joined: Mon Oct 02, 2006 8:37 pm UTC
Location: Utah, USA

Postby rlo » Thu Oct 05, 2006 12:04 am UTC

Could someone please provide a pointer to the original non-solution post? It doesn't seem to have Blue Eyes in the title...
rlo
 
Posts: 92
Joined: Wed Oct 04, 2006 11:43 am UTC

Here you go

Postby Larissa » Thu Oct 05, 2006 12:39 am UTC

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

And thanks to my physicist husband, my logic program is undergoing a re-install . . . please pardon the construction dust.
Larissa
 
Posts: 9
Joined: Mon Oct 02, 2006 8:37 pm UTC
Location: Utah, USA

Postby Gible » Wed Oct 11, 2006 9:36 pm UTC

Cirne wrote:
Gozer wrote:One interesting thought occurs, but it's a bit of a spoiler, so highlight below only if you already know the answer to the puzzle.


SPOILER:
======
My coworker thought this was a clever way for the guru to get people off the island. But then I realized that the guru is taking a rather substantial risk of leaving the island herself! If the Nth day wound up with an empty ferry, she would be joining the exodus the very next night!
======


Not quite! Since it is the Guru herself who makes the statement, everyone knows she does not know her own eye color, and so she will never factor into their solutions. And so, she will never be able to figure out her own eye color from her own statements. The problem would not change even if the Guru's own eyes were blue.

This logic I don't quite follow. Why would they not factor her into their solutions? (especially if the Guru's eyes were blue.)
I believe this is the same problem that I have with each of them (not) coming to the same conclusion as the Guru's statement themselves and counting days from some arbitrary point before this.
Edit: Having just sent the puzzle url to someone(and wallowed in sadistic ecstasy :lol: ) I believe the Guru also provides the arbitrary point at which everyone knows to count from.
Gible
 
Posts: 4
Joined: Wed Oct 11, 2006 9:24 pm UTC
Location: Hamilton, New Zealand

The information provided by the Guru

Postby jks » Thu Oct 12, 2006 7:14 am UTC

I hang out with people who are so cool that many of them solve this problem in a few minutes. Then I ask them what happens if the Guru says the same thing, not publicly so everyone can hear it at once, but privately to each person. When they figure that out, I ask them what happens if the Guru says, privately to each person, “I can see someone who has blue eyes, and I'm telling that to everyoneâ€
jks
 
Posts: 3
Joined: Thu Oct 12, 2006 6:49 am UTC
Location: Helsinki, Finland

Next

Return to Logic Puzzles

Who is online

Users browsing this forum: No registered users and 6 guests