Les prisonniers ( remake )

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





Posted by: bruce.ml

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é ?


Posted by: scelerat

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


Posted by: bruce.ml

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


Posted by: aviateurpilot

Citation:
1 chance sur 2^100 de s'en sortir

il n'a pas raison
la probabilité de s'en sortir est 4$ \(\frac{C_{100}^{49}}{C_{100}^{50}}\)^{100}=\( \frac{50}{51} \)^{100} est il est impossible d'augmenter cette probablité.


Posted by: bruce.ml

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.


Posted by: bruce.ml

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


Posted by: bruce.ml

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


Posted by: scelerat

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


Posted by: bruce.ml

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


Posted by: scelerat

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


Posted by: Imod

Salut à Fahr au passage

Imod


Posted by: bruce.ml

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


Posted by: bruce.ml

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


Posted by: Imod

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

Je n'ai même pas essayé

Imod


Posted by: Flodelarab

Citation:
Posté par aviateurpilot
il n'a pas raison
la probabilité de s'en sortir est 4$ \(\frac{C_{100}^{49}}{C_{100}^{50}}\)^{100}=\( \frac{50}{51} \)^{100} est il est impossible d'augmenter cette probablité.

légère imprécision:
3$ \(\frac{C_{99}^{49}}{C_{100}^{50}}\)^{100}=\( \frac{50}{100} \)^{100}

On retrouve bien le 1/2


Posted by: alben

Citation:
Posté par bruce.ml
mais au passage il n'a pas été prouvé que cette solution était optimale :P 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


Posted by: bruce.ml

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


Posted by: scelerat

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


Posted by: Imod

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


Posted by: imbe6le

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


Posted by: Patastronch

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


Posted by: Flodelarab

Citation:
Posté par Patastronch
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 ...
Je rappelle à nos chers mathématiciens qu'un type en prison est un type qui a violé au moins une fois les lois. Ce n'est donc pas un problème insurmontable pour eux.
Je n'ai lu nulle part que les prisonniers avaient été jugés à Outreau .........


Posted by: Patastronch

Citation:
Posté par Flodelarab
Je rappelle à nos chers mathématiciens qu'un type en prison est un type qui a violé au moins une fois les lois. Ce n'est donc pas un problème insurmontable pour eux.
Je n'ai lu nulle part que les prisonniers avaient été jugés à Outreau .........


Dans ce cas j'ouvre les 100 tiroirs moi !


Posted by: Flodelarab

Citation:
Posté par Patastronch
Dans ce cas j'ouvre les 100 tiroirs moi !

OUI !!!!
Je relie les poignées par une ficelle et je tire 1 fois. Rien a me reprocher


Posted by: Joker62

Moi je bute le dirlo :D


Posted by: Imod

A-t-on le droit de se faire tatouer le plan de la prison sur le corps ?

Imod


Posted by: Flodelarab

J'espère que ce site est légal car si on se retrouve tous en prison, on n'a pas fini d'emmieller les geôliers


Posted by: juliengoestony

Et aller dans l'ordre croissant.

Le 1er prisonnier ouvre les tiroirs 1à 50.
Le 2eme prisonnier ouvrre les tiroirs 2 à 51.
Etc



Avec l'espoir que les numéros soient disposés dans l'ordre et commencent dans un des 50 premiers tiroirs.


Posted by: bruce.ml

C'est un peu mieux que les 1/2^99 mais c'est toujours très loin des 0.33 dont j'ai parlé !


Posted by: juliengoestony

Les prisonniers ouvrent tous le 1er tiroir. Quand l'un d'eux à trouvé, il passent au tiroir suivant.

(il y a là une forme de communication puisque on voit le prisonnier passer au tiroir suivant)


Posted by: juliengoestony

Le directeur a une pile de numéros très peu mélangée. Ils avance du tiroir 1 au tiroir 100 (ou recule) histoire de ne pas se fatiguer à faire des allez-retours. Bref une situation des plus habituelles.
Tantôt il prend le numéro du dessus de la pile, tantôt il prend le numéro du dessous.

Alors:
le prisonnier no 1 ouvre les tiroirs 1 à 25 et 100 à 75
le prisonnier no 2 ouvre les tiroirs 1 à 25 et 100 à 75
le prisonnier no 3 ouvre les tiroirs 2 à 26 et 99 à 74
le prisonnier no 4 ouvre les tiroirs 2 à 26 et 99 à 74
etc.

Ca ne marche évidemment pas avec une pile totalement mélangée. D'ailleurs je n'arrive pas à croire qu'il existe une technique dans ce cas-là.


Posted by: bruce.ml

Les numéros sont parfaitement aléatoirement mélangés !


Posted by: juliengoestony

J'abondonne.

Ma réponse du 1er nov. me semble la seule applicable.


Posted by: Rain'

Si on a deux prisonniers, 4 tiroirs dont 2 à ouvrir par chacun.

Le premier choisit aléatoirement, sans nuire à la généralité, il choisit les tiroirs 1et 2. On considère que le deuxième sait ce que va faire le premier.

Si le premier n'a pas trouvé son numéro, ils vont mourir et ça on peut rien y faire.

Si le premier a trouvé son numéro, le deuxième a tout intérêt à ne pas le retrouver , ce qui lui ferait perdre une de ses deux chances.

Ainsi si par exemple le premier a ouvert les tiroirs 1 et 2 et que son numéro est dans le tiroir 2, le deuxième a tout intérêt a ouvrir 1,3 ou 1,4 ou 3,4. Or il ne sait pas si le premier a trouvé son numéro dans le tiroir 1 ou dans le tiroir 2 donc il ne sait pas s'il doit choisir entre 1,3 ou 1,4 ou 3,4 d'une part ou alors 2,3 ou 2,4 ou 3,4 d'autre part.

Tout ça pour dire qu'il a intérêt à ouvrir les boites 3 et 4.

Ainsi le premier a une chance sur 2 de trouver et le second a 2 chances sur 3 de trouver son numéro si le premier a trouvé le sien.

Soit 1/3 et pas 1/4.

Y a plus qu'à passer à 100 personnes, je reviens tout à l'heure.


Posted by: bruce.ml

Bon je vais donner ma solution puisque certaines personnes ne sont pas capables de suivre un lien .

Chaque prisonnier fait ceci : il regarde son papier, où il voit le nombre n. Il ouvre le tiroir n, et regarde le nombre n1 qui est dessus, puis il ouvre le tiroir n1 etc.
Un prisonnier trouvera son numéro si le cycle auquel ce dernier appartient dans la permutation des nombres est d'ordre inférieur à 50.
Or une permutation d'ordre 100 a tous ses cycles de longueur inférieure à 50 dans environ 1/3 des cas.


Posted by: Imod

Une solution est fournie depuis le 15/10 par scelerat dans son lien message #10 . Tout ça est un peu suréaliste

Imod










-