Énigme
50 Pacman de tailles différentes sont en file indienne et se déplacent dans la même direction. Si un Pacman se trouve juste derrière un autre Pacman plus petit que lui, il le mange.
Quelle est l’espérance du nombre de Pacman restants après suffisamment de temps ?
Solution
Soit E(50) la valeur cherchée (le nombre de Pacman ayant survécu parmi les 50 initiaux). Sans perte de généralité, considérons le plus petit Pacman de la file. S’il est tout derrière (1 chance sur 50), il survit et le nombre de survivants correspond à 1 + E(49) (le problème se réduit aux 49 insectes devant lui) ; sinon (49 chances sur 50), il est mangé et le nombre de survivants correspond à E(49).
Par conséquent, on en déduit l’équation suivante :
E(50) = 1/50 x [1 +E(49)] + 49/50 x E(49) = 1/50 + E(49)
C’est-à-dire : E(50) = 1 + ½ + … + 1/50 ~ 4.499