Stratégie de vie sauve

par **fahr451** » 11 Déc 2006, 14:28

bonjour à tous

j'ai proposé (ce très joli pb à mon sens) autre part sans succès :

100 prisonniers sont en instance d' être exécutés . Le bourreau dispose 100 boites avec dans chaque boite le nom d'un prisonnier.
Chaque prisonnier choisira 50 boites qu'il ouvrira une à une.
Si le prisonnier trouve son propre nom il sera mis de côté, isolé des autres.
Si le prisonnier ne trouve pas son nom tous les prisonniers (les 100) seront exécutés.
Finalement ils auront la vie sauve ssi tous les prisonniers ont trouvé leur propre nom.
Sans stratégie un prisonnier a une chance sur deux de trouver son nom donc la probabilité de vie sauve est 1 sur 2 puissance 100 .
Trouver une stratégie pour que la probabilité de vie sauve soit peu différente de 1-ln2.

par **Imod** » 11 Déc 2006, 15:36

Le problème n'est pas très explicite sur la méthode utilisée pour choisir les boîtes . Si par exemple le deuxième prisonnier voit le choix du premier, il a intérêt à choisir les cinquante autres boîtes puis le troisième celles du premier ... La méthode apporte une petite chance supplémentaire de survie .

Imod

par **fahr451** » 11 Déc 2006, 15:41

les prisonniers ne communiquent pas entre eux un prisonnier ne sait pas ce que le précédent a choisi.Mais en fait (je donne une indication précieuse) Ils font TOUS exactement la même chose.

par **Imod** » 11 Déc 2006, 16:28

Je n'ai pas encore tout à fait compris ce que les prisonniers peuvent ou ne peuvent pas faire , par exemple , ont-il le droit de déplacer les boîtes . Si c'est le cas le nième prisonnier choisi les cinquante premières boîtes puis échange la boîte qui contient son nom avec la (50+n)ième .

Imod

par **fahr451** » 11 Déc 2006, 16:36

les prisonniers ne déplacent pas les boites ne les marquent pas ne renseignent en aucune façon les suivants sur ce qu'il ont trouvé.
Il n ' y a aucune "astuce" ni "truc" c 'est un vrai problème mathématique.

par **Imod** » 11 Déc 2006, 16:57

Peut-on quand même considérer que les boîtes sont numérotées ? Peut-on parler de la première , la deuxième ... qui seront les mêmes pour chacun des prisonniers ?

Imod

par **sandrine_guillerme** » 11 Déc 2006, 16:59

Salut,

Je pensais à ça aussi .. ça ressemble un peu à l'énigme du roi et les 100 prisoniers mais bon dans cette derniers les prisonniers pouvaient dire un seul mot en fait .. donc là je bloque quand m :/

par **sandrine_guillerme** » 11 Déc 2006, 17:07

(si quelqu'un trouve la réponse prière de la cacher) on est tous en train de checher lol )

merci d'avance .

par **BancH** » 11 Déc 2006, 18:45

Peut-on avoir des précisions?

-Les détenus font-ils leur test les uns après les autres?
-Sont-ils dans des salles différentes?
-Si un détenu échoue à son tests, les autres prisonniers sont-ils directement informés ou exécutés?
-Possèdent-ils un repère temporel?

par **sandrine_guillerme** » 11 Déc 2006, 19:16

humm .. je crois avoir trouvé en effet mais je ne suis pas sure .. c'est du pur raisonnement logique .. j'hallucine ..

En tout cas je vais essayer de voir comment je pourrais rédiger ceci ..

et pour BancH :

1/ Oui
2/Là je suppose qu'ils sont dans la même salle .
3/ exécutés d'après ce que j'ai fais !
4/Nan .

par **fahr451** » 11 Déc 2006, 20:56

les boites sont numérotées oui si on veut ;les prisonners le font à tour de rôle si un échoue ils sont tous executés

par **Imod** » 11 Déc 2006, 21:16

Bon je commence à comprendre le problème . Chacun des prisonniers pris individuellement a une chance sur deux de trouver son propre nom mais la stratégie doit être collective ( d'où l'intérêt des boîtes discernables ) . Il est clair que si par exemple tous les prisonniers choisissent les mêmes boîtes ils vont tous périr à coup sûr . Il faut donc que collectivement ils décident du choix de chacun pour maximaliser leur chance de survie . On pourrait par exemple imaginer que le premier choisisse 1;...;50 , le deuxième 2;...;51 etc ... l'idée étant , à chaque étape de faire le meilleur choix possible en prenant comme hypothèse que jusque là on est encore en vie ( ce qui limite les possibilités ) sinon tout choix est vain .

Imod

par **fahr451** » 11 Déc 2006, 21:19

pour aider (car je pense que ce problème est vraiment dur à trouver)

je dirai que tousles prisonniers font "la même chose" sans se soucier du choix des autres.

par **sandrine_guillerme** » 11 Déc 2006, 21:27

tu as recu mon MP fahr451?

par **sandrine_guillerme** » 11 Déc 2006, 21:32

caché alors

par **Imod** » 11 Déc 2006, 21:33

Fahr451 , je vois bien ce que tu veux dire par "ils font tous la même chose" , ils ont mis au point une stratégie commune simple à appliquer mais il faut trouver le ressort du problème . Par exemple si le premier a décidé de choisir les cinquante premières boîtes , le deuxième doit considérer comme acquis que le nom du premier figure dans ces cinquante premières boîtes et faire son choix avec cette hypothèse et ainsi de suite . La réalisation pratique de la stratégie est sans doute très simple mais la découverte du ressort en est la clef .

Imod

par **fahr451** » 11 Déc 2006, 21:40

-> je ne lis pas les mp ( j 'en ignore le fonctionnement mais je ne désespère pas)
-> imod en fait ce que je dis est bcp plus : on peut considérer qu 'un gardien chef (fort en maths) explique à chaque prisonnier la stratégie à adopter
Il dira EXACTEMENT la même chose aux 100 prisonniers.

en fait :
non imod ce que choisit le deuxième prisonnier ne dépend nullement de ce qu' a choisi le 1er prisonnier ; la seule chose qui compte c 'est qu' effectivement le 1er prisonnier a trouvé son propre nom sinon c 'est fini pour tout le monde.

par **Imod** » 11 Déc 2006, 21:59

fahr451 a écrit:on peut considérer qu 'un gardien chef (fort en maths) explique à chaque prisonnier la stratégie à adopter Il dira EXACTEMENT la même chose aux 100 prisonniers. Ce que choisit le deuxième prisonnier ne dépend nullement de ce qu' a choisi le 1er prisonnier ; la seule chose qui compte c 'est qu' effectivement le 1er prisonnier a trouvé son propre nom sinon c 'est fini pour tout le monde.

Je ne suis pas sûr que nous soyons en totale contradiction mais il est sûr que le choix du deuxième utilise le choix du premier ou au moins le fait qu'il y ait eu un premier , si chacun fait le même choix tout le monde meurt à coup sûr . Sans doute la stratégie peut-elle se réduire au rang du prisonnier mais elle en dépend forcément .

Imod

par **sandrine_guillerme** » 11 Déc 2006, 22:07

Je suis super contante Merci fahr pour l'énigme

par **fahr451** » 11 Déc 2006, 22:10

imod :
si l un des 40 premiers échoue le 41 ième prisonnier n'aura pas lieu de choisir quoi que ce soit; on est d'accord ;
"ils font la même chose" signifie non pas qu 'ils choisissent les mêmes boites bien sûr mais que le principe de choix est le même pour tous.
sandrine : j'aimerais les détails de calculs.

Stratégie de vie sauve

stratégie de vie sauve

Qui est en ligne