Problème des 100 prisonniers

Le problème des 100 prisonniers a différentes interprétations dans la littérature. La version décrite principalement dans cet article est celle de Philippe Flajolet et Robert Sedgewick^[1]:

« Le directeur d'une prison offre une dernière chance à 100 condamnés à mort, numérotés de 1 à 100. Une pièce contient une armoire à 100 tiroirs. Le directeur place au hasard le numéro d'un prisonnier dans chaque tiroir fermé. Les prisonniers entrent dans la pièce, l'un après l'autre. Chaque prisonnier peut ouvrir et consulter 50 tiroirs dans n'importe quel ordre. Les tiroirs sont ensuite refermés. Si, lors de cette fouille, chaque prisonnier trouve son numéro dans l'un des tiroirs, tous les prisonniers sont graciés. Si même un prisonnier ne trouve pas son numéro, tous les prisonniers meurent. Avant que le premier prisonnier n'entre dans la pièce, les prisonniers peuvent discuter de la stratégie à adopter, mais ne peuvent plus communiquer une fois que le premier prisonnier est entré pour consulter les tiroirs. Quelle est la meilleure stratégie pour les prisonniers ? »

Si chaque détenu choisit 50 tiroirs indépendamment et au hasard, la probabilité qu'un seul détenu trouve son numéro est de 50 %. La probabilité que tous les détenus trouvent leur numéro est alors le produit des probabilités simples, soit (1/2)¹⁰⁰ ≈ 0,0000000000000000000000000000008, un nombre extrêmement faible, laissant supposer que les prisonniers sont condamnés avec une quasi-certitude.

Après étude plus approfondie, il existe une stratégie qui assure la survie de tous les prisonniers avec une bien meilleure probabilité, supérieure à 30 %. En effet, il faut prendre en compte le fait que les prisonniers n'ont pas à décider à l'avance quels tiroirs ouvrir, ni les choisir complètement au hasard. Chaque prisonnier peut utiliser les informations obtenues grâce au contenu de chaque tiroir déjà ouvert pour décider lequel ouvrir ensuite. Autre observation importante : de cette manière, la réussite d'un prisonnier n'est pas indépendante de celle des autres, car elle dépend de la répartition des nombres^[2].

Pour décrire la stratégie, on suppose que comme les prisonniers, les tiroirs sont également numérotés de 1 à 100 ; par exemple, rangée par rangée, en commençant par le tiroir en haut à gauche. La stratégie est désormais la suivante^[3]:

1. Chaque prisonnier ouvre d’abord le tiroir portant son propre numéro.
2. Si ce tiroir contient son numéro, il a fini avec succès.
3. Sinon, le tiroir contient le numéro d'un autre prisonnier, et il ouvre ensuite le tiroir étiqueté avec ce numéro.
4. Chaque prisonnier répète les étapes 2 et 3 jusqu'à ce qu'il trouve son propre numéro, ou échoue parce que le numéro ne se trouve pas dans les cinquante premiers tiroirs ouverts.

Si le prisonnier pouvait continuer ainsi indéfiniment, il reviendrait inévitablement au tiroir de départ, complétant ainsi un cycle de la permutation. En commençant par son propre numéro, le prisonnier s'assure d'être sur le cycle spécifique de tiroirs contenant son numéro. La seule question devient alors de savoir si un des cycles de la permutation dépasse cinquante tiroirs ; ce cycle serait unique, puisqu'un seul peut représenter plus de la moitié du total des tiroirs.

L'intérêt de cette stratégie est illustré par l'exemple suivant, avec huit détenus et des tiroirs, où chaque détenu peut donc ouvrir quatre tiroirs. Le directeur de la prison a réparti les numéros des détenus dans les tiroirs de la manière suivante :

Numéro du tiroir	1	2	3	4	5	6	7	8
Numéro du prisonnier	7	4	6	8	1	3	5	2

Les prisonniers agissent désormais comme suit :

• Le prisonnier 1 ouvre d'abord le tiroir 1 et trouve le numéro 7. Ensuite, il ouvre le tiroir 7 et trouve le numéro 5. Ensuite, il ouvre le tiroir 5, où il trouve son propre numéro et réussit.
• Le prisonnier 2 ouvre les tiroirs 2, 4 et 8 dans cet ordre. Dans le dernier tiroir, il trouve son propre numéro, le 2.
• Le prisonnier 3 ouvre les tiroirs 3 et 6, où il trouve son propre numéro.
• Le prisonnier 4 ouvre les tiroirs 4, 8 et 2, où il trouve son propre numéro. Il s'agit du même cycle rencontré par le prisonnier 2 et que retrouvera le prisonnier 8. Chacun de ces prisonniers trouvera son propre numéro dans le troisième tiroir ouvert.
• Les prisonniers 5 à 7 trouveront également chacun leur numéro de manière similaire.

Dans ce cas, tous les détenus trouvent leur numéro. Cependant, ce n'est pas toujours le cas. Par exemple, la seule modification des numéros qui échange les contenus des tiroirs 5 et 8 entraînerait l'échec du détenu 1 après avoir ouvert les tiroirs 1, 7, 5 et 2 (et ne trouvant pas son propre numéro).

Numéro du tiroir	1	2	3	4	5	6	7	8
Numéro du prisonnier	7	4	6	8	2	3	5	1

Et dans l'arrangement suivant, le prisonnier 1 ouvre les tiroirs 1, 3, 7 et 4, et à ce moment-là, il doit s'arrêter sans succès :

Numéro du tiroir	1	2	3	4	5	6	7	8
Numéro du prisonnier	3	1	7	5	8	6	4	2

En effet, tous les prisonniers sauf le numéro 6 (qui réussissent directement) échouent.

Représentations des graphes des permutations (1 7 5)(2 4 8)(3 6) et (1 3 7 4 5 8 2)(6)

L'attribution des numéros de détenus aux tiroirs par le directeur de la prison peut être représentée mathématiquement comme une permutation des nombres de 1 à 100, soit une application bijective de l'ensemble des nombres naturels de 1 à 100 sur lui-même. Une suite de nombres qui, après application répétée de la permutation, revient au premier nombre est appelée un cycle de permutation. Chaque permutation peut être décomposée en cycles disjoints, c'est-à-dire sans éléments communs. La permutation du premier exemple ci-dessus peut s'écrire en notation cyclique comme suit :

${\displaystyle (1~7~5)(2~4~8)(3~6)}$

et peut donc se décomposer en deux cycles de longueur 3 et d'un cycle de longueur 2. La permutation du troisième exemple est en conséquence

${\displaystyle (1~3~7~4~5~8~2)(6)}$

et se compose d'un cycle de longueur 7 et d'un cycle de longueur 1. La notation du cycle n'est pas unique puisqu'un cycle de longueur ${\displaystyle l}$ peut être écrit de ${\displaystyle l}$ différentes manières selon le numéro de départ du cycle. Lors de l'ouverture des tiroirs avec la stratégie ci-dessus, chaque prisonnier suit un seul cycle qui se termine toujours par son propre numéro. Dans le cas de huit prisonniers, cette stratégie de suivi de cycle est réussie si et seulement si la longueur du cycle le plus long de la permutation est au plus égale à 4. Si une permutation contient un cycle de longueur 5 ou plus, aucun prisonnier dont les numéros se trouvent dans un tel cycle n'atteint son propre numéro après quatre étapes.

Dans le problème initial, les 100 prisonniers réussissent si le cycle le plus long de la permutation a une longueur d'au plus 50. Leur probabilité de survie est donc égale à la probabilité qu'une permutation aléatoire des nombres 1 à 100 ne contienne aucun cycle de longueur supérieure à 50. Cette probabilité est calculée ainsi.

Une permutation des nombres de 1 à 100 peut contenir au plus un cycle de longueur ${\displaystyle l>50}$ . Il y a exactement ${\displaystyle {\tbinom {100}{l}}}$ façons de choisir les nombres d'un tel cycle (puisqu'il s'agit alors d'une combinaison). Au sein de ce cycle, ces nombres peuvent être répartis de ${\displaystyle (l-1)!}$ façons puisqu'il y a ${\displaystyle l}$ permutations pour représenter des cycles distincts de longueur ${\displaystyle l}$ en raison de la symétrie cyclique. Les nombres restants peuvent être disposés en ${\displaystyle (100-l)!}$ façons. Par conséquent, le nombre de permutations des nombres de 1 à 100 avec un cycle de longueur ${\displaystyle l>50}$ est égal à

${\displaystyle {\binom {100}{l}}\cdot (l-1)!\cdot (100-l)!={\frac {100!}{l}}.}$

La probabilité qu'une permutation aléatoire (uniformément distribuée) ne contienne aucun cycle de longueur supérieure à 50 est calculée avec la formule des événements simples et la formule pour des événements complémentaires ainsi données par

${\displaystyle 1-{\frac {1}{100!}}\left({\frac {100!}{51}}+\ldots +{\frac {100!}{100}}\right)=1-\left({\frac {1}{51}}+\ldots +{\frac {1}{100}}\right)=1-(H_{100}-H_{50})\approx 0,31183,}$

où ${\displaystyle H_{n}}$ est le ${\displaystyle n}$ -ième nombre harmonique . Par conséquent, en utilisant la stratégie du suivi du cycle, les prisonniers survivent dans un peu plus de 31 % des cas^[3].

Dans le cas général où on considère un nombre de ${\displaystyle 2n}$ prisonniers, avec ${\displaystyle n}$ est un nombre naturel quelconque, la probabilité de survie des prisonniers avec la stratégie de suivi du cycle est donnée par

${\displaystyle 1-(H_{2n}-H_{n})=1-(H_{2n}-\ln 2n)+(H_{n}-\ln n)-\ln 2.}$

Avec la constante d'Euler–Mascheroni ${\displaystyle \gamma }$, définie telle que :

${\displaystyle \lim _{n\to \infty }(H_{n}-\ln n)=\gamma }$

on trouve une probabilité de survie asymptotique de

${\displaystyle \lim _{n\to \infty }(1-H_{2n}+H_{n})=1-\gamma +\gamma -\ln 2=1-\ln 2\approx 0,30685.}$

Étant donné que la suite des probabilités est strictement décroissante, les prisonniers survivent avec la stratégie de suivi du cycle dans plus de 30 % des cas, et ceci indépendamment du nombre de prisonniers^[3].

En 2006, Eugene Curtin et Max Warshauer ont démontré l'optimalité de la stratégie de suivi de cycle. Cette démonstration repose sur une équivalence avec un problème connexe dans lequel tous les prisonniers sont autorisés à être présents dans la pièce et à observer l'ouverture des tiroirs. Mathématiquement, cette équivalence repose sur le lemme de transition de Foata, une bijection entre la notation cyclique (canonique) et la notation unilinéaire des permutations. Dans le second problème, la probabilité de survie est indépendante de la stratégie choisie et égale à celle du problème initial avec la stratégie de suivi de cycle. Puisqu'une stratégie arbitraire pour le problème initial peut également être appliquée au second problème, mais ne permet pas d'obtenir une probabilité de survie plus élevée, la stratégie de suivi de cycle est nécessairement la stratégie optimale^[2].

Le problème des 100 prisonniers a été étudié pour la première fois en 2003 par Anna Gál et Peter Bro Miltersen dans les actes du 30e International Colloquium on Automata, Languages and Programming (ICALP^[4]). Dans leur version, le joueur A (le directeur de la prison) colorie aléatoirement des bandes de papier avec les noms des joueurs de l'équipe B (les prisonniers) en rouge ou en bleu et place chaque bande dans une boîte différente. Certaines boîtes peuvent être vides (voir ci-dessous ). Chaque joueur de l'équipe B doit deviner sa couleur après avoir ouvert la moitié des boîtes pour que son équipe gagne^[4]. Initialement, Gál et Miltersen supposaient que la probabilité de gagner tendait rapidement vers zéro avec l'augmentation du nombre de joueurs. Cependant, Sven Skyum, un collègue de l'Université d'Aarhus, a attiré son attention sur la stratégie de suivi de cycle pour le cas de ce problème où il n'y a pas de boîtes vides. La recherche de cette stratégie a été laissée en exercice dans la publication. L'article a reçu le prix du meilleur article^[2].

Au printemps 2004, le problème est apparu dans la colonne des puzzles de Joe Buhler et Elwyn Berlekamp dans la revue trimestrielle The Emissary du Mathematical Sciences Research Institute . Les auteurs ont alors remplacé les boîtes par des ROMs et les bandes de papier de couleur par des nombres signés . Ils ont constaté que la probabilité de gagner peut également être augmentée lorsque les membres de l'équipe ne trouvent pas leurs propres nombres. Si la réponse donnée est le produit de tous les signes trouvés et si la longueur du cycle le plus long est la moitié du nombre pair de joueurs plus un, alors les membres de l'équipe participant à ce cycle ont tous une réponse fausse ou correcte. Même si cette extension de la stratégie offre une amélioration visible pour un petit nombre de joueurs, elle devient négligeable lorsque le nombre de joueurs augmente^[5].

Au cours des années suivantes, le problème est entré dans la littérature mathématique, où il a été façonné de différentes manières, par exemple avec des cartes sur une table^[6] ou des portefeuilles dans des casiers (sous le nom de casier puzzle^[2]). Sous la forme d'un problème de prisonnier, il a été posé en 2006 par Christoph Pöppe dans la revue Spektrum der Wissenschaft et par Peter Winkler dans le College Mathematics Journal^[7],[8]. Avec de légères modifications, cette forme a été adoptée par Philippe Flajolet, Robert Sedgewick et Richard P. Stanley dans leurs manuels de combinatoire^[1],[3]. Le problème, ou énigme, ainsi qu'une explication détaillée de la solution, ont été présentés par la chaîne Veritasium dans une [vidéo] « video », sur YouTube de 2023.

Dans un premier temps, Gál et Miltersen ont étudié dans leur article le cas où le nombre de boîtes est deux fois supérieur au nombre de membres de l'équipe, tandis que la moitié des cases sont vides. Ce problème est plus complexe, car les cases vides ne mènent à rien et la stratégie du cycle de suivi est alors inapplicable. La question de savoir si, dans ce cas, la probabilité de gagner tend vers zéro lorsque le nombre de membres de l'équipe augmente reste ouverte^[4].

En 2005, Navin Goyal et Michael Saks ont développé pour l'équipe B une stratégie basée sur la stratégie de suivi de cycle pour un problème plus général où la proportion de boîtes vides ainsi que la proportion de boîtes que chaque membre de l'équipe est autorisé à ouvrir sont variables. La probabilité de gagner tend toujours vers zéro dans ce cas, mais plus lentement que ne le suggèrent Gál et Miltersen. Si le nombre de membres de l'équipe et la proportion de boîtes ouvertes sont fixes, la probabilité de gagner reste strictement supérieure à zéro lorsque des boîtes vides sont ajoutées^[9].

Si le directeur de la prison n'a pas à distribuer les numéros aléatoirement dans les tiroirs, mais qu'il réalise que les détenus pourraient appliquer la stratégie de suivi de cycle et devine la numérotation des cases qu'ils utiliseront (comme les numéros indiqués sur les cases), il peut déjouer cette stratégie. Pour ce faire, il doit simplement s'assurer que l'attribution des numéros des détenus aux tiroirs constitue une permutation dont la durée du cycle est supérieure à 50. Les détenus peuvent à leur tour contrer ce problème en convenant entre eux d'une numérotation aléatoire spécifique des tiroirs, à condition que le directeur ne l'entende pas ou ne prenne pas la peine de répondre en remplaçant les numéros dans les cases avant l'entrée des détenus^[10].

Si un prisonnier entre en premier dans la pièce, inspecte toutes les boîtes, puis échange le contenu de deux boîtes, tous les prisonniers survivront. En effet, tout cycle d'une durée supérieure à 50 peut être interrompu, garantissant ainsi que tous les cycles ont une durée maximale de 50.

Pour un nombre suffisamment important de prisonniers ${\displaystyle N}$, ils peuvent assurer leur évasion en ouvrant bien moins de la moitié des tiroirs. Plus précisément, chaque prisonnier ne doit ouvrir que ${\displaystyle O\left(N{\frac {\ln \ln N}{\ln N}}\right)}$ tiroirs pour sécuriser l'évasion de tous les prisonniers.

Dans la variante où tout prisonnier qui trouve son numéro est libre, la probabilité attendue de survie d'un individu étant donné une permutation aléatoire est la suivante :

• Sans stratégie : ${\displaystyle {\frac {1}{2}}}$
• Avec la stratégie pour le problème d'origine : ${\displaystyle (1-\ln(2))\cdot 1+\sum _{k=\lfloor n/2\rfloor +1}^{N}{\frac {1}{k}}\left(1-{\frac {k}{n}}\right)=1-\ln(2)+\sum _{\lfloor n/2\rfloor +1}^{N}{\frac {1}{k}}-\sum _{k=\lfloor n/2\rfloor +1}^{N}{\frac {1}{n}}=1-\ln(2)+\ln(2)-{\frac {1}{2}}={\frac {1}{2}}}$

Il est à noter que, bien qu'on obtienne des espérances égales, elles proviennent de lois très différentes. Avec la deuxième stratégie, certains prisonniers sont simplement destinés à mourir ou à vivre selon une permutation particulière, tandis qu'avec la première stratégie (c'est-à-dire sans stratégie), il y a « véritablement » une chance sur deux pour chaque permutation.

En 2009, Adam S. Landsberg a proposé la variante plus simple suivante du problème des 100 prisonniers qui est basée sur le célèbre problème de Monty Hall :

« Derrière trois portes closes, une voiture, ses clés et une chèvre sont distribués aléatoirement. Deux joueurs jouent : le premier doit retrouver la voiture, le second les clés. Si les deux joueurs réussissent, ils peuvent conduire la voiture jusque chez eux. Le premier joueur entre dans la pièce et peut ouvrir deux des trois portes consécutivement. S'il réussit, les portes se referment et le second joueur entre dans la pièce. Ce dernier peut également ouvrir deux des trois portes, mais il ne peut communiquer avec le premier joueur sous aucune forme. Quelle est la probabilité de gagner si les deux joueurs agissent de manière optimale ? »

Si les joueurs sélectionnent leurs portes au hasard, la probabilité de gagner n'est que de 4/9 (environ 44 %). Une stratégie optimale associe le premier joueur et la voiture au numéro 1, le deuxième joueur et les clés au numéro 2, et la chèvre au numéro 3. L'algorithme de base est donc :

• Le joueur 1 ouvre d'abord la porte 1. Si la voiture est derrière la porte, le joueur a réussi. Si les clés étaient derrière la porte, le joueur ouvre ensuite la porte 2 ; si, au contraire, la chèvre était derrière la porte, le joueur ouvre ensuite la porte 3.
• Le joueur 2 ouvre d'abord la porte 2. Si les clés sont derrière la porte, le joueur a réussi. Si la voiture était derrière la porte, le joueur ouvre ensuite la porte 1 ; si la chèvre était derrière la porte, le joueur ouvre ensuite la porte 3.

Dans les six distributions possibles de voiture, clés et chèvre derrière les trois portes, les joueurs ouvrent les portes suivantes (dans les cases vertes, le joueur a réussi) :

Le succès de la stratégie repose sur l'établissement d'une corrélation entre les succès et les échecs des deux joueurs. Ici, la probabilité de gain est de 2/3, ce qui est optimal puisque le premier joueur ne peut pas avoir une probabilité de gagner supérieure à cela. Dans une autre variante, trois prix sont cachés derrière les trois portes et trois joueurs doivent trouver indépendamment les prix qui leur sont attribués en deux essais. Dans ce cas, la probabilité de gagner est également de 2/3 lorsque la stratégie optimale est employée.

Au lieu de devoir trouver leur numéro lors des 50 premiers essais, le test pourrait consister à trouver le numéro lors des 50 essais impairs : 1, 3, ..., 97, 99. Chaque détenu a 50 % de chances de trouver son propre numéro lors d'un essai impair. La stratégie principale fonctionnera pour tous les détenus si la permutation des détenus ne contient que des cycles de longueur impaire. Pour 100 détenus, la probabilité que tous réussissent avec la stratégie principale est d'environ 7,9589 %, ce qui est nettement supérieur à la probabilité (1/2)¹⁰⁰ qui serait obtenue si chaque détenu ouvrait les tiroirs indépendamment au hasard.