Encore une histoire de prisonniers [Résolu]

Attention, une très tordue et pas facile :

The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.

"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure.

"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."

What is the strategy they come up with so that they can be free?

Source : http://www.techinterview.org

Traduction :

Le directeur d'une prison accueille 23 nouveaux prisonniers à leurs arrivées. Il leur dit : "Aujourd'hui, vous pouvez vous parler, établir une stratégie, mais à partir de demain, vous serez dans des cellules isolées avec aucun contact avec l'extérieur".

"Dans la prison, il y a une salle, appelée la salle des interrupteurs, qui contient deux interrupteurs étiquetés A et B. Chacun peut être dans une position 'on' ou 'off', mais je ne vous dirai pas leurs positions initiales. Les interrupteurs ne sont connectés à rien du tout."

"A partir de demain, et quand bon me semblera, je sélectionnerais un prisonnier au hasard et je l'escorterais dans la salle. Le prisonnier devra choisir un interrupteur, et changer sa position. Il doit en bouger un, et en bouger un seul. Il ne peut pas ne pas en bouger, ni bouger les deux. Ensuite, il sera reconduit dans sa cellule."

"Personne n'entrera dans la salle avant que je n'y amène le prisonnier suivant, qui devra effectuer la même chose. Je choisis le prisonnier aléatoirement, je peux en choisir un trois fois de suite, ou le choisir, puis en choisir d'autre, puis revenir choisir le même".

"Mais, au bout de suffisamment longtemps, tout les prisonniers auront visité la salle autant de fois que tout le monde. A n'importe quel moment, n'importe quel prisonnier pourra me dire : 'Nous avons tous visité la salle au moins une fois.' et être sûr à 100%."

"Si il a raison, vous serez tous libérés. Si il a tort, vous serez tous jetés aux crocodiles"

Quel est la stratégie que les prisonniers vont mettre en place afin d'être libérés ?

[Jahprend]

Je suis pas vraiment sur d'avoir compris la fin, ce qui leur permet d'etre liberé, c'est juste de dire "oui, on l'a tous visité"?

Parce que si c'est ca, bah ils se font passer le mot de tous dire ca et pis c'est tout (je dois avoir mal compris, alors explique plus en détail).

N'importe quel prisonnier peut dire "oui, on l'a tous visité".

Après, deux possibilités : soit c'est vrai (le directeur le sait, lui), alors il libère les prisonniers. Si jamais un prisonnier dit "oui, on l'a tous visité" alors qu'il au moins un prisonnier à ne pas l'avoir visité, alors tout le monde meurt (ce qui n'est pas le but recherché par les prisonniers à vrai dire ^^).

Donc il ne suffit pas de le dire, il faut en plus être sûr que ça soit vrai.

[Jahprend]

Est ce que le directeur doit demander a un mec qui viens de passer dans la salle, et qui donc connait les positions des interrupteurs, ou il peut demandé à n'importe qui, genre le premier à y être aller, et qui n'y es jamais retourner (par exemple, car je sais qu'ils peuvent y aller plusieurs fois).

Pas trop compris ta question, mais le directeur n'a rien à demander, et attention spoiler, de toute façon, celui devra dire "oui, on l'a tous visité" sera certainement le dernier à être rentré dans le salle (je vois mal comment un gars dans une cellule isolé peux se réveiller et dire comme ça la phrase sans aucun info ^^)

[gyzmau]

Mais, au bout de suffisamment longtemps, tout les prisonniers auront visité la salle autant de fois que tout le monde. A n'importe quel moment, n'importe quel prisonnier pourra me dire : 'Nous avons tous visité la salle au moins une fois.' et être sûr à 100%."

"Si c'est vrai, vous serez tous libérés. Si c'est faux, et l'un de vous n'a pas encore visité la salle, vous serez tous jetés aux crocodiles"

je rectifierais légèrement par

A n'importe quel moment, n'importe quel prisonnier pourra me dire : 'Nous avons tous visité la salle au moins une fois.'
"Si il a raison, vous serez tous libérés. Si il a tort, vous serez tous jetés aux crocodiles"
Comment faire pour etre sur que tous le monde l'a visité au moinsune fois et donc être libere?

En ésperant que ca ne change pas l'enigme lol.

[Jahprend]

Pas trop compris ta question, mais le directeur n'a rien à demander, et attention spoiler, de toute façon, celui devra dire "oui, on l'a tous visité" sera certainement le dernier à être rentré dans le salle (je vois mal comment un gars dans une cellule isolé peux se réveiller et dire comme ça la phrase sans aucun info ^^)

Bah moi aussi je voyais mal comment il était possible que un mec qui soit pas le dernier à rentrer dans la salle ( et qui donc est sur d'être le dernier à avoir modifié les interrupteurs) mais c'est pas précisé sur l'énigme, alors je pose quand même la question

Sinon j'ai du mal à voir comment le mec peut repérer un multiple de 23 changements sur 2 interrupteurs dont on connais pas la position initiale, alors ils ont qu'a discrètement gratté un trait sur le mur chacun entre les 2 interrupteurs, et chaque prisonniers regardent avant de sortir s'il y en a 23 et pis c'est tout !

PS : je sais que c'est pas la solution

Sinon j'ai du mal à voir comment le mec peut repérer un multiple de 23 changements sur 2 interrupteurs dont on connais pas la position initiale

Si t'avais aucun mal, ça serait beaucoup moins marrant

[Jahprend]

Si t'avais aucun mal, ça serait beaucoup moins marrant

il est vrai

Sinon, les prisonniers ont rien le droit de faire d'autre dans la salle que modifier la position d'un des interrupteurs? savoir s'il faut cherché quelque chose de tordu (comme ce que j'ai mis avant ) où alors plus se tourner vers une solution mathématique en rapport avec les interrupteurs.

Purement logique & mathématique.
Comme dirait l'auteur de l'énigme, il n'y a pas de 'aha' trick.

[Arnaud_03]

Bonjour,

J'aurais deux question :

1) Les prisonniers sont-ils sûrs que le premier d'entre eux passera le lendemain du jour où ils arrivent ou bien le directeur peut-il feinter et attendre plusieurs jours avant de faire passer le premier prisonnier ?

NB : À ce que j'ai compris, la fréquence de passage des prisonniers n'est pas régulière ?

2) Connais-tu la (une) solution au problème que tu énonces ? À mon avis non, ou alors tu as cherché à nous envoyer sur une fausse piste...

EDIT : Explication en spoiler ci-dessous :

Considérons que le premier prisonnier passe forcément le lendemain. Tant qu’ils peuvent communiquer, les prisonniers doivent désigner un prisonnier P qui sera celui chargé de comptabiliser le nombre de prisonniers passés. Le premier prisonnier à passer devra placer l’interrupteur A sur la position ‘on’ si ce n’est pas déjà le cas. Tous les prisonniers suivants n’auront le droit que de manipuler l’interrupteur B. Seul le prisonnier P pourra remettre l’interrupteur A sur ‘off’. Si un prisonnier qui n’a encore jamais touché à l’interrupteur A le voit sur la position ‘off’, il devra le remettre sur ‘on’ pour signaler son passage au prisonnier P. Tous les prisonniers qui passeront ensuite ne pourront là encore manipuler que l’interrupteur B. À son passage suivant, le prisonnier P remettra l’interrupteur A sur ‘off’ et comptabilisera un passage supplémentaire. Une fois que le prisonnier P aura comptabilisé le passage des 22 autres prisonniers, il pourra dire qu’il est sûr que tout le monde est passé au moins une fois…

Si les prisonniers ne sont pas sûrs que le premier d’entre eux passera le lendemain : il est impossible pour un prisonnier de savoir s’il est le premier à passer. Dans ce cas, le prisonnier P ne pourra pas savoir si quelqu’un d’autre est passé avant lui à son premier passage. Comptabiliser un seul passage des autres prisonniers ne pourra donc pas suffire, c’est pourquoi tous les autres prisonniers devront signaler deux fois leur passage par la méthode énoncée précédemment. Comme le doute persistera toujours sur le premier passage, le prisonnier P ne le comptabilisera pas. Mais lorsqu’il aura recensé un total de 43 passages (chaque prisonnier signalant ses 2 premiers passages), le prisonnier P sera sûr que tout le monde est déjà passé au moins une fois. Le prisonnier P est sûr d’atteindre au moins 43 passages après un certain temps car il ne peut rater au maximum qu’un seul passage d’un autre prisonnier (le premier), et avec 43 passages comptabilisés, il est sûr que 21 prisonniers sont passés au moins 2 fois et que le 22è est passé au moins une fois...

J’espère avoir été assez clair…

PS : Je disais que tu nous avais envoyé sur une fausse piste car tu disais penser que le prisonnier à pouvoir être sûr que tous les autres étaient passés au moins une fois était le dernier à faire son passage, mais le prisonnier qui est chargé de se prononcer au moment venu doit être désigné à l'avance...

EDIT 2 : Merci !

1) Pas de connaissance des jours de toute façon, question sans fondement :p

2) J'avais pas vu ça comme ça, mais effectivement, ça a pu donner une fausse piste à l'insu de mon plein gré.

Sinon , tu explique parfaitement la réponse, pourrais tu la mettre en Spoiler par contre, histoire de laisser chercher ceux qui le veulent !!

Edit : pour mettre en spoiler, tu colores juste le texte en blanc, ça suffit.

[Jahprend]

J'ai eu le temps de lire 2 fois la réponse, mais je dois pas avoir assez de neurones parce que j'ai franchement pas compris l'histoire du mec qui regarde les mecs passé...

Petite question subsidiaire que je me pose à moi-même et aux autres :

Si on considère que en moyenne, le directeur emmène un prisonnier par jour dans la cellule, et que les prisonniers sont choisis de manière totalement aléatoire selon une loi uniforme, combien de jours en moyenne les prisonniers devront attendre avant d'être libéré ?

Edit : Auto-réponse;

Sur 100.000 itérations, j'arrive à une durée moyenne de 1079 jours d'incarcération.
Pas si longtemps, 2 ans, 11 mois, 14 jours. Quand on voit ce qu'a tenu Ingrid, c'est peanuts ^^

[Arnaud_03]

J'ai estimé la durée à 1012 jours, mais d'une manière différente :

Pour recenser les 43 passages, le prisonnier doit en effectuer 44 (doute sur le premier passage). Or, avec une loi uniforme, le prisonnier P a une chance sur 23 de passer chaque jour, donc (je ne sais pas si le calcul peut être simplifié à ce point) on obtiendrait 44 * 23 = 1012 jours d'incarcération...

Envoyé par Arnaud_03

J'ai estimé la durée à 1012 jours, mais d'une manière différente :

Pour recenser les 43 passages, le prisonnier doit en effectuer 44 (doute sur le premier passage). Or, avec une loi uniforme, le prisonnier P a une chance sur 23 de passer chaque jour, donc (je ne sais pas si le calcul peut être simplifié à ce point) on obtiendrait 44 * 23 = 1012 jours d'incarcération...

Certes, mais le prisonnier 'answer man' peut passer dans la salle sans que le switch aie changé de position, ie : aucun nouveau prisonnier n'est passé dans la salle entre 2 passages successifs de l'answer man. Donc les 1012 jours sont une sous estimation de la moyenne de passage. Je pense que la solution théorique doit être trouvable, mais mon niveau en proba est proche du vide absolu ^^

[Arnaud_03]

Envoyé par Scorpi0

Certes, mais le prisonnier 'answer man' peut passer dans la salle sans que le switch aie changé de position, ie : aucun nouveau prisonnier n'est passé dans la salle entre 2 passages successifs de l'answer man. Donc les 1012 jours sont une sous estimation de la moyenne de passage.

Je pense que tu as raison en effet. Mon raisonnement est trop simpliste, même s'il permet de corroborer le fait qu'on doit bien tomber sur un peu plus de 1000 jours...

Bon, je viens de faire les calculs pour différents nombres de prisonniers, j'en déduis que le nombre de jours moyens d'emprisonnement est asymptotiquement égal à

Code :

2*(Nombre de prisonniers)²

Qu'est ce qu'on se marre

Cela permet d'en déduire un premier résultat quand même, si on suppose que les prisonniers ont 30 ans, et qu'il meurt tous a 80 ans, ce qui leur accorde jusqu'à 50 ans d'emprisonnement, soit 18250 jours, alors si ils sont 95 ou plus, ils ont peu de chance en moyenne de sortir vivant...

[AL1986]

Salut,

Le fait est que tout dépend du nombre de fois que le directeur décidera de faire passer les prisonniers à la switch room. Il faut que ce nombre de fois permette au prisonnier P de faire les comptes. Si le directeur décide qu'aucun prisonnier ne visitera la switch room plus de 22 fois (23 étant le nombre minimum de fois que le prisonnier P est supposé visiter la switch room pour être sûr que tous les 22 autres prisonniers y sont passés au moins une fois), il est impossible que P affirme que tous les prisonniers ont visité la switch room.