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. After much pressure from human rights groups, the dictator reluctantly agrees to let you visit the island and speak to the prisoners under the following conditions: you may only make one statement, and you cannot tell them any new information. What can you say to help free the prisoners without incurring the dictator's wrath? After thinking long and hard, you tell the crowd, "At least one of you has green eyes." The dictator is suspicious but reassures himself that your statement couldn't have changed anything. You leave, and life on the island seems to go on as before. But on the hundredth morning after your visit, all the prisoners are gone, each having asked to leave the previous night. So how did you outsmart the dictator? It might help to realize that the amount of prisoners is arbitrary. Let's simplify things by imagining just two, Adria and Bill. Each sees one person with green eyes, and for all they know, that could be the only one. For the first night, each stays put. But when they see each other still there in the morning, they gain new information. Adria realizes that if Bill had seen a non-green-eyed person next to him, he would have left the first night after concluding the statement could only refer to himself. Bill simultaneously realizes the same thing about Adria. The fact that the other person waited tells each prisoner his or her own eyes must be green. And on the second morning, they're both gone. Now imagine a third prisoner. Adria, Bill and Carl each see two green-eyed people, but aren't sure if each of the others is also seeing two green-eyed people, or just one. They wait out the first night as before, but the next morning, they still can't be sure. Carl thinks, "If I have non-green eyes, Adria and Bill were just watching each other, and will now both leave on the second night." But when he sees both of them the third morning, he realizes they must have been watching him, too. Adria and Bill have each been going through the same process, and they all leave on the third night. Using this sort of inductive reasoning, we can see that the pattern will repeat no matter how many prisoners you add. The key is the concept of common knowledge, coined by philosopher David Lewis. The new information was not contained in your statement itself, but in telling it to everyone simultaneously. Now, besides knowing at least one of them has green eyes, each prisoner also knows that everyone else is keeping track of all the green-eyed people they can see, and that each of them also knows this, and so on. What any given prisoner doesn't know is whether they themselves are one of the green-eyed people the others are keeping track of until as many nights have passed as the number of prisoners on the island. Of course, you could have spared the prisoners 98 days on the island by telling them at least 99 of you have green eyes, but when mad dictators are involved, you're best off with a good headstart.
Imaginez une île où 100 personnes, tous parfaits logiciens, sont emprisonnés par un dictateur fou. Il y a pas d'échappatoire, sauf par le biais d'une règle étrange. La nuit, tout détenu peut approcher les gardes et demander à partir. S'il a les yeux verts, il sera libéré. Sinon, il sera jeté dans le volcan. En l'occurrence, les 100 prisonniers ont tous les yeux verts, mais ils vivent ici depuis leur naissance, et le dictateur s'est assuré qu'ils ne puissent pas apprendre la couleur de leurs propres yeux. Il n'y a pas de surfaces réfléchissantes, toute l'eau se trouve dans des contenants opaques, et surtout, ils ne sont pas autorisés à communiquer entre eux. Cependant ils se voient à l'appel chaque matin. Néanmoins, ils savent tous que personne ne prendrait le risque de partir sans une garantie absolue de succès. Après une énorme campagne des groupes de défense des droits de l'homme le dictateur accepte à contrecœur de vous laisser visiter l'île et de parler aux prisonniers sous les conditions suivantes: vous ne pouvez faire qu'une seule déclaration, et vous ne pouvez leur communiquer aucune nouvelle information. Que pouvez-vous dire pour aider à libérer les prisonniers sans encourir la colère du dictateur ? Après avoir longuement réfléchi, vous déclarez à la foule: « Au moins l'un d'entre vous a des yeux verts.» Le dictateur est méfiant mais se rassure, en se disant que votre déclaration ne pouvait pas avoir changé grand chose. Vous quittez, et la vie sur l'île semble reprendre son cours.. Mais le matin du centième jour après votre visite, tous les prisonniers sont partis, chacun ayant demandé de partir la nuit précédente. Alors, comment vous êtes vous joué du dictateur ? Ça pourrait vous aider de réaliser que le nombre des prisonniers est arbitraire. Simplifions les choses avec deux prisonniers, Adria et Bill. Chacun voit une personne avec les yeux verts, et pour tout ce qu'ils en savent, cette personne pourrait être la seule. La première nuit, chacun reste en place. Mais quand ils voient l'autre toujours présent lendemain, ils acquièrent de nouvelles informations. Adria réalise que si Bill avait vu une personne aux yeux non-verts à ses côtés il serait parti la première nuit après avoir conclu que la déclaration ne pouvait se référer qu'à lui-même. Bill réalise simultanément la même chose à propos d'Adria. Le fait que l'autre personne ait attendu indique à chaque prisonnier que ses propres yeux doivent être verts. Et le matin du deuxième jour, ils sont tous les deux partis. Maintenant, imaginez un troisième prisonnier. Adria, Bill et Carl voient chacun deux personnes aux yeux verts, mais ignorent si les deux autres voient aussi deux personnes aux yeux verts, ou simplement une seule. Ils attendent la fin de la première nuit comme avant, mais le lendemain matin, ils ne peuvent toujours pas être sûrs. Carl pense: "si je n'ai pas les yeux verts, Adria et Bill se regardaient l'un l'autre et vont donc partir tous les deux la deuxième nuit." Mais quand il les revoit tous les deux le troisième matin, il réalise qu'ils ont du le regarder aussi. Adria, Bill et Carl ont tous mené le même raisonnement, et ils partent la troisième nuit. En utilisant ce genre de raisonnement inductif, nous pouvons voir que le motif se répète peu importe le nombre de prisonniers. La clé est le concept de la connaissance commune, inventé par le philosophe David Lewis. La nouvelle information ne résidait pas dans votre déclaration elle-même, mais dans le fait de la dire à tout le monde simultanément. Maintenant, en plus de savoir qu'au moins l'un d'entre eux a les yeux verts, chaque prisonnier sait aussi que tout le monde suit à la trace toutes les personnes aux yeux verts qu'il peut voir, et que chacun d'eux sait aussi cela, et ainsi de suite. Ce qu'un prisonnier lambda ne sait pas c'est si il fait lui-même parti du groupe des prisonniers aux yeux verts que les autres observent jusqu'à ce que soient passées autant de nuits qu'il y a de prisonniers sur l'île. Bien sûr, vous auriez pu épargner aux prisonniers 98 jours sur l'île en leur disant: « Au moins 99 d'entre vous ont les yeux verts »