The green-eyed/ blue-eyed puzzle/ conundrum
Today I want to share a puzzle that my friend Aaron Abrams told me a few days ago. I’m sure some of you have heard it before, but it’s confusing me, so I’m asking for your help.
Set-up
Here’s the setup. There’s an island of people, all of whom have either blue eyes or green eyes. By social convention they never discuss eye color, because there’s a tragic rule that states that, if you ever figure out your eye color, you have to leave the island within 24 hours. Oh, and there are no mirrors.
OK, get it? So think of the island as pretty small, maybe 100 people, so you know everyone else’s eye color but not your own.
Here’s what happens next. Some castaway arrives by swimming onto the island, stays for a few days and hangs out with the folks there eating island food and having island parties, and then after building himself a boat he prepares to leave. Not being trained in the social customs of the island, on the day he leaves he says, “hey, it’s good to see some people with green eyes here!”.
Puzzle
So the puzzle is, what happens next?
Here’s what’s obvious. If you are a person who only sees blue eyes, you know by his statement that you must have green eyes. So you have to leave the next day.
But actually he said “some people.” So even if you only see one other person with green eyes, then you have to leave, with that other green-eyed person, after one day.
With me so far?
But hey, what if you see two other people with green eyes? Well, you might think you’re safe, and you’d wait to see them leave together the next day. But what if they don’t leave after one day? That must mean that you also have green eyes. Then all three of you have to leave, after two days. Get it?
Then you work by induction. If you see N other people with green eyes, they should all leave after N-1 days, or else you have green eyes too and all (N+1) of you leave after N days.
Conundrum
OK, so here’s the conundrum. The guy who started this whole mess really didn’t do much. He just stated what was obvious to everyone already on the island, namely that some people had green eyes. I mean, yes, if there were really only 2 people with green eyes, then he clearly added real information, because both those people had thought only 1 person had green eyes.
But just for the fun of it, let’s assume there were 17 people with green eyes. Then they guy really didn’t add information. And yet, 16 days after the guy left, so do all the green-eyed islanders. So really the guy just started a count-down more than anything.
So, is that it? Is that what happened? Or was the original set-up inconsistent? Is it not an equilibrium at all? Or is it an unstable equilibrium?
Saying
In any case, Aaron and his friend Jamie have developed a saying, it’s a green-eyed/ blue-eyed thing, which means it’s an apparently information-free fact which changes everything. I think I’ll use that.
mathbabe 
Beforehand, everyone on the island knows that there is someone with green eyes. And if there are at least two green eyed people, then everyone knows that everyone knows that there is someone with green eyes. And if there are three, everyone knows that everyone knows that everyone knows that there is someone with green eyes. Etc, etc.
After the statement, everyone knows that everyone knows that there is someone with green eyes. And everyone knows that everyone knows that everyone knows that there is someone with green eyes, etcetera, to infinity. This is why it only works if the entire island hears the statement. (I think.) The information added isn’t what the visitor said, it’s the fact that everyone heard him.
(This explanation was taught to me by Joe Halpern.)
LikeLike
I think that’s correct, yes. This puzzle is described on the page http://en.wikipedia.org/wiki/Common_knowledge_(logic) which specifically states “When the outsider’s public announcement (a fact already known to all) becomes common knowledge, the blue-eyed people on this island eventually deduce their status, and leave.”
That’s how I’ve always resolved it, as well. Essentially, it begins with all of the islanders knowing that there are green-eyed people, and all of them knowing that all of the others know that there are green-eyed folk (etc. etc), but they do not all know that they all know that….that there are green-eyed people. The visitor’s statement allows them to get to that point.
LikeLike
Your explanation reminds of the answer to another conundrum I heard once, but it was a condemmed man who would be pardoned if he could state which day he would be executed at least 24 hours before the execution (given he must be executed within a week). I read it about 20 years ago, so I can’t reproduce the answer properly, but he guesses the day using a similar logic chain (it can’t be the final day, because I’ll know for sure a day ahead. Having eliminated that day, it can’t be six days hence for the same reason etc..). In that case the logic failed and he is completely surprised when the execution occurs, I think on the third day.
LikeLike
This has the right answer but I think it’s a little unclear from the post, so I want to reiterate it a bit.
Before the visitor there is only a finite chain of “everybody knows that everybody knows that … some people have green eyes”. For instance if there are three green eyed people – “everybody knows that there are some green eyed people” (I’m assuming “some” means 2 or more), but it’s not true that “everybody knows that everybody knows that there are some green eyed people”, since the green-eyed people see one 2 other green eyed people.
If there are 4 green eyed people – “everybody knows that everybody knows that there are some green eyed people”, but the next layer is not true and so on.
What the visitor does is they make that knowledge chain infinite, so that all layers are now true – and that’s the new piece of information.
LikeLike
Let’s see, now somehow you have to work this into the next Slate Money Podcast and watch Felix’s head explode. 😉
LikeLike
The set up isn’t quite right. What gets the countdown going is the imperative that you must leave after 24 hours. Once that is known, then all the green-eyed people will leave. So the visitor is just a kind of timer saying, “starting now.” Previously the islanders had no moment in which to set a start, and the timing of departure is what informs the green-eyed that they are green-eyed. No?
LikeLike
…so you’d get the same effect without the visitor if you suppose that the island chief one day announced that anyone who figures out that s/he has green eyes must leave in 24 hours. That adds information for sure, since it partitions everyone into stayers and leavers. The start time is what counts.
LikeLike
Even though the link to the wikipedia webpage about ‘Common knowledge’ has already been given, I would like to point out that this puzzle was discussed at (great) length over at Terry Tao’s blog: http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/
LikeLike
The common knowledge element is indeed what changes the situation. This is what starts the clock, as rob notes, meaning that all green-eyed residents leave after N+1 days. Then, of course, the only people left on the island have blue eyes, so they all have to leave on the N+2 day, emptying the island completely!
It’s fun and worthwhile to do a few simple examples with the knowledge operator K as it acts on subsets of possible states of the world, or “events.” There’s a good explanation in Ken Binmore’s game theory text Fun and Games.
LikeLike
I think it’s just the clock, David, not the common knowledge, since as Cathy mentions, everyone already knew there were green eyes among them. What the visitor adds is the clock, and the clock starts the countdown, which leads to the increasing information.
LikeLike
The common knowledge aspect is subtle; just because a group of people all know the same thing doesn’t make it common knowledge.
Say that the set of all possible states of the world is X and the actual state of the world is x, an element of X. An event is a subset E of X. If an individual i knows E, that means that person i knows the true state of the world is one of the elements of E, denoted Ki(E). [Sorry, no subscripts available.] For consistency, we must of course have x in E. So X could be all different distributions of eye colors among inhabitants, and E the subset of X in which 2 or more inhabitants have green eyes.
Take residents i and j. At the beginning of the story both know that there is at least one person with green eyes. But “common knowledge” of event E implies that i knows E, that j knows that i knows E, that i knows that j knows that i knows E, and so on ad infinitum. This must hold for every subset of residents.
So information *is* added to the system by the utterance of the person who was visiting the island: the existence of at least two green-eyed inhabitants, while known individually to each resident beforehand, now becomes common knowledge. And it is this change in the knowledge structure that sets off the chain reaction leading to all the green-eyed people leaving the island after N+1 days.
LikeLike
That’s certainly true of one or two green-eyed islanders as Cathy specified that one or two are the obvious cases. I think she was concerned with more than two — her example was 17. In that case the visitor doesn’t add more common knowledge than was present before. That’s the puzzle, no? So the additional knowledge begins with the second day — it’s still the clock, not the common knowledge.
LikeLike
I once spent several days of vacation talking about this problem with my family, so I actually have an argument for why common knowledge doesn’t exist. This wasn’t obvious to me at first, so it might be helpful to some folks.
In the version we used, the island was full of logicians, which we labeled L1, L2, etc. We also abbreviated the statement “some people on the island have blue eyes” to S, because otherwise the explanation gets super long.
Consider the case where there are just three logicians, all with blue eyes. Before the visitor arrives:
L1 knows S. L1 knows that L2 knows S, because L1 knows that L2 can see L3. With respect to each other, L1 and L2 have common knowledge of S, because both know that the other can see L3.
But, it is not the case that L1 knows that L2 knows that L3 knows S. L1 doesn’t know his eye color – we can represent his knowledge as ?BB, where the first, second, and third entries represent the color of L1, L2, and L3 respectively. L1 knows that L2 doesn’t know his eye color – L1’s knowledge of what L2 knows is ??B. Finally, L1 knows that L2 knows that L3 doesn’t know his own eye color, so L1’s knowledge of L2’s knowledge of L3’s knowledge is ??? – so L1 doesn’t have 3rd order knowledge of S.
Every time you add a logician, you stick him at the end of the chain – so until the visitor arrives, common knowledge is impossible.
LikeLike
I think this is right. In the island example, however, the visitor adds the departure clock by which the knowledge becomes shared — as the green-eyed fail to leave, more self-knowledge is added.
LikeLike
Right – L1’s knowledge of L2’s knowledge of L3’s knowledge (there has to be a better way to say that) goes from:
??? (no idea what any of the eye colors are) to {B??, ?B?, ??B} (L1 knows that L2 knows that L3 knows that at least one person has blue eyes. And this is necessary to start the clock.
If anyone has a good description of why it’s necessary, I would appreciate it. Jumping straight to the proof by induction feels like it’s missing some explanatory steps – the proof is correct, but doesn’t really explain why common knowledge is important.
LikeLike
I don’t think common knowledge plays any dynamic role. It’s self-knowledge that is induced by watching the clock as others refuse to leave the island. Or you could say the knowledge of others’ self-ignorance induces self-knowledge. Maybe that’s what’s meant by the role of common knowledge. But I think it’s misleading, at least in the context of Cathy’s example, which is about what the visitor adds. That’s the clock — the imperative beginning with his statement.
It’s like the internet joke: bartender asks three logicians “do you all want a beer?” The first says “Not sure.” The second, “Not sure.” The third then says “Yes. We all want a beer.” Now, they don’t need a countdown — they could all have looked at one another, observe the uncertainty, and all come up with a yes. But in this case there’s a question being put at a single moment. For the islanders, there is no single moment for them to ask, since they don’t discuss eye color ever, and there’s no moment at which the chief announces the law, and islanders are born at irregular times and without initial knowledge of the rule, so they don’t all learn it at once. So the visitor just adds the clock. That’s the additional “information” that is played out as the islanders fail to leave in 24 hour increments.
LikeLike
Say that there are k people with blue eyes.
If k=1, then it is not even first-order knowldege, for everyone, that at least one person has blue eyes. The blue-eyed person himself has never observed a blue-eyed person. It is first-order knowledge for everyone else, but not for him.
If k=2, then it is, universally, at least first-order knowledge that at least one person has blue eyes. Each of the two blue eyed people has seen the other. However, it is not universally second-order knowledge. Each blue-eyed person sees one other blue-eyed person; however, he does not know if that person has seen a blue-eyed person, because he does not know his own status.
This pattern holds. It is, universally, [k-1]-th order knowledge that at least one person has blue eyes. It is *not* common knowledge that at least one person has blue eyes, not even if the entire population has blue eyes.
Once the outside makes a statement that at least one person has blue eyes, that becomes common knowledge. Each day that nobody departs, it becomes common knowledge that one more person has blue eyes, right up to the point that everyone with blue eyes is able to infer their own status, on the kth day.
You can define this as “starting a clock” if you like, but in doing so you’re just refusing to understand what common knowledge *means*. The clock starts from the moment that it becomes common knowledge, according to the definitions used by those who study formal logic. Because of the departure rule, each day that elapses expands what is commonly known.
LikeLike
My brain might be impaired by lack of caffeine right now, but I don’t understand the induction step. If I see 3 other people with green eyes, everyone else sees at least 2 people with green eyes. Why should anyone know in this case what their eye color is?
LikeLike
Suppose you have green eyes. You see two others with. After 24 hours, they haven’t left because they think that you and the other are the green-eyed. So now you know your eye color (and they now know theirs too now), and you’d leave the next day with them. Or take four with green eyes. After 24 hours, none leave because none knows her/his eye color. But if there were only three green-eyed, they’d all leave after 48 hours. They don’t (because they are looking at you as the third), so now you (and they all) know and leave next day.
LikeLike
Maybe I’m REALLY impaired – cause this just isn’t registering for me.
In this case, each green eyed individual would believe that N = either 2 or 3. (i.e. they see 2 green eyed people with the possiblity that they’re the 3rd).
Each blue eyed individual would believe that N = 3 or 4 (i.e. they see 3 green eyed people with the possibility that they’re the 4th).
How does any individual deduce their own eye color armed with this information?
Nobody would figure out their own eye color on day 1. Thus, the 24 hour timer is meaningless after that.
If I’m green-eyed – after 1 day, nobody has left and I still only know that N = 2 or 3. 24 more hours pass with nobody leaving.
After 2 days, nobody has left and I still only know that N = 2 or 3. 24 more hours pass with nobody leaving.
…and so on.
Why exactly are we stacking 24 hour timers on end?
LikeLike
Say you know Alice and Bob and them alone to have green eyes. You don’t know your own eye colour.
On day 0 everyone is told that someone has green eyes. This does not surprise Alice and Bob, so they stay for another day.
So on the morning of day 1 Alice and Bob are still around, as you expect. Suppose your eyes were blue. Then the only green-eyed person known to Alice would be Bob, and on that morning she’d say to herself “Bob has green eyes. If my eyes were blue, then Bob wouldn’t know any green-eyed people, and would therefore have left last night. But Bob didn’t leave — so my eyes must be green and I must leave tonight”. Bob would of course think the same thought. In conclusion: if your eyes were blue, Alice and Bob would leave after day 1.
In the morning of day 2, you see Alice and Bob are still around. Now you ask yourself: why didn’t they leave? Just like Alice would have reasoned yesterday, you now realize that your green eyes is the reason they are still around. You’d then leave that very evening.
LikeLike
rob, suppose the visitor hadn’t said, “I see there are some people here with green eyes,” but instead had said only, “Remember the rule about leaving after 24 hours if you ever figure out your own eye color. Start figuring … now!”
Do you think the situation would be the same, i.e., that people would soon figure out their own eye color and have to leave?
LikeLike
yme: no. It is crucial that he say there is at least one green-eyed person (and fewer than 100).
Everybody knows (by personal observation) that both colors are present but there isn’t an infinite regression that “everybody knows that everybody knows … that both colors are present.
I’ll simplify it to 5 people on the island and suppose 2 are blue=eyed. They are unimaginatively named A, B, C, D and E. A and B are blue-eyed.
Now, everyone knows by personal observation that both colors are present. That is, they can see both colors themselves. But, they don’t know that everybody else knows that. In particular, A sees only one person with blue eyes. So, he doesn’t know if B sees only green eyes (if A eyes are green.) in which case B doesn’t know both colors are present. A knows both colors are present but he doesn’t know if B knows that.
So, we have a stable situation where A and B are uncertain about their eye color. But, if someone says that there is at least one blue-eyed person, A thinks this may be news to B and, if so, B would leave. But when he doesn’t, it tells A that the information was not news to B and so his eyes must be blue, too.
The case with 17/100 is the same except with an much longer string of “everybody knows …”.
But, I have a question about a similar classic problem, the “Unexpected Hanging”. A judge tells a prison warden to execute a prisoner next week. But, he must do so on a day the prisoner does not expect. If he can’t do that, he must release the prisoner.
The prisoner figures, he can’t execute me on Saturday because I would know it is coming. So, if I am alive on Friday, I would know he would have to kill me that day. But, since I know he can’t kill me on Saturday, I would expect it on Friday so he can’t kill me then, either. This reasoning eliminates all possible days, so he can’t kill me.
But, suppose Sunday passes and the prisoner isn’t killed. He thinks, “see, I’m right”. Monday passes and he is further confirmed. Then, to the prisoner’s surprise, the warden shows up with a noose on Tuesday morning..
LikeLike
N =1 or 2 seems like a special case to me.
But in the case where N >2, everybody knows by personal observation that both colors are present in multiple people.
In this case A sees more than one person with blue eyes and knows with certainty that B-F see more than one person with blue eyes. As is the case with each individual relative to the others.
So, if someone says that there is more than one blue eyed person, it’s news to nobody and, in turn, nobody will think this could possibly be news to anybody else. This reveals nothing to anybody, and so nobody leaves.
What am I missing?
LikeLike
Let’s assume you think your eyes are blue. Let’s say you see two people with green eyes. Then you think, ok those guys are gonna see each other know they are the only two guys with green eyes, and they will leave after 1 day.
Case 1: They leave after 1 day. This is consistent with your assumption that you have blue eyes, so all is good.
Case 2: They do not leave after 1 day. This is inconsistent with your reasoning. Therefore your assumption is wrong, and you have green eyes. Now that you know your eyes are green, you have 1 day to leave. You will leave after two days.
LikeLike
I can’t reply to you Cathy, but I think I see it now
Making it 4 blue & 4 green. I assume my eyes are blue again, I see the three people with green eyes and none of them leave after 1 day.
Case 1: Your scenario above plays out over two days, consistent with my assumption of blue eyes.
Case 2: They do not leave after 2 days. Inconsistent with my assumption of blue eyes – so I have green eyes. I leave after 3 days.
Is that right? Thanks for the hand holding…
LikeLike
“If N>2, everybody knows by personal observation that both colors are present in multiple people.”
Consider the statement P: “there are at least N-1 people with green eyes”. The outside observer knowns that everyone knows P. But now consider two of the green-eyed people, Alice and Bob. Alice and Bob individually know P (as you say, by personal observation). But let Q be the statement “Bob knows P”. Does Alice know Q? She doesn’t.
Alice knows there are at least N-1 people with green eyes (one of which is Bob). But if her eyes are green, then Bob only knows about N-2 people with green eyes. In fact, if Alice knew that Bob knows P, then it follows she has green eyes! (the only way for Bob to know P without knowing his own eye color is for him to see the N-2 green-eyed people other than him and Alice and also Alice herself).
So Alice and Bob know P, but each doesn’t know that the other knows it. It is the latter knowledge that is changed by the visitor.
LikeLike
But that example depends on there being only two people with blue eyes. So each of the blue eyed people looks at the other one and thinks “I’ll bet that person doesn’t know that there are any blue eyed people on the island”.
If the number of blues is > 2, that can’t happen. Everyone knows that everyone else knows that there blue eyed people on the island. And everyone knows that, and so on until you have an infinite regression to common knowledge.
I’m on the “inconsistent setup” side. Everyone on the island should be making these kinds of deductions since the day they were born, and leaving as soon as their age is equal to the number of blues on the island.
LikeLike
The issue is that you’re mistaken that with > 2 blue-eyed people, everyone knows that everyone knows… etc. to infinity. They know it to some level of recursion, depending on the number of blue-eyed people, but not to an arbitrary depth. Check my post above for an explanation.
LikeLike
No, my example works for 3 (or more) poeple it just gets more tedious to enurermate. Now: A, B and C have blue eyes. A looks at B and C and thinks they might only see one other people with blue eyes. So, everyone knows there are at least two people with blue eyes, but it isn’t true that “everyone knows that everyone knows there are at least two peopel with blue eyes. In particular, A, B and C all think that the other ones MIGHT only see one blue-eyed person.
No one thinks that anyone should leave after day one. But, when no one leaves after day one, now “everyone knows everyone knows there are at least 2 people with blue eyes. So, A knows that if his eyes are green, B & C will now know their eyes must be blue. So, on day two, B&C would leave. When B & C don’t leave, now everyone (including A, B & C) know there are at least 3 people with blue eyes. And, since they only see two, they know their own eye color.
LikeLike
Josh, I think you’re right about N=2, but when there are >2 (like 17) yme’s substitution of “remember your rule” would suffice to begin the countdown — since everyone already knows that there is at least one green-eyes. I think that’s why Cathy stated the question — how can the visitor change the island without adding information — in the context of >2. Seems to me where N>2, the only necessary change in information is the lack of leaving after the clock is set by whomever.
LikeLike
No, I don’t agree. Suppose there were even just one green-eyed guy. And someone said “remember the rule”.
Yes, he only sees blue eyes. But he could think his eyes are blue, too. At least possibly. It would still be true that everyone’s eyes are “either green or blue” So, he wouldn’t know his eye color.
The fact that there is at least one green-eyed person and that everyone knows everyone knows it is crucial.
Mentioning green eyes when no one has green eyes might seem odd but not so much since it would be necessary to maintain uncertainty (of course, this whole premise is odd in the usual math puzzle sort of way but, given that this is a math puzzle, it wouldn’t be unreasonable for someone to say “everyone’s eyes are either green or blue” when they could have said “everyone’s eyes are blue”. So, the one green-eyed guy could see only blue but still be uncertain.
LikeLike
Josh — Re the hanging: the prisioner hasn’t figured in the warden’s obtuseness. If the warden is too stupid to figure the game, there’s no way to predict. Crazy or irrational or just stupid behavior is often unpredictable and makes games hard to manage by game theory. A smart warden might even choose by lots. What I’m wondering about is this: if each day is equally impossible, then logically each is equally possible. That would include the last day, which would be a surprise too, wouldn’t it? The prisioner would think he couldn’t logically be hanged on the last day, so he might think he’s not going to be hanged at all. But he might think he’s wrong anyway.
LikeLike
Rob,
Thanks. I think the problem is “expected” isn’t well defined. If we say that he can’t be hanged on a day he could anticipate with certainty, you are right he could be hanged any day, including Saturday.
LikeLike
It’s a version of the barber’s paradox.
For the prisoner, the statement of his situation is, “he can hang me on any day I know he can’t (because it would be unexpected)”. If he can he can’t, if he can’t he can.
LikeLike
Cool, tomcohoe. Looked up the barber. They are very like, but I think not the same: in the case of the barber, I think there’s no such possible barber no matter what he does, but the warden can choose any day and it will be equally surprising. Maybe it’s the difference between “This sentence is both true and false” a mere contradiction (like the barber), and “This sentence is true” indeterminate in its truth (if it’s true, it’s true, if false it’s false, so it’s indeterminate, like the warden — if he hangs him any day, it’s a surprise) and “this is false” which is both true and false, a paradox.
LikeLike
I agree with rob that the case of the prisoner is not as paradoxical as the case of the barber.
I guess it depends on the exact phrasing of the question, but I think that in the usual formulation, in order for the prisoner to be hanged on a given day, it’s not necessary that he know that he wont be hanged on that day; it’s enough that he not know that he will be hanged. As long as he isn’t sure, it’s ok to hang him. And, we (and he) can conclude that he won’t be sure, because the assumption that he will be sure leads to a contradiction.
LikeLike
Let me rephrase that.
We (and he) can reach a contradiction by assuming all of the following: (1) he will be executed some time this week, (2) he knows that he will be executed some time this week, (3) he won’t know which day he’ll be executed, and (4) he knows that he won’t know which day he’ll be executed.
But reaching a contradiction doesn’t allows us to conclude that any specific one of the assumptions is false, for example, that (1) is false, which is what the prisoner in the story wrongly concluded. We can conclude only that at least one of them is false, but we don’t know which one. If it isn’t (1), the prisoner will be executed.
LikeLike
@rob
“They are very like, but I think not the same: in the case of the barber, I think there’s no such possible barber no matter what he does, but the warden can choose any day and it will be equally surprising.”
Actually rob, I think it’s closer than that. Neither the hangman nor the prisoner can conclude that the prisoner can or cannot be hung in accordance with the warden’s instructions. Consider the situation on the last day (for simplicity). The prisoner cannot conclude that he can be hung or cannot be hung (“if I can be hung, I can’t be hung – if I can’t be hung, I can be hung”), as you have agreed. But the hangman goes through the same process, because the logic is independent of who is reasoning. For the hangman: “If I can hang the prisoner today, the prisoner, using the same reasoning, knows it and expects to be hung, so I can’t hang him. If I can’t hang him today, the prisoner knows it and expects not to be hung, so I can hang him”.
The hangman cannot conclude that he can hang he prisoner without violating the warden’s instructions because he can only hang the prisoner if the prisoner expects not to be hung. The hangman can reason as well as the rest of us, so he knows the prisoner cannot draw the conclusion that he can’t be hung.
Ending the narration of the problem with the prisoner being hung is just a bum steer. The statement of the barber’s paradox could just have well been ended by having Joe come in and cut the barber’s hair, but traditionally, the paradox is left hanging. The reason is that It is supposed to be instructive. The hangman version has been complicated by putting in several layers of recursion and the ending in which logic is different for the hangman than for the prisoner, for some strange, inexplicable reason. That the narrative ends with the prisoner getting hung is a clever method of hiding the fact that the hangman is in every bit as much of a quandry as the barber.
The point is that we can be tricked by language into trying to solve a problem that is actually a logical paradox, and the problem can be increased in complexity by putting in layers of recursion and a conclusion that is not supported by logic.
Beware!
It is a lot more trouble to type out due to its increased complexity, but I am pretty sure that the green eyes/blue eyes thing has something wrong with it too (For example, how do the islanders find out the rules? How do the islanders know that everyone agrees to them? You could invoke God, I suppose, but what if some of the islanders read DesCartes and require evidence for the “assumption” they’ve always carried in their heads?).
LikeLike
tomcohoe said: “Ending the narration of the problem with the prisoner being hung is just a bum steer. The statement of the barber’s paradox could just have well been ended by having Joe come in and cut the barber’s hair”.
That doesn’t seem right to me.
If Joe cut the barber’s hair, it would be clear that the barber failed to satisfy the stated condition that he cuts the hair of all and only those who don’t cut their own hair, because there’s someone (namely, himself) whose hair he didn’t cut even though they didn’t cut their own hair.
On the other hand, in the case of the prisoner being executed to his surprise on Tuesday, it’s hard to argue that he knew (or should have known) that he would be executed then, so the conditions of the problem appear to have been satisfied: he was executed some day that week, and he didn’t know, before that day, that he would be executed then.
LikeLike
yme said: “it’s hard to argue that he knew (or should have known) that he would be executed then, …”
If the hangman can reason that he is allowed to hang the prisoner on Tuesday, then the prisoner, who has the same information as the hangman, can also reason that the hangman is allowed to hang him on Tuesday. Therefore the hangman cannot surprise him with a Tuesday hanging (the word “surprise” is the key to interpreting “does not expect [to be hung]” as “expects positively to be not hung”. Therefore the hangman cannot hang him, … which the prisoner can also reason. Therefore the hangman can hang him.
Etc, etc, etc.
There’s no way out. The wardens words are paradoxical and cannot be resolved to a specific meaning. Each conclusion satisfies the conditions requiring the opposite conclusion to be drawn.
I think that is clear, but in case not, I will go a little further. The warden’s words are not quoted. Rather, we are informed, in a paraphrase that may not be exactly the same as the warden’s words, what the instructions were. The phrase “… does not expect …” is ambiguous and it supports the interpretation,”expects that he will positively not be hung that day” and it also supports the interpretation “cannot draw the conclusion that he will be hung that day”. Only the first interpretation leads to the paradox, but it is the interpretation that is required, and that is because we are told that the prisoner is “surprised”, which could only be if the instructions were such that “… does not expect …” in the paraphrase came from the clear meaning, “expects that he will positively not be hung that day” in the warden’s actual words.
I don’t think I will say any more on this.
LikeLike
I don’t see how you get from “the prisoner concluded (wrongly, as it turned out) that he would definitely not be executed on Tuesday” to “the judge’s instructions were that the prisoner be executed on a day that he could definitely rule out.”
LikeLike
FWIW, as far I can tell the “common knowledge explanation” is correct, and it is not “just the clock.” At least, as mentioned by Rob and yme, “suppose that the island chief one day announced that anyone who figures out that s/he has green eyes must leave in 24 hours.”
In this scenario, I don’t see how any villager can deduce that they have green eyes, after any number of days, regardless of how many green-eyed villagers they have. Certainly, the original argument doesn’t work.
LikeLike
Actually, Sam, it seems to me now that the visitor can’t induce a countdown either if N>2. I think the problem is with the mathematical induction. If there are only 2 green-eyed islanders, then the plural entailment of the visitor’s “some green-eyed people” would result in common knowledge (or self-knowledge) and two green-eyed people leaving and all the blue-eyed leaving next day. That’s okay — it’s as if he said “There are two green-eyed people here.” But when you add another green-eyed islander to the group, you also add to the knowledge of the islanders, since they see something different. So the simple mathematical induction doesn’t carry.
LikeLike
If no one likes green-eyed people, and everyone knows it, so to speak, but no one ever says that no one likes green-eyed people, then the green-eyed people just wonder why it’s so hard to get a job. As soon as someone says, “of course, we don’t like green-eyed people on this island,” then suddenly things are very different.
Discrimination that is systemic but not “common knowledge” (in the technical sense) is hard to prove.
LikeLike
Someone probably already said this (i just came here looking for some writings on algos):
Islanders know that N green-eyed people have to leave sometime on the Nth day. But they don’t know when to start counting the days. They needed that one guy to start the count. Right?
Also, Hi Cathy!
LikeLike
What happens if they start counting on different days though? If, say, a bottle washes ashore with a picture of a green eye on it, or maybe it’s just a green bottle, and half of them start counting but half don’t, does that mess everything up?
This reminds me of quantum mechanics where it’s sometimes ambiguous what exactly counts as a “measurement”.
LikeLike
Bottle washing up doesn’t work as if only one green eyed person, it does not inform him that there is a green eyed person.
BTW, does anyone think here is any real difference between this kind of discussion and a group of scholastics debating the number of angels that could dance on the head of a pin? Note: the scholastics were very good at logic.
LikeLike
Oh, and while we’re on puzzles. Hope you haven’t heard of this one:
20 prisoners are set to be executed the next day. They will be lined up with everyone facing the same direction (can only see forward, can’t turn). They are all wearing either a red or blue hat (which they can’t see, so they don’t know what color they’re wearing, but they can see everyone in front of them). Starting from the 20th prisoner and working down to the first, they will be asked one by one to guess the color of their hat. If they guess correctly, they are spared. If incorrect, they’re executed.
The prisoners can devise a plan the night before to save as many of them as they can. What plan do they hatch and how many prisoners can be saved with 100% certainty.
Example: #20 says #19’s color. #19 gets saved, but it’s 50/50 for #20. #18 saves #17 and so on. Thus 50% can be saved with certainty.
LikeLike
Sorry, first post here. I hit the wrong reply button.
LikeLike
I have a way that all the prisoners can be saved except for #20, who has a 50% chance. It seems impossible to do better than that, because #20 has no one to give him any information about his own hat.
The trick is parity. #20 lets everyone know whether there are an even or odd number of red hats in front of him, by guessing that his own hat is, say, red if the number is even and blue if it’s odd. With this information, everyone else can, by the time their turn comes around, figure out their own hat color, which they say, thus allowing the next person in line to figure out theirs.
LikeLike
yup. this is the answer I know.
Had a lot of fun figuring this one out when I first heard it.
LikeLike
Another way to think about this is in terms of what you know when (i.e, information at a time horizon). You say: “if there were really only 2 people with green eyes, then he clearly added real information, because both those people had thought only 1 person had green eyes.” But they only become aware of that information a day later! If you’re OK with this, then if there were 17 people with green eyes, you have to say he added real information too, because all those people previously thought that maybe only 16 people had green eyes. It’s just that the information only kicks in 16 days later.
I don’t like the common knowledge formulation because it depends on a very technical notion of what “common knowledge” means. (As opposed to our common knowledge of what common knowledge means. 🙂 )
LikeLike
When I was a kid there was a variant of this problem involving only three people. They are the final candidates for a job. The employer has them close their eyes and puts a mark on each person’s forehead. (No mirrors, OC.) The he tells them that he has pet either a red mark or a black mark on each person’s forehead, and that at least one person has a black mark. The first person to figure out the color of his mark gets the job. After a couple of minutes one person correctly identifies the color of her mark. What color is it and how does she know?
As with the unexpected hanging, the reasoning in that problem is not strictly logical. The island story corrects the logic. 🙂
LikeLike
For your interview puzzle… The only answer that *can* be reached conclusively is “black”, though exactly how deduce it depends on the scenario you’re in.
If you can see two red marks, you know your own has to be black. This is the only scenario with truly conclusive knowledge, so perhaps it’s the one you had in mind?
If you see a red and a black, then if your mark is red, the person with the black mark is looking at two reds, and ought to infer his own mark is black. If he’s not jumping up to shout “black!” you might infer that he too is looking at one red and one black, i.e. that your own mark is black. On the other hand, he might just be dim-witted, so you don’t actually have a conclusive answer. Still, the only answer that can be reached conclusively in this circumstance is “black” from somebody, so it doesn’t change the answer to the actual question asked by the puzzle.
If you see two blacks, your own could still be black, because there was no assertion that there has to be at least one red. If your own mark were red, then each of the opponents would see a red and black, and should follow the logic from the paragraph above — either immediately saying black, or waiting for the other to *not* say black and then saying black. If neither of them does, then you can infer that all three of your are black.
The problem here is that there’s no control in place to set the tempo, or to prevent one of your competitors from being so irredeemably stupid that he can’t even infer “black” from seeing two reds. Only if you can see two reds yourself, can you have conclusive knowledge.
LikeLike
In the original problem the answer is that all three have black marks.
LikeLike
I guess if the interviewer includes in his instructions a clear statement that it is possible for any of the three candidates to logically infer the answer, then all three must be black — because a priori, that’s the only answer that can be reached conclusively. So any of the three will be looking at two black marks, and have one.
LikeLike
It seems like someone ought to immediately break the social convention and name two specific green-eyed people.
LikeLike
A post about the blue-eyed islanders puzzle? You are really in for it; this thing has crashed several comment threads on Terry Tao’s blog and there’s also a long Q&A about it on math.stackexchange. I’m not sure there’s anything that can be said about it that hasn’t already been said, several times, in those places.
LikeLike
The funny thing is that this post is not about the blue-eyed islander puzzle.
That puzzle is just as an illustration that a single bit of information fed into a complex system (here, the whole shebang of many agents computing in parallel) can have big macro consequences.
Now, this is not really original as well. Instead of “Blue eye/Green eye” thing, people like to use the expression “Butterfly effect” !
LikeLike
Just an observation: In situation when there is only one green eyed person on the island, everyone but that person knows that someone has green eyes. The green eyed guy is convinced that everyone is blue-eyed. So the stranger’s statement is news to the green eyed islander. I think that’s how “new bit” sneaks into that system: via the parallel world with only one green eyed islander.
In the setup described above, each islander only knows that his or her eye color is either blue or green. So the possibility of “everyone has blue eyes” is not excluded. And that’s what keeps them all on the island.
LikeLike
Hey, I think I got it! If there were only 2 people with green eyes, and the visitor said nothing, then the 2 people would not have to leave. It is precisely the visitor statement what implies that if there are 2 people with green eyes, then they will have to leave 48 hours after the statement.
Now, the argument by which all the 17th green eyed people will leave exactly after the 17th day relies on them being aware of the fact that if there were 2 people with green eyes, then they would know that they have to leave 48 hours after the visitor statement.
So the visitor’s statement is not only relevant information for the case where there are 2 green eyed people. It is also relevant for the case where there are 17. Again, because the argument to make the 17 out of the island uses that everyone is aware of the inductive argument, and what the visitor provides is the basis case for 2 green eyed people.
It is subtle, because the inductive reasoning is not something that only we do while looking at the problem, but it is actually a reasoning that the islanders would do as well, so they need the basis step, which is given by the visitor statement.
Works? 🙂
LikeLike
on the day he leaves he says, “hey, it’s good to see some people with green eyes here!”.
To me, that says he has never seen green eyes (on this island), until the day he leaves. Which implies that everybody, whom he has seen before this last day, has blue eyes. There are special cases for 2, 3, 4, 5? islanders seen by him for the first time this day.
Of course, you can repair the puzzle by saying something like he has seen every islander’s eyes, or all islanders know and remember exactly whose eyes he has seen. And he would better say something like he had never seen people (pl) with green eyes before coming to the island. Also, one of the green-eyes thinks he has seen the green-eyed priestess who serves the volcano goddess.
What if one/both/some/all the green-eyes decided to go sacrifice a pineapple, instead of seeing (and hearing) him off? If some of the green-eyes are liars, can anybody call them out?
LikeLike
Sorry, read this late — I see there are already a million comments. But here’s another one, because I’ve already written what I’ve pasted below for a book. This is a similar conundrum — in fact it might even be isomorphic in some sense.
A prisoner who has committed an especially heinous crime is brought before a judge for sentencing.
The judge says that the prisoner has transgressed so egregiously that he, the judge, is going to impose a particularly harsh sentence. The prisoner, he says, will certainly be executed at dawn on one of the next 60 days, but the prisoner will not know what day it will be.
“Aha!” says the prisoner, “I must be allowed to go free. The sentence cannot be carried out.”
“And why, pray tell,” replies the judge, “is that the case?”
The prisoner bases his argument on what is known as reduction ad absurdum – sometimes called “proof by contradiction”. In a reduction ad absurdum argument, a statement is proven false if it can be shown that if it were true, it would imply a falsehood. The prisoner claims that if the sentence were carried out, it would prove that at least one of the conditions that the judge stipulated was false.
The prisoner thus responds with the following soliloquy: “Suppose the sentence is carried out on the 60th morning. But then I will know that it will be carried out on that day, because you have decreed that it will be carried out on one of the next 60 days. But you have also stipulated that I will not know which day it will be. Hence, I cannot be executed on the 60th day, because if I am, I will know beforehand which day it will be, and the sentence will not be carried out in accordance with your decree.
“But if I cannot be executed on the 60th day, then I cannot be executed on the 59th day either, because I already know I cannot be executed on the 60th; so if I am executed on the 59th day, I will know that it will be on that day, and hence once again the sentence will not be correctly carried out.
“As you can see, this continues back to the very first day of the sentence, on which it cannot be carried out either. Therefore I must be allowed to go free.”
The judge listened carefully and then pronounced that the sentence must be imposed as he had declared. On the 42nd day the prisoner was executed. Paradoxically, in spite of the prisoner’s cogent reduction ad absurdum argument, he did not know it would be on that day. As the judge intended, the prisoner sweated profusely in the early morning hours every day up to then.
I think the resolution to both this and the green-eyed blue-eyed conundrum is a little humdrum. It’s that no one believes the rules are really hard and fast and furthermore, they can’t really be enforced. In the case of the judge and the prisoner, the judge could be capricious and execute the prisoner on the last day in spite of his rules — or even extend the period of the sentencing. In the blue-eyed green-eyed case it’s even more obvious. For example take the case of the two green-eyed people who don’t leave after one day. “Then,” it says, “all three of you have to leave, after two days.” Like hell we do — who’s checking? Like who’s enforcing these rules? If it’s some kind of court of law, I could just say I didn’t think of the interpretation that if the other two green-eyed people didn’t leave after a day that must mean that I have green eyes. And how could you prove I was lying?
LikeLike
So, the common knowledge is correct, a relatively concrete way to view it is as follow, consider the case with 2 people, Alice and Bob, while both have blue eyes, neither knows this and neither expects the other person to know it, so a concrete fact given by the visitor which was not known before is that now Alice knows that Bob knows that somebody has green eyes, whereas before, while Bob knew this fact, Alice did not know that Bob knew this fact. Similarly with three people, Alice, Bob, and Carol, Alice did not know that Bob knew that carol knew there was a person with green eyes (if Alice had blue eyes, and Bob assumed that he had blue eyes, and Carol incorrectly assumed she had blue eyes (from Bob’s perspective), then Bob would not assume this). This pattern holds for up to 100 people, so one knew concrete fact is that person 1 knows that person 2 knows that… person 100 knows that somebody has green eyes, which is a concrete new fact.
LikeLike
I’ve heard it said among people who understand both finance and common knowledge that the popping of a financial bubble often has a “blue-eyed/green-eyed” feel to it. The other common metaphor, which isn’t so different, is the story of the emperor’s new clothes.
I’d be curious to hear whether the readers (and author) of this blog agree.
If so, what types of policy or market structure can help disseminate information and achieve common knowledge (arguably, mandatory public disclosures already do this, to some extent)?
The way that markets are commonly taken to incorporate information is through prices. Do these provide common knowledge, or only the more limited kind of knowledge that the islanders had before the outsider’s fateful announcement?
LikeLike
Yes, Adam Smith, I think there are applications to Keynes’ Beauty Contest (stock prices), Hobbes’ Trap (pre-emptive invasion/arms race) and maybe even liquidity traps (investment/speculation/borrowing) and probably many others.
Contrary, or complemetary to, the solution I gave way up at the top (the visitor starts the clock, so gives no new information, but merely begins the induction), while is a correct solution, is partial to understanding Mathbabe’s question because, crucially, the visitor mentions ONLY green eyes.
Consider: the chief says, “The law must be enforced today.” No one will leave. (Say 3 green-eyed and 3 blue-eyed: the green-eyed would never know if they are the third green-eyed or the fourth blue-eyed; the blue-eyed would never know if they are the third blue-eyed or the fourth green-eyed.)
BUT if the chief says “The green-eyed must leave beginning today,” then the induction would commence immediately and three days later all the green-eyed would depart. So it’s a two part dynamic change in the system: 1) targeting one group and 2) starting the clock.
LikeLike
There is mild evidence going back to the 1960s that many stock market movements are driven by the realization that everyone else knows what you know.
LikeLike
This is a false paradox. it is a false induction because each step relies upon specific conditions (the assumed number of green sets of eyes). That specific number is fixed so cannot be carried forward.
The puzzle rests on distinguishing public information and private information.
For n1, followed by
2) departure events “or non-departure events” that convey private information
Special case: n=3
Everyone knows there are at least two people with green eyes. Among those three, each knows of two others. Their uncertainty are
A) each member of the group is uncertain as to his/her status so us uncertain as to n = 2 or n=3
B) the other known green eyed have private information, specifically their understanding of the uncertainty. If I am green, they have the same uncertainty as me. If I have blue , they have the uncertainty regarding n=1 or n=2.
The speaker publicly eliminates the n=1 possibility. That possibility is no longer private. Everyone knows n>1 and everyone knows that everyone else knows n>1. The declaration, therefore, contains information. I then gain new information by a “no departure event”, that is g1 and g2 do not leave. that n=3, so I must have green eyes.
If n=4, the speaker conveys NO new information. the departure event does not occur because everyone already know there are n>=2 green eyed. The no departure event conveys no information, The information chain stops and noone leaves the island.
So if n=4 (or greater), n-4 are uncertain as to n=4 or n=5. 4 people are uncertain as to n=4 or n=3. The speaker conveys no information by eliminating n=1, so the non-departure conveys no private information. Everyone lives happily ever after.
LikeLike
I see the flaw in my reasoning. Everyone has personal knowledge (green = either n or n – 1) conditioned on personal eye color. Everyone also knows that each person in the group has similar private knowledge that is conditioned on my (personally unknown) eye color.. Group knowledge is of the conditioned uncertainties.
Each event or non-event requires the reveling of private knowledge. For this event to be triggered, there must be a prior event. The announcement (for non-trivial n) conveys no knowledge directly, but begins the cascade of events that systematically eliminate n(g)= 1, 2,, 3 and so forth. When n-1 has been eliminated, I and all my peers know that we must have green eyes.
The announcement, therefore, though it conveys no information forces the revelation of private information.
LikeLike