L’énigme des 100 prisonniers et de l’ampoule

Cette énigme va vous rappeler celle de l’évasion impossible d’Alice et de Bob !

Énoncé

100 prisonniers sont confinés dans des cellules d’isolement.
Dans la prison, il y a une pièce centrale avec une ampoule ; cette ampoule est éteinte.
Aucun prisonnier ne peut voir l’ampoule depuis sa propre cellule.

Tous les jours, le directeur choisit un prisonnier au hasard, et ce prisonnier visite la pièce. Pendant sa visite, le prisonnier peut allumer l’ampoule s’il le souhaite.

Le prisonnier a deux choix: retourner dans sa cellule ou affirmer que les 100 prisonniers sont déjà tous allés dans le salon. Si cette affirmation est fausse, les 100 prisonniers sont donnés à mangés aux ours. Cependant, si c’est vrai, tous les prisonniers sont libérés.

Donc, l’affirmation ne devrait être faite que si le détenu est sûr et certain à 100% de sa validité, au risque de périr sous les crocs et les griffes des ursidés de la prison !

Les prisonniers sont autorisés à se retrouver une nuit dans la cour pour discuter d’un plan.
Sur quel plan devraient-ils s’entendre pour que quelqu’un finisse par faire une affirmation correcte ?

Un indice ?

Avant la solution, un petit indice… vous n’êtes bien sûr pas obligé de le lire !

Dans cette énigme, les prisonniers vont avoir besoin de trouver un compteur et d’un moyen pour lui de compter les prisonniers qui sont entrés dans la pièce tout en s’assurant qu’il ne compte pas le même prisonnier plus d’une fois. Tout cela grâce à la lumière.

Solution

Lorsque les prisonniers se rencontrent, ils s’entendent sur un plan qui doit être respecté à la lettre !

Un prisonnier est choisi comme capitaine, chargé du comptage.
Lorsqu’un prisonnier (autre que le capitaine) entre dans la pièce, il allume la lumière si et seulement si la lumière est éteinte et qu’il ne l’a jamais fait auparavant.
Lorsque le capitaine entre dans la pièce si la lumière est éteinte, il la laisse éteinte. Si la lumière est allumée, il l’éteint et ajoute 1 au compte des prisonniers.
Quand le compte du capitaine atteint 99, il peut dès lors affirmer que les 100 prisonniers sont tous entrés dans la salle et ils sont tous libérés.

Si cette procédure est suivie scrupuleusement, elle fonctionnera !

Mais combien de temps cela prendra-t-il ?

La durée du problème basé sur l’admission d’un prisonnier par jour dans la salle augmente avec le nombre de prisonniers.

La solution du comptage garantit un succès complet en 10.411 jours en moyenne, donc près de 30 ans. Espérons que les prisonniers sont en bonne santé !

Ce nombre de jours élevé est dû à un facteur: il y a 100 prisonniers, il faut donc 100 jours au minimum, or un prisonnier peut être amené plusieurs fois de suite dans la pièce tandis qu’un autre peut attendre des années avant de la rejoindre (c’est totalement aléatoire).

Sam Zylberberg
Les derniers articles par Sam Zylberberg (tout voir)

3 réflexions au sujet de “L’énigme des 100 prisonniers et de l’ampoule”

  1. Bonjour,

    C’est cette affirmation qui est fausse : « il y a 100 prisonniers, il faut donc 100 jours au minimum » puisqu’il faut que le compteur/capitaine soit appelé entre chaque prisonnier pour pouvoir constater que la pièce est allumé et l’éteindre => le minimum est donc de 199j (2n-1)

    Par contre je suis curieux d’avoir le raisonnement pour calculer le nombre de jour moyen, ainsi que la preuve (si elle existe) que cette solution est la plus « rapide en moyenne »

    Répondre
  2. Bonjour
    Cela implique qu’un des prisonniers (capitaine) puisse faire les allers retours à sa guise pour faires les vérifications. Or cela n’était pas précisé et on peut supposer que c’est impossible par la phrase « Tous les jours, le directeur choisit un prisonnier au hasard, et ce prisonnier visite la pièce » il n’y en a qu’un et pris au hasard
    Pour moi cette enigme ne fonctionne pas mais peut être que j’ai loupé un truc?

    Répondre
    • Bonjour,

      Il faut lire l’énigme jusqu’au bout : Les prisonniers sont autorisés à se retrouver une nuit dans la cour pour discuter d’un plan. Sur quel plan devraient-ils s’entendre pour que quelqu’un finisse par faire une affirmation correcte ?

      C’est suite à cette réunion qu’ils doivent mettre au point une stratégie de comptage, soit un des 100 prisonniers qui comptera avec méthode. Cela lui prendra environ 30 ans car ce n’est qu’un et un seul prisonnier, et ce choisi au hasard, qui va dans la cellule.

      Répondre

Laisser un commentaire