Interesting Logic Problem

[jrbd]

Finally, the answer is not "No one leaves the island."

The answer is "The professor screwed up telling the puzzle."

Everybody (presumably including the doctor) can see everybody else at all times, so their situation never changes: every night, they know there are lots of people with blue and green eyes present, and nobody ever leaves. Then one night the doctor tells them something they already knew (since everybody can always see everybody else).

I think your prof did this just so he wouldn't ever have to pay up, and to teach you something about problems in the real world (i.e. they're often messed up).

[TeleMang]

^^^ nah i understood it'
pretty complex

looking at the light pattern right now
craziness

is the answer is a mathematical formula?
seems like it would have to be

I am of the belief that there is always a mathematical solution... finding it on the other hand...

I had a friend ask me this a while ago and it drove me crazy. I can only understand it formulawise when n=x

If any of you crazy math types can find an all encompassing formula i would appreciate it.

[AbsolutStoli]

so is your prof. going to tell the class what the answer is or just take whoever got it to dinner and let everyone else wonder?

[MeatPuppet]

I am of the belief that there is always a mathematical solution... finding it on the other hand...

There is a formula for this problem.

I used to have a pet turtle who told me the answers to these types of questions. But, ever since he died I can't do shit for logic problems.

[Jer]

Wait a sec. I think the Doctor's statement does add some "information."

In the two blue-eyed person case, everybody already knows that everyone, the Doctor included, can see someone with blue eyes - everybody knows there is at least one blue-eyed person on the island.

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.

The information is about who knows what.


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

TLuv - nicely worded proof, very clear & concise. Did anyone write up a purely symbolic proof?

P.S. - Probably should point out to your prof that Google is now capable of solving these lovely test pieces.

[AbsolutStoli]

I am of the belief that there is always a mathematical solution... finding it on the other hand...

I had a friend ask me this a while ago and it drove me crazy. I can only understand it formulawise when n=x

If any of you crazy math types can find an all encompassing formula i would appreciate it.

hmmmm....the answer is 42.

[Jer]

I am of the belief that there is always a mathematical solution... finding it on the other hand...

Gödel: there are statements that are true for which no proof can exist.

[Buster Highmen]

How about another one just to keep things rolling.

There is a hallway that is 'x' yards long. Every yard there is a lamp with a string attached (for switching the lamp on/off). The first person walks down the hallway pulling every string (thus turning every light on). The second person sees this (and for some unknown reason is really pissed) and decides to go through pulling every second string. The third person, not be left out, goes through pulling every third string. This continues for a total of 'n' people. How many lights are left on after every person has walked through?

Without loss of generality, n == x. Since for all values of n > x, they never touch a string.

What Tacoma means to say is that her proof is based on induction. She's proven it true for x == 1, assumes it true for some x and then proves it true for x+1.

In keeping with that incredibly powerful strategy think about increasingly larger cases.

If x == 1, the light is on.
If x == 2, the first light is on, the second light is off.
If x == 3, the first light is on, the second light is off and the third light is off.

Now things get more interesting because 4 is divisible by 2. (edit, fixed, dylsexics untie!)

If x == 4, the first light is on, the second light is off, the third light is off and the fourth light is on.
(edit) The 4th light is on because person 2 turned it off, but person 4 turned it back on.

So the first observation is that for each prime p < x, the pth light is off. But if 2*p < x, the 2*pth light is on. Similarly for 3 and similarly for any prime q for which q*p < x.

But if i==2*2*p < x, then the ith light will be off.

Now I'm guessing that prime number and factors play a role.

In fact I'll venture that if i < x is a product of an even number of distinct primes, the ith light is off.

(running out of time) Guess: In the prime factoring of a number i < x, if any of the primes powers are even, the light will be off. Otherwise it will be on.

(re-edit, that wasn't right, but none of you give a shit anyway....)

[MeatPuppet]

hmmmm....the answer is 42.

Of course it is.

























What was the question again?

[Viva]

so is your prof. going to tell the class what the answer is or just take whoever got it to dinner and let everyone else wonder?

The prof will enter the classroom and declare "I see someone who derived the correct answer" and nothing else. No one will leave the classroom and after 100 midnights everyone will have died of starvation.

[BeanDip4All]

P.S. - Probably should point out to your prof that Google is now capable of solving these lovely test pieces.

I think that's why he gave it to us on a printed out handout to disuade anyone from doing that... and also that whole honor code thing

[smitchell333]

Yeah but the question still was erroneously posed and therefore not valid.

"Who should the Island and...."

[BeanDip4All]

Yeah but the question still was erroneously posed and therefore not valid.

"Who should the Island and...."

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.

[AbsolutStoli]

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.

has the person been blind from birth or blinded by something? does this blind person understand the concept of color? if not, can the person grasp the concept of the rules in the first paragraph (even if he/she can keep track of everyone else through the sense of touch)?

[smitchell333]

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.

Where's my sushi?


I'd guess that if that person has blue eyes then just reduces the # of people who leave the island since he cant do any of the visual deduction you outline, but the day they leave stays the same. If he doesnt have blue eyes it has no impact.

[pappag]

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.

"Any random person with blue eyes can see 100 brown eyed people and 99 blue eyed people (the Doctor, with green eyes), but that does not tell them about their own eye color; to their knowledge the totals could be 101 blue and 99 brown. Or 100 blue, 99 brown, and he could have purple eyes."

Well, according to your original post, all blue-eyed people have the ability to see so your question is moot. The solution would be the same even if brown-eyed people were blind.

[eirikainersharp]

The reason you need the doctor's initial observation:

Basically if the doctor is not present the problem can't be solved - think algebra: you need a system of two eigen functions (ie. non equivalent functions or "different bits of infomation") to be able to two unknown variables - you can't solve for x and y if you only know x+y=5 you also need x-y=1. Similarly in this case you cannot solve for 100 unknowns if you only have 99 different bits of information you need 100 - your 99 observations and the doctors 1.

Tacomagirl - what class is this for?

[BeanDip4All]

Tacomagirl - what class is this for?

doesn't have too much to do with the class, it was more him just wanting to torment us

[komo]

But the class is "Applied Econometrics and Business Forecasting."

thus the pricey sushi joint, i'm guessing his consulting income doesn't suck.

what kind of program is this for?

[MakersTeleMark]

Who does he



bang?

[TeleMang]

Perhaps this will help?

[Art Shirk]

If you have one bucket with 5 gallons of water in it, and one bucket with two gallons of water in it, how many buckets do you have?


In all seriousness, I love logical proofs but dislike logic games. Wish I could remember all my symbolic logic from college. Big ups to Irving Copi, the Don of Logic (besides that Aristotle guy). My professor from Santa Clara instilled much love for this stuff. One of the most brilliant logicians around, and climbed Le Dame Blanche every year.

[sfotex]

The answer formated a little differently (this is a classic networking bit-parity problem presented backwards)
Base case:
If there were 1 blue, 1 brown,1 green, Green says I see a blue
Blue wouldn't see another blue and leave 1st night
Brown will wait to see if blue leaves first night, if blue doesn't leave then they're both blue.


If there were 2 blue, 2 brown, Green says I see a blue

Bl1 sees 1xbl, 2xbr - if he was the only blue he wouldn't see another blue, if he was brown there would be only one blue and the other blue would leave the 1st night (see above), so he leaves night 2

Bl2 sees 1xbl, 2xbr - if he was the only blue he wouldn't see another blue, if he was brown there would be only one blue and the other blue would leave the 1st night (see above), so he leaves night 2

Br1 sees 2xbl, 1xbr - if he was blue the others won't leave on night 2, so he'll wait until night 3 (damn, they left, I'll never know what I am)

Br2 sees 2xbl, 2br - if he was blue the others won't leave on night 2, so he'll wait until night 3 (damn, they left, I'll never know what I am)
Gr


If there were 3 blue, 3 brown, Green says I see a blue

Bl1 sees 2xbl, 3xbr - if he was the only blue he wouldn't see another blue, if he was brown there would be only 2 other blues and the other 2 blues would leave the 2nd night (see above), so he/she leaves night 3

Bl2 sees 2xbl, 3xbr - if he was the only blue he wouldn't see another blue, if he was brown there would be only 2 other blues and the other 2 blues would leave the 2nd night (see above), so he/she leaves night 3

Bl3 sees 2xbl, 3xbr - if he was the only blue he wouldn't see another blue, if he was brown there would be only two other blues and the other two blues would leave the 2nd night(see above), so he/she leaves night 3

Br1 sees 3xbl, 2xbr - if he was blue the others won't leave on night 3, so he'll wait until night 4 (damn, they left, I'll never know what I am)

Br2 sees 3xbl, 2xbr - if he was blue the others won't leave on night 3, so he'll wait until night 4 (damn, they left, I'll never know what I am)
Gr

Br3 sees 3xbl, 2xbr - if he was blue the others won't leave on night 3, so he'll wait until night 4 (damn, they left, I'll never know what I am)

and so forth

[jrbd]

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.

[Beaver]

I thought with tomorrow being Friday and all, people might want to take a stab at discrete math instead of looking at NSFW pix.

A logician you will not make.