Problème de Josèphe

Buste du premier siècle, probablement de Flavius Josèphe, conservé à Ny Carlsberg.

En mathématiques et en informatique, le problème de (Flavius) Josèphe ou problème de Caligula est un problème d'élimination, conduisant à l'obtention d'un unique survivant.

Il a été énoncé sous différentes formes, mais sa première formulation est due à Flavius Josèphe.

Problème originel

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-elleModèle:,Modèle:, ?

L'histoire se serait déroulée lors du siège de Jotapata par Vespasien, en Modèle:Ap JCModèle:Sfn.

Problème général

Les soldats sont au nombre de Modèle:Mvar, numérotés de 1 à Modèle:Mvar ; les premiers soldats éliminés sont ceux dont le numéro est multiple d'un entier $k⩾2$ ($k=3$ dans le problème originel) ; après un tour, les éliminations de Modèle:Mvar en Modèle:Mvar des soldats restants se poursuivent jusqu'à ce qu'il n'en reste qu'un. On demande le numéro $J_k(n)$ de ce soldatModèle:,Modèle:,.

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

$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 $J_3(10)=4$.

Il est remarquable que le calcul de $J_k(n)$ se programme très facilement, mais qu'on ne connait de formule simple que pour $k=2$Modèle:Sfn.

Pour le problème originel, on obtient $J_3(41)=31$ qui est donc la place prise par Flavius Josèphe.

Voir les suites Modèle:OEIS2C, Modèle:OEIS2C, Modèle:OEIS2C, Modèle:OEIS2C donnant les valeurs de $J_k(n)$ pour $k=2,3,4,5$.

Solution dans le cas où k = 2

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

Si le nombre initial de personnes est pair, alors le soldat à la position Modèle:Mvar au Modèle:2e est à la position Modèle:Math au Modèle:1er (peu importe la valeur de Modèle:Mvar). Donc, la personne à la position $J_2(n)$ était auparavant à la position $2J_2(n)-1$ . Cela nous permet de trouver la Modèle:1re de récurrence :

$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 Modèle:1er. Pendant le Modèle:2e, le soldat à la Modèle:2e est exécuté, puis le Modèle:4e, etc. Dans ce cas, le soldat à la position Modèle:Mvar était auparavant à la position Modèle:Math. Cela nous permet de trouver la Modèle:2e de récurrence :

$J_2(2n+1)=2J_2(n)+1$.

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

Les valeurs tabulées de Modèle:Mvar et $J_2(n)$ font apparaître un schéma :

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$J_2(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

Les $J_2(n)$ forment une suite de valeurs impaires croissantes qui recommence à 1 lorsque Modèle:Mvar est une puissance de 2.

Si nous choisissons Modèle:Mvar et Modèle:Mvar de façon que Modèle:Math et Modèle:Math, alors $J_2(n)=2l+1$. Les valeurs de la table respectent cette relation. De même, après Modèle:Mvar exécutés, il ne reste que Modèle:Math soldats et nous allons au Modèle:MathModèle:E soldat. Il est le survivant. Donc $J_2(n)=2l+1$.

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

Cas général

En numérotant les positions de 0 à Modèle:Math, on a la formule de récurrence permettant d'obtenir $J_k(n)$  :

$J_k(n)=(J_k(n-1)+k)modn$ avec $J_k(1)=0$

Elle apparaît lorsque nous observons comment le nombre de survivants change en passant de Modèle:Math à Modèle:Mvar.

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

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

Crible de (Flavius) Josèphe

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 Modèle:Mvar en Modèle:Mvar, où Modèle:Mvar est la valeur d'un entier non éliminé déterminé. Pour cette raison, il a baptisé ce crible "crible de Flavius Josèphe"Modèle:,.

Description du crible

Dans la liste des entiers naturels non nuls, on barre un nombre sur 2 en commençant par barrer le deuxième :

Puis dans la liste restante, on barre un nombre sur 3 en commençant par barrer le troisième.

Puis on barre un nombre sur 4, un nombre sur 5, etc. Et ceci à l'infini, ce qui donne la liste : 1, 3, 7, 13, 19, 27, 39, 49, 63, 79,...

Elle est répertoriée comme Modèle:OEIS.

Ce qui est remarquable est que le Modèle:Mvar-ième nombre restant est équivalent à $\pi \frac{n^2}{4}$ et que le nombre de nombres restants inférieurs à Modèle:Mvar équivaut à $2\sqrt{\frac{n}{\pi }}$.

Autres cribles similaires

Un autre crible imaginé par Ulam et ses compères, semblable mais donnant des résultats différents, est celui dont les survivants sont les nombres chanceux.

Un troisième crible du même type est celui dit de Tchoukaillon, voir la Modèle:OEIS, et un quatrième est celui donnant les nombres pseudo-chanceux, voir la Modèle:OEIS.

Voir aussi

Liens externes

• Modèle:En Josephus Flavius Game (applet Java), sur cut-the-knot
• Modèle:MathWorld

Bibliographie

Modèle:Cormen2en, chap. 14 (« Augmenting Data Structures »), p. 318