Les prisonniers et l’ampoule [Solution]

Nos pauvres prisonniers peuvent-ils espérer s’en sortir (vivants si possible) ? L’énoncé du problème ne mentionnait pas leur espérance de vie, ainsi on ignorera la vraisemblabilité d’une réponse qui leur ferait pourtant attendre des centaines d’années (voire bien plus). Ici nos prisonniers sont immortels (sauf quand ils sont exécutés :p), ces chanceux !

Parlons déjà d’une solution qui n’en est pas une, qui est celle d’utiliser les probabilités.

Le gardien choisissant au hasard, de façon uniforme, nos prisonniers peuvent se dire qu’au bout d’un certain temps, les chances que chacun ait été appelé seront suffisamment élevées pour qu’ils puissent sans risque affirmer être tous passés dans la salle. Je tiens cependant à dire que l’énoncé précisant bien qu’il leur faudrait une certitude absolue pour s’en sortir, cette solution n’est pas valable pour notre problème. Il est tout à fait possible, mais avec une probabilité quasi-nulle, qu’un des prisonniers ne soit jamais pris sur une période de mille ans. Mais pour son intérêt mathématique, étudions-là de plus près.

On retrouve ici une version du problème du collectionneur de coupons, qui se pose ainsi : On suppose qu’il y a n coupons différents de probabilité égale à obtenir, et on regarde le nombre d’essais T qu’il faudra faire pour collecter l’ensemble des coupons. S’il est facile d’obtenir les premiers rapidement, les derniers demanderont un temps bien plus élevé (pour une collection de 42 coupons, il faut effectivement 42 essais en moyenne pour obtenir le dernier si l’on est déjà en possessions des 41 premiers). C’est pourquoi le temps moyen pour collecter l’ensemble est bien plus long que le nombre de coupons lui-même.
On trouve facilement que l’espérance de ce temps T se calcule ainsi :

On pourra calculer E(T) – ou s’en rapprocher via le développement asymptotique de Hn –  et trouver par exemple que pour 42 coupons, le temps moyen pour réunir l’ensemble des coupons est de 182 essais.

Retournons à nos prisonniers. Ils décident simplement d’attendre que la probabilité qu’ils aient été tous choisis soit suffisamment forte pour annoncer sans risque que c’est bien le cas. On pourra prendre une valeur arbitraire comme 99.9%.
Pour calculer la probabilité exacte qu’ils auraient d’être tous choisis après un temps T, on va utiliser une matrice stochastique (ou de Markov), la matrice M de taille 42×42 des transitions.

Très bien. On notera que la probabilité au bout de 2048 jours n’est pas exactement 1 contrairement à ce que mon tableur m’indiquera, mais plutôt 0.999… avec un certain nombre de 9.
Soit. Au bout de 1024 jours la probabilité qu’ils aient été tous choisis est supérieure à 99.9%, nos prisonniers pourraient donc s’estimer satisfaits de ces chances et l’annoncer au gardien. Mais ce n’est pas la solution attendue pour ce problème. Fin de notre digression.

Voyons d’abord une solution bien inefficace.
Les prisonniers répartissent les jours en blocs de 42 jours et chacun passant dans la salle  applique le procédé suivant :

  • Si c’est le 1er jour du bloc :

– Si l’ampoule est éteinte, il l’allume.
– Si elle est déjà allumée, et que le premier bloc de 42 jours est déjà passé plus tôt, il annonce au gardien que tous les prisonniers sont passés dans la pièce.

  • Pour tous les jours du bloc :

– Si c’est sa première visite dans la pièce durant ce bloc, il ne fait rien.
– Si c’est son second passage ou plus dans la pièce durant ce bloc, il éteint l’ampoule (ou la laisse éteinte si elle l’est déjà).

L’idée derrière cette stratégie est qu’éventuellement, avec une probabilité 1, les prisonniers seront assez chanceux pour qu’il y ait un bloc de 42 jours où aucun d’entre eux ne passera dans la pièce deux fois. C’est à dire que chacun n’y entrera qu’une et une seule fois. Ainsi l’ampoule sera allumée le premier jour et le restera après 42 jours, n’étant éteinte qu’en cas de deuxième passage. Au premier jour du bloc suivant, le prochain prisonnier saura donc qu’au bloc précédent chacun d’entre eux y est passé et pourra l’annoncer au gardien.
Bon il y a un petit problème cependant. Pour un bloc donné, la probabilité de succès est le nombre de permutations des 42 prisonniers divisé par le nombre de façon possible qu’ils aient d’entrer dans la pièce. Pour n prisonniers, c’est (n!/n^n).
Le nombre moyen de blocs pour y arriver est égal à 1/pp est la probabilité de succès dans un bloc.  Ainsi le nombre moyen de blocs est de n^n/n!. Chaque bloc étant de n jours, le nombre moyen de jours avant leur libération est de n^(n+1)/n!.
Pour info, pour nos 42 prisonniers, ça fait quand même 4.48*10^18 jours, soit un peu plus de 12 millions de milliards d’années. Faut être patient.
Bon ils auraient plutôt intérêt à se mettre d’accord sur une méthode qui aboutisse avant la fin de l’univers.

Voici la solution classique à l’énigme :
Les prisonniers se mettent d’accord pour faire de l’un d’eux le Compteur. Grâce à une stratégie particulière, ce Compteur sera chargé de déterminer lorsque chacun de ses camarades sera passé dans la pièce et d’annoncer lui-même au gardien que tous y sont allés de façon sûre. Cette stratégie est la suivante. Quand un prisonnier, autre que le Compteur, entre dans la pièce :
– Si l’ampoule est éteinte et qu’il ne l’a jamais lui-même allumé, il l’allume.
– Si elle est déjà allumée ou s’il l’a déjà allumé lui-même, il ne fait rien.
Lorsque maintenant le Compteur entre dans la pièce :
– Si l’ampoule est allumée, il l’éteint et ajoute 1 à son compteur mental.
– Si elle éteinte, il ne fait rien.
On voit directement que chacun des prisonniers n’allumera qu’une seule fois l’ampoule, quel que soit le nombre de leur passage dans la pièce. Le Compteur lui devra à chaque fois « valider » ce passage en éteignant l’ampoule avant qu’un autre prisonnier ne puisse l’allumer, et ce 41 fois. Au final, lorsqu’il aura éteint 41 fois l’ampoule, il saura que tous les autres prisonniers sont passés au moins une fois dans la pièce et peut donc sortir de ce calvaire.
On peut remarquer que compte tenu de l’énoncé ils pourraient choisir leur Compteur comme étant le premier prisonnier à passer dans la pièce (au premier jour du début de l’expérience), un détail qui leur permettrait juste de gagner quelques jours.

OK, et combien de temps ça prendrait tout ça ?
A chaque fois que le Compteur attend avant de passer dans la pièce, la probabilité que la lampe soit allumée est la probabilité qu’un des prisonniers qui n’a pas été encore comptabilisé y aille avant lui. S’il y a k prisonniers non comptés, cette probabilité est k/(k+1). Ainsi le nombre moyen de passages avant que le Compteur voit l’ampoule allumée est de (k+1)/k.
moyen
1901 jours, un peu plus de 5 ans donc. Pas trop mal. C’est bien plus long que la méthode probabiliste, mais ça correspond à l’idée du problème qui était de trouver ce genre de stratégie.

Il existe des méthodes plus optimales, certaines utilisant des assistants au comptage, d’autres en comptant des groupes de prisonniers plutôt qu’un par un. Des méthodes qui sont bien plus complexes et plus rapide (une par exemple nous donnera des temps moyens de 532 jours, soit bien mieux que la méthode classique). Mais ce n’est pas le but de mon article de les décrire et vous invite à consulter ce document si vous voulez en savoir davantage.

Également de nombreuses variantes du problème peuvent se trouver, avec plusieurs ampoules dans la pièce, plusieurs pièces, la condition de succès qui demande cette fois que chacun des prisonniers annonce un jour correctement qu’ils sont tous passés, voire que chacun annonce le même jour (variante d’ailleurs impossible)…

Publicités
Cet article, publié dans Enigme, est tagué , . Ajoutez ce permalien à vos favoris.

4 commentaires pour Les prisonniers et l’ampoule [Solution]

  1. abe dit :

    A partir du moment où ils se réunissent avant l’épreuve pourquoi ils ne se posent tout simplement pas la question pour savoir qui est passé ou non?

  2. abcde dit :

    Billet très intéressant !
    Je pense que le calcul de la fin est erroné : s’il y a k prisonniers non comptés, la proba qu’un de ceux là y aille est k/n ce qui prend n/k jours. Ensuite la proba que le compteur y aille est toujours 1/n d’espérance n.
    Au final pour un k donné, l’espérance est n/k + n jours. En faisant la somme sur k on trouve : n(n-1) + n(1/2 + 1/3+ 1/4+…+1/(n-1) ), ce qui s’approxime par n ( n-1 + ln(n-1) + 0.577 ), et non n( (n-1)*ln(n-1) + 0.577) comme indiqué dans l’article.

    • abou dit :

      Je suis d’accord avec abcde, le calcul présenté dans l’article est inexact. De plus le calcul des puissances de la matrice me semble également erroné : je trouve bien les mêmes probas mais pour des valeurs de n systématiquement 2 fois plus petites que celles annoncées… (par exemple je trouve bien une proba de 0.996079 mais pour n=384 et non 768 comme c’est écrit). Une explication ?

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s