{"word_count": 1358, "character_count": 7542}
L’autre jour, quelqu’un me félicitait pour mon blog, c’était une étudiante en maths, qui disait comprendre certaines choses en probas et en stats (entre autres sur les applications possibles)…. mais pour la théorie des groupes, elle ne voyait toujours pas d’intérêt…J’étais bien entendu ravi que mon blog serve à quelque chose, mais en fait la théorie des groupes peut avoir des applications amusantes (bon, tout dépend aussi de ses centres d’amusement). Par exemple MacGyver pourrait avoir eu besoin de connaître des résultats sur les groupes pour sortir des prisonniers des geôles afghanes…Considérons le gardien de prison sadique qui annonce le “jeu” suivant (Anatole, un collègue ici me l’avait suggéré l’autre jour en me mettant au défi de trouver une solution…. mais faut pas pousser, je suis plus fort que MacGyver ! bon, et il faut dire que le jeu est classique…on le trouve expliqué ici ou là):Tous les prisonniers (disons qu’ils sont 20) se voient attribuer un numéro, entre 1 et 20. Le premier prisonnier est appelé et se retrouve face à 20 portes, derrière lesquelles sont cachés des numéros (allant de 1 à 20 là encore). Il a droit d’en ouvrir 10 (au maximum) et il doit retrouver son numéro. S’il n’y arrive pas,tous les prisonniers sont exécutés (lui compris). S’il y arrive, il n’est pas sauvé pour autant car le commandant appelle le second prisonnier, qui se retrouve à son tour devant les 20 portes, et doit trouver son numéro… Etc.Les prisonniers commencent à paniquer, car tout le monde doit trouver son numéro pour être sauvé. En raisonnant rapidement, un des prisonniers explique qu’un seul prisonnier aurait 50% de chances d’y arriver. Avec deux, comme ils ont tous les deux 50% de chances, on tombe à 25%, etc. Avec n prisonniers, on est à 1/2n, qui est de l’ordre d’une chance sur un million avec 20 prisonniers…. Et qu’ils ont de la chance de n’être que 20 ! Avec 30 prisonniers, ilsauraient une chance sur un milliard de s’en sortir (ce qui est faible, on en conviendra).Mais MacGyver, qui avait pris le cours Théorie des Groupes 101 à l’université (et qui avait R installé dans sa montre digitale) ditpas du tout, j’ai une stratégie qui nous donne environ une chance sur trois de tous s’en sortir (vu comme ça c’est pas terrible, mais par rapport à 1 chance sur un milliard, c’est vachement bien),et accessoirement, cette probabilité ne dépend pas du nombre de prisonnier (tant que l’on puisse ouvrir moitié moins de portes qu’il y a de prisonniers)Bon, sur le moment, les autres prisonniers se fichent du fait que même s’ils étaient 1000 ils auraient une chance sur trois de survivre, ils veulent comprendre la stratégie de Mac… Comme le rappelle Mac, le commandant ne fait que choisir une permutation de , même s’il est sadique (ou parce qu’il est sadique, les profs de maths sont sadiques, tout le monde sait ça). Et toute permutation peut se décomposer en un produit ds combinaisons cycliques (on parle de la décomposition en produit de cycles à supports disjoints, c’est un truc utilise je crois pour les amateurs de Rubik’s cube),Par exemple, considérons la permutation suivante (c’est la première que j’ai eu sous R),Elle se décompose en 5 permutations cycliquesLa plus grande est la dernière, et elle permute sur 7 nombres. Autrement dit, si chacun utilise cette stratégie, il ouvrira au plus 7 portes. Le point important est qu’ils ne peuvent pas être pris dans une autre permutation que la leur, car ils ont pris leur porte, donc au pire, il tire le numéro de la première porte qu’ils ont ouvert… qui est le numéro qu’ils doivent tirer pour survivre ! Regardons sur notre exemple&#62; set.seed(1)&#62; portes = sample(1:n,size=n,replace=FALSE)&#62;  prisonnier=1&#62;  essai = c(prisonnier)&#62;  nessai = 1&#62;  i = porte[prisonnier]&#62;  while(nessai &#60;= 50) {+  essai = c(essai, i)+  if(i == prisonnier) {+  cat(“Le prisonnier”, prisonnier, “a ouvert”, nessai, “portes\n”)+  break; }+  else {+  i = porte[i]}+ n essai =n essai+1 }Le prisonnier 1 a ouvert 4 portes&#62;  cat(“Le prisonnier”, prisonnier, “a ouvert les portes suivantes”, paste(essai[-length(essai)], collapse=” – “), “\n”)Le prisonnier 1 a ouvert les portes suivantes 1 – 6 – 14 – 10soit iciLe prisonnier 1 a ouvert 4 portesLe prisonnier 1 a ouvert les portes suivantes 1 – 6 – 14 – 10Le prisonnier 2 a ouvert 7 portesLe prisonnier 2 a ouvert les portes suivantes 2 – 8 – 9 – 19 – 18 – 17 – 12Le prisonnier 3 a ouvert 2 portesLe prisonnier 3 a ouvert les portes suivantes 3 – 11Le prisonnier 4 a ouvert 5 portesLe prisonnier 4 a ouvert les portes suivantes 4 – 16 – 7 – 15 – 5Le prisonnier 5 a ouvert 5 portesLe prisonnier 5 a ouvert les portes suivantes 5 – 4 – 16 – 7 – 15Le prisonnier 6 a ouvert 4 portesLe prisonnier 6 a ouvert les portes suivantes 6 – 14 – 10 – 1Le prisonnier 7 a ouvert 5 portesLe prisonnier 7 a ouvert les portes suivantes 7 – 15 – 5 – 4 – 16Le prisonnier 8 a ouvert 7 portesLe prisonnier 8 a ouvert les portes suivantes 8 – 9 – 19 – 18 – 17 – 12 – 2Le prisonnier 9 a ouvert 7 portesLe prisonnier 9 a ouvert les portes suivantes 9 – 19 – 18 – 17 – 12 – 2 – 8Le prisonnier 10 a ouvert 4 portesLe prisonnier 10 a ouvert les portes suivantes 10 – 1 – 6 – 14Le prisonnier 11 a ouvert 2 portesLe prisonnier 11 a ouvert les portes suivantes 11 – 3Le prisonnier 12 a ouvert 7 portesLe prisonnier 12 a ouvert les portes suivantes 12 – 2 – 8 – 9 – 19 – 18 – 17Le prisonnier 13 a ouvert 2 portesLe prisonnier 13 a ouvert les portes suivantes 13 – 20Le prisonnier 14 a ouvert 4 portesLe prisonnier 14 a ouvert les portes suivantes 14 – 10 – 1 – 6Le prisonnier 15 a ouvert 5 portesLe prisonnier 15 a ouvert les portes suivantes 15 – 5 – 4 – 16 – 7Le prisonnier 16 a ouvert 5 portesLe prisonnier 16 a ouvert les portes suivantes 16 – 7 – 15 – 5 – 4Le prisonnier 17 a ouvert 7 portesLe prisonnier 17 a ouvert les portes suivantes 17 – 12 – 2 – 8 – 9 – 19 – 18Le prisonnier 18 a ouvert 7 portesLe prisonnier 18 a ouvert les portes suivantes 18 – 17 – 12 – 2 – 8 – 9 – 19Le prisonnier 19 a ouvert 7 portesLe prisonnier 19 a ouvert les portes suivantes 19 – 18 – 17 – 12 – 2 – 8 – 9Le prisonnier 20 a ouvert 2 portesLe prisonnier 20 a ouvert les portes suivantes 20 – 13En adaptant un code développé ici par Matt Asher, on peut d’ailleurs visualiser tout ça sur un petit dessin,,Bref, la grande question est “quelle est la probabilité que la plus grande sous permutation cyclique soit sur un ensemble de taille supérieure à 10” ? On peut faire un peu de Monte Carlo pour voir…. c’est ce que fait Matt. Mais sinon on peut aussi faire du dénombrement (ce qui est pareil que les probas). Le nombre de permutations contenant un cycle de longueur supérieure à 10 (strictement) se calcule de la manière suivante: soit k la taille du cycle, alors je peux choisir les  nombres de  manières. Il y a alors  permutations circulaires de ces k nombres, et on permute les  nombres qui reste comme on veut, ce qui donne  possibilités. Bref, j’en suis àpermutations ayant un cycle de longueur k, soit en tout,Or comme on a en tout  permutations possibles, la probabilité de s’en sortir vivant estEt là où Mac est fort, c’est qu’effectivement, avec n prisonniersSoit environ 30% de chances de s’en sortir….Moralité, la théorie des groupes peut être marrante et intéressante…. Bon, c’est la seule application à la vraie vie qui me vient à l’esprit, et à moins d’être enfermé en prison avec un geôlier sadique, c’est dur de trouver des applications. N’empêche que la solution est passionnante (mais MacGyver a toujours été mon héros pour ça…)