100 autres prisonniers

[scelerat]

Les directeurs de prison ne manquent pas d'imagination quand ils ont 100 prisonniers a l'isolement et qu'ils ont besoin de faire de la place.
En voila un autre qui se propose de leur donner une chance d'etre tous liberes. Il leur indique qu'il va les reunir une seule fois, puis qu'il les remettra dans leurs cellules isolees. Chaque jour, il conduira un prisonnier choisi au hasard dans une piece, ou il pourra soit ne rien faire, soit manoeuvrer l'interrupteur de l'ampoule electrique, soit affirmer que tous les prisonniers sont passes au moins une fois dans la piece. Si l'affirmation est vraie, ils seront tous liberes, si elle est fausse, ils seront tous executes.
L'ampoule est eteinte au depart, nul n'y touche entre deux visites de prisonniers, et les prisonniers ne peuvent communiquer en aucune maniere apres la reunion initiale. Quelle strategie doivent-ils utiliser pour etre tous liberes ?

(Bruce.ml n'a pas le droit de repondre, il connait visiblement l'enigme, mais je ne l'ai pas trouvee ici dans les archives :we: )

[bruce.ml]

C'est justement parceque cette énigme a déjà été postée que mon thread avait un "remake" dans son nom :id:

[Imod]

C'est justement parceque cette énigme a déjà été postée que mon thread avait un "remake" dans son nom :id:

Comme je ne connais pas , je questionne ! y at-il plus de deux positions pour l'interrupteur ou l'ampoule ?

Imod

[ThSQ]

Amusant !

Une suggestion :

Les prisonniers commencent par choisir l'un d'entre eux P0 (celui qui sait compter jusqu'à cent et qui est copain avec le gardien de préférence sinon ça risque d'être longuet ....).

L'ampoule est donc éteinte au début. Un prisonnier P1 # P0 entre et voit éteint, il allume. Les autres passent et voit allumé, ils ne font rien. Au bout d'un certain temps le fut du canon est froid et p0 (re-)passe. P0 voit allumé et sait donc qu'il y en a un de passé. P0 éteint.

Si c'est P0 ou P1 qui entrent juste ensuite ils touchent à rien jusqu'à ce que P2#P0 et P1 entre. Il voit éteint. Cool, il allume. Les autres ne font rien en voyant allumé jusqu'à ce que P0 repasse et voit allumé. P0 sait donc que 2 sont passés. Il éteint.

etc .... dès qu'un entre et voit éteint et qu'il n'a pas déjà allumé il le fait. Les autres ne font rien. P0 repasse, .....

Je crois que ça marche mais il n'y a aucune garanti que ça se termine avant la mort de tous les prisonniers .... Si P0 s'embrouille dans ses comptes c'est foutu aussi :(

[bruce.ml]

C'est correct, la seule chose est que l'ampoule n'est pas forcément éteinte au départ ;)

[Flodelarab]

Chaque jour, il emmène un prisonnier .........
Il suffit d'attendre 100 jours.


énoncé bidon.

[ThSQ]

a seule chose est que l'ampoule n'est pas forcément éteinte au départ

:hum: ah ? Je cite : 'L'ampoule est eteinte au depart"

Sinon il suffit que P0 fasse un tour de plus au cas où

[ThSQ]

Chaque jour, il emmène un prisonnier .........
Il suffit d'attendre 100 jours.


énoncé bidon.

Rien ne dit qu'il emmène un prisonnier différent chaque jour .....

[bruce.ml]

:hum: ah ? Je cite : 'L'ampoule est eteinte au depart"

Sinon il suffit que P0 fasse un tour de plus au cas où

Au temps pour moi, l'autre énoncé était plus difficile alors

[Patastronch]

Au temps pour moi, l'autre énoncé était plus difficile alors

C'est pareil non ? Il suffit que celui choisis le premier jour eteigne la lumiere a son premier passage si elle est allumée et on se retrouve dans une situation déjà résolue plus haut :p

[bruce.ml]

C'est pareil non ? Il suffit que celui choisis le premier jour eteigne la lumiere a son premier passage si elle est allumée et on se retrouve dans une situation déjà résolue plus haut :p

Oui j'ai pensé à ça au moment où j'ai post mon précédent message, il devait y avoir une hypothèse en plus car je me souviens que c'était plus compliqué, mais je ne retrouve plus le thread

[Imod]

Chaque jour, il emmène un prisonnier .........
Il suffit d'attendre 100 jours.

A condition de connaître le jour de départ , mais bon de toute façon , je n'ai rien compris au problème :we:
Imod

[Flodelarab]

A condition de connaître le jour de départ , mais bon de toute façon , je n'ai rien compris au problème :we:
Imod

Comme moi.

J'ai compris quand j'ai compris la solution.
En fait P0 valide chacun des prisonnier en éteignant.
Tous les prisonniers allument 1 fois et une seule et a ce moment là tout le monde peut sortir
.... Cela dit, il faut que P0 soit choisi 99 fois au moins. Ils ont le temps de crever 100 fois

[Patastronch]

Oui j'ai pensé à ça au moment où j'ai post mon précédent message, il devait y avoir une hypothèse en plus car je me souviens que c'était plus compliqué, mais je ne retrouve plus le thread

L'hypothèse doit etre qu'on ne connait pas le jour de départ. Car dans ce cas la tous les Pi ont aucun moyen de savoir si la lampe est eteinte a cause de P0 ou parcequ'ils sont le premier choisis. De meme P0 ne poura pas savoir si la lampe est allumée parceque quelqu'un l'a allumé ou parcequ'elle l'était au départ et que personne n'a osé l'éteindre ou qu'il est le premier choisi.

Si on ne ocnnait pas le jour de départ, ni l'état de la lampe initiale le probleme se complique fortement. Mais avec une des deux conditions précédentes remplies la solution donnée marche parfaitement.

[Imod]

Bon , en effet c'est simple et amusant mais l'épreuve peut durer un moment , ce qui gache un peu le plaisir .

Imod

[scelerat]

.... Cela dit, il faut que P0 soit choisi 99 fois au moins. Ils ont le temps de crever 100 fois

On peut d'ailleurs remarquer que la mort d'un prisonnier avant qu'il n'ait eu l'occasion d'allumer l'ampoule condamne tous les autres...
Mais si tout le monde vit, ils ont de bonnes chances de s'en sortir au bout d'une trentaine d'annees. Tiens, comment calculer la probabilite pour qu'ils s'en sortent au bout de M jours ?

[Flodelarab]

Si on ne connait pas le jour de départ, ni l'état de la lampe initiale le probleme se complique fortement.

Aucune importance.
P0 se considère comme le point de départ.
Il compte à partir de lui.
Donc il éteint en arrivant.
Et hop il commence à compter.
(Ne jamais confondre définition et instanciation )

[scelerat]

Aucune importance.
P0 se considère comme le point de départ.
Il compte à partir de lui.
Donc il éteint en arrivant.
Et hop il commence à compter.
(Ne jamais confondre définition et instanciation )

Mais si la lampe etait eteinte au depart, et qu'un autre l'a allumee, celui la ne sera jamais compte par P0, car un visiteur n'allume que si c'est la premiere fois qu'il passe.

[Flodelarab]

OK

Contre-objection:

Ya bien une solution technique mais c'est de moins en moins réaliste.
On fait 2 canaux de signalisation. Par exemple, les jours pairs (le jour de la réunion etant le jour 0) et les impaires.
Chacun allume une fois par canal.

Si, la première fois pour P0, la lampe est éteinte P0 sait que le premier jour, la lampe était éteinte.
Si, la première fois pour P0, la lampe est allumée,
* Soit qqun a allumé, auquel cas, il a utilisé son droit pour 1 canal mais il a toujours son droit pour l'autre.
* Soit personne n'a allumé, Le GARDIEN l'avait allumé ( :-o la saleté !) et P0 en aura compté un de trop sur le canal 1 mais il attendra 99 sur les 2 canaux de toute façon.

Est ce clair ?

[Patastronch]

Tiens, comment calculer la probabilite pour qu'ils s'en sortent au bout de M jours ?

Un petit essai surement faux vu l'abération du résultat. Mais je vois pas ou ca coince.

Il faut que chacun des prisonniers soit passé au moins une fois et qu'entre chacun de ces passages P0 soit passé et qu'enfin P0 repasse une derniere fois.

Pour M=198 (nombre de jour minimum pour que la stratégie se termine), les possibilités de passage pour P0 sont unique (tous les jours pairs). Pour les 99 autres, on peut les intervertir comme on souhaite mais tous doivent passer au moins une fois, soit 99! possibilités. Le nombre total de possibilités total est .

La proba pour M=198 vaut donc : .


Passons a M+1 jours :

Soit P(M) la probabilité pour que les prisoniers soient libre le Mème jour (donc correspond au nombre de possibilités pour que la stratégie se termine en M jours), le nouveau jour disponible peut etre inséré de M manieres différente (on ne peut l 'ajouter a la fin sinon ca voudrait dire que la stratégie s'est achevée en M jours). De plus ce jour la n'importe quel prisonier peut etre sélectionné. On a donc possibilitées que la stratégie s'acheve en M+1 jours. Soit :

Donc

Ce qui est absurde puisque ca voudrait dire qu'il existe une valeur M telle que P(M)>1.

Conclusion de l'étudiant de mauvaise foi : Contradiction ! Il n'existe pas de proba pour qu'ils puissent s'en sortir au bout de M jours.

Bon en gros ce que je dis est faux mais je vois pas trop pourquoi :hum: