100 autres prisonniers

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: 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 )


Posted by: bruce.ml

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


Posted by: Imod

Citation:
Posté par bruce.ml
C'est justement parceque cette énigme a déjà été postée que mon thread avait un "remake" dans son nom

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

Imod


Posted by: 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 :(


Posted by: bruce.ml

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


Posted by: Flodelarab

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


énoncé bidon.


Posted by: ThSQ

Citation:
Posté par bruce.ml
a seule chose est que l'ampoule n'est pas forcément éteinte au départ ;)


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

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


Posted by: ThSQ

Citation:
Posté par Flodelarab
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 .....


Posted by: bruce.ml

Citation:
Posté par ThSQ
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 :)


Posted by: Patastronch

Citation:
Posté par bruce.ml
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


Posted by: bruce.ml

Citation:
Posté par Patastronch
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 :(


Posted by: Imod

Citation:
Posté par Flodelarab
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
Imod


Posted by: Flodelarab

Citation:
Posté par Imod
A condition de connaître le jour de départ , mais bon de toute façon , je n'ai rien compris au problème
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


Posted by: Patastronch

Citation:
Posté par bruce.ml
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.


Posted by: Imod

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

Imod


Posted by: scelerat

Citation:
Posté par Flodelarab
.... 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 ?


Posted by: Flodelarab

Citation:
Posté par Patastronch
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 )


Posted by: scelerat

Citation:
Posté par Flodelarab
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.


Posted by: 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 ?


Posted by: Patastronch

Citation:
Posté par scelerat
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 100^M.

La proba pour M=198 vaut donc : \frac{99!}{100^{198}}.


Passons a M+1 jours :

Soit P(M) la probabilité pour que les prisoniers soient libre le Mème jour (donc P(M)\times 100^M 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 100\times M\times (P(M)\times 100^M) = M\times P(M)\times 100^{M+1} possibilitées que la stratégie s'acheve en M+1 jours. Soit : P(M+1)=M\times P(M)

Donc P(M+1)=P(198)\times \prod_{i=198}^{M} i = \frac{M!}{197!} \times \frac{99!}{100^{198}}

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


Posted by: Patastronch

Citation:
Posté par 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 ?


Comment les autres savent que P0 est deja passé et qu'il connait l'etat de la lampe initial et que donc ils peuvent commencer a appliquer leur stratégie ?


Posted by: Flodelarab

Cela dit, si un canal arrive à 100, on arrête les frais. Le gardien avait allumé et les 99 autres ont allumé depuis.


Posted by: Flodelarab

Citation:
Posté par Patastronch
Comment les autres savent que P0 est deja passé et qu'il connait l'etat de la lampe initial et que donc ils peuvent commencer a appliquer leur stratégie ?
Ils s'en moquent. Ils allument tous 1 fois un jour pair et une fois un jour impaire. Sinon ils ne font rien


Posted by: Patastronch

Citation:
Posté par Flodelarab
Ils s'en moquent. Ils allument tous 1 fois un jour pair et une fois un jour impaire. Sinon ils ne font rien


Je comprends pas comment P0 peut savoir si la lampe a ete allumé sur le canal 1 ou 2.


Posted by: scelerat

Citation:
Posté par Patastronch
Soit P(M) la probabilité pour que les prisoniers soient libre le Mème jour (donc P(M)\times 100^M 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 100\times M\times (P(M)\times 100^M) = M\times P(M)\times 100^{M+1} possibilitées que la stratégie s'acheve en M+1 jours. Soit : P(M+1)=M\times P(M)

Donc P(M+1)=P(198)\times \prod_{i=198}^{M} i = \frac{M!}{197!} \times \frac{99!}{100^{198}}

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


Peut-etre que pour que pour que la strategie s'acheve en M jours, il faut aussi qu'elle ne se soit pas deja achevee avant !


Posted by: Flodelarab

Citation:
Posté par Patastronch
Je comprends pas comment P0 peut savoir si la lampe a ete allumé sur le canal 1 ou 2.
Il s'en moque. Il compte.

Le gardien a pu agir sur le canal 1 ou le canal 2 mais pas les 2. Y'en a donc un qui est vierge.

Voilà pourquoi j'ai rectifié la conclusion.
Si on arrive à 100 sur un canal, on stoppe la machine. Sinon, on attend 99 sur chacun.
L'un des 2 étant vierge, il y a bien 1 passage par prisonnier.


Posted by: scelerat

Citation:
Posté par 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 ?

Non, l'ampoule est eteinte

Par contre, si chaque prisonnier allume les DEUX premieres fois ou il trouve la lampe eteinte, le jour ou P0 a compte 197, c'est bon !


Posted by: Patastronch

Citation:
Posté par Flodelarab
Il s'en moque. Il compte.

Le gardien a pu agir sur le canal 1 ou le canal 2 mais pas les 2. Y'en a donc un qui est vierge.

Voilà pourquoi j'ai rectifié la conclusion.
Si on arrive à 100 sur un canal, on stoppe la machine. Sinon, on attend 99 sur chacun.
L'un des 2 étant vierge, il y a bien 1 passage par prisonnier.


Comment P0 compte sur un canal ? Comment il peut savoir si la lampe qu'il voit allumée doit faire +1 au canal 1 ou au canal 2 ? Désolé d'insister mais y a un truc qui m'échappe.


Par contre ton idée m'en a donnée une autre. Au lieu d'avoir le droit d'allumer qu'une seule fois la lampe, ils doivent tous l'allumer 2 fois.

Ainsi quand P0 compte 198 il est sur que tout le monde est passé. Et 198 est une valeur atteignable que la lampe soit eteinte ou allumée au départ.


Posted by: Patastronch

Citation:
Posté par scelerat
Non, l'ampoule est eteinte

Par contre, si chaque prisonnier allume les DEUX premieres fois ou il trouve la lampe eteinte, le jour ou P0 a compte 197, c'est bon !


Arg grilled ! mais bon j'ai comtpé 198 et pas 197 t es sur de toi ? je revérifie


Posted by: Imod

Citation:
Posté par scelerat
Non, l'ampoule est eteinte Par contre, si chaque prisonnier allume les DEUX premieres fois ou il trouve la lampe eteinte, le jour ou P0 a compte 197, c'est bon !

La vie en prison est devenu un véritable calvaire , j'espère que la pharmacie est bien fournie en aspirine et qu'on ne les réveille pas en pleine nuit pour aller voir l'ampoule

Imod


Posted by: Patastronch

Citation:
Posté par Imod
La vie en prison est devenu un véritable calvaire , j'espère que la pharmacie est bien fournie en aspirine et qu'on ne les réveille pas en pleine nuit pour aller voir l'ampoule

Imod


Surtout que si on te reveille pour t 'appercevoir qu'elle est deja allumée t es venere !


Posted by: Flodelarab

Citation:
Posté par scelerat
Non, l'ampoule est eteinte

Par contre, si chaque prisonnier allume les DEUX premieres fois ou il trouve la lampe eteinte, le jour ou P0 a compte 197, c'est bon !
Non. Si l'ampoule est éteinte, la première solution marche et il ne compte pas 197 mais 99. Revois ta copie.

Si l'ampoule est allumée a la base, alors il y a nécessité d'allumer 2 fois. C'est le même principe que mes 2 canaux. Mais en moins contraignant.


Posted by: Flodelarab

Citation:
Posté par Patastronch
Comment P0 compte sur un canal ? Comment il peut savoir si la lampe qu'il voit allumée doit faire +1 au canal 1 ou au canal 2 ?
Un canal les jours pairs et un canal les jours impaires. Lampe allumée = +1 TOUJOURS! Sur le canal qui correspond au jour.


Posted by: bruce.ml

Ce qui peut être amusant à faire c'est d'examiner un probleme similaire mais dans lequel on a plusieurs lampes ! des lampes numérotées de 1 à n. Et deuxième probleme subsidiaire : n lampes mais on ne peut pas les différencier ! par exemple elles sont mélangées pas le gardien à chaque sortie d'un prisonnier de la salle xD


Posted by: Flodelarab

Citation:
Posté par bruce.ml
Ce qui peut être amusant à faire c'est d'examiner un probleme similaire mais dans lequel on a plusieurs lampes ! des lampes numérotées de 1 à n. Et deuxième probleme subsidiaire : n lampes mais on ne peut pas les différencier ! par exemple elles sont mélangées pas le gardien à chaque sortie d'un prisonnier de la salle xD

ben si tu as 100 lampes, tu attends que les 100 soient allumées ...... c bête.


Posted by: Patastronch

Citation:
Posté par Flodelarab
Un canal les jours pairs et un canal les jours impaires. Lampe allumée = +1 TOUJOURS! Sur le canal qui correspond au jour.


Mais comment il sait quel jour elle a été allumé pour lui attribuer un canal ? Pfff le dialogue de sourd !


Posted by: Patastronch

Citation:
Posté par scelerat
Peut-etre que pour que pour que la strategie s'acheve en M jours, il faut aussi qu'elle ne se soit pas deja achevee avant !

Ca suffit pas de dire que l jour en plus est inséré ailleur que le dernier jour ?

Arg non en tapant je m'appercois que non. Voila la couille ! A la fois ca doit pas etre la seule erreur car on peut interpréter un calcul similaire pour que P(M) soit la proba que la stratégie s'acheve en au plus M jour, et cette proba est plus grande que 1 a partir d'une certaine valeur. Donc y a une autre erreur :p Decidement c est plein de conneries mon P(M) !


Posted by: Flodelarab

Citation:
Posté par Patastronch
Mais comment il sait quel jour elle a été allumé pour lui attribuer un canal ? Pfff le dialogue de sourd !

Oui, il ne sait pas.
il compte jusqu'à 198.

D'ailleurs, à cette occasion, on se rend compte que le fait que le jour soit pair ou impair n'a aucune incidence. Et on retombe tous sur la même solution.

[edit] d'ailleurs, je ne sais pas qui a dit 197, mais c'est faux car 2*98+gardien=197 et on se fait tous fusiller.


Posted by: Patastronch

Citation:
Posté par Flodelarab
Oui, il ne sait pas.
il compte jusqu'à 198.

D'ailleurs, à cette occasion, on se rend compte que le fait que le jour soit pair ou impair n'a aucune incidence. Et on retombe tous sur la même solution.

[edit] d'ailleurs, je ne sais pas qui a dit 197, mais c'est faux car 2*98+gardien=197 et on se fait tous fusiller.

Aaah je savais bien que c'etait 198 :)

Bon maintenant au moins onest tous d'accord, plus qu'a trouver l expression de P(M) :p


Posted by: Flodelarab

A chaque tour, le gardien doit en choisir 1 en particulier. Sinon, le tour ne sert à rien.

Je vois donc un schéma de Bernoulli avec succès ou echec répété à l'infini.
On connait la proba d'un succès et celui d'un echec.
On sait qu'il faut au moins 198 succès parmi M si la lampe est éteinte au début et 199 parmi M si elle est allumée.

Le calcul est trivial

D'accord avec ce modèle ?


Posted by: Patastronch

Citation:
Posté par Flodelarab
A chaque tour, le gardien doit en choisir 1 en particulier. Sinon, le tour ne sert à rien.

Je vois donc un schéma de Bernoulli avec succès ou echec répété à l'infini.
On connait la proba d'un succès et celui d'un echec.
On sait qu'il faut au moins 198 succès parmi M si la lampe est éteinte au début et 199 parmi M si elle est allumée.

Le calcul est trivial

D'accord avec ce modèle ?


presque, la proba d'un succés n'est pas constante, puisqu'il ne doit pas forcément en choisir un en particulier. P1 peut etre 99 personnes parmi 100, P2 98 personnes parmi 100... Et P0 qui doit etre choisi entre chaque Pi pour le valider ne peut etre qu'une seule personne parmi les 100. TOut ca ca fait un beau bordel de proba de succés :)


Posted by: scelerat

Citation:
Posté par Patastronch
Arg grilled ! mais bon j'ai comtpé 198 et pas 197 t es sur de toi ? je revérifie

Ca depend comment on compte. Moi, j'ai suppose que P0, a sa premiere visite, initialisait le compte a 0 et eventuellement eteignait la lumiere si elle etait allumee. Ca assure qu'il ne compte que des prisonniers, en en ratant eventuellement un.


Posted by: scelerat

Citation:
Posté par Flodelarab
Non. Si l'ampoule est éteinte, la première solution marche et il ne compte pas 197 mais 99. Revois ta copie.

Mon "Non, l'ampoule est eteinte " etait une reponse a "Est-ce clair ?", pas une hypothese de travail


Posted by: scelerat

Citation:
Posté par Patastronch
Bon maintenant au moins on est tous d'accord, plus qu'a trouver l expression de P(M) :p

A mon avis, ca s'ecrit Somme pour toutes les decompositions de M en somme de 99 entiers > 1 de la probabilite pour que le deroulement soit tel que le j-ieme cycle dure le j-ieme terme de la decomposition. Un cycle etant defini comme le temps entre deux visites de P0 ou il eteint. La probabilite que le cycle j dure m est quelque chose comme \sum_{k=1}^{m-1} \left( { \frac{j}{100} \right)^{k-1} \frac{100-j}{100} \left( { \frac{99}{100} \right)^{m-k-1}\frac{1}{100}
(k-1 qui ne vont pas allumer, un qui allume, m-k-1 qui ne sont pas P0, P0).
Il n'y a plus qu'a simplifier les formules...


Posted by: Flodelarab

Citation:
Posté par Patastronch
presque, la proba d'un succés n'est pas constante, puisqu'il ne doit pas forcément en choisir un en particulier.
Vrai! Je suis allé trop vite.


Posted by: juliengoestony

C'est simple et génial.










-