A bunch of people have explained this correctly, but maybe not clearly. The answer has to do with people’s mental models of what everyone else things.
So let’s say we have 5 people:
Amy, Beth, Clarice, Daphne, Erica
What does Amy know?
Amy knows: “4 people have green eyes, Amy is unknown”
What does Amy think that Beth knows?
Amy thinks that Beth knows: “3 people have green eyes, Beth is unknown. Amy is X”. (Amy knows that Beth knows the color of Amy’s eyes. But Amy doesn’t know what that is.)
Note that from Amy’s perspective, the minimum number of people that Beth knows have green eyes is 3.
What does Amy think that Beth thinks that Clarice knows? “2 people have green eyes. Clarice is unknown. Beth is X, Amy is Y”. X means “Amy knows that Beth’s eyes are green. And Clarice knows that Beth’s eye’s are green. But Beth doesn’t know that Clarice knows that Beth’s eyes are green”. Y means “Amy knows that Beth and Clarice both know what color Amy’s eyes are. But Amy doesn’t know what that is”.
Note that from Amy’s perspective, the minimum number of people that Beth knows that Clarice knows have green eyes is 2.
Extend that twice more, and you’ll find that the minimum number of people that Amy knows that Beth knows that Clarice knows that Daphne knows that Erica knows are green, is 0.
So, someone can think that someone can think that someone can think that… (repeat several more times) someone can think that there are zero people with green eyes.
But now, someone publicly says “at least one person has green eyes”. And everyone heard that.
Now it is NOT possible, given the information everyone has that everyone knows everyone has, to think that someone can think that someone can think that someone can think that … someone can think that zero people have green eyes.
That’s the new information that was introduced. Although I suspect that may also have not been clear.
If, in fact, the above questions are relevant, then I think it must just be an error or sloppiness in the statement of the problem. I’m pretty sure the xkcd version of the problem doesn’t have that problem. In the xkcd telling, it’s an island not a prison, and at the opening of the problem, everybody is just there.
I hadn’t thought of it this way, but this actually makes sense, when you work it through the way you’ve explained it.
I still need to get it to crystalise in my head, but this is a fresh perspective I hadn’t thought of. My brain can traverse person 1 thinking what person 2 thinks about person 3, but I can’t “make the jump” (mentally) to person 4.
The only real way to do get the problem is to slowly expand the number of people, and realize that there’s nothing different between each scenario. There is no reason why 3 or 4 would be any different, since nothing has changed.
The problem is that our brains intuitively only handle about 3 recursions before taking shortcuts. The only trick I know for getting around that is to start from what you’ve determined for 3 and treat it as right without going back through the entire logic again.
So, they’re perfect logicians? Why does this imply that they will interpret the statement as “begin the algorithm”?
One very, very important thing to note: There are schools of logic! Each school makes different assumptions about basic concepts. Each, of course, might think their school is more perfect (!) than the others. And therefore, they might not trust those that belong to another school.
These are people who get into long discussions about the truthfulness of statements like “There isn’t a rhinoceros in this room.”
So a statement like “One of you has green eyes.” could easily provoke very different, perfectly logical, reactions.
It’s tough. Even if you “make the jump” to 4, you might not be able to do 5. It’s the same for everybody. The thing to keep in mind here is that things become so terribly complicated so very quickly, that extremely soon none us can actually handle the idea anymore. We can’t hold the whole essence of a statement in our head and perfectly understand it.
That’s why we use logic.
If we can use a reliable logical process that preserves truth when we jump from person 1 to person 2 – a simple enough case that we can understand it all at once – then that same logical process will preserve truth jumping from 2 to 3, and from 3 to 4, and so on. As the long as the logical process is secure and reliable, then we can keep using it again and again. That’s why we can make a statement about 100 or 1000 or any arbitrarily high number and be confident that the conclusion is sound, even though we can no longer untangle the layers.
I don’t think that has anything to do with anything. The answer doesn’t depend on the subtle philosophical differences between different types of logic. And there is no “begin the algorithm”, that’s completely wrong and misleading. If I say “there’s $100 in that box” and you open the box and take the $100, I didn’t say “begin the algorithm”, I just gave you new information that allowed you to deduce where to find $100. Similarly saying “at least one person has green eyes” is giving new information, even though it sounds like it isn’t, which is what makes the puzzle so confusing.
Maybe (or maybe not…) one way to help is to conceptualize it, in our post-Snowden world, is that the visitor’s statement’s text contains no new information, but the statement’s metadata [who, where, and crucially, when] does have information. And some of that that information (the when) is enough for the logicians to take a step in their reasoning that they couldn’t before.
The solution seems to require that the logicians all come to the same strategy and thus use the day counting mechanism as the same way to count how many people are in the population with that eye color.
If the solution is the perfect - i.e., the fastest - mechanism for this determination, then the solution works. But I’m not seeing how that’s the optimal, most perfect, and logical solution.
We know from the story that the guards are not as perfect as the prisoners. Otherwise, they would pick up on the one piece of information, realise that the game was up, and do whatever it is that everyone is fearing - and thus keeping them from speaking directly to everyone - to everyone.
So, once the guards don’t punish everyone, the logicians would start to communicate in similarly obtuse terms. I mean, if getting off the island is the principal concern of every prisoner there, and they’re all of a single mind logically, then any one thing said would be taken as a piece of evidence. Just say, “Sorry, I mistook you for someone else”, and everyone can go home that night.
The only way to make the answer the actual solution to the problem is to assume that the inventor of the solution would come up with ever tightening criteria until his answer was the only legal solution. So, yeah, if you require that to be the answer, the perfect logicians will come to it. But from just the descriptions given, that answer is probably not actually the optimal or likely solution.
I’m not quite sure what point you think you’re making. Sure, the puzzle is just a puzzle. In any remotely real life situation, it would fall apart instantly, as there is no such thing as a perfect logician, much less a group of perfect logicians who all trust that all the others in the group are also perfect logicians.
But I honestly feel like your response is just the logic puzzle equivalent of threadshitting. You might as well ask whether the guy with the rowboat and the chicken and the fox and the corn has a leash and a stake to keep the fox from wandering off if it’s left alone, and why can’t he hide the corn in a tree or something.
Also, you keep talking about a “strategy” and a “day counting mechanism”, as if the whole thing is just a plan that some people came up with. It’s not. It’s an inescapable outcome of the setup of the puzzle.
Yeah. Even if the prisoners somehow came up with different strategies, they would still be equivalently optimal–they’d still all leave on the same day. The presented strategy only requires that the others all leave as soon as possible. This must be the same day since everyone receives the same information (and they all know this to be the case).
The arcane and paradoxical use is the fault of language. It’s not that you’re dense, it’s that it’s impossible to speak 100 iterations of “everyone knows” while having it come out making sense. I promise that no one - not a soul - read each word when I copy/pasted that terribly long sentence above.
The thing is, you’re not supposed to understand the English. That’s why I said…
And now you’re experiencing the “forced error” of trying to interpret the sentence. You rephrased it as “I could conceive of one of the other prisoners as actually seeing zero when he must actually be seeing at least one,” but that’s not even close to what I said. See below.
This is a perfect explanation, but as Max says, it is not clear. It is right, it is accurate,but it is not clear. Most people, tired of typing, insert something like “Extend that twice more” and to be fair, the reader won’t read any further anyway even if they did type it out. They wouldn’t even understand it. So we’re stuck with this “I suspect that may also have not been clear” ending in perpetuity.
That’s because most people can’t go further than 3. You’re in good company. To understand it, instead of having my mental characters say what they thought, I had them write it down on paper. Then the next person in line had to assess what was on the paper of the preceding person. This prevents you from making the common mistake, as DiFool did, of “shortcutting” from person B to person D.
You can untangle the layers. You just have to, as I said, have each person write down an answer on paper. Thus:
Interviewer: “How many people have green eyes in this prison?”
A: “Well, I count 99, but it might be 100. I can’t say for sure because I don’t know my own eye color. If I’m green-eyed, it’s 100, but if I’m brown or blue, it’s only 99. So 99 or 100, but I cannot say for sure. So I offer you two numbers, knowing one is wrong and one right.”
Interviewer: “Person B, I asked person A to count the green eyed people here. What did he tell me?”
B: “Well, I count 99 people, so I myself know there’s at least 99, maybe 100. However, I’m counting A, while there’s no way he could’ve counted himself. I have no clue if he counted me or not. So I can deduce that he either said “99 or 100” or he said “98 or 99”. If I have green eyes (and I don’t know that I do), person A knows that and said “99 or 100,” accounting for his own ignorance. But if I don’t have green eyes, he’d have said “98 or 99.” I’m aware that he only said one of those pairs, so one is the correct pair and the other is incorrect, but there’s no way for me to know which pair it was. So I offer you four total numbers, knowing two are wrong and two are right. Just so we’re clear, I myself know it’s either 99 or 98, but that’s not what you asked me.”
Interviewer: “Person C, I just talked to person B about person A. What did B tell me?”
C: “Well, I count 99 people, so I myself know there’s at least 99, maybe 100, but that’s not the question you’ve asked of me. You want to know what B said, and I know he’s wicked smart, like me. So I can tell you this confidently: If I have green eyes, he said “99 or 100” or “98 or 99.” If I don’t, B must’ve said “‘98 or 99’ or ‘97 or 98’.” I offer you eight numbers in total, and yes, I know 4 of those are wrong. I know that B only gave you four numbers, but the thing is, without knowing my own eye color, I can’t possibly tell you which four of those eight are the ones he said. And just so we’re clear, I know there are either 99 or 100 green-eyed people here. I also know that B knows that two of his four numbers are wrong. But neither of those is what you asked me.”
Interviewer: “But where did the 97 come from?”
C: “Well, I only said that’s possible if I have non-green eyes, and I might very well. I have no idea if that’s the case, but I could have blue eyes. If that were so, then B would see 99 green-eyed people, just like I do. So he’d think there was a minimum of 98 since he’s not counting himself or me. He’d thus be forced to conclude that if he’s not counting himself or me, then neither is A, who in addition wouldn’t count himself. So since I might not have green eyes, and B thinks the same, and A thinks the same, B might’ve included a 97 in his answer. Again, he might not have, but I couldn’t know.”
So A’s lowest number is 99, forcing B’s lowest to be 98, and thus C’s lowest to be 97. Everyone is aware that this is a wrong answer, but that’s not the point because it’s not what anyone was asked.
Why did the logician prisoners even need to know, in a theoretical sense, that everyone else knew that at there is at least 1 Green eyed person?
That knowledge was known on the first day of incarceration to everyone who had working eyes. Why not start then instead of waiting?
If there was just Amy as a sole prisoner who did not know her eye color, then of course she could not act until she was alerted to the fact of her eye color being the chosen color or not.
If there are two, Amy and Mary, who do not want to act until they are each certain that the other knows at least one of them has Green eyes; then that is reasonable as well to wait for the extra information. If both had either Blue or Brown eyes, and they used the method, they would both go at 0(G’s seen)+1 days and both be killed. And if there was Mary with G eyes, she would never know it until the extra info was given, and thus always be too wary to ever use the ingroup/outgroup algorithm. I know Chessic Sense, let me have this lie for demonstration purposes
If Amy, Mary, and Dave are the prisoners they could only act on the first day of imprisonment if they are all G’s. Each person sees 2 others, and from their own perspective they must assume they are B eyed, and also that every other person sees themselves as B eyed. Thus, even though objectively each person sees 2 Green people, their lone viewpoints are not certain enough as universal information unless every member of the prison group can objectively verify at least 1 G eyed person from at least a 2 person (seemingly B eyed) perspective.
The bottom single person is the observer, the G’s changing to B’s is what must be assumed by the observer if they want 2 person objectivity with everyone else. if there is at least 1 G in every frame of 2 person reference, then everyone can objectively know that everyone else can objectively see at least that many G’s. With such a guarantee that everyone sees there are G’s to be freed, then the sifting algorithm can be used safely on the first day of incarceration instead of waiting for the extra information later.
(AG MG) (AB MG) (AG MB) (DG MG) (DB MG) (DG MB) (AG DG) (AB DG) (AG DB)
(DG…).(DB…).(DB…).(AG…).(AB…).(AB…).(MG…).(MB…).(MB…)
truth…D/A …D/M…truth…A/D…A/M…truth…M/A…M/D
If someone was truly B eyed, then this would not work, as in one reference frame all a person must be assumed to see is nothing but B’s which does not give that person enough information to trust that there are any G’s do begin with.
(AB MG) (AB MB)
(DG…)…(DB…)
truth…D/M might see a sea of B. Safer to do nothing for now…
In a group of five or more, knowing that everyone objectively sees at least 1 Green eyed person gets easier (by a ratio it seems). Amy, Mary, Dave, Ruth, Jon. They need at least 3 Green eyed people to always safely say that everyone can see G. Because with only 2 G, those two could be in the same observing pair and thus be forced to be safe and conclude all B’s. With 3, even the other two G’s will agree that at least 1 other G person exists. Thus, they are all safe in knowing that everyone else knows at least a G exists and are free to use the algorithm on the first day to truly see if they are G’s or not.
If the Dictator was smart, in order to stop this from happening he would have to keep everyone in small groups just underneath the threshold of certainty. It would be much easier in th XKCD example as there are large groups of blue/brown/green/red eyed people and only Blues could escape. In our case of all green eyed people, everyone would have to be kept in solitary pairs.
In our example even if the Dictator moved them around such that they never knew how many people in total there were, once they settle into any sized group for any period of time (say over lunch) they could begin within that group. As they know that everyone else objectively saw plenty of G eyed people, which acts as its own “there is at least one green eyed person” and everyone in this impromptu group knows this; and that the person across from them has G eyes so the algorithm would safely sift the true G’s out.
Everything you’re saying kinda sorta sounds like it makes sense. But it’s wrong. And the easiest way to see it’s wrong is to apply it to the case with only two people.
Each person sees the other. Each person knows that there’s at least one person with green eyes.
But neither person has any way to deduce the color of their own eyes. So they sit there forever.
Now, a stranger comes in and says “at least one person has green eyes”, WHICH THEY BOTH KNEW, and then things kick off.
In any of the possible cases, the situation is perfectly stable forever. No person can ever know anything about their own eyes. How could they? Nothing gives them any information. UNTIL, something happens which does.
That wasn’t my point. My point was that the solution to the problem only works if all of them come to the same solution based on the information given. The only way that occurs - and the problem states as much - is if it is the optimal solution.
I’m satisfied that it is a workable answer, but I’m not satisfied that it is the perfect answer. So if we are to accept that these are all perfect logicians, I don’t think that this is the solution they would land on, and subsequently the order of events would play out differently.
The problem’s answer is interesting, and works, but by the constraints given, I don’t think that it is the actual answer. It’s just the answer which is the most interesting.
Can you suggest a different, better, solution? Feel free to talk about the case where there are 3 or 4 green eyed people, just to make things simple, or explain why your solution only works with more than that.
I strongly believe that this is not the “best” solution. Rather, it is the only, inevitable solution. But I’m willing to be convinced otherwise.
Because the logicians are perfect, their individual algorithms must at least be equivalent, even if they aren’t identical. As such, everybody who sees the same thing must perform the same action (either stay or go). There are thus only two states that can exist after each night passes:
P: Everybody remains
Q: Everybody who has green eyes leaves
Furthermore, the game ends upon a Q, so the game must always progress as PPPQ, PPPPPPPPQ, etc., and the string lengths must be ordered with respect to the number of green-eyed prisoners.
Given all this, it’s fairly obvious that you can’t do better than leaving on the day of the green-eyed-prisoner count. There’s nowhere to transmit additional information.
