Aller au contenu
Omnikalc

Calculateur du problème de Josèphe : trouver la place sûre dans un cercle

Saisissez le nombre de personnes dans le cercle et la position de départ pour trouver la position du survivant quand une personne sur deux est éliminée.

Mis à jour le
Vos paramètres

Valeur hors limites

Valeur hors limites

Résultats

Position du survivant (en comptant depuis la personne 1)

73

Position du survivant avec votre point de départ
82
Plus grande puissance de deux inférieure ou égale au nombre de personnes
64
Personnes à ajouter pour que la personne 1 survive
28
Personnes éliminées avant le survivant
99

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.

Questions fréquentes

Qu’est-ce que le problème de Josèphe ?

Le problème de Josèphe est un jeu d’élimination. Des personnes se tiennent en cercle, et une personne sur k est éliminée jusqu’à ce qu’il n’en reste qu’une. La question est de savoir où se placer pour être la dernière. Il porte le nom de l’historien Flavius Josèphe, qui, selon une légende, a survécu à un suicide collectif de rebelles juifs en l’an 67 en se plaçant au bon endroit.

Quelle est la formule pour une personne sur deux ?

Quand une personne sur deux est éliminée, le survivant est à la position J(n) = 2 × (n − 2ᵐ) + 1, où 2ᵐ est la plus grande puissance de deux qui ne dépasse pas n. Si n est une puissance de deux, le survivant est toujours la personne 1. Si on écrit n en binaire, J(n) s’obtient en déplaçant le premier chiffre à la fin.

Pourquoi les puissances de deux comptent-elles ?

Au premier tour du cercle, la moitié des personnes sont éliminées, et quand n est une puissance de deux, le tour suivant repart de la personne 1 avec la moitié des personnes. Le problème se répète à une taille plus petite jusqu’à ce qu’il reste une personne, donc la personne 1 survit. Pour les autres valeurs de n, les premières éliminations ramènent le cercle à une puissance de deux.

Et si le décompte saute plus d’une personne ?

Pour une personne sur trois ou plus, il n’existe pas de formule fermée simple, et le survivant se trouve par la récurrence J(n, k) = (J(n − 1, k) + k) mod n. Le calculateur traite le cas k = 2. Pour un k plus grand, suivez la récurrence pas à pas ou utilisez un programme.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.