Bonjour, les prisonniers connaissent-ils leur propre numéro ?

J'ai réfléchi et je propose une piste :

 Cliquez pour afficher

Déjà le prisonnier a raison de dire 1 chance sur 2¹⁰⁰ à la seule condition que le tirage soit équiprobable. Or les prisonniers peuvent élaborer une stratégie, ce qui influe forcément sur les probabilités. Je donne un exemple simple :
-Si la loi était équiprobable, alors dans les 1 chance sur 2¹⁰⁰ on compterait la possibilité que les prisonniers choisissent les 50 mêmes tiroirs, ce qui logiquement dans ce cas là ferait à coup sûr échouer 50 prisonniers.
-Ils suffit que les prisonniers pensent à ça et fassent en sorte que les prisonniers ne choisissent pas tous les 50 mêmes tiroirs, et on a déjà comme nouvelle probabilité : 1/(2¹⁰⁰-1), m'voyez ? :p
La probabilité est donc selon moi très possible à augmenter.

Maintenant intéressons-nous au 1-ln2, il m'intrigue celui-là ! Alors je suis sur 2 pistes à la fois :

La formulation est "probabilité > 1-ln2", peut-être essaie-t-on de nous induire en erreur avec le ln2, en effet je ne vois pas ce que les logarithmes viennent faire là-dedans. Or on sait que 1-ln2 > 0.30, donc serait un moyen de dire qu'on pourrait trouver une probabilité supérieure à 0.30 ? Peut-être essaie-t-on ne nous faire comprendre qu'il est possible d'atteindre 1/3.

Et puis j'ai réfléchis à cette formulation, "1-ln2", ce n'est pas banal. En fait, je me dis que ça ressemble pas mal à l'événement de Bernoulli ou je ne sais plus quoi. Vous savez ? C'est l'événement qui ne peut avoir que 2 issues : Soit c'est bon, soit c'est faux. Le bon a pour probabilité p, et le faux a pour probabilité 1-p.

Cette formulation "probabilité > 1-ln2" pourrait donc nous mettre sur la piste en nous indiquant qu'il faut raisonner avec l'élément contraire. En effet cela veut dire que l'on doit cherche la probabilité de l'événement contraire telle qu'elle soit inférieure à ln2. Or ln2 < 0.7, donc la probabilité de l'événement contraire doit être inférieure à 0.7, peut-être pourrait-elle être 2/3 ?

Mais maintenant demandons-nous ce qu'est l'événement contraire. L'événement que l'on souhaite est : Tous les prisonniers ont trouvé leur numéro parmi les 50 tiroirs tirés. L'événement contraire serait donc : Il y a au moins un prisonnier qui n'a pas eu son numéro parmis les 50 tirés. Il faut faire en sorte que cet événement ne dépasse pas 0.7 de probabilité.

Je cherche, je cherche...

Bien pensé!

Bonjour

 Cliquez pour afficher

C'est un problème difficile proposé par Colmez? (école polytechnique).
La stratégie est la suivante :
On suppose les boites qui contiennent les numeros elles-mêmes numerotées.
Lorsque l'un des condamnés ouvre sa boite, il choisit celle qui porte son numero; s'il a gagné tant mieux, sinon il ouvre la boite qui porte le numero contenu dans la premiere boite qu'il a ouverte, et ainsi de suite. Ainsi, au bout d'un certain temps, le cycle va se refermer, et il ouvrira une boite qui contient son propre numero, et il gagnera.
La question est : Le cycle se refermera-t-il en moins de 50 ouvertures? Quelle est cette proba?

Je crois que Colmez propose cette énigme dans le cadre de la théorie des groupes

A+

Bonjour, j'ai approfondi ma réfléxion :

 Cliquez pour afficher

Je pense que la probabilité de réussite est maximale lorsque tous les prisonniers ont pris chacun une combinaison différente de boîte. Je m'explique :

-Le prisonnier n°1 entre, il tire 50 tiroirs, 2 possibilités :
*Il n'a pas eu le bon numéro, et là le problème est réglé, peu importe ce qui se passe après ils sont tous morts

*Il a eu un bon numéro, et dans ce cas là, si un autre prisonnier prend la même combinaison de tiroirs, alors il n'aura pas 50 chance sur 10, mais plutôt 49 chances sur 100. En effet, puisque le prisonnier précédent aura eu un bon numéro avec cette même combinaison, on est certain que parmi les 50 boîtes il y en a une qui ne va pas pour le prisonnier suivant. Les prisonniers doivent donc se débrouiller pour prendre chacun une combinaison différente de boîte.

La solution la plus simple serait :
-Le prisonnier n°1 prend les tiroirs de 1 à 50.
-Le prisonnier n°2 prend les tiroirs de 2 à 51.
-...
-Le prisonnier n°51 prend les tiroirs de 51 à 100

Là on est un peu coincé, il reste 49 prisonniers à qui il faut trouver des solutions. Et pour maximiser les chances, je pense qu'il faut faire en sorte que chaque tiroir ait été pris un même nombre de fois. Là, sur les 51 premiers prisonniers, le tiroir 1 a été pris 1 fois, tandis que le tiroir 50 a été pris 50 fois, ça ne va pas, donc avec les autres prisonniers on va arranger ça, il faut que chaque tiroir ait été pris 50 fois, donc on peut faire :

Sur les 49 prisonniers restant : les 49 prennent le 1 et le 100, 48 prennent le 2 et le 99, 47 prennent le 3 et le 98, etc...et personne ne prend le 50.
Cela donne :
-Le prisonnier n°52 prend le 1, le 100, du 2 jusqu'au 49
-Le prisonnier n°53 prend le 1, le 100, du 52 jusqu'au 99
-Le prisonnier n°54 prends le 1, le 100, le 2, le 99, du 3 jusqu'au 48
-Le prisonnier n°55 prend le 1, le 100, le 2, le 99, du 53 au 98
-Le prisonnier n°56 prends le 1, le 100, le 2, le 99, le 3, le 98, du 3 jusqu'au 47
-Le prisonnier n°57 prends le 1, le 100, le 2, le 99, le 3, le 98, du 53 jusqu'au 97
-...
-Le prisonnier n°100 prend le 1, le 2, le 3, ..., jusqu'à 25, puis le 100, le 99, le 98, ... jusqu'à 25

Ainsi, tous les prisonniers ont pris des combinaisons différentes de tiroirs, et chaque tiroir a été tiré le même nombre de fois.

Je pense qu'il s'agit là de la probabilité maximale. Maintenant calculons cette probabilité, c'est une autre affaire.

Combien y a-t-il de combinaisons possibles ? 50 parmi 100, non ? Ce qui fait environ 10²⁸. Et combien de combinaisons favorables ? Je dirais la moitié, mais je ne suis pas sûr, à ce moment là la probabilité serait d'environ 1 sur 2, ce serait beaucoup trop énorme !!

Et puis avec mon calcul je ne trouve pas de réponse avec logarithme, ni de 1/3 ou 2/3, comme je l'avais dit dans mon premier post.

Il faut encore que je cherche la probabilité, mais déjà êtes vous d'accord avec le raisonnement ci-dessus ??

Il reste plus qu'à appronfondir

approfondir

Ca veut dire quoi ? Que je ne suis pas sur la bonne piste ? Ou que je n'ai pas du tout assez approfondi ?

Bonsoir à tous

 Cliquez pour afficher

En se concertant, les prisonniers peuvent décider des tiroirs qu'ouvrira le premier qui entrera dans le bureau, puis ceux qu'ouvrira le 2eme etc..
Par ailleurs, pour chacun entrant dans le bureau, on se place dans l'hypothèse où les précédents ont tiré le bon numéro (sinon, de toutes façons, c'est fichu).
S'ils décident que le premier ouvrira les tiroirs 1 à 50, ils ont 1 chance sur 2 de franchir le premier obstacle. S'ils décident que le 2eme ouvrira les tiroirs  51 à 100, ils ont un peu plus de 1 chance sur 4 de franchir les deux premiers obstacles, mais on est déjà au-dessous du seuil imposé de 1-ln(2).
Ca ne marche donc pas comme cela.
Il ne faut donc pas qu'ils décident autoritairement des 50 numéros de tiroirs choisis par chaque prisonnier mais plutôt de ce que celui-ci choisira après le tirage du bon numéro, afin de donner une information supplémentaire à ceux qui suivent.
J'y travaille...

  

Bonsoir

La solution proposé par Ming est en effet la bonne . Le résultat est surprenant mais il date un peu

Imod

En effet, la stratégie de Ming est très bien pensée, bravo !

Bonjour à tous

Je dois être complètement bouché, alors expliquez-moi SVP:

Il me semble que MING ne répond pas du tout à la question: il ne considère pas qu'il y a un ensemble de prisonniers et que tout le problème revient à élaborer une stratégie pour améliorer la probabilité de survie pour le GROUPE ENTIER.
Il semble même considérer qu'il n'y a qu'un seul prisonnier.

Bonjour rogerd,

Je ne prétends pas maîtriser le problème mais, pour ma part, je me suis amusé à écrire un petit programme de simulation que j'ai fait tourné avec un nombre restreint de tiroirs (car, rapidement, le nombre de possibilités devient astronomique).
Et bien, c'est incontestable...
La méthode de Pierre Colmez que ming a cité plus haut donne de meilleurs résultats que n'importe quelle stratégie pré-établie du type :
- le prisonnier p(i) ouvre les tiroirs (t(i,k) pour k de 1 à n/2)
- le prisonnier p(j) ouvre les tiroirs (t(i,k) pour k de 1 à n/2)
- ...

En fait, la méthode de Pierre Colmez augmente légèrement toutes les probabilités individuelles et donc, finalement, augmente confortablement l'espérance de gain du groupe dans sa totalité.

D'autre part, comme aucune information ne circule entre les prisonniers, et comme l'énoncé ne précise même pas si leur ordre de passage est établi et connu avant qu'ils définissent leur stratégie, le tirage aléatoire des tiroirs rend redondant le tirage aléatoire des passages (et inversement). Finalement, il ne reste pas grand chose pour distinguer les prisonniers au moment d'ouvrir les tiroirs (à part peut-être les prisonniers passés avant lui). La méthode Colmez considère qu'ils sont tous équivalents à ce moment là et ne tient pas compte de leur ordre de passage.

Je tiens, au passage, à rendre un petit hommage à Pierre Colmez qui est un mathématicien français contemporain reconnu et un joueur de Go tout aussi reconnu.
J'ai été surpris de le voir cité à l'occasion de cette énigme

Errata :
le 2ème t(i,k) doit être lu t(j,k)

Ah, si... une petite info supplémentaire peut-être...

Mon programme tendrait à montrer (dit avec toutes les précautions possibles) que les meilleures stratégies pré-établies seraient celle du genre :
Les prisonniers 1 à 50 ouvrent tous les tiroirs 1 à 50 et Les prisonniers 51 à 100 ouvrent tous les tiroirs 51 à 100.
Ainsi, toutes les permutations de tiroirs qui ne permutent que les tiroirs 1 à 50 entre eux et/ou les tiroirs 51 à 100 entre eux sauvent le groupe.
Il ne reste plus que les permutations qui échangent au moins un tiroir<51 avec un tiroir>50 pour être fatales... et elles sont encore très nombreuses

Je n'ai pas testé de stratégies qui tiendraient compte de l'ordre de passage car je n'ai pas été capable d'en trouver une qui tiennent la route... Essayez juste d'en formalisé une avec seulement 4 ou 8 prisonniers avant de l'étendre à 100 prisonniers. Moi, déjà avec ces petits volumes, je butte toujours sur des contradictions.

Bonjour Rodival

Si je te comprends bien, tu interprètes ainsi la solution de Ming:
*Chaque prisonnier applique la "méthode Colmez" (c.a.d. suivre le cycle en espérant qu'il boucle avant le cinquantième coup).
*Il n'y a pas d'autre concertation préalable entre les prisonniers.

Pourrais-tu me dire si j'ai bien compris?

Merci d'avance!

Voilà comment je vois le problème :
  
Les tiroirs et les prisonniers sont numérotés de 1 à 100 . Le premier prisonnier prend le message contenu dans le premier tiroir , le lit ,  ouvre le tiroir dont le numéro correspond à celui qu'il vient de lire , lit le nouveau message , ouvre le tiroir  correspondant au numéro qu'il vient de lire ... Il s'arrête quand il découvre son propre nom ou quand il a ouvert 50 tiroirs . Les autres font la même chose en commençant par le tiroir portant leur propre numéro .

On note f(n) le numéro figurant dans le nième tiroir , les messages lus par le nième prisonnier sont f(n) , f^2(n) , f^3(n) , ... , f^50(n) .  
On peut remarquer que si la trajectoire du nième prisonnier boucle alors n est le dernier message lu avant le retour au point de départ , le  prisonnier est donc "gagnant" . Le nième prisonnier trouvera son nom si et seulement si son orbite a un cardinal inférieur ou égal à 50 et les prisonniers sortent gagnant si toutes les orbites de f sont de cardinal inférieur ou égal à 50 .

Il n'y a plus qu'à calculer la probabilité pour que ceci se réalise

Imod      

Ce qui n'est pas si évident que ça...

Mais si quelqu'un est dans un orbite inférieur à cinquante tous les tiroirs de ce cercle sont aussi gagnants...

Si toutes les orbites ont un cardinal inférieur à 50 c'est gagné , sinon c'est forcément perdu pour l'un des prisonniers donc pour tout le monde . Le reste des calculs ne pose pas de problème , on trouve une^probabilité de gain d'environ 0,312 .

Imod

Rebonsoir

>lmod: la probabilité pour qu'une permutation des 100 premiers entiers, choisie au hasard, n'ait pas d'orbite plus grande que 50 est donc de 0,312.
Comment mènes-tu le calcul?

Bonjour rogerd,

Bonjour,

La probabilité qu'une permutation ait une orbite de longueur (il ne peut y en avoir qu'une) est égale à:

.

D'où la probabilité qu'il n'y ait pas d'orbite supérieure à 50:

en utilisant .

Merci jandri

Bonsoir à tous

et merci à lmod, Rodival, Eric1 et Jandri pour leurs éclaircissements.

Le résultat est tellement spectaculaire que j'ai du mal à m'en remettre!

Bonjour,

Ce qui est bizarre c'est qu'en appliqua

appliquant cette méthode avec un nombre de boites de 4, de 6 et de 8, je ne trouve pas de variation de la probabilité de trouver son numéro avant de dépasser la moitié.

Par exemple pour 6 boites :

Il y'a 6! répartitions possible des numéros au sein des boites

Admettons que l'individu ai le numéro 1.
Conformément à la stratégie énoncé par ming il va donc commencer par choisir la boite numéro 1 :

Il y'a donc 5! possibilités pour qu'il trouve du premier coup

Si il ne trouve pas du premier coup alors dans ce cas il y'a 4!*5 possibilités pour qu'il trouve au deuxième coup : si la boite est numéroté 2 il faut que le numéro 1 soit dans la deuxième boite.

Si il échoue il peut encore trouver au troisième essai : et là il y'a 5*4*3! répartitions qui permette ce dénouement.

Au total on trouve donc bien une probabilité de 1/2 qu'il trouve son numéro en appliquant cette stratégie.

Bonjour daxtero,

Ton calcul est juste.
Plus généralement, la probabilité que dans une permutation de prise au hasard le 1 soit dans un cycle de longueur est égale à .

Donc s'il y a boites, la probabilité que l'individu numéro 1 trouve son numéro en au plus tentatives est égale à .

Rien de tel qu'un exemple exhaustif pour essayer d'apréhender le phénomène...

Comparaison de trois stratégies avec 4 tiroirs :

A) Stratégie "Le prisonnier ouvre son tiroir puis le(s) suivant(s)" :
- p1 ouvre t1,t2
- p2 ouvre t2,t3
- p3 ouvre t3,t4
- p4 ouvre t4,t1

Bravo à tous! Vous avez ma reconnaissance ^^. Je vous laisse réfléchir puis ceux qui veulent la réponse vous pouvez me contacter à mon mail

Bonjour,
Je suis nouveau sur ce forum, excusez moi si certaines règles ne sont pas respecte dans mon post
je crois que la probabilité qu'ils soient sauvés est nettement supérieur:
en effet, le nombre total de combinaison est 100!  

et le nombre total de boucle supérieur a 50 est: 99!x50 (car si on cherche un cas avec une boucle de plus de 50 alors ouvre un tiroir le numéro pioché doit être différent de celui du tiroir ce qui fait 99 possibilité, de meme pour le deuxième qui doit être différent des deux premier ce qui fait 98 possibilités...   jusqu'au 50ieme tiroir ou il y a 50 possibilité(100-50)
au 51eme tiroir c'est de nouveau 50les 49 restants + le premier) puis le 52ieme ou il y a 49 possibilités( les 38 restants + le premier)........... ce qui donne (99x98x97x......x3x2) x 50 (du numero 51 ) ce qui fait bien 99!x50

la probabilité kil y ai une boucle de plus de 50 est:
le nombre de cas avec une boucle de plus de 50 divisé par le nombres de cas total

ce qui fait (99!x50)/100 = 50/100 = 1:2   (0,5)

les prisonniers ont donc autant de chance d'y rester que de s'en sortir!!!!!