100 prisonniers et une ampoule

énigme 100 prisonniers une ampoule interrupteur

100 prisonniers sont enfermés dans une prison. Chaque prisonnier est seul dans sa cellule sans fenêtre et n’a aucun moyen de communiquer avec les autres ni de savoir ce qu’il se passe en dehors de la cellule.

Le directeur de la prison lance un jeu pour faire de la place afin de faire des travaux de rénovation. Si les prisonniers gagnent, ils seront libérés sinon ils seront fusillés.

Le principe du jeu est le suivant. Chaque jour, un gardien fera venir l’un des prisonniers choisi aléatoirement dans une salle. Un même prisonnier peut venir plusieurs fois, même à la suite. C’est le hasard qui décide qui est désigné chaque jour. A l’intérieur, il n’y a qu’une ampoule et un interrupteur permettant de l’allumer et de l’éteindre. Le prisonnier est libre d’allumer, d’éteindre ou de ne rien faire. Il ne peut rien faire d’autre dans cette salle et ne peut pas toucher l’ampoule. Seuls les prisonniers peuvent appuyer sur l’interrupteur, le gardien n’a pas le droit d’y toucher. Au début du jeu, l’ampoule est éteinte et les prisonniers le savent.

Pour gagner le jeu, l’un des prisonniers doit pouvoir dire “tous les prisonniers (les 100) sont passés au moins une fois dans cette salle” et que ça soit vrai.

Juste avant de débuter ce jeu, les 100 prisonniers ont le droit exceptionnellement de discuter ensemble pendant quelques minutes afin d’établir une stratégie. Ce sera la seule fois. Ils ne pourront plus communiquer après autrement qu’avec cette ampoule.

Comment faire pour gagner ce jeu ?

Voir la solution

 

24 commentaires Écrire

  1. Alexis 28 janvier 2018 à 18h27 Répondre

    J’ai trouvé la bonne solution ! Je suis content: j’ai mis une heure au moins, je suis passé par 3 stratégie différentes, mais elle devenait de plus en plus compliquées, alors que celle ci est certes très longue, mais super simple.
    Je ne suis pas sûr qu’une autre solution puisse marcher.

  2. Raphaelle 30 décembre 2017 à 14h49 Répondre

    Comment le prisonnier désigné peut savoir quand un prisonnier est passé? Il faudrait qu’il passe énormément de fois, si ce n’est derrière chaque prisonniers

  3. Antoine 2 juin 2017 à 07h47 Répondre

    Non non pas un temps infini.

    Selon un calcul rapide impliquant la loi binomiale negative. L’espèrence de temps passer dans la prison avant de trouver la solution est de 28,54 années. Ça reste jouable 😀

  4. Steredenn22 29 juillet 2016 à 19h40 Répondre

    @ Vasavoir…

    Si le premier prisonnier à passer allume puis repasse 99 autres fois de suite, il trouvera l’ampoule allumée 99 fois, sans savoir que c’est lui qui l’a allumée la première fois…

    Et même si “n” jours se passent entre deux de ces 100 passages, pendant lesquels le ‘compteur’ ne passe pas dans la salle (donc n’éteint pas), mais “n” autres prisonniers qui ne peuvent rien faire puisque l’ampoule est allumée, l’ampoule sera encore allumée, toujours par lui lors de son premier passage. Compter les jours ne lui servira donc d’aucune façon…

    Donc s’il crie “Victoire !” lors de son centième passage, ça fait cent fusillés !
    Ce doit être optimal du point de vue du Directeur, qui veut entreprendre les travaux le plus vite possible !!!

    Je me trompe ?

  5. Steredenn22 29 juillet 2016 à 19h10 Répondre

    Remarques sur l’énoncé et la solution associée (qui donne au ‘compteur’ le rôle d’éteindre et aux autres prisonniers le rôle d’allumer une seule fois) :

    – Il n’est pas nécessaire que la lumière soit éteinte au début du jeu, mais alors le ‘compteur’ devra compter jusqu’à 100 et non jusqu’à 99. En effet, la lampe sera toujours éteinte à la suite de son premier passage, ce qui ramène au problème précédent, mais avec ce passage initial en plus.

    – La notion de temps n’a pas d’importance dans ce problème de logique pure. Les gardiens, peuvent décider du rythme de passage des prisonniers – pourquoi pas un tous les 10 secondes ou un par minute ? Ceci évite les arguties sur une libération qui n’interviendrait qu’après la fin des temps…

    – Que le prisonnier ‘doive’ (et non ‘puisse’) allumer l’ampoule la première fois où il passe et la trouve éteinte est dans l’esprit de la stratégie collective où chacun a intérêt à gagner le plus vite possible que suggère le jeu.

    Je n’ai pas résolu la question de savoir si le ‘compteur’ est le premier à savoir que tous les prisonniers sont passés, mais intuitivement je dirais que oui. Je ne vois pas bien ce qu’un prisonnier peut compter alors :
    – qu’il ne sait absolument pas combien de prisonniers ont pu passer dans la salle à l’ampoule entre deux de ses propres passages, y compris aucun, sauf si l’ampoule a changé d’état,
    – et qu’il peut lui-même passer un nombre de fois successives quelconque sans qu’aucun autre prisonnier ne passe.
    Confirmation ou contre-exemple ?

  6. vasavoir 29 juin 2016 à 23h27 Répondre

    pourquoi tout le monde veut désigner un compteur je ne comprends pas, sachant qu’il a 1 chance sur 100 d’être celui qui arrive le premier à découvrir que 99 autres personnes sont passées, autant donner la même tache à chacun d’entre eux : allumer la lumière si c’est la première fois qu’on passe, l’éteindre sinon.
    si en arrivant la lumière est allumée, on compte + 1, si elle est éteinte, on l’allume si c’est la première fois qu’on passe (et on compte à nouveau +1), sinon on ne fait rien et ne compte rien. ainsi, le premier prisonnier (à repasser pour la 99 ème fois au moins) à compter que l’ampoule était allumée à 99 reprises peut se lever et dire que les 100 personnes sont passées. je pense que c ‘est un peu plus opti

  7. Thierry 21 juin 2015 à 11h31 Répondre

    c’est pire que cela Georges : le premier a passer ne doit pas être le compteur, donc il ya 99/100 qu’il passe, ensuite le compteur a 1/100 de passer, le suivant parmis ceux qui ne sont pas passés, a 98/100 puis le compteur toujours 1/100 etc.
    Ce qui nous fait (x-1)!/x^(2*(x-1)) chance avant d’arriver au terme de cette histoire… ce qui ne nous garanti pas qu’au bout de ce nombre incommensurable de jours, ça fonctionne (1 chance sur 2 ne veut pas dire qu’en 2 coups on gagne)
    incommensurable parcequ’ici avec 100 personnes, ça fait: 99!/100^(2*99) je ne vous raconte pas le nombre de 0

    même avec 10, on dépasserai incommensurablement l’âge de l’univers

    il faut refaire l’énigme avec 4 personnes et un passage toutes les minutes, ça fait déjà en gros 1/40 dont au pire en quelques heures c’est jouable

  8. Georges 24 avril 2015 à 16h16 Répondre

    Si le chef doit passer 100 fois (99+1), on peut considérer que les autres doivent passer le même nombre de fois. Ce qui veut dire qu’il y aura eu 10.000 passages environs. Sachant qu’il n’y a qu’un passage par jour, il faudra 10.000 jours pour arriver à la solution, soit un peu plus de 27 ans! On peut pas dire que le directeur soit pressé de faire ses travaux de rénovation.

  9. Chris 12 avril 2015 à 05h59 Répondre

    L’énoncé est incorrect :” …ni de savoir ce qu’il se passe en dehors de la cellule” veut dire qu’il ne peut pas y avoir de “compteur” désigné puisqu’il ne peut pas savoir nonplus ce qui se passe

  10. dd 10 mars 2015 à 04h22 Répondre

    Chaque prisonnier est attribué d’un numéro (de 1 à 100), qu’il communiquera (par un nombre précis de on/off) lorsqu’il sera dans la salle.
    Chaque prisonnier mémorise les numéros communiqués à chaque passage, et pourront ainsi constater lorsque les 100 prisonniers seront passés au moins une fois.

  11. Missgaspa
    Missgaspa 22 octobre 2014 à 21h05 Répondre

    Ouf c’est compliqué!

    Est ce que les autres prisonniers ont un moyen de voir de l’extérieur de la pièce si l’ampoule est allumée ou pas? j’imagine que non..

    Le premier entre et allume l’ampoule. Je pense à une solution ou l’ampoule n’est allumée que lorsqu’un prisonnier y est pour la première fois. Et il faudrait trouver un moyen d’additionner les journées où l’ampoule est allumée..?

    Est ce que les prisonniers se voient de temps en temps, genre à la cantine? ce serait + simple 🙂 Est ce qu’ils ont le droit de faire une marque sur le mur?

  12. Madina
    Madina 22 octobre 2014 à 18h38 Répondre

    Quoi que….

    tout bien considéré, c’est sans doute encore plus rapide si lui seul éteint et les 99 autres n’allument qu’une seule fois. Dans ce cas il n’aura à compter que jusqu’à 99.

    Mais bon, les 2 solutions marchent.

  13. Madina
    Madina 22 octobre 2014 à 18h07 Répondre

    je penche pour la solution suivante :
    Un et un seul prisonnier est désigné pour allumer la lumière.
    Tous les autres n’auront le droit de l’éteindre qu’une et un seule fois (le première étant le meilleur choix pour que cela soit le plus court possible). Aux autres passages ils ne devront rien faire.

    Le prisonnier désigné pour allumer la lampe l’allume à chaque fois qu’elle est éteinte, c’est à dire à son premier passage puis à chaque fois qu’un des 99 autres prisonniers l’aura éteinte. Il doit compter le nombre de fois qu’il l’allume. A la 100ème il sera donc certains que les 99 autres l’ont éteinte et pourra glorieuseemnt l’annoncer.

    Y en a dans la caboche du vieux singe, non ?

  14. Clad74
    Clad74 22 octobre 2014 à 13h52 Répondre

    Il y a un prisonnier qui est chargé d’éteindre la lumière.
    Pour le premiers passage d’un des 99 autres prisonniers, ils ont pour ordre d’allumer la lumière si elle est éteinte et de ne rien faire si elle est déjà allumée.
    Lorsque le prisonnier chargé d’éteindre la lumière voit l’ampoule allumé, il compte +1. Et dès qu’il est à 99, il peut s’écrier que tous les prisonniers sont passés au moins une fois. Cela implique que ce prisonnier devra être appelé au minimum 99 fois. Ça peut être long 😀

  15. Greg
    Greg 22 octobre 2014 à 13h08 Répondre

    j’ai une solution mais elle demandera beaucoup de temps :
    les prisonniers choisissent arbitrairement l’un d’eux qui aura pour rôle de compter les passages, appelons le X:
    voici ce que doit faire chaque prisonnier :
    chacun d’entre eux doit se considérer comme “compté” dès lors qu’il est désigné, qu’il arrive dans la salle et que la lumière est éteinte. Dans ce cas, il allume la lumière et devient “compté”
    Voici ce que doit faire chaque prisonnier s’il est désigné
    si c’est X : s’il voit la lumière, il compte un passage de plus et l’éteint, sinon il ne fait rien
    pour les autres prisonniers
    1er cas : il n’est pas “compté”
    si la lumière est allumée, il ne fait rien : c’est que quelqu’un d’autre a été compté, donc il doit attendre que X
    éteigne la lumière
    Si la lumière est éteinte, il l’allume et peut dès lors se considérer comme “compté”
    2eme cas : il est déjà “compté”
    il ne fait alors rien : que la lumière soit éteinte ou allumée, il la laisse telle quelle
    dès que X compte 99 passages, tout les autres prisonniers sont passés, et lui aussi(au moins 99 fois même)
    donc c’est gagné

  16. Greg
    Greg 22 octobre 2014 à 12h52 Répondre

    au passage, le directeur veut faire de la place, mais le temps que le jeu finisse, il y en a dans le meilleur des cas pour 100 jours, il aurait pu faire plus simple…

  17. Greg
    Greg 22 octobre 2014 à 12h32 Répondre

    si j’ai bien compris, il n’y a qu’au départ que les joueurs connaissent l’état de l’ampoule ?
    sinon seul celui qui est désigné peut voir si elle est éteinte ou allumée?

Ajouter un commentaire