A difficult puzzle about blue-eyed prisoners who are stuck on an island

The number of islanders in this case does not matter. To simplify the task, we will leave only two prisoners - conditional Andrey and Masha. Each of them sees a prisoner with blue eyes, but knows that this blue-eyed one may be the only one.

On the first night, they both wait. In the morning they see that their companion in misfortune is still here, and this gives them a hint. Andrei guesses that if his eyes were not blue, then Masha would have freed herself on the first night, realizing that she was the only blue-eyed prisoner. In the same way, Masha thinks about Andrey. They both understand the following: "If the other waits, my eyes can only be blue." The next morning they both leave the island.

Now let's consider the situation when there are three prisoners: Andrey, Masha and Boris. Each of them sees two captives with blue eyes, but is not sure how many blue-eyed ones see the others - two or only one. On the first night, the prisoners wait, but the morning does not yet bring clarity.

Boris reasons like this: “If my eyes are not blue, Andrei and Masha are only watching each other. That means they will leave the island together next night. " But on the third morning, Boris sees that they have not gone anywhere, and concludes that the prisoners are watching him. Andrey and Masha think in the same way, so on the third night they all leave the island.

This is called inductive logic. You can increase the number of prisoners, but the reasoning will remain true and will not depend on the number of islanders. That is, if there were four prisoners, they would leave the island on the fourth night, five on the fifth, one hundred on the hundredth.

The key to this puzzle is the concept of shared knowledge. This is the knowledge that each member of the group possesses, and each member of the group knows that all the other members of the group know, and everyone knows that everyone knows, that everyone knows, and so on ad infinitum.

Thus, it becomes clear that the new information was given to the islanders not by the girl's statement itself, but by the fact that they all heard it at the same time. Now all the prisoners not only know that at least one of them has blue eyes, but that everyone is watching all the blue-eyed, and that they all know it, and so on.

The only thing that each individual prisoner does not know is whether he belongs to the blue-eyed, which the others are watching. He will only know this when as many nights have passed as there are prisoners on the island. Of course, the girl could have saved the prisoners from 98 nights on the island, saying that at least 99 of them have blue eyes. But jokes with an unpredictable dictator are bad, and it's better not to risk it.

The puzzle is based on the TedEd video.