Heu... je me lance...
L'idée est que l'utilisation de cette stratégie peut décomposer les 40 coffres en plusieurs groupes de coffres (qui bouclent sur eux même). Chaque voleur rentre dans la boucle qui contient son coffre, mais à la plus mauvaise place de cette boucle: le 1er coffre ouvert est celui sur lequel pointe le coffre contenant le nom recherché. Pour trouver son coffre en au plus 20 coups, il font donc que le coffre contenant son nom soit dans une boucle d'au plus 20 coffres.
Autrement dit, tous meurent s'il existe 1 boucle de 21 coffres ou plus (disons X et dans ce cas, X voleurs ne trouveront d'ailleurs pas leur nom)
Or des boucles de taille 21 ou plus (sur 40), il ne peut y en avoir qu'une (à la fois).
La question est donc de savoir combien il existe de boucles d'ordre supérieur ou égal à 21 (toujours sur 40) différentes.
**************
Commençons par dénombrer cas de boucles d'ordre exactement 21. Il en existe A(40/21) (Arrangement de 21 parmi 40) différentes, à ceci près que l'ordre n'est pas totalament aléatoire puisque le dernier élément des 21 est connu. Bref, on en a donc A(40/21) / 20. Et ce indépendemment des 19 autres coffres, qui de leur côté générent 19! possibilités.
On a donc A(40/21)/20*19! boucles d'ordre 21 possibles.
Plus généralement, on a A(40/k)/k*(40-k)! boucles d'ordre k. Soit plus simplement 40!/k. Et il faut sommer tout ça pour k allant de 21 à 40. Soit 40! * E(1/k) pour k allant de 21 à 40
Cela nous donne le nombre de cas mortels. Le nombre de cas total est 40! La proba de mort est donc 40! * E(1/k) / 40!. Sit E(1/k) pour k allant de 21 à 40.
Plus généralement pour un nombre de voleurs tendant vers l'infini, on a à calculer la limite de E(1/k) pour k allant de p+1 à 2p. On scinde en "pour k allant de 1 à 2p" moins "pour k allant de 1 à p".
La limite est donc de ln(2p) - ln(p), soit ln(2).
La proba "minimale" est donc de 1-ln(2), soit 0,306852819
C'est ça amalfi?
Je ne suis pas certain de tout car j'avais gribouillé ça sur un morceau de papier ce WE, à Villebon, en même temps que je jouais à TuT contre kime1 pour le 1er tour du tournoi
. Bon, bien sur j'ai perdu...
Plus sérieusement, et pour rendre à Jules ce qui lui appartient, je n'avais pas réussi à modéliser le dénombrement des boucles (en gros avant les ***** c'est bibi) et sans un repas avec le futur lauréat de la médaille Fields... (75% de l'après *******)
Beiträge anzeigen
... mais des lancers de dès aussi... 
)).
