Exo sur les permutations

[lol37]

Salut.
Y'a t'il quelqu'un qui pourrait me donner un exercice sur tout ce qui touche au groupe symétrique ( et alterné ? il faut que ce problème soit appliqué aux cas concret ( résolution de casse tête ... si résoluble ou pas )
Merci énormément d'avance à ceux qui voudront bien prendre la peine de m'aider

[alavacommejetepousse]

bonsoir

cent prisonniers tous enfermes initialement dans une meme piece vont sans doute mourir

les geoliers ont disposé cent boites dans chaque boite le nom d un prisonnier different

le premier prisonnier choisit cinquante boites s il n y trouve pas son nom tous les prisonniers seront executes s il le trouve il est mis de cote sans moyen de communiquer avec les autres etc etc


les prisonniers seront collectivement sauves si chaque prisonnier trouve son nom
dans le cas contraire ils seront collectivement executes

un prisonier matheux indique qu il y a une strategie qui bie loin des (1/2)^ 100 chances de survie leur assure a peu pres ln 2 chances de rester en vie

bon courage (posté ici par moi même il y a deja des annees)

[Ben314]

Salut,
Je me sent quand même un peu obliger de rajouter que alavacommejetepousse, il y va pas avec le dos de la cuillère : le casse tête est... splendide, mais aussi... trés dur.

Donc, si tu est un peu sec, n'hésite pas à lui demander quelques "indics"...

[lol37]

y'a de la probabilité ?
ps : merci pour le probleme

[Ben314]

y'a de la probabilité ?
ps : merci pour le probleme

Un peu, vu que la réponse est du type "en appliquant cette méthode on a ..% de chance de rester en vie" mais ce qui est le plus difficile est de trouver quelle méthode les prisonnier vont mettre en oeuvre pour avoir le plus de chance possible de s'en sortir...

[lol37]

salut
C'est bien chance ?

[Ben314]

La proba que les prisonniers s'en sortent est d'environ 1-ln(2)
En fait, s'il y avait 2n prisonniers qui ont le droit d'ouvrir n boites chacun, alors, lorsque n->oo, la proba. qu'ils s'en sortent tend vers 1-ln(2)...

As tu trouvé la façon de procéder des prisonniers ?

[lol37]

salut,
je vais essayer de voir comment ils font..

[benekire2]

Personne peut mettre une indic svp ? :doh:

Merci !

[Ben314]

Indice 1 (trés vague) : On peut considérer que les boites sont numérotées 1,2,3,...,100 et que les noms des prisonniers sont un,deux,trois,..., cent.
Indice 2 (plus précis) : On pourra se souvenir que toute permutation se décompose de façon unique en cycles à supports disjoints...

[lol37]

Bon j'avoue la je sèche lol, si quelqu'un n'y voit pas un inconvénient tu peux nous exposer la solution ? ( ou alors si quelqu'un cherche encore : en PM )

[Ben314]

C'est effectivement trés dur.
Je met la strtégie des prisoniers en "blanc" pour le cas où certains cherchent encore.
Attention : l'exo n'est pas fini pour autant, il faut montrer que cette stratégie conduit à une chance de survie environ égale à 1-ln(2) et c'est là qu'intervient le groupe symétrique...
Les prisoniers décident une bonne fois pour toute d'attribuer des numéros aux boites (1 à 100), de "convertir" leur noms en numéro (1 à 100) et d'appliquer la méthode suivante :
Lorsque le prisonier nommé 'k' entre dans la salle des boites, il commence par ouvrir la boite numéro k puis, si sur le papier qu'il y a dedans n'est pas écrit 'k' (i.e. son nom), alors il ouvre la boite dont le numéro est celui écrit sur le papier, puis, si sur le papier qu'il y a dedans n'est pas écrit 'k', il ouvre la boite dont le numéro est écrit etc etc... j'usqu'à ce qu'il tombe sur 'k' (son nom) ou bien qu'il ait épuisé ces 50 essais.
A noter que, avec cette méthode, il est impossible qu'un seul prisonier ne trouve pas son nom : en fait, dés qu'un prisonier ne trouve pas son nom, on est sûr qu'au moins la moitié d'entre eux ne trouveront pas leur nom (pourquoi ?)

Edit : j'ai enfin trouvé comment faire du "vrai" blanc :zen:

[benekire2]

C'est effectivement trés dur.
Je met la strtégie des prisoniers en "blanc" pour le cas où certains cherchent encore.
Attention : l'exo n'est pas fini pour autant, il faut montrer que cette stratégie conduit à une chance de survie environ égale à 1-ln(2) et c'est là qu'intervient le groupe symétrique...
Les prisoniers décident une bonne fois pour toute d'attribuer des numéros aux boites (1 à 100), de "convertir" leur noms en numéro (1 à 100) et d'appliquer la méthode suivante :
Lorsque le prisonier nommé 'k' entre dans la salle des boites, il commence par ouvrir la boite numéro k puis, si sur le papier qu'il y a dedans n'est pas écrit 'k' (i.e. son nom), alors il ouvre la boite dont le numéro est celui écrit sur le papier, puis, si sur le papier qu'il y a dedans n'est pas écrit 'k', il ouvre la boite dont le numéro est écrit etc etc... j'usqu'à ce qu'il tombe sur 'k' (son nom) ou bien qu'il ait épuisé ces 50 essais.
A noter que, avec cette méthode, il est impossible qu'un seul prisonier ne trouve pas son nom : en fait, dés qu'un prisonier ne trouve pas son nom, on est sûr qu'au moins la moitié d'entre eux ne trouveront pas leur nom (pourquoi ?)

Edit : j'ai enfin trouvé comment faire du "vrai" blanc :zen:

Salut le truc qui m'intrigue là dedans (pour l'instant) c'est comment tu fais ce vrai blanc ? Enfin, c'est un vrai faux celui ci , c'est une couleur qui correspond mieux au fond mais je trouve pas laquelle :zen:

Sinon , je réfléchis au problème demain matin, là je peut plus réfléchir à cette heure , enfin disons que mes activités sont limités .