Les prisonniers ( remake )

par **bruce.ml** » 12 Oct 2007, 19:38

Nous retrouvons nos 100 prisonniers condamnés à mort. Le directeur de la prison propose un nouveau challenge à nos prisonniers :
1) il leur attribue à tous un numéro entre 1 et 100
2) il installe dans son bureau une armoire avec 100 tirroirs, dans chaqun desquels il met aléatoirement un et un seul numéro entre 1 et 100. Chaque numéro apparait une et une seule fois.
Il propose à chaque prisonnier de venir ouvrir 50 tirroirs de son bureau, pour regarder le numéro qui est dedans. Les prisonniers ne peuvent pas communiquer entre eux, ni changer les numéros de place, ni laisser un tirroir ouvert, ni coller un chewing gum sur l'interrupteur de la lampe ...
De deux choses l'une :
- Tous les prisonniers ont trouvé leur numéro en ouvrant les tirroirs auxquels ils avaientt le droit : ils sont tous graciés.
- Sinon, ils sont tous exécutés.

Un probabiliste dans le groupe des prisonniers dit : "aie aie aie ! on est mal : 1 chance sur 2^100 de s'en sortir". A-t-il vraiment raison ? n'y a-t-il pas un moyen d'augmenter cette probabilité ?

par **scelerat** » 13 Oct 2007, 09:20

Le directeur interrompt-il la procedure si un prisonnier ne trouve pas son numero ?

par **bruce.ml** » 13 Oct 2007, 09:54

Si c'est le cas ils seront de toute façon tous exécutés, donc ça ne change rien.

par **aviateurpilot** » 13 Oct 2007, 10:26

1 chance sur 2^100 de s'en sortir

il n'a pas raison
la probabilité de s'en sortir est

est il est impossible d'augmenter cette probablité.

par **bruce.ml** » 13 Oct 2007, 11:11

Je ne comprends pas d'où tu sors cette formule, chaque prisonnier a 1 chance sur 2 de trouver son numéro en ouvrant aléatoirement les tirroirs auxquels il a le droit, donc le groupe a 1 chance sur 2^100 de s'en sortir en ouvrant les tirroirs de façon aléatoire. Et il est possible de faire beaucoup mieux.
Pour que vous sachiez un peu mieux vers quoi vous orienter, je vous donne la probabilité : environ 1 chance sur 3 de s'en sortir.

par **bruce.ml** » 13 Oct 2007, 16:41

c'est beaucoup plus facile que les histoires de cercles de coté pi de notre ami emdro :P

par **bruce.ml** » 14 Oct 2007, 00:28

Bon petit indice : le directeur, en rangeant les tickets dans ses tiroirs, a effectué une permutation de {1..100}. Le but de la manoeuvre est de trouver certaines permutations qui ont certaines proprietés, qui apparaissent avec une probabilité pas trop mauvaise, et dans lesquelles on a une technique pour gagner à 100%.

par **scelerat** » 15 Oct 2007, 08:42

bruce.ml a écrit:Si c'est le cas ils seront de toute façon tous exécutés, donc ça ne change rien.

Ca change que si une strategie a ete mise au point entre les prisonniers, chacun saurait qu'elle a marche avec les precedents. Par exemple, mettons qu'un prisonnier de numero pair ouvre les tiroirs pair, et un de rang impair les tiroirs impairs. Le dernier prisonnier sait qu'il va s'en sortir, puisque les 50 tiroirs impairs ont ete ouverts par les 50 prisonniers impairs, donc si c'est arrive jusqu'a lui, les 50 numeros impairs etaient tous dans des tiroirs impairs.

par **bruce.ml** » 15 Oct 2007, 15:22

scelerat a écrit:Ca change que si une strategie a ete mise au point entre les prisonniers, chacun saurait qu'elle a marche avec les precedents. Par exemple, mettons qu'un prisonnier de numero pair ouvre les tiroirs pair, et un de rang impair les tiroirs impairs. Le dernier prisonnier sait qu'il va s'en sortir, puisque les 50 tiroirs impairs ont ete ouverts par les 50 prisonniers impairs, donc si c'est arrive jusqu'a lui, les 50 numeros impairs etaient tous dans des tiroirs impairs.

Mais de toute façon si quelqu'un n'a pas trouvé son numéro avant qu'il entre dans la pièce, il sera exécuté, donc ça ne sert à rien qu'il joue. Mais c'est bien, tu as trouvé une stratégie qui gagne avec une probabilité de 1 sur 2^99, c'est deux foix mieux que l'algorithme naïf :++:

par **scelerat** » 15 Oct 2007, 16:40

bruce.ml a écrit:Mais c'est bien, tu as trouvé une stratégie qui gagne avec une probabilité de 1 sur 2^99, c'est deux foix mieux que l'algorithme naïf :++:

J'ai aussi trouve, mais pas tout seul, la solution (cf. cafe mathematique, http://www.maths-forum.com/showthread.php?t=25239). Elle est quand meme tres difficile a decouvrir pour qui n'a pas en tete certaines caracteristiques des permutations, et pour moi-aussi donner un indice, je dirais qu'il faut que le prisonnier se fasse guider d'une certaine maniere par le directeur dans son choix des tiroirs a ouvrir.

par **Imod** » 15 Oct 2007, 18:21

Salut à Fahr au passage :we:

Imod

par **bruce.ml** » 15 Oct 2007, 18:26

Mince j'étais certain que ça aurait déjà été posé ... malgré mes recherches infructueuses sur le forum avant de post :P

par **bruce.ml** » 15 Oct 2007, 18:32

mais au passage il n'a pas été prouvé que cette solution était optimale :P et ça, ça doit être rudemement difficile !

par **Imod** » 15 Oct 2007, 18:36

bruce.ml a écrit:mais au passage il n'a pas été prouvé que cette solution était optimale et ça, ça doit être rudemement difficile !

Je n'ai même pas essayé :we:

Imod

par **Flodelarab** » 15 Oct 2007, 18:52

aviateurpilot a écrit:il n'a pas raison
la probabilité de s'en sortir est est il est impossible d'augmenter cette probablité.

légère imprécision:

On retrouve bien le 1/2

par **alben** » 16 Oct 2007, 09:52

bruce.ml a écrit:mais au passage il n'a pas été prouvé que cette solution était optimale et ça, ça doit être rudemement difficile !

Bonjour,
Merci d'avoir posté cette enigme qui est vraiment très belle, j'avais raté celle lancée par Fahr.
Optimale par rapport à quel critère ? On présuppose que toutes les permutations sont équiprobables, ce qui n'est certainement pas vrai, ne serait-ce que parce que le gardien ne va pas proposer l'identité. En revanche, s'il est très malin (ou très paresseux) il va se contenter d'une permutation circulaire, ce qui garantit l'échec total de la stratégie proposée.
D'ailleurs, dans le cas où le gardien choisit au hasard sans tricher, il est à peu près certain qu'il voudra éviter les points fixes et les cycles trop courts. Sous cette hypothèse, la proba que la stratégie soit gagnante se trouve divisée par deux, ce qui reste quant même beaucoup mieux que les 10^-30 initiaux

par **bruce.ml** » 16 Oct 2007, 10:42

Toutes les permutations ne sont pas equiprobables non, mais on en prend une au hasard. Si le directeur joue le jeu il prend ses 100 tickets, il les mélange, et les fout dans un tirroir :)

par **scelerat** » 16 Oct 2007, 10:49

alben a écrit:D'ailleurs, dans le cas où le gardien choisit au hasard sans tricher, il est à peu près certain qu'il voudra éviter les points fixes et les cycles trop courts.

Il suffit aux prisonniers de se reaffecter des numeros entre eux au hasard,, et d'aller non pas la boite k, mais au numero n(k) affecte au prisonnier k, cela garantit que la permutation resultante est aleatoire (mais ca demande que tous les prisonniers aient une bonne memoire).

On peut meme se demander s'il est possible de choisir une permutation qui "brise" probablement plus de longs cycles qu'elle n'en cree...

par **Imod** » 16 Oct 2007, 14:03

scelerat a écrit:Il suffit aux prisonniers de se reaffecter des numeros entre eux au hasard,, et d'aller non pas la boite k, mais au numero n(k) affecte au prisonnier k, cela garantit que la permutation resultante est aleatoire (mais ca demande que tous les prisonniers aient une bonne memoire).

En effet le dernier mot est toujours aux prisonniers et ce que fait le gardien est sans importance ( sauf s'il a eu vent d'une stratégie des prisonniers et qu'il veut la contrecarrer ) .

Imod

par **imbe6le** » 16 Oct 2007, 19:45

Le premier prisonnier ouvre les 50 boites et met tous les numéros dans la premiere boite, le second ouvre les 50 autres et met aussi tous les noms dans la premiere boites, comme ca tous les autres trouverons leurs numero dans la première boite

Les prisonniers ( remake )

Les prisonniers ( remake )

Qui est en ligne