validity of proof (100 green eyes riddle)

Question

Here is the 100 green eyes riddle:

Imagine an island where 100 people,all perfect logicians,are imprisoned by a mad dictator.There's no escape,except for one strange rule. Any prisoner can approach the guards at night and ask to leave. If they have green eyes, they'll be released. If not, they'll be tossed into the volcano. As it happens, all 100 prisoners have green eyes, but they've lived there since birth, and the dictator has ensured they can't learn their own eye color. There are no reflective surfaces, all water is in opaque containers, and most importantly, they're not allowed to communicate among themselves. Though they do see each other during each morning's head count. Nevertheless, they all know no one would ever risk trying to leave without absolute certainty of success.

On a morning, they are provided the information that "At least one of you has green eyes." causing that on the hundredth morning after the sentence all the prisoners are gone.

The riddle and solution were available here: https://www.youtube.com/watch?v=98TQv5IAtY8

In their proof, they consider that having the information that "At least one of you has green eyes."in case of 2 green-eyes people causes them to leave on the second day. This same element being used to prove the same conclusion for 3 green-eyed people on the third day etc.. which leads to conclusion that on the 100th day, all the 100 green eyed people have left.

My question is:

Is it valid to consider "a group of 2 green eyed people would escape on the second day", since actually the sentence "At least one of you has green eyes.", was only pronounced in front of the group of 100 ?

Answer 1

Using the assumptions you have made, where the prisoners can neither see their own eye color nor anyone else’s, they would indeed be unable to escape.

However, I believe the original problem allowed the prisoners to see each other, and hence, each other’s eye color. With this added stipulation, anyone without green eyes might as well not be on the island. Assume only one person has green eyes. They see the other 99 blue-eyed people and, knowing that at least one has green eyes, it must be themselves.

If there are two with green eyes, they see one other person also with green eyes. Then on the second day, as no one escaped, they both realize their eye color and flee the following night.

Answer 2

I will present a solution to the problem, but first let us make a few assumptions. Assume it is common knowledge on the island that every islander is a perfect reasoner. I.e., if something can be proven, the islander themselves can prove it. Also assume the Guru makes the announcement on day $0$. The Guru never lies, and all the islanders know this. Additionally, if an islander discovers their eye color, they leave the next morning. So someone who discovers their eye color on day $i$ leaves the morning of day $i+1$. Additionally, let us take this as a more general problem:

Given the conditions you describe, but with $n$ people with green eyes on the island, on what day will the first person leave and on what day will the last person leave?. For simplicity, call such a scenario an $n$-green scenario. Observe that an $n$-green scenario is characterized by the fact that any green eyed sees only $n-1$ green eyed people. Note that the number of blue-eyed is irrelevant. Set it at your favorite number; mine is 6.

I will give a proof of the claim that an $n$-green scenario will terminate on day $n$, which I am using as short hand to mean the first and last green-eyed leaves on day $n$.

Now we proceed by induction. For the base case we only need to show that a $1$-green scenario terminates on day $1$. This is sort of trivial. On day $0$, the Guru announces they see a green-eyed. Since the green-eyed looks around and sees a sea of blue-eyed, they are forced to conclude that they themselves are green-eyed.

Okay, now for the inductive step. We may assume that we have a proof that an $n$-green scenario terminates on day $n$$^*$. Now we wish to prove that an $n+1$-green scenario terminates on day $n+1$. So assume that the Guru makes their announcement in front of $n+1$ green eyed people. Any given green-eyed, call them Bob, will look around and see only $n$ other green eyed people. For the sake of deduction, let Bob suppose that he himself is not green eyed. I.e., Bob thinks to himself, "if I'm not green eyed, what follows?" So Bob essentially assumes that the other green-eyed are in an $n$-green scenario. More explicitly, Bob will assume that any other green-eyed only sees $n-1$ green eyed. But since their is a proof that an $n$-green scenario terminates on day $n$, Bob will deduce that all the green eyed will leave on day $n$. But, since Bob's assumption is fallacious and each green-eyed sees $n$, not $n-1$ green-eyed, nobody leaves on day $n$. Bob then concludes that his assumption was false, so Bob concludes he must have green eyes. Thus, Bob will leave the next day, day $n+1$. But since our selection of $Bob$ was arbitrary, each and every green eyed will leave on day $n+1$.

This completes the induction. Thus, we have shown that an $n$-green scenario terminates on day $n$. Set $n=100$, et viola.

(*) this is, for our purposes, the same as assuming that the claim holds for $n$. This is just the type theoretic induction principle. Since the assumption is that the islanders are prefect reasoners, not omniscient, the computational perspective fits better within the framework.