Problème des 100 prisonniers
Le texte ‘Une stratégie enfantine’ donne une solution détaillée en une seule page du problème des n = 2 k = 100 prisonniers’.
Soit M la variable aléatoire : plus grande longueur d’un cycle d’une permutation de n éléments prise au hasard. Les valeurs de P (M = k) pour k > n / 2 sont facilement calculables, on a alors P (M = k) = 1 / k, et utiles pour le problème des 100 prisonniers.
Pour les plus petites valeurs de k, une fonction récursive f (n) trouvée sur Internet donne la réponse et le programme Python ‘dessin_cycle_max’ donne une représentation graphique de la loi de M.
Le programme Python ‘ Plus long cycle d’une permutation_force brute’ vérifie les valeurs données par f (n) avec celles données par la force brute, en se limitant à n < 11 (au delà la force brute prend trop de temps).