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

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Prelates, Moderators General

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

Postby douglasm » Mon Mar 29, 2010 3:00 am UTC

skeptical scientist wrote:Imagine you were a cave man living in 40,000 BCE, and you saw lightning for the first time. What would you think was going on? Now you're actually not a cave man, and you presumably know what lightning is, but when you imagine yourself as a caveman, you deny yourself access to that information, and simulate reasoning without it. That's exactly what's going on here, and why the information the top person has is irrelevant when determining how the hypothetical person will reason. All that's relevant is the information the hypothetical person has.

Exactly. A's actual knowledge is not fully available in the imagined brain of the person he's hypothesizing about. A imagines what B's analysis might look like, and in doing so restricts the knowledge to what both A and B know. A's imagined B then hypothesizes about person C, which reduces it to knowledge that A, B, and C all share. And so on with persons D, E, F, G, H, etc. The eye color of each and every one of these people is unknown to at least one of the people involved, so the eye color of any person in the list at any given level of the nested hypotheticals is treated as unknown, and the minimum number of blue-eyed people is treated as the count of blue-eyed people who are not in that list.

Anyway, the nested hypotheticals thing is a rather difficult to understand explanation and is not necessary to solve the problem. Basic induction can do it quite easily.

Base step: Clearly, if there is exactly 1 blue-eyed person on the island, he will leave on day 1.

Inductive step: Assume that if there are n blue-eyed people on the island they will leave on day kn, and this can be logically deduced (the manner of deduction is irrelevant, only that it can be done). Suppose that there are, in fact, n+1 blue-eyed people on the island. Each of them will deduce that if his own eyes are not blue then all blue-eyed people will leave on day kn. When day kn passes without anyone leaving, he will realize that his own eyes must be blue and leave the next day, day kn+1. This works no matter what value n has, and gives that kn+1 = kn + 1.

For any number n, if there are n blue-eyed people on the island they will all determine their eye color and leave on day n.
douglasm
 
Posts: 521
Joined: Mon Apr 21, 2008 4:53 am UTC

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

Postby skeptical scientist » Mon Mar 29, 2010 12:53 pm UTC

phenom, have you reconsidered your position at all?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

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

Postby phenom » Mon Mar 29, 2010 1:05 pm UTC

prediction of the next message: "oops, I misspoke when I said 6 wouldn't work, it will still logically work, 7 is the lowest number that it will fail."


Haha no.

However, i AM willing to accept that I was wrong all along.

This is a great puzzle (or w/e) because there is such a "logical" disconnect between what everyone knows everyone knows, and what no one knows everyone knows everyone knows.

Anyways, yes I concede, the solution is legitimate for all cases.
phenom
 
Posts: 12
Joined: Sat Mar 27, 2010 3:03 pm UTC

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

Postby Qaanol » Tue Mar 30, 2010 12:14 am UTC

I respect you for being willing to make that statement. It is never easy, and many people could learn from your ability to accept logic.
Small Government Liberal
User avatar
Qaanol
 
Posts: 2557
Joined: Sat May 09, 2009 11:55 pm UTC

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

Postby douglasm » Tue Mar 30, 2010 3:20 am UTC

Out of curiosity, which argument convinced you?
douglasm
 
Posts: 521
Joined: Mon Apr 21, 2008 4:53 am UTC

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

Postby KornDog » Fri May 14, 2010 12:43 pm UTC

Greetings!

Everyone gouges out one eye and looks at their own one eye. Everyone leaves on the first day. Done. LOL
KornDog
 
Posts: 2
Joined: Fri May 14, 2010 12:39 pm UTC

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

Postby Kingreaper » Fri May 14, 2010 5:04 pm UTC

That assumes that not only do they want to leave, they're willing to cause a possibly mortal wound in order to do so.
User avatar
Kingreaper
 
Posts: 160
Joined: Sun Jan 27, 2008 4:23 pm UTC

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

Postby KornDog » Sat May 15, 2010 6:35 am UTC

Firstly, the eye gouging thing was meant to be humorous as it's ridiculous yet totally within the realm of possibility. Secondly, we're talking about 200 people that are perfect logicians, on an island, with no reflective surfaces. Meaning the water that the boat travels on never gives a reflection, or there is no water in the vicinity. But if we're for assumptions, the inductive proof assumes that each person on the island is: not deaf (and can hear the guru), is not color-blind, is able to remember what the guru said on day x (i.e. they have sufficient memory), or that they even paid attention, or that they even understand what the guru said. It's all pretty ridiculous.
KornDog
 
Posts: 2
Joined: Fri May 14, 2010 12:39 pm UTC

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

Postby Lem0n » Sat May 15, 2010 12:33 pm UTC

and keep track of days (or count how many times the boat has come)
Lem0n
 
Posts: 87
Joined: Tue Dec 15, 2009 8:15 pm UTC

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

Postby dedalus » Sun May 16, 2010 2:30 pm UTC

If you're sitting on a desert island, and you were a perfect logician, you'd probably be able to do all those... Besides, it's pretty easy; they simply have to keep a running count of 'no. of days till I know whether I can leave or have to wait for the daft girl to open her yapper again'.

Personally, I'm more interested by the question of which bored rich kid left a hundred mute logicians on an island with those stipulations...
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.
User avatar
dedalus
 
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

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

Postby Blayze III » Sun May 16, 2010 6:09 pm UTC

When I first read it I thought, "The Guru would be the only one who leaves, and on the same night she spoke, by virtue of knowing only she can speak and having spoken and the Guru having to have Green Eyes." But, that turns out not to be true, as the Guru could have any eye color- I was misread a bit of it. However, the 100 nights after part the blue-eyed people leaving definitely works- interesting puzzle.
Blayze III
 
Posts: 3
Joined: Sun May 16, 2010 5:54 am UTC

What information does the guru give?

Postby WhiteDragon » Sat Aug 21, 2010 4:52 am UTC

I think that the piece of information that the guru gives is not in her speech. After all, since there are >2 blue-eyed people, everyone on the island can see at least one blue-eyed person. It is in the fact that she has non-blue and non-brown eyes, showing the existence of at least 3 possible eye colors.
WhiteDragon
 
Posts: 27
Joined: Tue Feb 12, 2008 1:46 pm UTC

Re: What information does the guru give?

Postby Lem0n » Sat Aug 21, 2010 5:31 am UTC

WhiteDragon wrote:I think that the piece of information that the guru gives is not in her speech. After all, since there are >2 blue-eyed people, everyone on the island can see at least one blue-eyed person. It is in the fact that she has non-blue and non-brown eyes, showing the existence of at least 3 possible eye colors.


you're wrong
but this has been explained many times in the thread, so I won't go into details
Lem0n
 
Posts: 87
Joined: Tue Dec 15, 2009 8:15 pm UTC

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

Postby WhiteDragon » Sat Aug 21, 2010 6:11 am UTC

jestingrabbit wrote:I know, I was short and snarky. But its explained in the thread lots. Like, probably five or more times on every page...

But anyway, look at it like this. Say there are only four blue eyed people, called A, B, C, and D. A knows that B, C and D have blue eyes. A knows that B knows that C and D have blue eyes. A knows that B knows that C knows that D has blue eyes. A knows that B knows that C knows that D might not know that there is someone with blue eyes.

That last statement changes when the guru speaks.

How is there any possibility of D not knowing that there is someone with blue eyes, since D also can see at least B and C?
WhiteDragon
 
Posts: 27
Joined: Tue Feb 12, 2008 1:46 pm UTC

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

Postby Lem0n » Sat Aug 21, 2010 6:24 am UTC

WhiteDragon wrote:How is there any possibility of D not knowing that there is someone with blue eyes, since D also can see at least B and C?


there isn't
and A knows that
but A doesn't know that B knows that C knows...
Last edited by Lem0n on Sat Aug 21, 2010 7:25 am UTC, edited 1 time in total.
Lem0n
 
Posts: 87
Joined: Tue Dec 15, 2009 8:15 pm UTC

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

Postby jestingrabbit » Sat Aug 21, 2010 7:07 am UTC

Yeah, its the difference between someone knowing something, someone knowing that someone else knows something and so on. In our regular life its rare that this sort of thinking is necessary, which is what makes the puzzle interesting.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
User avatar
jestingrabbit
 
Posts: 5597
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

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

Postby dedalus » Sun Aug 22, 2010 11:57 am UTC

WhiteDragon wrote:
jestingrabbit wrote:I know, I was short and snarky. But its explained in the thread lots. Like, probably five or more times on every page...

But anyway, look at it like this. Say there are only four blue eyed people, called A, B, C, and D. A knows that B, C and D have blue eyes. A knows that B knows that C and D have blue eyes. A knows that B knows that C knows that D has blue eyes. A knows that B knows that C knows that D might not know that there is someone with blue eyes.

That last statement changes when the guru speaks.

How is there any possibility of D not knowing that there is someone with blue eyes, since D also can see at least B and C?


A sees 3 people with blue eyes. Thus, A knows that B sees *at least* two people with blue eyes. However, A cannot guarantee that B sees any more then 2 people with blue eyes. Thus, as far as A knows, B knows that C sees *at least* one person with blue eyes. But from A's perspective, B might not be able to guarantee that C can see any more then one person with blue eyes - ergo, A can only know that B knows that C sees *at least* one person with blue eyes - D. Thus, as far as A knows, B knows that C knows that D sees *at least* zero people with blue eyes. A can guarantee that D sees someone with blue eyes, because B has blue eyes. But A cannot guarantee that B knows that C knows that D will definitely see anyone with blue eyes.
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.
User avatar
dedalus
 
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

Re: Re:

Postby UrielZyx » Sun Aug 29, 2010 10:12 pm UTC

xkcd wrote:
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 :)


Good job on the recursion, but I do not think it is needed, in my opinion if they all know that they are all perfect logicians, and they all know that they all know they are all perfect logicians, it is enough, and the knowing descends through the hypothetical recursion.

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!
======


That is not true, and here's why:

Spoiler:
If you consider the example with only one blue eyed person except for the guru, the one man knows that the guru doesn't see her own eyes, and so he will go of the island anyway, the same can be shown for any N amount of blue eyed since they all know not to include the guru in there calculations, because they all know that she can not see her own eyes.
UrielZyx
 
Posts: 20
Joined: Thu Jul 29, 2010 7:21 pm UTC

Re: Re:

Postby Lem0n » Sun Aug 29, 2010 10:24 pm UTC

UrielZyx wrote:Good job on the recursion, but I do not think it is needed, in my opinion if they all know that they are all perfect logicians, and they all know that they all know they are all perfect logicians, it is enough, and the knowing descends through the hypothetical recursion.


I raised this point a few months back, but it seems it was already fixed: viewtopic.php?f=3&t=3&start=720#p1929702
Lem0n
 
Posts: 87
Joined: Tue Dec 15, 2009 8:15 pm UTC

Re: Re:

Postby phlip » Mon Aug 30, 2010 1:34 am UTC

UrielZyx wrote:Good job on the recursion, but I do not think it is needed, in my opinion if they all know that they are all perfect logicians, and they all know that they all know they are all perfect logicians, it is enough, and the knowing descends through the hypothetical recursion.

I don't think that's true. Say I throw you into a room filled with people you've never met before, and don't know anything about. And as far as you know, noone knows anything about anyone else, other than what's immediately visible.

If I tell them there's a blue-eyed person in the room, and there's only one, they'll be able to figure it out immediately... but if there are 2 or more, they won't be able to figure it out, because they won't be sure the other would be clever enough to figure it out (since the reasoning requires one of the 2 being able to deduce that the other would have already left if they were the only one, which means that each of the two needs to know the other is a perfect logician... or at least smart enough to figure out the 1-person case).

Say I pull you aside and tell you privately that everyone in the room is a perfect logician, and they've never met before today. Then suppose I do the same with each person (without anyone noticing that I'm telling it to everyone), so everyone knows that they're all perfect logicians, but to no more levels than that. Now if I tell everyone here's a blue-eyed person in the room, and there are two, they'll be able to leave, since I've told them that the other person is able to solve the one-person case. But they won't be able to do 3, since I haven't told them the other person can solve the 2-person case.
Note that in the asymmetrical case where I tell you that everyone's a perfect logician, but everyone else is left in the dark, and you're one of the 2 blue-eyed people, you'll leave, but the other one won't.

Now say I pull you aside and tell you privately that the previous message I gave you, that everyone in the room is a perfect logician, I actually gave to everyone. But, again, I don't tell you that this latest message I've also given to everyone. Now, similarly, you'll be able to solve the 3-person case... because I've told you that everyone can solve the 2-person case, so if you only see 2 and they don't leave, you know it must be the 3-person case and you're one of them. But I haven't told you that everyone else will be able to solve the 3-person case on their own, so you won't be able to solve the 4-person case. Even if I tell that last bit to everyone.

So in that last case, everyone knows that everyone knows that everyone's a perfect logician, but it's still not enough. You need "everyone knows" to at least 99 levels... and making it unboundedly-many levels is the easiest way to do that.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7186
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Re:

Postby UrielZyx » Mon Aug 30, 2010 12:01 pm UTC

phlip wrote:
UrielZyx wrote:Good job on the recursion, but I do not think it is needed, in my opinion if they all know that they are all perfect logicians, and they all know that they all know they are all perfect logicians, it is enough, and the knowing descends through the hypothetical recursion.

I don't think that's true. Say I throw you into a room filled with people you've never met before, and don't know anything about. And as far as you know, noone knows anything about anyone else, other than what's immediately visible.

If I tell them there's a blue-eyed person in the room, and there's only one, they'll be able to figure it out immediately... but if there are 2 or more, they won't be able to figure it out, because they won't be sure the other would be clever enough to figure it out (since the reasoning requires one of the 2 being able to deduce that the other would have already left if they were the only one, which means that each of the two needs to know the other is a perfect logician... or at least smart enough to figure out the 1-person case).

Say I pull you aside and tell you privately that everyone in the room is a perfect logician, and they've never met before today. Then suppose I do the same with each person (without anyone noticing that I'm telling it to everyone), so everyone knows that they're all perfect logicians, but to no more levels than that. Now if I tell everyone here's a blue-eyed person in the room, and there are two, they'll be able to leave, since I've told them that the other person is able to solve the one-person case. But they won't be able to do 3, since I haven't told them the other person can solve the 2-person case.
Note that in the asymmetrical case where I tell you that everyone's a perfect logician, but everyone else is left in the dark, and you're one of the 2 blue-eyed people, you'll leave, but the other one won't.

Now say I pull you aside and tell you privately that the previous message I gave you, that everyone in the room is a perfect logician, I actually gave to everyone. But, again, I don't tell you that this latest message I've also given to everyone. Now, similarly, you'll be able to solve the 3-person case... because I've told you that everyone can solve the 2-person case, so if you only see 2 and they don't leave, you know it must be the 3-person case and you're one of them. But I haven't told you that everyone else will be able to solve the 3-person case on their own, so you won't be able to solve the 4-person case. Even if I tell that last bit to everyone.

So in that last case, everyone knows that everyone knows that everyone's a perfect logician, but it's still not enough. You need "everyone knows" to at least 99 levels... and making it unboundedly-many levels is the easiest way to do that.



Thank you, I didn't think of that, for some reason something in my logic got confused.
UrielZyx
 
Posts: 20
Joined: Thu Jul 29, 2010 7:21 pm UTC

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

Postby londonderry » Sun Sep 26, 2010 1:06 pm UTC

Although it would make the puzzle a lot easier by giving a huge hint at the solution I wonder if it should be more explicit in making it clear that everyone hears the guru, and everyone knows that everyone heard and so on...at the very least it should perhaps say the guru said "loudly and clearly". Common knowledge of an absence of deafness and blindness is also necessary.
londonderry
 
Posts: 1
Joined: Sun Sep 26, 2010 12:08 pm UTC

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

Postby Gwydion » Mon Sep 27, 2010 6:52 am UTC

Actually, blindness/deafness can exist in this system, so long as no blind or deaf individuals have blue eyes. Each individual's status, however, needs to be common knowledge, for pretty obvious reasons.
User avatar
Gwydion
 
Posts: 252
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

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

Postby Ontnut » Thu Oct 14, 2010 6:50 pm UTC

I have a problem with this solution, and 20 pages is a lot to go through to see if someone did mention it: I'll lay it out here so someone can tell me I'm wrong :)

Person 1: brown eyes
Person 2 and 3: blue eyes

Night 1: They all know someone must have blue eyes, and can each see someone with blue eyes amongst the other two people (person 1 sees two blue eyes while the others see one of each), meaning they are all unsure what colour they personally are. So nobody leaves. Person 1 can know that they do NOT have blue eyes, since we know there must be a mixture of eye colours. Person 1 however, does not know what colour his eyes may be (ie he cannot say that since there are 2 blues, I must be brown), since there is no limit placed on how many eye colours there can be in this problem.

Night 2: They see nobody has left, but the only information that provides is that nobody knows they themselves are the one with blue eyes, though they can see others with blue eyes. Nobody leaves again. Person 1 thinks: I can see two blue eyes, so I know I'm not blue, but strangely, neither has left despite me knowing they have blue eyes. Person 2 and 3 each think, I can see one of each colour, so there's no way for me to determine what colour my own eyes are simply by the fact that the Guru sees blue eyes. Nobody leaves again.

Night 3: The solution says that the persons should think, since nobody left either night, I should know my eye colour through process of elimination and will be able to leave. The fundamental issue here is that the solution is based off of two options for the persons...either I have blue eyes, or I don't. This is true, but the implication is that since I don't have blue eyes, I must have brown eyes, which is false, since nobody knows how many colour combinations there are. The problem is, person 2 and 3 can see two different eye colours, one being blue, and that the person with blue eyes hasn't left. Neither 2 or 3 can logically determine their own eye colour from that information, since they could be blue, brown, red or green. Person 1 sees two blue eyes, and I think the solution wants us to conclude that since he sees two blue eyes that haven't left, Person 1 can determine he himself has brown eyes. The problem is that he could have red, green or black eyes and he wouldn't know it, thus he wouldn't be able to leave. He can't know beyond a shadow of a doubt what his exact colour is. Persons 2 and 3 are also stuck because they KNOW someone in front of them has blue eyes and could be the person the Guru is talking about, yet, since they can also see that person 1 has brown eyes, they cannot be certain if there are 2 blue eyes and 1 brown eye, or 2 brown eyes and 1 blue eye. The only saving grace I see is that since person 1 sees two blue eyes, neither of whom are leaving, he could assume he has brown eyes, but the rules say that he could have green or red.

This will continue for all remaining nights since person 2 or 3, seeing one brown and one blue eye, cannot determine by process of elmination what their own colour is, so 2 and 3 can never leave. Person 1 will always see two blue eyes, which fulfills the Guru's rules, but though he knows he does not have blue eyes, he doesn't know WHAT colour his are, since the rules state that there could be 100 brown, 99 blue and 1 red.
Ontnut
 
Posts: 1
Joined: Thu Oct 14, 2010 6:38 pm UTC

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

Postby Goldstein » Fri Oct 15, 2010 10:10 am UTC

Ontnut wrote:Person 1 can know that they do NOT have blue eyes, since we know there must be a mixture of eye colours.


While I don't think this affects your reasoning, I don't recall it being in the problem statement. Person 1 has no reason to know there must be a mixture of eye colours.

Ontnut wrote:Night 2: They see nobody has left, but the only information that provides is that nobody knows they themselves are the one with blue eyes, though they can see others with blue eyes. Nobody leaves again.


You say that the solution given in this thread suggests they'll leave on night three, but it actually says that the blue-eyed people should leave on night two. The information provided from no-one leaving on night one is that no-one believes they are the only person with blue eyes. This is equivalent to everybody being able to see someone else with blue eyes. In your example, this means person 2 knows that person 3 can see another blue-eyed person, and person 2 knows this can't be person 1 (because person 2 can see that person 1's eyes aren't blue), so person 2 can infer that he or she has blue eyes. The same reasoning with different numbers also allows person 3 to reach this conclusion about themselves, and so persons 2 and 3 can know that they have blue eyes before night 2 arrives.

Ontnut wrote:Person 1 sees two blue eyes, and I think the solution wants us to conclude that since he sees two blue eyes that haven't left, Person 1 can determine he himself has brown eyes.


No. The solution given at the start of this thread states that no people with non-blue eyes will ever leave.
Chuff wrote:I write most of my letters from the bottom
User avatar
Goldstein
 
Posts: 985
Joined: Wed Nov 05, 2008 9:38 pm UTC
Location: Newcastle, UK

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

Postby douglasm » Sun Oct 24, 2010 5:59 am UTC

Ontnut wrote:Night 2: They see nobody has left, but the only information that provides is that nobody knows they themselves are the one with blue eyes, though they can see others with blue eyes. Nobody leaves again. Person 1 thinks: I can see two blue eyes, so I know I'm not blue, but strangely, neither has left despite me knowing they have blue eyes. Person 2 and 3 each think, I can see one of each colour, so there's no way for me to determine what colour my own eyes are simply by the fact that the Guru sees blue eyes. Nobody leaves again.

This is where you go wrong. Person 1 thinks: not enough information, I have to wait.

Persons 2 and 3 each think:
I see precisely one person with blue eyes. If there were, in fact, only one person with blue eyes that person would have left last night. That person did not leave last night, therefore there must be more than one person with blue eyes. The only way for this to be possible is if I have blue eyes. Thus, I must have blue eyes.
douglasm
 
Posts: 521
Joined: Mon Apr 21, 2008 4:53 am UTC

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

Postby imatrendytotebag » Tue Oct 26, 2010 6:10 am UTC

It's actually an interesting philosophical point that if, say, a professor were to make an announcement in a classroom (or a guru on an island) that each person would immediately assume the unbounded recursion, ie that everyone knows that everyone knows that everyone knows... etc.
Hey baby, I'm proving love at nth sight by induction and you're my base case.
User avatar
imatrendytotebag
 
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

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

Postby krucifi » Tue Oct 26, 2010 6:31 am UTC

i cant seem to find it amongst all the comments but may i ask how many people would leave and on what day if the seer or mystic woman person said she sees brown eyes AND blue eyes?
i can see it working but i also cant.
i mean if only one person had blue eyes then one would leave in day on the rest on day two
if two people had blue eyes then they would both leave on day two the rest on day three.
i cant seem to work out whether the full 200 would leave on day 100 or not
Yes, my name is the negative frequency of radioactive decay, of the initial speed of light's radius.
And on the eighth day God created Irony.
But on the ninth day Satan was all like, "Nuh uh!"
And ironically made Alanis Morrisette his minion.
User avatar
krucifi
 
Posts: 69
Joined: Mon Mar 22, 2010 3:12 am UTC

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

Postby phlip » Tue Oct 26, 2010 7:20 am UTC

krucifi wrote:i mean if only one person had blue eyes then one would leave in day on the rest on day two

Only if the guru's statement was that she sees only blue and brown eyes. Otherwise, on day 2, while people may be able to tell their eyes aren't blue, they still won't be able to rule out their eyes being, say, green.

Also: you would need some extra information being common knowledge... specifically, that noone has any other forms of information. For instance, the original puzzle still works if everyone knows everything the puzzle says they know, and then one person knows something extra. I mean, it would change the result, but everyone would still only deduce things that are true... noone will deduce anything false. Even moreso, the solution still works if noone has any extra information, but people suspect that others might possibly have extra information. Not that they know others have extra information... because they don't, and if someone "knows" something that's false, then all bets are off, but just that they can't rule it out. Even with that, n blue-eyed people will still leave on night n.

This is because information is additive... if me telling you thing A would let you deduce thing X, then me telling you both things A and B, then you'd be able to deduce things X and Y. If I tell you thing A, there's nothing extra I can tell you that will stop you from deducing thing X. For instance, if you see no blue-eyed people, and the guru tells you she sees a blue-eyed person, then you'll know your eyes are blue, regardless of what extra information you have.

So, conversely (or rather contrapositively) if the guru tells you she sees a blue-eyed person, and you can't deduce your eyes are blue, then I can tell you can see a blue-eyed person, because otherwise you would be able to immediately deduce that. So I can tell you can see a blue-eyed person, regardless of any extra information you may or may not have.

So we're able to get information about what other people know, from the fact that they can't deduce things. On the other hand, we can't necessarily get information about what other people know, from the fact that they can deduce things.

For instance, say you have blue eyes (but don't know that), and you can see another blue-eyed person. The guru makes the announcement. Then, later that same afternoon, she secretly pulls your blue-eyed companion aside and tells them directly that they have blue eyes. Then your blue-eyed companion would leave night 1, and you would not be able to deduce your eye-colour. You certainly can't deduce your eyes aren't blue, because they are, and valid logic will never give you a false conclusion from true premises. So then, new scenario, say you can see another blue-eyed person, the announcement happens, and the blue-eyed person leaves that night. It's possible that the aforementioned pulling-them-aside happened... you can't say for sure... all you know is what you've seen. So you can't rule it out. And because you can't rule it out, you can't rule out the possibility that your eyes are blue.

In this case, there'd be no option but to wait it out... if there was 1 person with blue eyes and 199 people with brown eyes, and the guru said "I see someone with blue eyes and someone with brown eyes, and these are the only two eye colours I can see", then the blue-eyed person would leave on night 1, and the brown-eyed people on night 199.

However, if there was another rule in the puzzle that said "Noone has any other information other than the eye colours they can see, and the guru's announcement", in the "stuff that everyone knows that everyone knows that everyone knows, ad infinitum" section, then your answer would be right, and the blue-eyed person would leave on night 1, and the brown-eyed people would leave on night 2.

Note also that while we, as outside omniscient observers who've read the puzzle statement know that there's no other sources of information, the actual people on the island don't know that unless the puzzle specifically says they do.

To answer your other question, though, even with all of this extra stuff so that the "blues leave on night 1, browns on night 2" answer works for the 1-to-199 case, if there are 100 of each, everyone will still leave on night 100... the same as if the guru just said "I see at least one blue-eyed and at least one brown-eyed person" and people couldn't assume no-extra-info.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7186
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

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

Postby krucifi » Wed Oct 27, 2010 4:33 am UTC

yea my post did have the word ONLY in it and i thought it was unnecessary so i edited it immediately lol.
Although i cant help myself wondering all the different scenarios and results if say for example the oracle says there is at least 10 people with blue eyes. what day would people leave then? would it be day 90?
i like knowing how logic would work in circumstances that would seem to defy itself. what if the oracle said i can see at least 99 blue eyes and 99 brown eyes. not using the word only.
Yes, my name is the negative frequency of radioactive decay, of the initial speed of light's radius.
And on the eighth day God created Irony.
But on the ninth day Satan was all like, "Nuh uh!"
And ironically made Alanis Morrisette his minion.
User avatar
krucifi
 
Posts: 69
Joined: Mon Mar 22, 2010 3:12 am UTC

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

Postby douglasm » Wed Oct 27, 2010 5:09 am UTC

krucifi wrote:yea my post did have the word ONLY in it and i thought it was unnecessary so i edited it immediately lol.
Although i cant help myself wondering all the different scenarios and results if say for example the oracle says there is at least 10 people with blue eyes. what day would people leave then? would it be day 90?
i like knowing how logic would work in circumstances that would seem to defy itself. what if the oracle said i can see at least 99 blue eyes and 99 brown eyes. not using the word only.

The greater numbers effectively just allow the logicians to start at a later point in the exact same logic chain. With the oracle's statement being "I see at least 10 people with blue eyes," all the blue-eyed people would leave on day 91 and the brown-eyed crowd would stay indefinitely. With the oracle's statement being "I see at least 99 people with blue eyes and at least 99 with brown eyes," all 200 people would leave on day 2.
douglasm
 
Posts: 521
Joined: Mon Apr 21, 2008 4:53 am UTC

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

Postby Keand64 » Sat Oct 30, 2010 4:35 am UTC

Okay, so, feel free to correct me if the analogy is wrong or whatever, but this is my simplification of the problem and solution, and the one that makes my brain hurt the least.

Any individual's goal is to determine his eye color, because if he knows that, he can leave.

Because Any individual cannot see his own eye, the only way he can determine his eye color is from other individuals' knowledge.

So we can assume a "pool" of knowledge that everyone knows, and that pool can be used to determine an individuals eye color.

Now if the individuals could communicate amongst themselves, they could simply add information to the pool until they reach the conclusion that 100 people have blue eyes, but the cannot, so:

Because they cannot communicate, they have to use an alternative method to fill this pool with information:

Nobody knows that there are 100 blue-eyed people. 1 person knows that there are 99 blue-eyed people.

However, 2 people do not know that there are 99 blue-eyed people: each of them knows individually, but as a single unit the two do not know their own eye color, and can only conclude that there are at least 98 people.

Continuing the the previous sentence ad centum, any individual can conclude that everybody as a single unit, knows nobody's eye color. Or rather: because nobody knows there own eye color, it is entirely possible for every single person to believe their own eye color to be brown, or red, or a psychedelic sine-wave pattern, even though any other person in the group would know otherwise.

The guru's statement adds to that pool of knowledge that there is at least 1 blue-eyed person in the group: the importance of this statement is not that it adds to any individuals knowledge, but that it adds to the total pool of knowledge, and as I said in the third point, it is this pool that is can be used to determine an individual's eye color.

The next part is just recursion through the possibilities: if there is only one blue-eyed person, he would not see any other blue-eyed people, and leave. Because he doesn't leave on the first night, there are at least two blue-eyed people, who would leave on the second night unless there were three, and so on and so forth.

However, if each person sees 99 other people with blue-eyes, why would it be necessary to wait the 99 days to confirm this? The answer, I think, is this:

The goal of each individual is to determine their own eye color, because that is how they can leave the island. However, the only way a blue-eyed person will know his eyes are blue is if the other 99 blue-eyed people wait 99 days, which they would only do if they saw 99 blue-eyed people, and from that he can conclude that his eyes are blue.

Any lesser amount of days, and the others could be waiting because they see 98 blue-eyed people, which is something he already knew anyways.

So please tell me if there are any significant flaws in this analogy, since as much as I like the (relative) simplicity of this interpretation, I really would like it to be a correct visualization.
CorruptUser wrote:That's how the robots will takeover. Sentient spambots.

In the future, man will be required by law to enlarge his penis and use vicodin, and on occasion, donate $5000 to a Nigerian.
User avatar
Keand64
 
Posts: 35
Joined: Wed Dec 16, 2009 1:05 am UTC
Location: Somewhere, presumably

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

Postby phlip » Sat Oct 30, 2010 4:49 am UTC

Yes, that's an entirely reasonable way of looking at it.

The technical name for the "pool" of knowledge you're referring to is common knowledge... stuff that everyone in a group knows, and everyone in the group knows that everyone else in the group knows it, and so on ad infinitum.

So, among any two blue-eyed people... each of them knows there's at least 99 blue-eyed people, but it's only common knowledge among the two that there's at least 98.

And amongst everyone on the island, the fact that there are blue-eyed people at all isn't common knowledge. But after the guru's announcement, it is.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7186
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

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

Postby douglasm » Sat Oct 30, 2010 3:23 pm UTC

Wow. After seeing so many people come here to post how we're all Completely Wrong, it's a pleasant surprise to see a post like that that's completely correct. Your understanding of the solution is entirely correct, with no flaws at all that I can see.

And, of course, the reason the 98 case would have to wait is that they wouldn't be able to tell the difference between 98 and 97 until day 97 has come and gone. Each additional passing day differentiates between one additional borderline case, and only the information in the all-island common knowledge pool can influence which borderline case any given day deals with, so the 100 blue-eyed people are stuck waiting because the earlier days deal with cases 1 and 2, 2 and 3, 3 and 4, 4 and 5, 5 and 6, and so on.
douglasm
 
Posts: 521
Joined: Mon Apr 21, 2008 4:53 am UTC

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

Postby Keand64 » Sat Oct 30, 2010 5:57 pm UTC

Wow thanks. Looking at the Wikipedia article for common knowledge, I'm guessing that there's no actual difference between the "pool" of knowledge and the chain of "everyone knows that everyone knows that..." other than the way they are visualized. Which is really what I was going for, since the visualization of a chain of nested hypotheticals doesn't make a lot of sense. (Of course, the actual logic of them does, but it really isn't intuitive).
CorruptUser wrote:That's how the robots will takeover. Sentient spambots.

In the future, man will be required by law to enlarge his penis and use vicodin, and on occasion, donate $5000 to a Nigerian.
User avatar
Keand64
 
Posts: 35
Joined: Wed Dec 16, 2009 1:05 am UTC
Location: Somewhere, presumably

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

Postby number7 » Tue Nov 16, 2010 12:14 am UTC

My solution is that for any eye colour with 3 or more representatives on the island, people with that eye colour leave on the second day, whether the Guru speaks or not. Where is the flaw in this reasoning?
The Guru will be sitting alone on the third day.

__Argument__
I am a logician on the island.

There are X people with Blue eyes (X>2). I see N Blue eyed people, and know that X=N or possibly X=N+1 (if I have Blue eyes). If I am an outsider (ie, do not have Blue eyes), X=N and anyone with Blue eyes sees N-1 Blue eyed people. If I have Blue eyes, X=N+1 and anyone with Blue eyes can see N Blue eyed people.

I have a friend with Blue eyes who sees J Blue eyed people (ie, a Blue eyed person must see J Blue eyed people). He only has options of X=N-1 (thinking neither he or I have Blue eyes), X=N (one of us has Blue eyes), X=N+1 (both of us have Blue eyes). I know N-1 people who he can see who have Blue eyes (I can see them!), so he cannot think X<N-1.

X= N || N+1
J= N-1 || N

Day 1:
A person with Blue eyes (eg, my friend) could plausibly believe X=N-1, X=N, X=N+1, of which one has to be exactly right. Anyone who sees N-2 Blue eyes then knows X=N-1 and that they have Blue eyes. They would leave tonight. I know no-one will, but my friend might have doubts.

Day 2:
A person with Blue eyes could only agree with my unspoken conclusions, X=N or X=N+1. If my friend sees X=N-1 Blue eyed people, he concludes X=N and leave tonight. I know X=N, problem solved.

Day 3:
Anyone with Blue eyes now knows X=N+1. I, then, know X=N+1 even if I don't have Blue eyes. I see N Blue eyes, so I must have Blue Eyes. I leave tonight. X=N+1, problem solved.
number7
 
Posts: 1
Joined: Tue Nov 16, 2010 12:01 am UTC

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

Postby phlip » Tue Nov 16, 2010 11:52 am UTC

The flaw is here:
number7 wrote:Day 1:
A person with Blue eyes (eg, my friend) could plausibly believe X=N-1, X=N, X=N+1, of which one has to be exactly right. Anyone who sees N-2 Blue eyes then knows X=N-1 and that they have Blue eyes. They would leave tonight. I know no-one will, but my friend might have doubts.

For brevity, let's call your friend "Person F" (the F stands for "Friend") and pick some arbitrary other blue-eyed person as "Person A" (the A stands for "Person we don't really care about too much").

Now, as you've reasoned, you personally know that X is either N or N+1. And you know that F knows that X is either N-1, N or N+1. So far, so good. You also, similarly, know that A knows that X is either N-1, N or N+1. But the important thing is that this is all just stuff that you know.

So, you know that A has narrowed it down to at least N-1/N/N+1. But that's not the important thing for what you're trying to reason. And that's what F knows that A knows. Or, more accurately, what you know that F knows that A knows. Because you're trying to figure out what F is able to figure out, by seeing A not leave on night 1.

So, imagine that your eyes are actually brown, and X=N. Think about what your friend would be thinking... they'd go through similar reasoning to what you did, and think up their own numbers for X', N' and J'. Except their N' would be one lower than your N, because they'd see one fewer blue-eyed person. And so their X' and J' would be one lower than yours as well. So, like how you know the lowest number of blue-eyed people A can see is N-1, your friend knows that the lowest number of blue-eyed people A can see is N'-1... but since N' = N - 1, that means that, if your eyes are brown, then F only knows that A knows that there are at least N - 2 blue-eyed people on the island.

Then because, as far as you know, your eyes could be brown, you can't rule out the possibility that this is exactly what F thinks, so as far as you know, F could only knows that A knows that there are at least N - 2 blue-eyed people on the island. So for this chain of knowledge, you know that F knows that A knows that X is N-2, N-1, N or N+1. And for every person you add to the chain, the lower bound gets one lower, until it reaches 0 (which happens to be when the chain includes every blue-eyed person). And these longer chains are also important as the days go on, because you're reasoning based on what F is able to figure out, so you need to figure out what F knows. But F is reasoning based on what A is able to figure out, so you need to know what F knows that A knows. And A is trying to reason based on what B is trying to figure out, so A needs to figure out what B knows, so F needs to figure out what A knows that B knows, so you need to figure out what F knows that A knows that B knows. And it continues like this.

But if all that is too complicated to take in at once (the whole he-knows-that-she-knows-that-they-know thing takes a fair bit of thinking about to understand) then there's a simpler point that could help convince you that your result is wrong, even though it doesn't explain what's wrong with it or help convince you that the real answer is right:

What your proof is saying... if I have not-blue eyes they'll leave day 2, if I have blue eyes we'll leave day 3. Regardless of how many blue-eyed people there are. According to that, if my eyes are not blue, and I see 10 blue-eyed people, then all the blue-eyed people will figure it out and leave on day 2, that's how I know my eyes aren't blue and don't try to leave on day 3 claiming I have blue eyes. On the other hand, if my eyes are blue, and I see 9 blue-eyed people, then they won't leave on day 2, so I, and all the other blue-eyed people, will figure out we have blue eyes and leave on day 3.
However, these are the same situation... the situation where there are 10 blue-eyed people total on the island. The only difference is that it's described from a different point of view. How can they disagree on the result? Say I have brown eyes, but have a friend who has blue eyes, and we meet up after the experiment is over and compare results. Will I be saying that the blue-eyed people left on day 2, and he say that the blue-eyed people left on day 3?
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7186
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

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

Postby douglasm » Tue Nov 16, 2010 2:53 pm UTC

number7 wrote:My solution is that for any eye colour with 3 or more representatives on the island, people with that eye colour leave on the second day, whether the Guru speaks or not. Where is the flaw in this reasoning?
The Guru will be sitting alone on the third day.

Even without picking apart your argument for exactly where you went wrong, there is a very simple contradiction that means your argument could not possibly be correct. You say, for example, that a group of 10 blue-eyed people would leave on day 2, and they would do this because a group of 9 would have left the previous day. Yet your own theory also states that a group of 9 would leave on day 2. So which is it, does a group of 9 leave on day 2 or the day before?

Any solution that gives an answer independent of the size of the group of blue-eyed people either arrives at its answer without using the information of time passing at all or must necessarily be contradictory and therefore wrong. If figuring out your own eye color can be done without using information gained from time, then all the information required is available on day 1 and would be figured out immediately. There is quite obviously insufficient information for a day 1 solution, so it is not possible for a correct solution to produce a day number that is independent of the number of blue-eyed people.

As for the specific error in your logic, you're not handling the nested hypotheticals correctly. You know that your friend has to see at least N-1 blue-eyed people, but for all you know he could be thinking that a third person might be seeing N-2 blue-eyed people.
douglasm
 
Posts: 521
Joined: Mon Apr 21, 2008 4:53 am UTC

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

Postby andrewww » Fri Nov 19, 2010 4:50 am UTC

douglasm wrote:
skeptical scientist wrote:Imagine you were a cave man living in 40,000 BCE, and you saw lightning for the first time. What would you think was going on? Now you're actually not a cave man, and you presumably know what lightning is, but when you imagine yourself as a caveman, you deny yourself access to that information, and simulate reasoning without it. That's exactly what's going on here, and why the information the top person has is irrelevant when determining how the hypothetical person will reason. All that's relevant is the information the hypothetical person has.


Exactly. A's actual knowledge is not fully available in the imagined brain of the person he's hypothesizing about. A imagines what B's analysis might look like, and in doing so restricts the knowledge to what both A and B know. A's imagined B then hypothesizes about person C, which reduces it to knowledge that A, B, and C all share. And so on with persons D, E, F, G, H, etc. The eye color of each and every one of these people is unknown to at least one of the people involved, so the eye color of any person in the list at any given level of the nested hypotheticals is treated as unknown, and the minimum number of blue-eyed people is treated as the count of blue-eyed people who are not in that list.


I've been discussing the puzzle with my friend lately and it's really been bugging us, haha. The point I brought up was similar to skeptical scientist's - the idea that there is an unsafe assumption made in giving the hypothetical "1-person case" the information that the true (100-person case) logician knows (the information being that "there is at least one blue-eyed person on the island") but the "first" person should not in an isolated setting.

To reword that, how can the first person deduce his own eye color without being given outside information? The entire argument for the blue-eyed persons leaving is based on the first person being able to leave, but he cannot leave without being given outside information (making it an invalid proof).

---

I don't think douglasm has answered this question - it's not a matter of whether or not the logicians of the "true" island know what each other logician knows. It's a matter of what the "first person" knows by the thinker.
andrewww
 
Posts: 3
Joined: Fri Nov 19, 2010 4:40 am UTC

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

Postby douglasm » Fri Nov 19, 2010 1:15 pm UTC

andrewww wrote:To reword that, how can the first person deduce his own eye color without being given outside information? The entire argument for the blue-eyed persons leaving is based on the first person being able to leave, but he cannot leave without being given outside information (making it an invalid proof).

He can't. This is exactly the reason why the Guru's announcement is needed, as it supplies the information that makes the one person case work.
douglasm
 
Posts: 521
Joined: Mon Apr 21, 2008 4:53 am UTC

PreviousNext

Return to Logic Puzzles

Who is online

Users browsing this forum: No registered users and 2 guests