Enigme de prisonniers (pour changer)

[obi76]

Bonjours à tous,

Une petite énigme que j'ai trouvé amusante, en espérant qu'elle n'ai pas été déjà postée...

Je me lance :

Dans une prison, il y a 100 prisonniers. Le problème, c'est que la surpopulation guette (hé oui ^^), donc le directeur de la prison a trouvé une solution.

Il met les 100 prisonniers dans une salle, puis les appelle chacun leur tour dans une pièce annexe. Dans cette pièce se trouvent 100 boites, contenant chacune le nom d'un prisonnier (on considère qu'ils ont tous des noms différents).

Lorsqu'un prisonnier rentre dans cette pièce, il choisi 50 boites.

- Si dans ces 50 boites se figure son nom, alors il est mis de côté et on passe au suivant.
- Si son nom n'y figure pas, tous les prisonniers sont morts (les 100).

On eut en conclure que chaque prisonnier a une chance sur 2 que son nom apparaisse. Il faut que les 100 prisonniers y arrivent, ce qui leur fait une chance de survie de (1/2)^100, donc une chance sur 100000000000000000000000000000 0. Bref, aucune chance de survie.

Néanmoins ils ont le droit de parler entre eux AVANT de se faire appeler et d'élaborer une stratégie avant que le jeu ne commence. Or, ils ont trouvé une technique permettant d'amener leur chance de survie à 30% (à peu près).

ma question : quelle est-elle ?

Bon courage pour ceux qui s'ennuient
-----

[_Goel_]

De mémoire, je crois que ça a déjà été posé... mais je me souviens plus de la réponse...

[_Goel_]

J'en étais sûr !

Réponse piquée sur un autre topic (à chercher !)

 Cliquez pour afficher

Par "CoucouHibou" :


Pour le calcul, je n'ai qu'une méthode pédestre. Mais allons-y :

Ce que nous devons savoir c'est que le fait de numéroter les boites et les gens implique que la relation boite/gens soit une permutation de n éléments. Yat parle de cycle. En effet, une permutation associe un numéro dans une liste de n numéro à un autre numéro dans une liste de n numéros, et ce de manière bijective. On peut représenter la permutation d'une autre manière : au lieux d'avoir deux listes de n numéros reliés, on n'en prend qu'une, de n numéros fléchés les uns aux autres : une et une seule flèche arrive à chaque numéro, et une et une seule en part. De cette manière, on peut dégager des circuits fermés, de taille plus ou moins grande.

Maintenant, soyons fous, prenons le cas de n personnes

Nombre total de permutations :



Parmis lesquelles (n-1)! permutations circulaires (un seul cycle de taille n).

Nombre de cas ou la permutation présente un cycle de grandeur p :



C'est à dire qu'on enlève n-p numéros au hasard (1e terme) qu'on permute n'importe comment (deuxième terme : toutes les permutations de n-p) et on fait un cycle avec les p numéros restant. Attention, cette expression n'est valables que si p est supérieur à n/2, dans ce cas il existe un et un seul cycle de taille p dans les permutations.

Maintenant faisons la somme pour p variant de n/2 à n, divisons par n!, le résultat est :



Où R est la probabilité que la permutation correspondant à la numérotation choisie par le mathématicien ne comporte pas de cycle plus grand que n/2. R tend vers ln(2) pour n grand puisque pour tout t réel strictement positif :

[obi76]

mea culpa...

[A voir en vidéo sur Futura]

[Petithassane]

Bonjour.
C'est bien jolie toutes ces intégrales et factoriels et exponentiels, p, n ,....
Mais ça nous dit pas comment font les prisonniers d' autant plus qu'eux ils n'ont pas fait "math sup".
Alors pour le moment je conseille aux prisonniers, l'émeute avec prise d'otage de ce directeur fou, jusqu'à ce qu'il renonce à sa méthode guillotinesque!

[CoucouHibou]

Bonjour,

ce qui a été proposé ici n'est que la démonstration que la solution donne bel et bien une probabilité de survie de 1-ln(2).

Toute la discussion est là : http://forums.futura-sciences.com/sh...d.php?t=110550

Je peux réexpliciter la solution ici pour n prisonniers :

 Cliquez pour afficher

La solution consiste, pour les prisonniers, à attribuer un numéro entre 1 et n à chacun, et à mémoriser tous les couples nom/numéro pendant la période où ils peuvent discuter.

Pendant cette même période, il faut ensuite qu'ils se mettent d'accord pour définir un protocole pour attribuer des numéros entre 1 et n aux boîtes dans la salle de manière non ambiguë.

Ensuite le test commence...

Chaque prisonnier qui rentre dans la salle va chercher la boîte qui correspond au numéro attribué à son propre nom. Il en sort un nom, qu'il lit. Comme il se rappelle du numéro attribué à ce nom, il va chercher la boîte correspondante, l'ouvre, lit le nom et réitère jusqu'à ce qu'il trouve son nom ou qu'il ait ouvert n/2 boîtes.

La démonstration citée plus haut par _Goel_ a pour but de montrer que, de cette manière, la probabilité de s'en sortir est de 1-ln(2), soit 31% de chances, ce qui est largement supérieur à la probabilité de 1/2ⁿ obtenue en faisant une ouverture aléatoire pour chaque prisonnier.

Cordialement,

Hibou

[invitef2c8fa7c]

Bonjour,

Cette égnime est assez amusante mais il me semble que vous prenez le problème à l'envers... Il est effectivement trivial que les prisoniers on environ 1-ln(2) chances de s'en sortir (quand n tend vers l'infini).

La question intéressante à mon avis est plutôt que ce passe t-il si aucun prisonier ne doit trouver sa boite ( si un seul trouve son numéro tout le monde meurt)? Cette règle du jeu semble duale de la précédente mais cela change pas mal le jeu.

Il y a toujours 1/2^100 de suvivre s'ils procèdent au hasard. Peut-on trouver une stratégie meilleure pour ce jeu?

[invité576543]

Il y a toujours 1/2^100 de suvivre s'ils procèdent au hasard.

Pas plutôt (99/100)¹⁰⁰

Cordialement,

[invitef2c8fa7c]

En fait chacun doit toujours ouvrir 50 boites comme précédemment

[invité576543]

En fait chacun doit toujours ouvrir 50 boites comme précédemment

Désolé, j'avais mal compris. (1/2)¹⁰⁰, d'accord

Cordialement,

[invite986312212]

Bonjour,

Cette égnime est assez amusante mais il me semble que vous prenez le problème à l'envers... Il est effectivement trivial que les prisoniers on environ 1-ln(2) chances de s'en sortir (quand n tend vers l'infini).

je suis impressionné! pour moi ce n'est pas du tout trivial... saurais-tu montrer que cette stratégie est optimale?

La question intéressante à mon avis est plutôt que ce passe t-il si aucun prisonier ne doit trouver sa boite ( si un seul trouve son numéro tout le monde meurt)? Cette règle du jeu semble duale de la précédente mais cela change pas mal le jeu.

Il y a toujours 1/2^100 de suvivre s'ils procèdent au hasard. Peut-on trouver une stratégie meilleure pour ce jeu?

si on interprète la règle ainsi: dès qu'un prisonnier échoue (i.e. trouve son nom) tous sont immédiatement exécutés, ce qui signifie qu'à chaque fois qu'un prisonnier est confronté au choix des boîtes, il sait que les précédents n'ont pas échoué, on peut peut-être trouver une stratégie.
Par exemple: les 50 premiers prisonniers ouvrent les 50 premières boîtes. La probabilité de survivre est 2^{-50}. Maintenant, les 50 suivants savent que les noms des 50 premiers sont dans les 50 dernières boîtes, ils n'ont qu'à ouvrir ces boîtes. La probabilité de survie est donc ramenées de 2^{-100} à 2^{-50}, une amélioration d'un facteur 2^50, ce qui est énorme

[CoucouHibou]

Pour répondre à l'énigme duale, je dirais qu'utiliser la même stratégie que pour l'énigme classique est déjà une meilleure idée que la stratégie aléatoire. En effet les chances de réussites sont de 1/n, puisque la seule manière de survivre dans ce cas c'est lorsque la permutation génère un cycle de taille n ((n-1)! possibilités sur n! permutations au total).

C'est un résultat pas vraiment élégant parce qu'il dépend de n, maintenant je doute qu'on puisse faire mieux, mais ça reste à démontrer.

[Petithassane]

Tout bien réfléchi,
les prisonniers ont fait "math sup". L'histoire se passe dans le futur. Les dirigeants ont décidé d'exterminer les mathématiciens; je ne sais pour quelle raison : prise de tête; empêcheurs de tourner en rond; de gouverner tranquillement...?

Je plaisante, bien sûr, c'est la rubrique ludique.