100 prisonniers et une ampoule
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 ?
c’est dur
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.
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
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 😀
@ 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 ?
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 ?
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
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
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.
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
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.
Lorsqu’un prisonnier passe une 2ème fois il ne touche à rien sinon il allume et éteint
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?
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.
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 ?
En espérant que l’ampoule ne grille pas ^^
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 😀
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é
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…
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?
Ils n’ont qu’à tenir leur réunion dans cette fameuse salle, et le tour sera joué…
Même très perplexe.. 😉
Je n’ai pas mis assez d’images, c’est peut-être pour ça 😀
Pas du tout 😀
Je vous sens perplexe sur cette énigme 🙂
Oui en effet