Dans le problème de Josèphe, des personnes se tiennent en cercle et une personne sur deux est éliminée jusqu’à ce qu’il n’en reste qu’une. Le calculateur du problème de Josèphe donne la position du survivant, la position pour un autre point de départ, la plus grande puissance de deux inférieure au nombre de personnes et les personnes à ajouter pour que la personne 1 gagne.
Comment se fait le calcul
- Saisissez le nombre de personnes debout en cercle.
- Saisissez la position où commence le décompte. La personne 1 est celle qui ouvre le cercle. Si le décompte commence à la personne 5, le survivant se décale de 4 places.
- Le décompte saute une personne et élimine la suivante, puis continue autour du cercle, jusqu’à ce qu’il n’en reste qu’une. C’est le cas où une personne sur deux est éliminée.
- Le calculateur donne la position du survivant J(n) = 2 × (n − 2ᵐ) + 1, où 2ᵐ est la plus grande puissance de deux inférieure ou égale à n, le survivant pour votre point de départ et le nombre de personnes à ajouter pour que la personne 1 gagne.
Exemple
100 personnes se tiennent en cercle et une personne sur deux est éliminée. La plus grande puissance de deux inférieure ou égale à 100 est 64, donc le survivant est à la position 2 × (100 − 64) + 1 = 73. Si le décompte commence à la personne 10 au lieu de la personne 1, le survivant se décale de 9 places à la position 82. Pour que la personne 1 soit la survivante, le cercle devrait avoir 128 personnes, donc vous en ajoutez 28. Au total, 99 personnes sont éliminées avant le survivant.
Pourquoi c’est utile
Le calculateur aide les étudiants en mathématiques et en informatique, les enseignants et les amateurs de casse-têtes à voir une récurrence classique et sa forme fermée élégante. Il aide aussi à organiser des jeux d’élimination ou à choisir un point de départ dans un jeu pour un groupe d’enfants.
À savoir
La formule suppose que le décompte commence à la personne 1, qui est sautée, et que la personne 2 est éliminée en premier. Si la première personne comptée est éliminée, le survivant change, donc vérifiez la règle de votre jeu. Le calculateur traite une personne sur deux. Pour d’autres pas de décompte, il faut un programme utilisant la récurrence.
Outils liés
Le calculateur de permutations compte les ordres d’un groupe, celui du logarithme trouve la puissance de deux, celui des combinaisons compte les façons de choisir des personnes, et celui du calendrier de tournoi organise les matchs entre équipes.