Interesting Logic Problem

[snowburns]

This is ridiculous

[Tye 1on]

Fine. Who should leave the island?

Also, no one's attempted to answer my "What if there is a blind person on the island?" query.

Yeah.

And why do drive-thru ATM's have Braille?

[AbsolutStoli]

If there had been two purple-eyed people present (in addition to the other 201) on the island, would they both leave on the second night? Why? Neither one knows whether his eyes are purple or green, right? But if the doctor says "I see someone with purple eyes", then they both know on the second night following that they have purple eyes. However, this argument doesn't work if there are three purple eyed people; the doctor would have to say "I see TWO people with purple eyes", and then they all three would leave on the following night.

The "induction" argument for this problem is fundamentally flawed, as the step from N-blue-eyed to N+1-blue-eyed doesn't work wihout the doctor saying "I see N people with blue eyes".

I knew the prof was being a cheapskate here...you should demand sushi for the whole class, since there is no solution that meets all the stated conditions.

i was hoping i wasnt the only one who thought this. that whole solution only works if there is only one of the announced color (blue in this case). if there is more than one of the announced color then it doesnt work.

if the dr. says "i see someone with blue eyes" and there are more than 1 blue and however many brown, everyone sees someone with blue eyes. the assumption that one of the blues is going to leave each night, eventually leaving just 1 blue for the 100th night cant be made because either all blues leave or none, because no one can make the conclusion that they have blue eyes if there are 2 blues and at least 3 people.

i hope that made sense...

[jrbd]

Also, no one's attempted to answer my "What if there is a blind person on the island?" query.

From the problem statement:

Everyone sees everyone else at all times

So therefore the blind person can see. Which is just as logical as the problem statement as a whole.

[sfotex]

Ok, here's another way to think of it:
there are 3 groups of people on the island:

Those that see 99 blue eyes, 100 brown eyes, and one green eye (i.e. the people with blue eyes)

Those that see 99 brown eyes, 100 blue eyes, and one green eye (i.e. the people with brown eyes)

Those that see 100 brown eyes and 100 blue eyes (the doctor)

WHen the doctor announces he sees someone with blue eyes the people on the island go thru the inductive reasoning that's been outlined in previous emails, and 100 days from the doctors announcment all the people that see 99 blue eyes and 100 brown eyes leave on the ferry.

Is someone had violet eyes, then there would now be 4 groups, so there would be different grouping/reasoning going on.

[komo]

i was hoping i wasnt the only one who thought this. that whole solution only works if there is only one of the announced color (blue in this case). if there is more than one of the announced color then it doesnt work.

if the dr. says "i see someone with blue eyes" and there are more than 1 blue and however many brown, everyone sees someone with blue eyes. the assumption that one of the blues is going to leave each night, eventually leaving just 1 blue for the 100th night cant be made because either all blues leave or none, because no one can make the conclusion that they have blue eyes if there are 2 blues and at least 3 people.

i hope that made sense...

I think jrb is right that this problem is hard to do formally by induction, probably because it's hard to figure out a good notation. In any case, the way people above have used 'induction' is kind of loose. You don't really need induction here.

The 'proofs' provided above depend on the condition that every person 1) knows the eye color count at all times and 2) acts logically and knows that everyone else acts logicially too. I think the italicized part is what gives jrb & stoli trouble.

So the reasoning for why n blue-eyed people would all individually decide to leave after n days is something like 'given that n-1 days have passed and the n-1 blue-eyed people on the island haven't left, i must also be blue eyed'

THis feels like induction, but isn't really the same thing in a formal sense.

[summit]

However, blue-eyed person A does not know that blue-eyed person B can see someone else with blue eyes. From A's perspective, A might have purple eyes, and B might not see anyone with blue eyes at all.

But after the Doctor makes his statement, and then B does not leave, A learns some new information: A now knows that B can see someone else with blue eyes.

I disagree... knowing about other eye color of one random person does not reveal your own when there are that many people... could be purple.

People only get to leave when they know their own color. Telling them something they already know doesn't tell them their own eye color. Like i said before there are too many people for saying "blue>=1" to be of any help without there being a context of who he was referring to or limiting the nubmer of people in his presence


ITS A TRAP

The doctor says "I see someone with blue eyes." Everyone else on fucking island thinks to themselves "Really? Me too you mother fucking green eyed dumbass!"
Who gets kicked off the island? The doctor for finally getting the nerve to speak then saying something so monumentally retarded and unhelpfull as blue>=1

now... go kick your prof square in the nuts and nuke the island... put those poor mute bastards out of their misery

(also, they should ask the ferry captain... he can probably talk and being a ferry captian he might have a mirror in his purse)
also... if they were really a bunch of logicians they would have said "fuck this horseshit!" and seized the Ferry to escape
I know he ruled out genetics... but they could all have sex and probably derive enough data from their offspring's eyes to determine their own... but then their offspring would be left on the island (sux for them)

If there had been two purple-eyed people present (in addition to the other 201) on the island, would they both leave on the second night? Why? Neither one knows whether his eyes are purple or green, right? But if the doctor says "I see someone with purple eyes", then they both know on the second night following that they have purple eyes. However, this argument doesn't work if there are three purple eyed people; the doctor would have to say "I see TWO people with purple eyes", and then they all three would leave on the following night.

The "induction" argument for this problem is fundamentally flawed, as the step from N-blue-eyed to N+1-blue-eyed doesn't work without the doctor saying "I see N people with blue eyes".

I knew the prof was being a cheapskate here...you should demand sushi for the whole class, since there is no solution that meets all the stated conditions.

YESSSSSSSSSSSSSS!!!!

(and kick the proff square in the nuts!

[summit]

So the reasoning for why n blue-eyed people would all individually decide to leave after n days is something like 'given that n-1 days have passed and the n-1 blue-eyed people on the island haven't left, i must also be blue eyed'

Yea but won't all the brown eyed freaks be thinking the same thing and leave too?

[komo]

Yea but won't all the brown eyed freaks be thinking the same thing and leave too?

except each brown eye sees n blues, so they wouldn't leave till the next night...^

[summit]

except each brown eye sees n blues, so they wouldn't leave till the next night...^

BZZZZZZZZZT

Nobody on the island knows all the color totals (from how i interpreted the rules in the opening) if they did, then everyone would leave on the first night

And IF all the blues left, the browns still don't know indiviually what their eye color is... could be purple with yellow spots. They only know that there are 99 brown eyes and one green and themselves (unknown) walking around the island.

But the blues are still there because each blue is still an unknown (see the reasoning in previous posts).

Once again, the contextless statement by the doctor that "blue>=1" doesn't mean anything to a bunch of people who already know that "blue=99 or 100" (if they have blue eyes) or "blue==100 or 101" (if they have brown or green eyes). the data "blue>=1" is already included in their existing knowledge

if the doctor had said "i see 100 someones with blue eyes" the brown eyed folk would still be stuck on the island wondering whether or not their eyes were purple...

[BeanDip4All]

^

ha!!!

34567

[f2f]

Now 'fess up f2f - had you seen a similar problem before?

no i haven't. i did however study digital logic and have laid down a few FPGAs in mytime

[komo]

laid down a few FPGAs in mytime

my condolences


Summit: My understanding of the above solutions is that the blues all remain till the 100th night, whereupon they leave. Each brown sees all the blues the entire time, i.e. they always see 1 more blue than any blue eyed person would, thus no brown would make the logical leap to leave on the same night as a blue.

The prof's statement is meaningful simply because it provides an external check against which the logical network of the island people can start to work.

[smitchell333]

I've thought more about this and now that TacLuv has correctly stated the question I think I have an answer - although I suspect there are multiple answers.

I think the idea (Assuming everyone WANTS to get off the island and therefore constructs a logical solution to get themself off) is that

A) each person will count the # of others with blue eyes (ie for those with blue eyes = N). And the # of others with Green, and Brown eyes).

B) once you know these you will logically know that theoretically you have 4 options - you have:

1) Blue eyes, 2) Green eyes, 3) Brown eyes, 4) you have some other eye color and are the only one. There is no way of ever knowing for CERTAIN whether you have any eye color, other than guessing and presenting yourself as knowing you have an eye color and if you get off - you know.

C) Therefore you (assuming you want off the island) logically construct a plan to escape in the shortest possible time:

1) Night one - present yourself as either randomly blue or brown - you have 0 information to suggest either way but you know that statistically brown and blue are best represented and therefore your best guess - so by laws of chance approximately 50 blue and 50 brown will get off.

2) Night two - present yourself as the other option of the blue/brown from what you presented the day before -you have 0 information to suggest either way but you know that statistically brown and blue are best represented and therefore your best guess - so the remaining 50 blue and 50 brown will get off.

3) Night three - Doctor is the only one remaining - he will present himself as randomly chosen color other than blue, brown, green - "I have grey eyes" - the doctor could get off, but only by a lucky guess.

5) Day 4, etc - Dr presents himself as randomly chosen color other than blue, brown, green - "I have grey eyes" - the doctor could get off, but only by a lucky guess - he could be here forever but probably will be off by day 8 or 9 as there are really only a handful of common eye colors to guess.

[pappag]

Proof: If the original problem had been posed with 1 blue eyed person (and 199 of another color), it is obvious in this case that indeed this blue-eyed person would in fact learn something from what the doctor said and leaves on the 1st midnight. (The other 199 would not, however, since they already knew there was at least that one blue-eyed person.)

Ok, what if the original problem had been posed with 2 blue eyed folks, and 198 of another color? Well each of these two would not know their own eye color. Therefore, each would think, "either that person is the only blue-eyed person, or I also have blue eyes. If I do not have blue eyes, he will leave the island tonight" (by the reasoning above). Therefore, when they see one another on the island the next day, it hit's them both. "I must have blue eyes, too. Therefore, I have to leave tonight (2nd midnight for 2 blue-eyed people and 198 non-blue-eyed people). Note that this thought process is unique to these two -- the other 198 see 2 instead of 1 blue-eyed person.

Ok, if there were 3 with blue eyes, each of those three would think, "If I have non-blue eyes, then there are only two blue-eyed people, in which case they'll leave tomorrow night (2nd midnight)" (by the reasoning above about 2 blue-eyed people). Since they don't, they realize they must leave on the 3rd midnight.

If there are N with blue eyes, each of those N would think, "If I have non-blue eyes, which I really hope is true, then there are only (N-1) blue-eyed people, in which case they'll have to leave the island on the (N-1)th night." But they don't, so on the Nth night, all N blue-eyed people leave.

[summit]

OHHHHHHHHHHHHHHHHHHHHHHHH it makes sense now!

[smitchell333]

Think about if there was just one person with blue eyes on the island- he would know that they would leave the first night, becuase he knows he is the only person the Dr. was talking about. He would look around, see no one else, and know he should leave. So (THEOREM 1) if there is one blue eyed person, they would leave the first night.

Now consider there are two blue eyed people. On day 1, X thinks to himself, "Suppose that I don't have blue eyes. Since I can see one person (Y) with blue eyes, this must be the one-person case. Thus, Y, seeing nobody else with blue eyes, will leave tonight." (THEOREM 1) But Y doesn't leave that night, so on day 2, X thinks to himself, "Well, Y didn't leave, so Y must seen somebody else with blue eyes. That is, because they are all perfect logicians, Y must not have gone through the reasoning I went through. Thus, I must also have blue eyes." X does the same thing with Y, and they both leave the second night.

Thus, (THEOREM 2): If there are two blue-eyed people on the island, they will each leave the 2nd night.

This continues with the group leaving en mass on the corresponding night of the # of people in their group. When you reach the 99th night and no one has left, all 100 blue eyed people will leave together on the 100th night. Think of it as all the blue eyed people on the island playing a big game of chicken with each other, right up until the 100th night. Good thing they are all "perfect logicians!"



Yes, but the critical point is that he only speaks once. He doesn't reveal anything the people on the island don't already know, they can all look at each other and see someone with blue eyes. The Doctor speaking merely starts the cycle of blue eyed people leaving.

The problem with all this and all the N+1 talk is that you can play the guessing game this way but you never KNOW that you dont have Magenta eyes - therefore there is a better guessing scheme as I've outlined.

[Jer]

no i haven't. i did however study digital logic and have laid down a few FPGAs in mytime

Aha! ... me, I just happened to stumble across a paper on "belief propagation" in this week's Science.
Pretty interesting.

[MeatPuppet]

If there had been two purple-eyed people present (in addition to the other 201) on the island, would they both leave on the second night? Why? Neither one knows whether his eyes are purple or green, right? But if the doctor says "I see someone with purple eyes", then they both know on the second night following that they have purple eyes. However, this argument doesn't work if there are three purple eyed people; the doctor would have to say "I see TWO people with purple eyes", and then they all three would leave on the following night.

Not true, remember, these are perfect logicians. The third person would deduce that he had purple eyes after the two other people didn't leave on the second night...and so on, and so on...


Edit: Damn! Nick beat me to it.

[jrbd]

You know, I think I'm wrong about this (somewhat ); The blue-eyed people can deduce their color on day 100 when the other 99 blue-eyed people don't leave. However, since the doctor's announcement is meaningless, this means that the 100 brown-eyed people also can leave on that day; blue and brown are equivalent.

This basically is just a collective strategy for signalling other's eye color: if you see at least N of each color (N >= 2), and if you get to day N+1, you leave, since your color is the same as the group of N (and there can only be one such group, assuming everybody comes up with the same strategy). But there may be a better strategy, involving the greatest common divisor of the group sizes you see and the group sizes plus one, or something like that. If this is the case, as perfect logicians, the blue group could very well have all left on day 9 or something like that, right? After all, what did they all know on day 51 that was different than day 50? Maybe a logical rule would be something like: "if I see two groups of size N and N+1, then leave on day GCD(N,N+1), else if sizes are N and N+2, then leave on day N, else if they're both the same size, then I'm screwed". I suspect I'll be thinking about this while riding lifts this weekend....

Oh, yeah, and there's another problem: the first paragraph in the original statement (the part "everybody knows") never states directly that each person can have ONLY ONE eye color. What if some of them might have one blue eye and one brown eye? Or four eyes, two of each color??? The second paragraph implies that this isn't the case, but each of poor slobs on the island don't know whether he has four eyes or not, does he?

[jrbd]

btw, TacomaLuv, have you considered the possibility that your prof just wants an excuse to take you out to dinner?

[pappag]

You know, I think I'm wrong about this (somewhat ); The blue-eyed people can deduce their color on day 100 when the other 99 blue-eyed people don't leave. However, since the doctor's announcement is meaningless, this means that the 100 brown-eyed people also can leave on that day; blue and brown are equivalent.

Brown-eyed people can't leave the island because only blue-eyed people can get on the ferry. They might think they can leave, but will not be able to do so.

[f2f]

Aha! ... me, I just happened to stumble across a paper on "belief propagation" in this week's Science.
Pretty interesting.

i don't have username/password for that article

[Jer]

Article, perspective.

[Blurred]

It's clear that they're not on an island, water is a "reflective surface".

I think your professor is trying to get in your pants.