"The famously difficult green-eyed logic puzzle" - I disagree with the proposed solution

In My Humble Opinion
1

There’s a TED video with 3.8 million views and 29k likes called The famously difficult green-eyed logic puzzle:

It posits a situation of a prison island inhabited by 100 prisoners, all of whom are 'perfect logicians', and all of whom have green eyes. All prisoners can see each other, but not themselves - there are no reflective surfaces or cameras etc on the island. Communication between prisoners is strictly forbidden, hence, and importantly, no one has ever learned their own eye color.

On this island, there’s one means of escape: You can approach a prison guard at night, and ask to leave. If you have green eyes, you’re allowed to leave. If you don’t have green eyes, you die. Given that no one knows their own eye color, and no one is prepared to risk leaving unless they are absolutely sure they have green eyes, no one attempts to leave.wo

External to the island, a “free the 100 green-eyed prisoners” cause has gained momentum, to the point that the head of the prison has allowed one person to visit the island, and communicate to the prisoners, but there’s two conditions: This person can only make a single statement, and they can not reveal any new information.

The visitor addresses all 100 prisoners and says:

On the surface, it seems this has added no new information to the knowledge of the prisoners, all of whom are aware there are at least 99 green eyed prisoners on the island, so the head of the prison isn’t concerned by the statement. However, 100 days later, all prisoners have figured out their own green eye color, and hence, all ask to leave together on the 100th night.

The video then goes on to explain the supposed logic that was used by the prisoners to work out their own eye color, using an example where we’re asked to imagine there’s only two prisoners on the island. They hear the statement, then both prisoners leave on the second night (and the logic explained in the video is sound). The video then uses an example where there’s only three prisoners, and again after hearing the statement, they all use sound logic to work out their own green eye color, and they all leave on the the third night.

The video doesn’t attempt to explain how the logic works once you hit 4 or more prisoners, it just kind of implies that the logic will hold forever, and that if there’s x number of prisoners, they will take x number of days to work out their eye color, then leave the island. I don’t think the logic works once you reach 4 or more prisoners. There’s a very long explanation to why I think this, and a very short explanation, and here is the very short explanation…

…

In a scenario where there’s only two prisoners, being told “at least one of you has green eyes” does add information that can help them work out their own eye color. Although both prisoners already know there’s at least one green eyed prisoner on the island (they can see each other), what they can’t be sure of is that the other prisoner also knows of the existence of at least one green eyed prisoner. Hence, both prisoners use this new information to eventually work out their own eye color.

In a scenario with three prisoners, again, each individual prisoner already knows that at least one prisoner has green eyes. However, like the previous scenario, they can not be certain that every prisoner is aware of the existence of at least one green eyed prisoner. There’s sound logic to back this, but I am keeping this explanation brief.

Let’s add one more prisoner, so there are now four green eyed prisoners. In this scenario, every individual prisoner is aware of the existence of at least one green eyed prisoner, but crucially, they also know that every prisoner is aware of this. This is the important difference once you hit four or more prisoners. Hence, being told “at least one of you has green eyes” adds no new information to a green eyed prison population of four or more, hence, they can not use this statement to work out their own eye color.

2

Small correction:

3

For the record and reference:

Randall Munroe’s statement of the problem over at xkcd.

. . . and his solution, in detail.

(n.b.: It’s blue eyes in his telling.)

(ETA: It might not be quite the same problem, assuming OP is relating the TED video accurately. In the xkcd telling, there are 100 blue-eyed people and 100 brown-eyed people.)

4

You’re wrong…but I’m not going to go into the several pages necessary. You are in error in thinking there’s a difference between the case where n=3 and n=4. In all cases, everyone’s knowledge of the situation is vital.

The puzzle actually does work as published.

(Addendum: a very similar puzzle works as published. I believe Raymond Smullyan had a version. It is entirely possible that the TED video made a mistake and framed the puzzle badly in some way. I have not seen the video.)

5

Likewise, I didn’t view the video. But see my ETA to Post #3, above.

6

It’s false that the visitor adds no information. Otherwise, no one could make any conclusions at all.

It’s just that the visitor adds no first-order information. Everybody knows that there’s at least one green-eyed prisoner. And everyone knows that everyone knows that there’s at least one green-eyed prisoner. But it’s not true that [everyone knows that] x 100 there’s at least one green-eyed prisoner. That’s the crucial piece of information that the visitor adds and the solution to the problem.

See the Wikipedia article on common knowledge.

7

The visitor adds new information only if the prison population is two or three. The visitor adds no new information if the prison population is 4 or more, hence, the statement is of no use to the prison population.

8

To put another way:

In a scenario where there’s only two or three prisoners, everyone knows there’s at least one green eyed prisoner, but not everyone knows that everyone knows there’s at least one green eyed prisoner. Hence, to be told “at least one of you has green eyes” is game changing information, because each prisoner now thinks “Yes! I can now be certain everyone has this information!”.

With 4 or more prisoners, everyone knows there’s at least one green eyed prisoner, and everyone knows that everyone knows there’s at least one green eyed prisoner. Hence, if 4 or more prisoners are told “at least one of you has green eyes”, it changes absolutely nothing to what they already know about themselves, and each other.

9

This puzzle reminds me of the hanging judge puzzle.

A judge is sentencing a prisoner: “You are sentenced to death by hanging. There are thirty days in the upcoming month and the hangman will arrive at your cell at dawn on one of those days to take you to the gallows and carry out the sentence. But in order that you not be burdened with too much apprehension, I decree that you will not know the day of your execution in advance and the sentence will only be carried out on a day when you did not expect to be executed.”

The prisoner is unexpectedly happy with this sentence: *"This is great. I can’t be hung on a day when I am expecting to be executed. And the judge said the sentence has to be carried out on one of the thirty days next month. Now I can’t be executed on the 30th day of the month because if I was still alive on the evening of the 29th day then I would know I’d be hung the next morning. So it wouldn’t be unexpected and therefore the sentence can’t be carried out.

And now that I know that I can’t be hung on the 30th day, I know that I can’t be hung on the 29th day either. Because if I’m alive on the evening of the 28th day and I’ve already proven I can’t be hung on the 30th day then the 29th day would be the only day left in the month I could be hung on so again it wouldn’t be unexpected.

And it keeps going from there. If I’ve eliminated the the 29th and 30th days then on the evening of the 27th day, I’d know the 28th morning is the only one left and now it’s no longer unexpected. And I can keep going back like this, eliminating every day of the month as a possibility. In the end there’s no day they can hang me on so the sentence can’t be carried out."*

So the prisoner went back to his cell, happy about beating his sentence. Right up to the morning of the 13th day when the hangman unexpectedly showed up at his cell at dawn and took him to the gallows.

The point is that you can’t simply assume that any logical proof that works for cases n and n+1 and n+2 can automatically be extended to n+x.

10

With 4 prisoners, I know that everyone knows that everyone knows that there’s at least one green-eyed prisoner. But I don’t know that everyone knows that everyone knows that everyone knows that there’s a least one green-eyed prisoner. Someone could give me this information, however.

If someone external says that “at least one of you has green eyes”, that’s not the only information that’s transmitted. Because it’s made publicly, I also know that everyone heard that announcement. And that everyone saw that everyone heard the announcement, and so on.

If the visitor had engaged in private conversation with each prisoner, saying the same thing, the solution would not work. The common knowledge is the key ingredient.

11

With two prisoners, if one of the two has brown eyes, after the statement the other person knows for sure he has green eyes, but that doesn’t carry over to a larger population. If you plunk a brown-eyed person down into 99 green-eyed prisoners, being told at least one of you has green eyes is not new information to any of them.

12

No…because once the fourth day has gone by and no one has spoken up, now everyone knows…etc. The passage of a day, in which no one speaks, is part of the information. You know something more on day 78 than you knew on day 77.

This is why there is nothing special about the jump from 3 to 4.

13

In a four-or-more prison population, what is the new information that gets learned by hearing the statement “at least one of you has green eyes”? There must be new information passed at this instant if this information is useful, irrespective of what else the prison population can learn as the days unfold.

In a 2 or 3 prisoner scenario, the knowledge, learned by every prisoner, is “I can now be certain that every prisoner is aware that that all of us know there is at least one green eyed prisoner”.

In a 4-or-more prisoner scenario, this information is already known to all, they don’t need be told. So what’s the new information getting added by the statement?

14

I think I see where you are going with this KellyCriterion

this left side color is the observer, the right group are the others that they see The possibilities (the ordering of the observed don’t matter) for 3 are thus before the person gave the group the information:

G==GG, G==BG, G==BB, B==GG, B==BG, B==BB
With the information of at least 1 green,
G==GG, G==BG, B==GG, B==BG
G==BB is removed because the observer would leave right away on the first night, yet everyone is still there the next day . For each of the 3 individuals, at least 1 G needs to be in every reference frame simultaneously.

So each member knows that if they see BG, then the others must be seeing the observer as G to keep them there overnight. But all they see is GG waking up with them the next day, with the idea in the observer’s head that the others see BG waking up.

So how do we logic our way through the worst case scenario, GBG? With the information "At least one of you has green eyes” I do not see how we can move from that point. In every reference frame it is true that at least one has green eyes. Even if (as in reality), the truth was GGG, with no greater reason to believe that the observer is G/B, and the information is seen as fulfilled in everyone’s observation; why should this grand logician’s collusion of waiting X+1 days for every G that they see, begin?

Sure with GGG they all get out in 3 days; but GBG has the G’s get out in 2 and the B keeping mental notes such that he realizes that his timer could only be later if they saw him as B. B-b-but does this trick work if the B’s outnumber the G’s?

say 60B and 40G grouped up. G’s see 39 others(+1) for 40 day wait, B’s see 40(+1) for a 41 day wait. G’s get out on day 40 and B’s realize they have to stay in prison…

or your case of 4G, each see 3 other G’s and they all get out on the same 4th night

This seems to be less of a puzzle that can be solved by word logic, and more of a puzzle of math logic that lets you search out and safely extract any number of “things with a desirable trait” vs the chaff of “an undesirable trait”

That is not to say that word and math logic are different, this video by Day9 makes the case that math is really just another way to be precise towards problem solving and making arguments. Professor[9] - Combinatorics and Other Math - YouTube

15

It tells everyone what color to focus on and kicks off the logic chain.

16

The new information is, “No one has said, ‘Hey, I know the answer.’” Before that, that isn’t known. Now it is.

This increases, day by day. On day 78, you know more than you did on day 77. The knowledge is the same: “No one has spoken up.” Therefore no one has enough information to answer. But on day 100, it all adds up, and one person does know the answer.

17

I’m not sure what the breakdown in logic is.

Adria, Bill, Carl, and Devon all see 3 green-eyed people. If Adria has brown eyes, then she would expect Bill, Carl and Devon all to leave the third day after the interloper gives his message. When they don’t, she realizes she also has green eyes and they leave on the fourth day. And the same is true of Bill, Carl and Devon.

18

I disagree with that example.

IIRC, the point there is that, while an unexpected hanging on the 30th Day can be legitimately ruled out, the prisoner then slips up by saying “I know that I can’t be hung on the 30th day” – which is false.

He then makes the exact same slip-up for n+1: “And now that I know that I can’t be hung on the 30th day, I know that I can’t be hung on the 29th day either.”

(He builds that conclusion around the claim that “I’ve already proven I can’t be hung on the 30th day” – but he was wrong then, and he’s wrong now.)

He eventually concludes – as you say – that “there’s no day they can hang me on”. That’s wrong for Day 30; he should’ve ruled out an unexpected hanging, but instead ruled out getting hung at all. He’s just as wrong to rule out getting hung on Day 29, and Day 28, and so on: he thus gets hung unexpectedly, which – can happen on any day, once he’s falsely concluded that “there’s no day they can hang me on”.

As soon as he says “I can’t be executed on the 30th day of the month”, it can happen on the 30th day of the month. He then extends that mistake out past n+1 and n+2 to n+x – but that’s not introducing a new mistake, it’s just repeating his first one.

19

It is, unfortunately, one of those “just so” logic puzzle examples.

Clearly, there is an algorithm to deduce your eye color. (Assuming that the “approach the guard at night” bit is cleared up: everyone gets 1 chance per night at the same time.)

The key thing omitted: Everyone has to interpret the statement “at least one of you has green eyes” as “begin the algorithm”.

If just one person instead says to themselves, “yeah I knew that already” and doesn’t start the algorithm the same time as the others, it falls apart. In particular, does everyone trust all the others to know they should begin the algorithm?

There is nothing in the usual telling of these stories that explicitly states this condition.

Re: The Unexpected Hanging. This is just a long winded way of saying “There is no way with 2 or more people with the same information and logic skills, etc., for one to make a logical decision and not have everyone else also make the same logical decision. By the way, illogical decisions or ones based on information not known to others are different.” Which is sort of a “Well, duh!” statement.

20

There seems to be one in this telling; the OP said they’re all “perfect logicians”.