Problème de Josèphe

Quarante et un soldats juifs (dont Flavius Josèphe), cernés par des soldats romains, décident de se suicider. Ils se mettent en cercle, et un premier soldat est choisi au hasard pour être exécuté ; puis le troisième à partir de sa gauche (ou droite) est exécuté. Tant qu'il y a des soldats, la sélection continue de la même façon. Le but est de trouver à quelle place doit se tenir un soldat pour être le dernier. Josèphe, peu enthousiaste à l'idée de mourir, parvint à trouver cette place. Quelle est-elle[3] - [4] - [5] ?

L'histoire se serait déroulée lors du siège de Jotapata par Vespasien, en 67 apr. J.-C.[6].

Les soldats sont au nombre de n, numérotés de 1 à n ; les premiers soldats éliminés sont ceux dont le numéro est multiple d'un entier ${\displaystyle k\geqslant 2}$ (${\displaystyle k=3}$ dans le problème originel) ; après un tour, les éliminations de k en k des soldats restants se poursuivent jusqu'à ce qu'il n'en reste qu'un. On demande le numéro ${\displaystyle J_{k}(n)}$ de ce soldat[7] - [8] - [9].

Voici par exemple, pour ${\displaystyle n=10,k=3}$, les différents ordres d'élimination des soldats :

${\displaystyle i}$	1	2	3	4	5	6	7	8	9	10
Ordre d'élimination	6	4	1	10	8	2	5	7	3	9

Donc ${\displaystyle J_{3}(10)=4}$.

Il est remarquable que le calcul de ${\displaystyle J_{k}(n)}$ se programme très facilement, mais qu'on ne connait de formule simple que pour ${\displaystyle k=2}$[6].

Pour le problème originel, on obtient ${\displaystyle J_{3}(41)=31}$ qui est donc la place prise par Flavius Josèphe.

Voir les suites  A006257,  A054995,  A088333,  A181281 donnant les valeurs de ${\displaystyle J_{k}(n)}$ pour ${\displaystyle k=2,3,4,5}$.

Lors du premier tour complet, tous les soldats aux positions paires sont exécutés. Au deuxième tour, le nouveau 2^e est exécuté, puis le nouveau 4^e, etc.

Si le nombre initial de personnes est pair, alors le soldat à la position x au 2^e tour est à la position 2x – 1 au 1^er tour (peu importe la valeur de x). Donc, la personne à la position ${\displaystyle J_{2}(n)}$ était auparavant à la position ${\displaystyle 2J_{2}(n)-1}$ . Cela nous permet de trouver la 1^re formule de récurrence :

${\displaystyle J_{2}(2n)=2J_{2}(n)-1\,}$.

Si le nombre initial de soldats est impair, il vaut mieux voir le soldat à la position 1 comme exécuté à la fin du 1^er tour. Pendant le 2^e tour, le soldat à la 2^e position est exécuté, puis le 4^e, etc. Dans ce cas, le soldat à la position x était auparavant à la position 2x + 1. Cela nous permet de trouver la 2^e formule de récurrence :

${\displaystyle J_{2}(2n+1)=2J_{2}(n)+1\,}$.

On peut réunir les deux formules en : ${\displaystyle J_{2}(n)=2J_{2}(\left\lfloor n/2\right\rfloor )-(-1)^{n}}$, avec ${\displaystyle J_{2}(1)=1}$.

Les valeurs tabulées de n et ${\displaystyle J_{2}(n)}$ font apparaître un schéma :

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
${\displaystyle J_{2}(n)}$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

Les ${\displaystyle J_{2}(n)}$ forment une suite de valeurs impaires croissantes qui recommence à 1 lorsque n est une puissance de 2.

Si nous choisissons m et l de façon que n = 2^m + l et 0 ≤ l < 2^m, alors ${\displaystyle J_{2}(n)=2l+1}$. Les valeurs de la table respectent cette relation. De même, après l exécutés, il ne reste que 2^m soldats et nous allons au 2l+1^e soldat. Il est le survivant. Donc ${\displaystyle J_{2}(n)=2l+1}$.

On peut écrire ce résultat sous la forme close : ${\displaystyle J_{2}(n)=2n+1-2^{\left\lfloor \log _{2}(n)\right\rfloor +1}}$.

En numérotant les positions de 0 à n – 1, on a la formule de récurrence permettant d'obtenir ${\displaystyle J_{k}(n)}$ :

${\displaystyle J_{k}(n)=(J_{k}(n-1)+k){\bmod {n}}}$ avec ${\displaystyle J_{k}(1)=0}$

Elle apparaît lorsque nous observons comment le nombre de survivants change en passant de n – 1 à n.

Avec une programmation dynamique, elle a un temps d'exécution asymptotique en ${\displaystyle O(n)\,}$.

Pour de petites valeurs de k et de grandes valeurs de n, il existe une autre approche qui a aussi recours aux principes de la programmation dynamique, mais a un temps d'exécution asymptotique de ${\displaystyle O(k\log n)\,}$. Elle s'appuie sur l'idée de tuer le k^e, 2k^e..., ${\displaystyle \lfloor n/k\rfloor }$^e soldat d'un seul coup, puis de changer la numérotation .

Stanislas Ulam a inventé avec d'autres mathématiciens, dans les années cinquante, un crible, ressemblant au crible d’Ératosthène, consistant en une élimination dans l'ensemble de tous les entiers naturels non nuls, avec des passages successifs d'éliminations de k en k, où k est la valeur d'un entier non éliminé déterminé. Pour cette raison, il a baptisé ce crible "crible de Flavius Josèphe"[11] - [12].