problème de Flavius

En 67 après J.-C., selon l'épisode historique rapporté dans la source, Flavius Josèphe se trouve dans une grotte avec une quarantaine de compagnons, lors d'un conflit opposant Rome et Jérusalem. Décidés à se suicider plutôt qu'à se rendre, ils proposent un tirage au sort : le groupe se place en cercle et élimine chaque troisième personne.

Le même comptage recommence parmi les personnes restantes, sans revenir au début du cercle. La question est donc concrète : à quelle place faut-il se tenir au départ pour rester jusqu'à la fin ?

Le problème de Flavius, aussi appelé problème de Flavius Josèphe ou problème de Josèphe, porte sur un cercle de n personnes et un pas de comptage k. En partant d'une personne convenue, on compte cycliquement de 1 à k. Celle qui prononce k est éliminée, puis le comptage reprend à la personne suivante. Le processus s'arrête lorsqu'il reste une personne, ou au nombre de survivants fixé par une variante.

Pour la variante à un survivant, notons j_n son indice lorsque les places sont numérotées de 0 à n − 1. La récurrence est :

Elle exprime que, après la première élimination, le cercle restant est renuméroté. Pour retrouver une position usuelle numérotée à partir de 1, on ajoute 1 à j_n. Le récit source associe ce problème à Flavius Josèphe et rapporte qu'avec une quarantaine de compagnons, une élimination par trois laissa Josèphe en 31^e position et un compagnon en 16^e. Il mentionne aussi des variantes étudiées au fil des siècles, notamment par Ben Ezra et Tartaglia.

Sept personnes occupent les positions 1 à 7 autour d'un cercle. La position 1 commence à compter, le sens du parcours reste le même et chaque troisième personne est éliminée. Les données sont donc n = 7 et k = 3.

1. Les positions 1, 2, 3 sont comptées : la position 3 sort.
2. Le comptage reprend en 4 : la position 6 sort.
3. En poursuivant sur les personnes encore présentes, les positions 2, puis 7, puis 5 sortent.
4. Il reste 1 et 4. Le comptage 1, 4, 1 élimine finalement la position 1.

La position survivante est donc 4. Pour contrôler le résultat, la récurrence en indices commençant à 0 donne successivement 0, 1, 1, 0, 3, 0, 3 ; le dernier indice 3 correspond bien à la position 4. Le schéma récapitule le cercle initial et l'ordre d'élimination 3, 6, 2, 7, 5, 1.

Pour un petit cercle, on peut barrer les positions à mesure et reprendre le comptage juste après chaque position éliminée. Cette simulation directe est préférable lorsque l'on veut connaître tout l'ordre des sorties, pas seulement le dernier survivant.

Pour un grand nombre de personnes, la récurrence évite de conserver le cercle entier. On part de l'indice 0 pour une personne, puis on ajoute le pas k et on prend le reste modulo la nouvelle taille, jusqu'à atteindre n.

Avant tout calcul, il faut fixer la première personne, le sens, la valeur de k et le nombre de survivants recherché. Si l'une de ces conventions change, le résultat peut changer lui aussi.

Avec un tirage aléatoire. Dans le problème de Flavius, les sorties sont entièrement déterminées dès que le cercle, le départ, le sens et le pas sont fixés. Rejouer le cas n = 7 et k = 3 avec les mêmes conventions donne toujours la position 4. Un véritable tirage au sort pourrait donner un autre survivant à chaque essai.

Changer l'origine ou le sens. Une position comme « 4 » n'a de sens qu'après avoir fixé la personne qui commence et le sens du comptage. Le symptôme d'une convention implicite est un ordre d'élimination décalé ; il faut alors renuméroter le cercle avant de comparer les résultats.

Confondre pas et déplacement. Avec k = 3, la personne de départ compte pour 1 : la première sortie est donc la troisième personne, et non celle située trois déplacements plus loin. Pour éviter ce décalage d'une place, il faut écrire les premiers nombres comptés.

Cas charnières. Si n = 1, l'unique position est déjà survivante. Si k = 1, les positions sont supprimées dans l'ordre du parcours et la dernière position survit avec la convention de l'exemple. Ces cas doivent être traités explicitement plutôt que simulés comme un tour ordinaire.

Plusieurs survivants. La récurrence donnée dans la définition calcule un unique survivant. Si le processus s'arrête lorsqu'il reste deux personnes, comme dans le récit source, il faut simuler les éliminations jusqu'à deux ou employer une règle adaptée ; la formule à un survivant ne suffit pas.

Arithmétique modulaire — Elle explique le reste modulo n qui ramène chaque nouveau calcul dans le cercle des positions encore disponibles.

Analyse combinatoire — Elle replace ce problème d'élimination parmi les raisonnements sur des configurations finies et des choix ordonnés.