⭕ Le cercle de la survie
Place n personnes en cercle. On compte k à partir du n°1 et on élimine la k-ième, puis on repart du suivant. On continue jusqu'au dernier survivant. Où faut-il s'asseoir pour s'en sortir ?
Restants
41
Dernier éliminé
—
Survivant
—
Avec n = 41 et k = 3 (un homme sur trois), c'est exactement le cercle de la légende de Flavius Josèphe. Lance la simulation pour découvrir la place qui sauve.
⚔️ An 67 : un cercle de 41 hommes et une légende
Nous sommes en l'an 67 de notre ère, pendant la guerre judéo-romaine. Flavius Josèphe — historien juif, futur citoyen romain — est assiégé avec une quarantaine de compagnons dans une grotte de Yodfat (Jotapata), en Galilée. Plutôt que de se rendre aux Romains, ses compagnons décident de se donner la mort collectivement.
Selon la légende qui en est née, ils se placent en cercle et conviennent de s'entretuer : on compte le long du cercle et, à intervalle régulier, l'homme désigné est éliminé. Josèphe — qui, lui, ne tenait pas du tout à mourir — aurait calculé mentalement la position à occuper pour être l'un des deux derniers survivants… puis convaincu son voisin de se rendre avec lui aux Romains. La survie par les mathématiques.
La version mathématique standard du problème reprend ces chiffres : n = 41 personnes, on élimine un homme sur trois (k = 3). Le simulateur ci-dessus reconstitue exactement ce cercle.
🔁 Le problème généralisé J(n, k)
Les mathématiciens ont dégagé de l'anecdote un problème pur, le problème de Josephus :
On dispose n personnes numérotées de 1 à n en cercle. En partant de la n°1, on compte k personnes et on élimine la k-ième. On repart de la suivante, on recompte k, on élimine… et ainsi de suite jusqu'à ce qu'il n'en reste qu'une. La question : quelle est la position du survivant ?
On note J(n, k) cette position gagnante. Pour le cercle de Josèphe, on cherche donc J(41, 3). La simulation te donne la réponse… mais on peut aussi la calculer sans simuler, et c'est là que les mathématiques deviennent élégantes.
📐 La récurrence : se ramener à un cercle plus petit
L'astuce consiste à renuméroter le cercle juste après la première élimination. Quand on a éliminé la personne en position k, il reste n − 1 personnes, et le comptage redémarre à la position k + 1. Si on appelle 0 cette nouvelle première personne, on est ramené exactement au même problème, mais avec n − 1 personnes.
En numérotant les positions à partir de 0 (de 0 à n − 1), on obtient la fameuse relation de récurrence :
J(1, k) = 0
J(n, k) = ( J(n − 1, k) + k ) mod n
La position « humaine » du survivant (numérotée à partir de 1) est alors J(n, k) + 1.
Cette récurrence se calcule en une simple boucle, en temps linéaire O(n) et sans simuler le moindre cercle : on part de 0, et on ajoute k modulo m pour m allant de 2 jusqu'à n. Bien plus rapide que de tuer les gens un par un. Appliquée à n = 41, k = 3, elle donne le survivant en position 31.
✨ Le cas magique k = 2 : la formule binaire
Quand on élimine une personne sur deux (k = 2), une formule d'une beauté surprenante apparaît. Écrivons n en isolant la plus grande puissance de 2 qu'il contient :
Si n = 2a + l avec 0 ≤ l < 2a, alors le survivant est en position 2l + 1.
Exemple : pour n = 41 = 32 + 9, on a 2a = 32 et l = 9, donc le survivant (pour k = 2) serait en position 2·9 + 1 = 19.
Et voici le tour de magie en base 2 : prends l'écriture binaire de n, retire le bit de poids fort (le 1 de gauche) et recolle-le tout à droite. Le nombre obtenu est exactement la position du survivant. C'est une simple rotation circulaire à gauche d'un bit :
n = 41 = 101001₂ → on fait passer le 1 de tête à la fin : 010011₂ = 010011₂ = 19.
Difficile de faire plus élégant : la solution d'un problème de massacre antique tient dans un décalage de bits.
💻 Le lien avec l'informatique
Le problème de Josephus est un grand classique des cours d'algorithmique, car il illustre plusieurs idées centrales :
- Listes chaînées circulaires : la modélisation la plus naturelle relie chaque personne à sa voisine, en boucle fermée ; éliminer quelqu'un = supprimer un nœud.
- Files (queues) : on défile k − 1 personnes (qu'on renfile derrière) puis on élimine la k-ième — une implémentation en O(n·k) très lisible.
- Récurrence vs simulation : la formule J(n, k) = (J(n−1, k) + k) mod n résout le problème en O(n) sans aucune structure de données, exemple parfait d'optimisation par les maths.
- Arbres de Fenwick / segment trees : pour répondre en O(n log n) même quand on veut l'ordre complet des éliminations.
C'est un exercice qui revient sans cesse en entretien technique et en compétition de programmation (ICPC), précisément parce qu'il a plusieurs niveaux de solution, de la naïve à l'astucieuse.
🎓 Le lien avec ton programme
- Arithmétique modulaire : le « mod n » de la récurrence, le retour à 0 quand on boucle autour du cercle.
- Suites définies par récurrence : J(n, k) se construit terme par terme à partir de J(1, k) = 0.
- Numération en base 2 : la formule magique du cas k = 2 est une pure leçon d'écriture binaire et de puissances de 2.
- Algorithmique et complexité : comparer une solution O(n·k) (simulation) à une solution O(n) (récurrence) est un excellent point de départ.