Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

23 prisonniers et 2 interrupteurs

Bonsoir,

En v'la une autre : je doute que python y soit d'une quelconque utilité, mais gageons qu'elle plaira notamment à freddy et qu'elle plairait à Barbichu...

23 prisonniers sont un jour transférés vers une prison dans les Everglades en Floride.
A leur arrivée, le gardien les y accueille et leur tient ce discours :
<< Vous avez la journée pour vous concerter et échafauder un plan. Mais à partir de demain, vous serez maintenus  isolés les uns des autres, chacun dans une cellule, sans moyen de communication possible. >>

<< Dans la prison se trouve une pièce vide qui contient 2 petits leviers étiquetés A et B, chacun d'eux pouvant prendre deux postions : ON et OFF... Ces deux leviers sont actuellement tous deux positionnés en OFF et ne sont reliés à rien du tout ! >>

<< A partir de demain, de temps en temps, selon mon humeur, je choisirai un prisonnier au hasard et je le conduirai à la salle des leviers. Là, il devra obligatoirement modifier la position d'un levier et d'un seul, puis je le reconduirai à sa cellule. >>

<< Personne ne pénétrera dans la dalle des leviers jusqu'à ce que j'y conduise un autre prisonnier. et il devra faire la même chose : modifier la position d'un levier et d'un seul. >>

<< Je choisirai à chaque fois un prisonnier au hasard, je pourrai choisir le même 3 fois de suite comme je pourrai tout aussi bien venir jusqu'à la porte d'une cellule, changer d'avis et repartir (*) >>

<< Mais après un temps suffisamment long, vous serez tous passés dans la salle des leviers... A tout moment n'importe lequel d'entre vous pourra me dire : nous sommes tous passés au moins une fois dans la salle des leviers ! >>

<< Si c'est vrai, alors vous serez tous libres ; si c'est faux, vous serez jetés aux alligators ! >>

<< Réfléchissez bien ! >>

Quel plan suggérez-vous d'adopter ?

(*) Ma traduction de l'anglais : I may jump around and come back.
     J'ai essayé les traductions en ligne : il y a de quoi rire...
     Même mon Harraps ne connaît pas : to jump around, ni les dicos en ligne...

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : 23 prisonniers et 2 interrupteurs

Salut,

en effet, ça a l'air très sympa, mais je pense que d'autres prendront aussi du plaisir à cherche la bonne stratégie.

Pour les mariés, j'ai eu le temps tout à l'heure de faire le schéma ... Maintenant, place à l'étude !

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : 23 prisonniers et 2 interrupteurs

Salut à tous.

Déjà , pour commencer, le temps joue en leur faveur dans le sens . Patience et longueur de temps font.....

Maintenant , il y a 4 états possibles des 2 leviers.   off-off => 0-0 , off-on => 0-1 , on-on => 1-1 & on-off =>1-0

  s'ils conviennent de la stratégie suivante : le premier qui rentre devra laisser les leviers dans l'état 1-0
  s'il revient aussitot après il laissera  1-1 , une 3ème fois  à nouveau 1-0 ..1-1..1-0....
  si bien que dès qu'un prisonnier vient pour la première fois il laissera les leviers en 1-0 ou 1-1

  si ce n'est plus le cas , un prisonnier laissera 0-0 ou 0-1 ; si bien qu'il viendra un temps ou les états 1-0  & 1-1
laisseront la place aux états 0-0 & 0-1 qui seront les positions laissées par tous ceux qui seront déjà venus avant.
Donc le temps jouera en leur faveur . et là je crois qu'ils ont tous intéret à faire durer le plaisir parce que , se faire
bouffer par les crocos ...
c'est donc le moins patient qui tranchera .
                                                                            à plus.

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : 23 prisonniers et 2 interrupteurs

Re

   ou alors si je suis dans le lot je postule pour la place de délégué du personnel. par la meme occasion je serai
   le seul à pouvoir appeler le gardien et lui dire que nous sommes tous entrés une fois .

▼Solution

   voilà les ordres que je vais donner:  toute personne entrant la première fois et uniquement la première fois ,
placera le levier A sur on   et personne d'autre ne touchera à ce levier sauf moi quand j'aurais l'occasion d'y retourner. et la je compterai 1 et je le rebasculerai sur 0 .

dès qu'un "nouveau prisonnier" arrive pour la première fois derrière moi et trouve A = off alors il la rebascule
sur on et ce sera à nouveau à moi et à moi seul de le rebasculer sur off et je compterai alors 2

n.b. inutile de préciser que le levierB , lui , est accessible à tout le monde.

finalement , quand j'aurai remis 22 fois le levier A  sur  off je sais alors que tout le monde est
passé.
  Mais ça peut prendre un sacré bout de temps et les crocos sont capables de se bouffer entre eux.

                                                                                                  à plus.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : 23 prisonniers et 2 interrupteurs

Salut,

là , je pense cher JPP que tu as oublié que tu n'iras au maximum que trois fois dans la salle des interrupteurs, donc ...

Cela étant, en relisant l'énoncé, j'ai comme un doute.

Yoshi, je me trompe ?

Dernière modification par freddy (05-10-2011 19:22:08)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : 23 prisonniers et 2 interrupteurs

Salut,

Oui et non...
Je pense que 3 (fois) était un nombre exemple, je pense (je regarderai *) qu'on peut dire plusieurs fois...
Cela dit, je suis d'accord, la solution de jpp est en théorie -probabilistiquement- fonctionnelle mais elle n'offre aucune certitude.
Le "délégué du personnel", si j'ai bien compris, devra être passé 22 ou 23 fois dans la salle des leviers...
Ça fait un peu beaucoup, non, sachant que le gardien peut :
* au gré de son humeur n'emmener personne dans la salle,
* emmener plusieurs fois le même et qu'icelui est obligé de manœuvrer un levier et un seul (et une seule action : lever ou baisser),
et que les gars sont choisis au hasard...

Freddy, il y a quelle probabilité dans ces conditions qu'au bout d'un an :
* lui (=délégué du personnel) soit passé 22 ou 23 fois
* que chacun soit passé au moins une fois

On peut imaginer cette répartition sur 441  jours (plus qu'un an) si la salle est visitée une fois par jour...
20 * 22 +  1 (délégué) :
les 22 d'abord, et lui, la dernière visite !
Mais tout ce qu'il saura c'est que le levier de jpp a été manipulé un nombre pair de fois, ce qui ne prouve rien...

Bon, il est vrai qu'il n'y a pas de durée maxi de donnée...
M'enfin, y en a qui ont le temps de piquer leur crise, de choper "un cactus dans le myocarde" (et aussi le gardien !), et les alligators pourraient aussi se lasser d'attendre et aller bouffer le gardien en guise de hors d’œuvre et là ce serait la cata...

@+

[EDIT] Affutez vos neurones, il y a une 2e version, où l'état des leviers au départ n'est pas connu...

[EDIT 2] Oui, jpp tu es sur la voie, mais la solution est bien plus tordue que ça... Sur les 41 commentaires, aucun ne conteste la solution donnée ;-)
Bon, honnêtement, je n'aurais jamais trouvé, ou alors après 1 an de réflexion..

* 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

Dernière modification par yoshi (05-10-2011 19:50:17)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : 23 prisonniers et 2 interrupteurs

Re,

Bon, j'ai poussé un peu...
Il faut bien un "délégué du personnel" et il doit bien compter les passages...
Sauf qu'avec ton système, il ne lui sera pas possible de savoir exactement combien de personnes sont passées : il aura juste la parité du nombre de manipulations du levier B.

@+

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : 23 prisonniers et 2 interrupteurs

Bonjour Yoshi.

          Relit bien ma solution. c'est moi qui replace sur off. et c'est seulement le prochain nouveau qui replacera A SUR ON.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : 23 prisonniers et 2 interrupteurs

Salut,

Alors, je ne vois pas dans ce cas pourquoi l'auteur de l'énigme a imaginé un truc aussi tordu, ni pourquoi aucun des 41 commentaires n'a émis d'objection.
Quelque chose me gêne dans ta solution, et je n'arrive à pas trouver quoi...

(Vous n'êtes pas obligés de regarder :-) )

▼Solution traduite de l'anglais

1. Désigner un "compteur" parmi les 23, les 22 autres devenant des "transmetteurs"...

2. Tout transmetteur entrant dans la salle des leviers pour la première fois, devra pousser le levier B sur ON, s'il le voit sur OFF
   Par contre, il devra manœuvrer le levier A s'il voit le levier B en position ON et attendre patiemment sa prochaine visite.
   La mission d'un transmetteur est donc de saisir l'opportunité (et une seule fois) de pousser le levier B en position ON.
   Après avoir rempli sa mission, il devra manœuvrer le levier B à chaque prochaine visite
   En résumé, le rôle de chaque transmetteur est de signaler son passage au "Compteur"..

3. Le travail du "Compteur" consiste, lui, à remettre le levier B sur OFF à chaque fois qu'il le trouvera sur ON.
   A chaque fois qu'il remettra B sur OFF, il ajoutera 1 à son compte.
   Si le levier B est déjà sur OFF, il n'y touche pas,  manœuvre le levier A à la place et laisse son compteur de visites inchangé.
   Dès qu'il arrivera à 22, il pourra avertir le gardien de ce qu'il est sûr que tout le monde est passé au moins une fois dans la salle des leviers

@+

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : 23 prisonniers et 2 interrupteurs

Re

▼Il y a un blème.

dans le 2) le transmetteur a pour mission de manoeuvrer une fois B sur ON. et une seule fois. c'est le seul
qui servira au compteur.

par contre dans la traduction il doit y avoir une faille, car dans le 2 il est écrit: "le transmetteur devra manipuler le levier B  à chaque visite. " Alors que c'est ce fameux levier B  qui sert au compteur. Moi , je pense qu'à chaque visite c'est le levier A qui doit etre bougé. car lui , ne sert à rien . il est là uniquement pour le cas ou un nouveau trouve B sur ON
et que le compteur n'est pas encore passé le remettre sur OFF pour qu'un futur nouveau le remette à nouveau sur ON.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : 23 prisonniers et 2 interrupteurs

Salut,

Blème rectifié
Dans le copier/coller et la mise en page pour le forum, une condition avait sauté sans la première phrase du point 2.
Et il y avait un ONE en majuscules sur lequel je n'avais pas assez insisté : j'avais traduit ONE oppotunity, par l'opportunité.
A la réflexion, le l' dû à la suppression du a de l'article défini la pouvait prêter à confusion.
C'est pourquoi, je viens d'ajouter entre parenthèses : une seule fois.
Maintenant, c'est clair : j'ai bien compris la solution. C'est très finaud et simple à la fois...

▼Commentaire

Le levier A dans cette solution, joue le rôle d'échappatoire au cas où le transmetteur aurait déjà fait joujou avec le B, ou s'il ne pouvait jouer avec à cause de la stratégie définie.

Je te présente mes plus humbles excuses.

@+

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : 23 prisonniers et 2 interrupteurs

Bonsoir.

@Yoshi.  tu nous dis qu'il se peut que les positions des leviers A & B ne sont pas connues. cette version est un peu spéciale car le premier visiteur _ il ignore d'ailleur qu'il est le premier_ trouvera le levier A soit sur off soit sur on.

▼Texte caché

ma stratégie reste la meme , par contre comme je suis le compteur , lorsque je vais rentrer , deux cas possibles.
a) le levier A est sur off et là je suis sur d'etre le premier visiteur ; mais je ne peux quand meme pas
fonctionner comme précédemment, parce que avant d'entrer j'ignorais encore cette position.

b) le levier est sur on et là c'est moins marrant car sa position peut etre celle d'origine ou alors le premier visiteur l'ayant trouvé sur off l'a placé sur on .

dans ce second cas comme il y a une incertitude. je vais quand meme compter 1 mais je dois imposer à tous les prisonniers de pointer 2 fois A sur onparce que je ne suis pas sur que le premier basculement a vraiment
eu lieu.

donc en comptant jusqu'à 44  je serai absolument certain qu'au mieux , tous sont passé 2 fois et au pire 21 sont passés 2 fois et le premier une fois .

                                                                                 à plus.

Dernière modification par jpp (10-10-2011 19:11:07)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : 23 prisonniers et 2 interrupteurs

B'soir,

On a laissé passer assez de temps...

▼Solution de l'auteur

Désigner un "compteur" parmi les 23, les 22 autres devenant des "transmetteurs"...

Tout transmetteur entrant dans la salle des leviers pour la première fois, devra pousser le levier B sur ON, s'il le trouve sur OFF. Par contre, il devra manœuvrer le levier A s'il voit le levier B en position ON et attendra patiemment sa prochaine visite.
La mission d'un transmetteur est donc de saisir l'opportunité de pousser (une fois et une seule) le levier B en position ON.
Après avoir rempli sa mission, il devra manœuvrer le levier A à chaque prochaine visite.
En résumé, le rôle de chaque transmetteur est de signaler son passage au "Compteur".

Le travail du "Compteur" consiste, lui, à remettre le levier B sur OFF à chaque fois qu'il le trouvera sur ON.
A chaque fois qu'il remettra B sur OFF, il ajoutera 1 à son compte.
Si le levier B est déjà sur OFF, il n'y touchera pas et  manœuvrera le levier A à la place et laissera son compte de visites inchangé.
Dès qu'il arrivera à 22, il pourra avertir le gardien de ce qu'il est sûr que tout le monde est passé au moins une fois dans la salle des leviers.

@+