100 blue eyed islanders - how to prove the waiting time cannot be less than 100?

Question

Here is the famous blue eyed islanders puzzle and here is the traditional solution. It has been also discussed here in StackExchange.

What I don't understand is how do we know that for $n$ blu-eyed islanders it is impossible that any islander will leave the island before $n$ days. While it seems obvious and intuitive when we consider $n=2$ or even $n=3$ we can't rely on intuition for $n=100$. The inductive proof we are given assumes that we are in day $n-1$ with no islander leaving the island and go to the conclusion that the $n$ blue eyed islanders will all leave on day $n$. But what if there is a number $k$ such that everyone leaves on day $k-2$ or $k-1$? How can we exclude this possibility?

Answer 1

The islanders are logicians just like we are. So when the Oracle comes through, each of the blue-eyed islanders roll their eyes and say "Great, it's the blue-eyed islanders puzzle once again except in real life."

Excuse me, I mean each of the blue-eyed islanders thinks "I see 99 blue-eyed islanders. I know that they can all reason as well as I do, so they will find out that they have blue eyes and leave in 99 days." So nobody will leave for 99 days because nobody has a logical reason to. Only on the final day will the reasoners say "Why haven't they gone? Ah, it must be because they are also seeing 99 blue-eyed islanders, so I must leave with them tonight."

Answer 2

Notice that the inductive step, like any inductive proof, assumes that 'The statement holds for $k$' .... i.e. (in this case) that with $k$ blue-eyed islanders, none of them leaves before day $k$, but they do all leave on day $k$. So, at this point we indeed don't know that it is true, but rather we just assume that it is true, and see what follows. Well, what follows is that with $k+1$ blue-eyed islanders, they all leave on day $k+1$. That is, we can show that if $k$ blue-eyed islanders all leave on day $k$, then $k+1$ blue-eyed islanders, they all leave on day $k+1$. Now, that implication by itself does not mean that for any $k$: $k$ blue-eyed islanders leave on day $k$. However, once we prove the base case of the inductive proof ... we know that for any $k$, all blue-eyed islanders leave exactly on day $k$, and not before.

OK, but as you ask as a follow-up question: why exactly does the inductive step hold? That is, even if we assume that $k$ blue-eyed islanders all leave exactly on day $k$, why would it folow that with $k+1$ blue-eyed islanders, they all leave on day $k+1$?

Good question, and as Henning points out in the comments, the induction is actually quite subtle. Maybe the most intuitive way to think about what is going on is that each day that passes, a little bit more common knowledge is obtained: by induction you can show that on at the start of day $k$ (and not before), it is common knowledge that there are at least $k$ blue-eyed islanders.

To explain what I mean by this: take the simpler example of having only $3$ blue-eyed islanders $A$, $B$, and $C$. Obviously, they all see at least $2$ other blue-eyed islanders, and so they all know that there is at least $1$ blue-eyed islander, before they are being told this. In fact, since they see at least $2$ they all know that everyone else sees at least $1$, and so they all know that they all know that there is at least $1$ blue-eyed islander.

However, on the first day, $A$ does not know that $B$ knows that $C$ knows that there is at least $1$ blue-eyed islander: any nesting of "knowing that" like that is more than $2$ levels deep is not true. And it is this nesting that the islanders require in order to perform their logic and realize that they have blue eyes. Indeed, when the nesting can go arbitrarily many levels deep, we speak of 'common knowledge'. This is what is lacking before the islanders are told that there is at least $1$ blue-eyed islander: before that is pointed out, it is not common knowledge that there is at least $1$ blue-eyed islanders, even though individually, they all know that this is true, and even know of each other that they know it is true.

However, when they are told that there is at least $1$ blue-eyed islander, it does become common knowledge: Now, you can go any number of levels deep, and end with "that there is at least $1$ blue-eyed islander"", and it will be true, exactly because this statement was made open to the public. Indeed, this is the very importance of the islanders being told, in public, that there is at least $1$ blue-eyed islander: they all already knew this, and they even already knew that they knew this, but it wasn't common knowledge until it was pointed out in public.

OK, so after they are told this, it has become common knowledge. However, on day $1$ it is still not common knowledge that there are at least $2$ blue-eyed islanders. Again, they all know that there are at least $2$, but it is not common knowledge. Indeed, $A$ does not know that $B$ knows that there are at least $2$.

However, when the next day comes and passes, and it is revealed that no one was able to figure out that they had blue eyes, it has become clear that there must be at least $2$ blue-eyed islanders, since if there was only $1$, then that $1$ would have left. And, since it is common knowledge that they are all perfect logicians (this is actually an important assumption that is often not explicitly pointed out in the typical statements of this puzzle ... saying that they are all perfect logicians is not enough: they need to know this of each other, and to sufficient depth ... again, basically it needs to be common knowledge), it has now become common knowledge that there at least $2$ blue-eyed islanders ... something that was not true on day $1$.

... and so on! Indeed, this is where the induction comes in: you can show that on day $k$, it has become common knowledge that there are at least $k$ blue-eyed islanders, and not before that day. And, to perform their logic that allows the $k$ blue-eyed islanders to conclude that they must have blue eyes, it must be common knowledge (you'd need, as Henning states, a logic that deals with these "know that nestings"). Going back to the example: On the start of day $2$, it is common knowledge to the $3$ blue-eyed islanders that there are at least $2$ blue-eyed islanders, but not that there are at least $3$ (that is, they still do not know whether they have blue eyes themselves). So, on day 2, they still do not leave. However, upon seeing that, it now has become common knowledge that there are at least $3$ blue-eyed islanders, or else the $2$ would have left on day $2$. And, obviously, since they only see $2$, they now know that they must be the third, and hence they all leave on day $3$.

OK, but how exactly is it that they don't leave before day $3$? For this, you really need to go into the logic that the islanders employ to figure out whether they have blue eyes or not. And again, let's stick with the simpler example of there being $3$ blue-eyed islanders. OK, so at the start of day $1$, after they are being told there is at least $1$ blue-eyed islander, $A$, $B$, and $C$ look around, and see $2$ other blue-eyed islanders. Now, they know that there is at least $1$ blue-eyed islander, and in fact this fact is common knowledge ... but there is otherwise nothing that would tell them that they have blue eyes themselves. OK, so day $1$ passes without any of them leaving. No real surprise there, I think.

OK, but now it is the start of day $2$. Now it is a lot more interesting. They know no one left, so maybe that allow them to infer that they do have blue eyes? Well, let's see. $A$ thinks to themselves: "Hmmm. I see that $B$ and $C$ have blue eyes. Why didnt they leave? Is it because I have blue eyes? That is, would they have left if I did not have blue eyes? Well, let's think. If I didn't have blue eyes, then on day $1$ $B$ and $C$ would each see $1$ other blue-eyed islander, and therefore they would have thought to themselves: "Hmmm. If I dont have blue eyes', then that other person is the only person with blue eyes, and so that person will leave today, seeing as that person would see no one with blue eyes, but knows there is at least one. So, let me see what happens to day: if that person leaves, then I'll know I didn;t have blue eyes. But if that person doesn;t leave, then I do have blue eyes". But of course, both $B$ and $C$ reasoned that way. That is, they both will be waiting out today, seeing what the other person does. In other words, even if I ($A$) dont have 'blue eyes, nothing will happen on day $1$. And, if I do have blue eyes, then certainly nothing would happen on day $1$ either, because now the others would see at least two people with blue eyes, and hence the fact that there is at least one person with blue eyes tells them absolutely nothing about the color of their own eyes. So, the fact that nothing happened on day $1$ is compatible with me having blue eyes or not. So, I don;t know whether I have blue eyes or not". And so: $A$ (and by symmetry, $B$ and $C$), will do nothing on day $2$ either.

OK, so that's just a concrete example showing that with $3$ islanders, nothing will happen on days $1$ and $2$.

More formally, though, the induction you have to (and can) prove is that the common knowledge that there are at least $k$ blue-eyed islanders is only obtained at the start of day $k$, and not before. And, you gop through the above kind of reasoning that without that common knowledge, any blue-eyed islander can show that the lack of any action on the preceding days is compatible with them having blue eyes or not, meaning that without the common knowledge, they still don;t know.