stratégie de vie sauve

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





Posted by: fahr451

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.


Posted by: Imod

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


Posted by: fahr451

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.


Posted by: Imod

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


Posted by: fahr451

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.


Posted by: Imod

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


Posted by: sandrine_guillerme

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 :/


Posted by: sandrine_guillerme

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

merci d'avance .


Posted by: BancH

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?


Posted by: sandrine_guillerme

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 .


Posted by: fahr451

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


Posted by: Imod

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


Posted by: fahr451

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.


Posted by: sandrine_guillerme

tu as recu mon MP fahr451?


Posted by: sandrine_guillerme

caché alors


Posted by: Imod

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


Posted by: fahr451

-> 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.


Posted by: Imod

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


Posted by: sandrine_guillerme

Je suis super contante Merci fahr pour l'énigme


Posted by: fahr451

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.


Posted by: Imod

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

C'est exactement ce que j'ai dit en ajoutant que le choix devait se faire en fonction de la position du prisonnier . L'indice "fait la même" chose sous-tend un mécanisme qu'il serait bon de comprendre chacun suivant son rang ne fait pas "exactement" la même chose .

Imod


Posted by: fahr451

je donne la solution imod ?


Posted by: sandrine_guillerme

vous savez que le problème peut être étendue ..

tu peux travailler avec uniquement 4 prisonniers ..


Posted by: fahr451

on peut travailler avec 2n prisonniers n étant qq ,


Posted by: sandrine_guillerme

J'ai pas suivi ce que vous vous dites les gas .. mais pour fahr .. si on travaille avec 4 prisonnier ceci nous done 24 répartitions possible en fait .. dans 10 gagnantes ..


Posted by: Imod

Non , laisse moi un peu de temps ( ainsi qu'aux autres ) , je suis un peu lent à m'imprégner d'un problème mais j'aime ça

Imod


Posted by: fahr451

absolument sandrine 5/12 dans ce cas est la proba de vie sauve.
sandrine parle trop!


Posted by: sandrine_guillerme

Bon ok .. nickel ..

euh il fallait pas que je parle ? je croyais que tu me demandais de faire les détails moi
Bon désolée


Posted by: BancH

Avec deux prisonniers, on voit bien le principe de la stratégie:

A dit à B "Je prends la 1, tu prends la boîte 2".

-A prend la 1 il perd => exécution
-A prend la 1 il gagne => B gagne => vies sauves

D'une probabilité de 25% de sauver sa peau, on atteint 50% avec une stratégie.


Posted by: BancH

Citation:
Posté par fahr451
absolument sandrine 5/12 dans ce cas est la proba de vie sauve.
sandrine parle trop!
Je ne trouve pas pareil:

Si A choisis 1,2
B 3,4
C 1,2
D 3,4

Alors les probabilités sont 1/2 pour A, 2/3 pour B, 1/2 pour C et 1 pour D.

P=1/6


Posted by: fahr451

banch 1/6 <5/12 donc ta stratégie n'est pas la meilleure.


Posted by: BancH

Oui je vois, mais comment trouvez-vous 5/12?


Posted by: fahr451

c'est en fait la réponse à la question du problème pour n = 2 ( 4 prisonniers)
la méthode étant exactement la même pour 100 prisonniers.


Posted by: BancH

Oui mais avec en quoi consiste la tactique?


Posted by: BancH

C'est celle d'Imod?


Posted by: fahr451

si tu fais référence à le 1er choisit les 50 premières boites le second de la 51ième à la 100ième la réponse est NON car ce que choisirait le second dépendrait de ce qu'a choisi le premier ( prendre les autres) CE N'EST PAS le cas
chaque prisonnier fait "son " choix (lorsqu'il a l 'occasion de choisir)indépendamment des choix des autres.
PS banch es tu en 1iere ? si oui tu n'as pas a priori les connaissances pour trouver.


Posted by: Imod

Oui , la stratégie de BancH n'est rien d'autre que celle que j'avais proposée , elle n'est sûrement pas celle qui exploite au mieux les choix précédents , une permutation circulaire semble plus adaptée ( mais est-ce la meilleure stratégie ) ?

Je vais regarder dans les cas plus simples .

Imod


Posted by: fahr451

Imod se rapproche :) d'autre part je n'ai pas affirmé que c'était la meilleure stratégie j'ai juste dit qu'elle donnait une proba de vie sauve de 1-ln2 ( à qq centièmes pour 100 prisonniers) 1-ln2 à comparer à 1/2^100 ...


Posted by: BancH

Citation:
Posté par fahr451
PS banch es tu en 1iere ? si oui tu n'as pas a priori les connaissances pour trouver.
Arf, normalement les exos comme celui-ci ça nécessite seulement la logique et le raisonnement.

Mais les prisonniers peuvent quand même se dire "toi tu prendras ces boîtes, toi celles-là, moi ...." ?


Posted by: fahr451

je suis d 'accord banch je dirais même avant même que le premier prisonnier commence son choix les 100 prisonniers savent exactement ce que chacun d'entre eux va faire .


Posted by: BancH

Vous dites que le maximum avec quatre prisonniers c'est 5/12?


Posted by: fahr451

c'est la proba avec la stratégie que je propose; la même stratégie qui donne à peu près 1-ln2 pour 100


Posted by: Imod

Une tentative de formalisation du problème ( je ne sais pas si celà apporte grand chose ) . I=\{1;2;...;100\} et pour tout i\in I , A_i une partie de I à 50 éléments . \displaystyle{A=\prod_{i=1}^{100} A_i} et G_A=\{f\in \sigma_{100} / \forall i \in I , f(i)\in A_i\} . Le problème est de trouver un élément A rendant card(G_A) maximal .

Imod


Posted by: fahr451

-> imod on parle de permutation ça se réchauffe.


Posted by: Imod

Oui , le passage par les permutations me semble une bonne piste ( et ma formulation vraiment lourde ) j'ai du mal à me libérer suffisamment de temps pour réfléchir sérieusement au problème et c'est dommage car il est vraiment intéressant .

A bientôt , Imod


Posted by: fahr451

pour résumer on en est là:
Les boites sont (moralement) numérotées de 1 à 100.
Les prisonniers sont numérotés de 1 à 100 (ds l'ordre alphabètique).
L'expérience aléatoire est donc le choix (par le bourreau) d'une disposition des 100 numéros ds les 100 boites ; un résultat est donc une permutation
d e 1 ,100 ; l'ensemble des résultats étant muni de l équiprobabilité.Il y a 100! résultats.


Posted by: Imod

Oui fahr451 , le problème est clairement posé , il n'y a plus qu'à en trouver la solution .

Imod


Posted by: fahr451

la solution est la suivante:
le prisonnier 1 se rend à la boite 1 il ouvre la boite regarde le nombre k écrit sur le papier , se rend à la boite k etc ..
Il décrit donc l'orbite de 1 sous la permutation Il sera en sursis ssi il tombe sur 1 en au plus 49 itérations donc ssi l'orbite de 1 est de cardinal inférieur ou égal à 50
le prisonnier deux fera exactement la même chose il ira a la boite 2 etc
Les prisonniers seront saufs ssi toutes les orbites sont de cardinal =< 50
donc ssi la permutation ne comporte pas ds sa décomposition de cycle de longueur >50.
pour k>50
on compte les permutations ayant un cycle de longueur k
comme il y a 100 prisonniers il n ' y a qu 'un tel cycle.
On choisit le cycle :on se donne un arrangement de k parmi 100 il ya
A(100,k) façons de le faire mais par invariance par rotation il ya
A(100,k) /k tels k cycles (principe des bergers) et ensuite on se donne une permutation qq des (100-k) autres éléments.

la proba qu' une permutation ait un cycle >50 est donc

sigma (k=51;100) de A(100,k)(100-k)!/(100!k) = sigma 1/k
en utilisant soit une somme de riemann soit le dv de la somme partielle de la
série harmonique cette quantité vaut ln2 (à qq centièmes cv en 1/n)
la proba cherchée est donc 1-ln2.


Posted by: Imod

Vraiment machiavélique , j'aurais pu y passer des heures sans aboutir . Vraiment un beau problème !!!

Imod


Posted by: Kerdy

Faut il encore que les prisonniers soient intelligents (peut être un prof de maths dans le groupe qui aurait maltraité un élève )


Posted by: fahr451

:)

on peut aussi imaginer un régime totalitaire où les "dissidents" font quelquefois des maths.


Posted by: Imod

Pour fahr451 .

J'ai soumis ton problème au site Les Mathématiques.net où il a reçu je pense l'écho qu'il méritait ( Domi = Imod ) . Je me répète sûrement mais c'est un magnifique problème et grande honte au site à qui tu l'avais proposé sans réponse .

Encore merci , Imod


Posted by: fahr451

:)

c'était ici :) mais dans une mauvaise rubrique


Posted by: sandrine_guillerme

oué, je crois que tu l'avais posté dans supérieur, je m'e suis rendu compte qu'après un moment ..




Posted by: fahr451

ben oui ... y en a bien qui postent sur le théorème de fermat ds la section primaire...


Posted by: Imod

Je suis quand même surpris que le problème posté dans "supérieur" n'ai pas eu d'écho , je le survole ( depuis peu ) il est plutôt bien fréquenté et je vois mal comment tout le monde a pu passer à côté d'un tel problème .

Imod


Posted by: fahr451

Peu de temps après avoir vu ce problème j'en ai parlé à une personne fort susceptible de le trouver comme moi superbe, sa réaction fut (avant même la fin de l énoncé) : " c'est tellement artificiel..."


Posted by: Imod

farh451 ,

faire des maths c'est utiliser continuellement des artifices ou bien réciter sa leçon en boucle . Plus c'est astucieux et plus c'est joli et m... à ceux qui pensent le contraire

Imod










-