vignette|Chaque prisonnier doit trouver son propre numéro dans l'un des , mais ne peut en ouvrir qu'au plus la moitié. Le problème des 100 prisonniers est un problème mathématique de probabilités et de combinatoire.
Dans l'énoncé de ce problème, cent prisonniers numérotés doivent trouver leur propre numéro dans l'un des 100 tiroirs pour survivre. Les règles stipulent que chaque prisonnier ne peut pas ouvrir plus de la moitié des tiroirs et ne peut plus communiquer avec les autres prisonniers après que le premier prisonnier est entré pour y jeter un coup d'œil. Si les 100 prisonniers parviennent tous à trouver leur propre numéro, ils survivent tous ; en revanche, si un seul prisonnier ne le trouve pas, ils meurent tous. À première vue, la situation semble désespérée, mais une stratégie astucieuse offre aux prisonniers une chance réaliste de survie.
La première version du problème a été énoncée par Anna Gál et Peter Bro Miltersen en 2003.
Problème 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:
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 , un nombre extrêmement faible, laissant supposer que les prisonniers sont condamnés avec une quasi-certitude.
Solution
Stratégie 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.
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:
Chaque prisonnier ouvre d’abord le tiroir portant son propre numéro. Si ce tiroir contient son numéro, il a fini avec succès. Sinon, le tiroir contient le numéro d'un autre prisonnier, et il ouvre ensuite le tiroir étiqueté avec ce numéro. 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.
Exemples 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 : {| class="wikitable" style="text-align:center" |- ! 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). {| class="wikitable" style="text-align:center" |- ! 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 : {| class="wikitable" style="text-align:center" |- ! 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ésentation par permutation
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 :
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
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 peut être écrit de 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.
Probabilité de réussite vignette|Distribution de probabilité de la longueur du cycle le plus long d'une permutation aléatoire des nombres de 1 à 100. La zone verte correspond à la probabilité de survie des prisonniers. 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 . Il y a exactement 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 façons puisqu'il y a permutations pour représenter des cycles distincts de longueur en raison de la symétrie cyclique. Les nombres restants peuvent être disposés en façons. Par conséquent, le nombre de permutations des nombres de 1 à 100 avec un cycle de longueur est égal à
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
où est le -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.
Asymptote vignette|Les nombres harmoniques sont donnés approximativement par l'aire sous l'hyperbole et peuvent donc être approchés par un logarithme. Dans le cas général où on considère un nombre de prisonniers, avec est un nombre naturel quelconque, la probabilité de survie des prisonniers avec la stratégie de suivi du cycle est donnée par
Avec la constante d'Euler–Mascheroni , définie telle que :
on trouve une probabilité de survie asymptotique de
É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.
Optimalité 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.
Histoire 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.). 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. 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.
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.