La problématique et les notions
Comment une stratégie décidée avant le jeu, sans aucune communication pendant les recherches, permet-elle de faire passer la probabilité que les cent prisonniers gagnent de presque zéro à plus de 31 % ?
DénombrementPermutationsProbabilitésÉvénements incompatiblesSommes et logarithme (ouverture)
Il s’agit d’une énigme mathématique fictive. Le calcul suppose une permutation choisie uniformément au hasard, des boîtes numérotées et un placement inchangé entre les passages.
Exposé complet — environ 10 minutes
Une trame orale à comprendre et à s’approprier. Les démonstrations sont proposées pour être présentées progressivement devant le jury.
00:00–01:00Un jeu où personne ne devrait gagner
Imaginez 100 prisonniers portant les numéros de 1 à 100. Devant eux, 100 boîtes fermées, elles aussi numérotées. Dans chaque boîte est caché un numéro de prisonnier, et chaque numéro apparaît exactement une fois. Chacun entre séparément et peut ouvrir au maximum 50 boîtes ; il doit découvrir son propre numéro. Les boîtes sont ensuite refermées sans déplacer les papiers. Les prisonniers peuvent convenir d’une méthode avant l’épreuve, mais ils n’échangent aucune information ensuite. Pour que le groupe réussisse, il faut que tous les cent découvrent leur numéro. À première vue, c’est absurde : comment espérer coordonner cent réussites sans communication ? Je vais montrer qu’une propriété des permutations change presque tout.
01:00–02:00Pourquoi le hasard naïf condamne le groupe
Si chaque prisonnier choisit indépendamment 50 boîtes au hasard, il possède exactement une chance sur deux de trouver son numéro : l’emplacement recherché est uniformément réparti parmi 100 boîtes. En supposant les choix de boîtes des prisonniers indépendants les uns des autres, la probabilité que tous gagnent est alors \[P_{\mathrm{naïf}}=\left(\frac12\right)^{100}\approx7{,}89\times10^{-31}.\] Cela représente une probabilité quasiment nulle. Les cinquante ouvertures autorisées semblent pourtant suffisantes pour chaque individu pris isolément. Le vrai obstacle est le mot « tous » : multiplier cent probabilités égales à un demi écrase la chance collective. Il nous faudrait donc une stratégie qui ne rende pas chaque réussite indépendante des autres, mais qui relie leurs destins.
02:00–03:00Une toute petite version avec dix prisonniers
Pour comprendre la stratégie, remplaçons 100 par 10, et 50 par 5. Supposons que la boîte 1 contienne le numéro 2 ; la boîte 2, le numéro 4 ; la boîte 4, le numéro 5 ; la boîte 5, le numéro 3 ; enfin la boîte 3, le numéro 1. On dessine la chaîne \[1\longrightarrow2\longrightarrow4\longrightarrow5\longrightarrow3\longrightarrow1.\] C’est un cycle de longueur cinq. Dans les autres boîtes, nous pouvons avoir un autre cycle, par exemple \[6\to7\to8\to10\to9\to6.\] Les dix numéros sont présents une fois chacun : cet arrangement est une permutation. Toute permutation se décompose en cycles distincts. C’est le premier outil caché de l’énigme : au lieu de choisir des boîtes au hasard, nous pouvons suivre une structure.
03:00–04:00La stratégie des cycles
Le prisonnier numéro 4 commence par ouvrir la boîte 4. S’il y trouve le numéro 5, il ouvre ensuite la boîte 5. Il y trouve 3, ouvre la boîte 3, puis la boîte 1, puis la boîte 2 : cette dernière contient 4. Il a retrouvé son numéro après cinq ouvertures. Chaque prisonnier applique la même consigne : ouvrir d’abord la boîte portant son propre numéro, puis ouvrir celle indiquée par le papier découvert. Dans notre exemple, tous les prisonniers suivent l’un des deux cycles de longueur cinq et réussissent. Un prisonnier ne parcourt pas toute la permutation ; il parcourt uniquement le cycle qui contient son numéro. La stratégie est donc réalisable individuellement, sans signal laissé aux suivants.
04:00–05:00La condition exacte de victoire
Qu’arrive-t-il si un cycle est plus long que le nombre d’ouvertures autorisées ? Le prisonnier placé sur ce cycle ne pourra pas en faire entièrement le tour : il ne trouvera pas son propre numéro dans les 50 premières boîtes ouvertes. À l’inverse, si chaque cycle a une longueur inférieure ou égale à 50, tous les prisonniers atteignent leur numéro. Nous avons alors une équivalence très précise : \[\boxed{\text{Victoire collective}\iff\text{aucun cycle de longueur }>50.}\] Le problème n’est plus de prévoir cent recherches séparées, mais de compter les permutations qui ne contiennent aucun cycle trop long. C’est là que le dénombrement de Terminale devient décisif.
05:00–06:00Compter les permutations avec un grand cycle
Fixons une longueur \(k\) strictement supérieure à 50. Combien de permutations des nombres de 1 à 100 contiennent un cycle de longueur \(k\) ? Il faut choisir les \(k\) numéros du cycle : \(\binom{100}{k}\) possibilités. On peut disposer ces numéros en un cycle de \((k-1)!\) façons, car les rotations d’une même liste décrivent le même cycle. Les \(100-k\) autres nombres peuvent être permutés de \((100-k)!\) façons. Ainsi le nombre total vaut \[\binom{100}{k}(k-1)!(100-k)!=\frac{100!}{k}.\] Comme il existe \(100!\) permutations équiprobables, la probabilité d’un cycle de longueur \(k\) est exactement \(1/k\). Une fraction étonnamment simple apparaît.
06:00–07:00Une somme de fractions qui vaut presque 69 %
Une permutation ne peut pas contenir deux cycles strictement plus longs que 50, car ils utiliseraient plus de 100 éléments au total. Les événements « il existe un cycle de longueur 51 », « de longueur 52 », jusqu’à « de longueur 100 » sont donc incompatibles. Nous pouvons additionner leurs probabilités : \[P(\text{échec})=\sum_{k=51}^{100}\frac1k.\] En prenant l’événement contraire, \[\boxed{P(\text{victoire})=1-\sum_{k=51}^{100}\frac1k\approx0{,}3118278.}\] Autrement dit, un peu plus de 31 % des placements possibles donnent la victoire au groupe. On ne l’a pas simplement constaté sur ordinateur : nous venons d’établir la formule exacte à partir d’un comptage.
07:00–08:00Pourquoi le logarithme apparaît en coulisses
Que se passe-t-il si l’énigme compte \(2n\) prisonniers, avec \(n\) ouvertures chacun ? Notre raisonnement se généralise : \[P_n=1-\sum_{k=n+1}^{2n}\frac1k.\] Les sommes de fractions \(1/k\) sont liées à la fonction logarithme. Intuitivement, pour de très grands \(n\), la somme se rapproche de l’aire sous la courbe \(y=1/x\) entre \(n\) et \(2n\) : \[\int_n^{2n}\frac{dx}{x}=\ln(2).\] La probabilité tend ainsi vers \(1-\ln2\approx30{,}69\%\). C’est une ouverture : le cœur de la preuve est combinatoire, tandis que les intégrales expliquent pourquoi le pourcentage reste proche de 31 % quand le nombre de prisonniers grandit.
08:00–09:00L’ordinateur vérifie, mais ne démontre pas
Nous pouvons programmer une simulation : mélanger les numéros dans les boîtes, décomposer le placement en cycles, vérifier si le plus long mesure au maximum 50, puis recommencer quelques milliers de fois. La fréquence des parties gagnées fluctue autour de 31,18 %. On peut aussi compter les victoires de cent chercheurs indépendants, qui seront pratiquement inexistantes. Attention à la différence entre une fréquence expérimentale et une probabilité théorique. Un simulateur peut confirmer numériquement notre résultat, mais le raisonnement avec les permutations et les événements incompatibles est ce qui nous donne la certitude mathématique. Voilà un joli dialogue entre combinatoire, probabilités et algorithmique.
09:00–10:00Ce que le paradoxe nous apprend vraiment
Le plus étonnant est que la stratégie des cycles ne transforme pas un prisonnier isolé en génie du hasard : chacun conserve une chance de réussite de 50 % avec cinquante ouvertures. Elle agit sur la dépendance entre les réussites. Dans une permutation formée de petits cycles, presque tous gagnent ensemble ; dans une permutation comportant un cycle de longueur 78, tous les prisonniers de ce cycle échouent. Nous avons remplacé cent petits hasards indépendants par un phénomène collectif lié à la structure de la permutation. C’est la conclusion que je défendrais : les mathématiques peuvent parfois améliorer spectaculairement une stratégie sans modifier la probabilité individuelle de réussite. Elles nous obligent à penser les liens entre événements, pas seulement les événements séparément.
