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 Josèphe 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 dans son livre La Guerre des Juifs datant de la fin du premier siècle^[1]^,^[2].

Illustration tirée d'un ouvrage du Japonais Matu-oka de 1808. Le problème concerne un procédé de « décimation » de 30 enfants, 15 d'un premier lit et 15 d'un deuxième pour déterminer qui héritera (donc ici $n=30,k=10$ )^[3].

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-elle^[4]^,^[5]^,^[6]^,^[7] ?

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

Historique et variantes

Le problème est mentionné chez Abraham ibn Ezra (1092-1167)^[9].

Une variante de ce problème due à Tartaglia (1500 - 1557) est le problème des 15 chrétiens et des 15 Turcs où le nombre de personnes est égal à 30 et le procédé d'élimination de 9 en 9 ^[10]^,^[9]^,^[11] ; Cette variante se retrouve au Japon au début du XIX^e siècle avec une élimination de 10 en 10^[5]^,^[10] (voir illustration).

Une variante intitulée « problème de Caligula » par Édouard Lucas donne lieu à des développements dans l'intermédiaire des mathématiciens à la fin du XIX^e siècle^[12].

Problème général

Les personnes sont au nombre de $n$ , numérotés de 1 à $n$ ; les premières personnes éliminées sont celles dont le numéro est multiple d'un entier $k\geqslant 2$ ( $k=3$ dans le problème originel) ; après un tour, les éliminations de $k$ en $k$ des personnes restantes se poursuivent jusqu'à ce qu'il n'en reste qu'une. On demande le numéro $J_{k}(n)$ de cette personne ^[9]^,^[13]^,^[14].

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$ .

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

Il est remarquable que bien que le calcul de $J_{k}(n)$ se programme très facilement en utilisant la définition par récurrence suivante :

${\begin{cases}J_{k}(1)=1\\J_{k}(n)=1+\left((J_{k}(n-1)+k-1){\text{ mod }}n\right)\end{cases}}$ ,

l'on ne connaisse aujourd'hui pas de formule simple pour $J_{k}(n)$ , excepté pour $k=2$ ^[8].

Euler s'était déjà penché sur la question sans trouver de réponse précise en 1775^[15].

Voici les premières valeurs de $J_{k}(n)$ pour $1\leqslant n,k\leqslant 7$ ; A032434 donne les valeurs pour $1\leqslant k\leqslant n$ et A198788 lit ce tableau par antidiagonales montantes.


n \ k	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	2	1	2	1	2	1	2
3	3	3	2	2	1	1	3
4	4	1	1	2	2	3	2
5	5	3	4	1	2	4	4
6	6	5	1	5	1	4	5
7	7	7	4	2	6	3	5
Suite OEIS correspondante		A006257	A054995	A088333	A181281	A360268	A178853

Solution dans le cas où k = 2

Lors du premier tour complet, toutes les personnes aux positions paires sont éliminées. Au deuxième tour, la nouvelle 2^e est éliminée, puis la nouvelle 4^e, etc.

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

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

.

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

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

.

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

Les valeurs tabulées de $n$ 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 $n$ est une puissance de 2.

Si nous choisissons $m$ et $l$ de façon que $n = 2 m + l$ et $0 \leq l < 2 m$ , alors $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$ personnes et nous allons à la $2 l +1$ ^e personne. Elle est la dernière restante. Donc $J_{2}(n)=2l+1$ .

Théorème^[16] — Si $n = 2 m + l$ et $0 \leq l < 2 m$ , alors $J_{2}(n)=2l+1$ .

Démonstration par récurrence

Le cas $n =1$ est vrai. Analysons de façon séparée les cas $n$ pair et $n$ impair.

Quand $n$ est pair, on peut choisir $l 1$ et $m 1$ de sorte que $n/2=2^{m_{1}}+l_{1}$ et $0 \leq l 1 < 2 m 1$ . On a alors $l 1 = l /2$ .

Nous avons $J_{2}(n)=2J_{2}(n/2)-1=2((2l_{1})+1)-1=2l+1$ , où la deuxième égalité suit de l'hypothèse d'induction.

Quand $n$ est impair,on peut choisir $l 1$ et $m 1$ de sorte que $(n-1)/2=2^{m_{1}}+l_{1}\,$ et $0 \leq l 1 < 2 m 1$ . On a alors $l 1 =(l -1)/2$ .

Nous avons $J_{2}(n)=2J_{2}((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ , où la deuxième égalité suit de l'hypothèse de récurrence, ce qui achève la récurrence.

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

Cas général

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

J_{k}(n)=(J_{k}(n-1)+k){\bmod {n}}

avec

J_{k}(1)=0

Elle apparaît lorsque nous observons comment le nombre de personnes non éliminées change en passant de $n - 1$ à $n$ .

Avec une programmation dynamique, elle a un temps d'exécution asymptotique en $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 $O(k\log n)\,$ . Elle s'appuie sur l'idée d'éliminer la $k$ ^e, 2 $k$ ^e..., $\lfloor n/k\rfloor$ ^e personne d'un seul coup, puis de changer la numérotation ^{[réf. 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 $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"^[17]^,^[18].

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 suite A000960 de l'OEIS.

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

Autres cribles similaires

Un autre crible imaginé par Ulam et ses compères^[17], 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 suite A007952 de l'OEIS, et un quatrième est celui donnant les nombres pseudo-chanceux, voir la suite A249876 de l'OEIS.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Josephus problem » (voir la liste des auteurs).

↑ Flavius Josephe, Œuvres complètes, trad. en français sous la dir. de Théodore Reinach,.... trad. de René Harmand ; révisée et annotée par S. Reinach et J. Weill E. Leroux, Publications de la Société des études juives, 1900-1932 (lire en ligne), chap. VIII, N°7
↑ On trouvera une étude historique dans Laurent Signac, « Autour du problème de Josèphe », Bibnum,‎ 2012 (lire en ligne).
↑ Congrès international des orientalistes : compte-rendu de la première session, t. 1, Paris, 1873, p. 294-295
↑ (en) Peter Guthrie Tait, « On generalization of Josephus' problem », Collected Scientific Papers, vol. 2,‎ 1900, p. 432-435 (lire en ligne).
(de) W. Ahrens, Mathematische Unterhaltungen Und Spiele, Kapitel XV : das Josephsspiel, Archiv für Kulturgeschichte, 1913 (lire en ligne), chap. XV, p. 118-169
↑ André Sainte-Laguë, « Géométrie de situation et jeux : 68. Problème de Josèphe », Mémorial des sciences mathématiques, vol. 41,‎ 1929, p. 44-45 (lire en ligne).
↑ (en) W. W. Rouse Ball, Mathematical Recreations and Essays, Cambridge, 1937, 10^e éd., p. 23-27.
Signac 2012.
Jean Lefort, « Le problème de Flavius Josèphe », L'Ouvert, vol. 109,‎ 2004, p. 31-42 (lire en ligne).
André Sainte-Laguë, Avec des nombres et des lignes, La légende de Josèphe, Vuibert (réimpr. 1994) (1^re éd. 1937), p. 57-63
↑ Pierre Ageron et Gérard Hamon, « Le jeu des quinze croyants et des quinze infidèles : variations sur la violence »
↑ E. Lucas, « Problème de Caligula », L'Intermédiaire des mathématiciens, vol. 1,‎ 1897, p. 9, 30, 31, 189 (lire en ligne).
↑ (en) L. Halbeisen, N. Hungerbühler, « The Josephus Problem », Journal de Théorie des Nombres de Bordeaux, vol. 9, fascicule 2,‎ 1997 (lire en ligne).
↑ R. L. Graham, D. E. Knuth et O. Patashnik, Mathématiques concrètes, Paris, International Thomson Publishing France, 1998, p. 9-18 (k = 2) et 86-88 (cas général).
↑ (la) Leonhard Euler, « Observationes circa novum et singulare progressionum genus », Novi Comment. Akadem. Petropol, vol. 20,‎ 1775 (lire en ligne)
↑ On trouvera des prolongements pour l'étude de ce cas dans « G204. Le problème de Josèphe », Les jeux mathématiques de Diophante, plus de 800 problèmes mathématiques, 2009 et Graham, Knuth et Patashnik 1998.
(en) Verna Gardiner, R. Lazarus, N. Metropolis et S. Ulam, « On certain sequences of integers defined by sieves », Mathematics Magazine, vol. 29, n^o 3,‎ 1956, p. 117-122 (DOI 10.2307/3029719, zbMATH 0071.27002).
(de) Mats Erik Andersson, « Das Flaviussche Sieb », Acta Arithmetica, vol. 85, n^o 4,‎ 1998 (lire en ligne).

Voir aussi

Liens externes

(en) Josephus Flavius Game (applet Java), sur cut-the-knot
(en) Eric W. Weisstein, « Josephus Problem », sur MathWorld

Bibliographie

(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001, 2^e éd. [détail de l’édition], chap. 14 (« Augmenting Data Structures »), p. 318

Portail des mathématiques
Portail de l’informatique

[1] Flavius Josephe, Œuvres complètes, trad. en français sous la dir. de Théodore Reinach,.... trad. de René Harmand ; révisée et annotée par S. Reinach et J. Weill E. Leroux, Publications de la Société des études juives, 1900-1932 (lire en ligne), chap. VIII, N°7

[2] On trouvera une étude historique dans Laurent Signac, « Autour du problème de Josèphe », Bibnum,‎ 2012 (lire en ligne).

[3] Congrès international des orientalistes : compte-rendu de la première session, t. 1, Paris, 1873, p. 294-295

[4] (en) Peter Guthrie Tait, « On generalization of Josephus' problem », Collected Scientific Papers, vol. 2,‎ 1900, p. 432-435 (lire en ligne).

[:4-5] (de) W. Ahrens, Mathematische Unterhaltungen Und Spiele, Kapitel XV : das Josephsspiel, Archiv für Kulturgeschichte, 1913 (lire en ligne), chap. XV, p. 118-169

[6] André Sainte-Laguë, « Géométrie de situation et jeux : 68. Problème de Josèphe », Mémorial des sciences mathématiques, vol. 41,‎ 1929, p. 44-45 (lire en ligne).

[7] (en) W. W. Rouse Ball, Mathematical Recreations and Essays, Cambridge, 1937, 10^e éd., p. 23-27.

[Signac2012-8] Signac 2012.

[:0-9] Jean Lefort, « Le problème de Flavius Josèphe », L'Ouvert, vol. 109,‎ 2004, p. 31-42 (lire en ligne).

[:5-10] André Sainte-Laguë, Avec des nombres et des lignes, La légende de Josèphe, Vuibert (réimpr. 1994) (1^re éd. 1937), p. 57-63

[11] Pierre Ageron et Gérard Hamon, « Le jeu des quinze croyants et des quinze infidèles : variations sur la violence »

[12] E. Lucas, « Problème de Caligula », L'Intermédiaire des mathématiciens, vol. 1,‎ 1897, p. 9, 30, 31, 189 (lire en ligne).

[13] (en) L. Halbeisen, N. Hungerbühler, « The Josephus Problem », Journal de Théorie des Nombres de Bordeaux, vol. 9, fascicule 2,‎ 1997 (lire en ligne).

[:3-14] R. L. Graham, D. E. Knuth et O. Patashnik, Mathématiques concrètes, Paris, International Thomson Publishing France, 1998, p. 9-18 (k = 2) et 86-88 (cas général).

[15] (la) Leonhard Euler, « Observationes circa novum et singulare progressionum genus », Novi Comment. Akadem. Petropol, vol. 20,‎ 1775 (lire en ligne)

[16] On trouvera des prolongements pour l'étude de ce cas dans « G204. Le problème de Josèphe », Les jeux mathématiques de Diophante, plus de 800 problèmes mathématiques, 2009 et Graham, Knuth et Patashnik 1998.

[:1-17] (en) Verna Gardiner, R. Lazarus, N. Metropolis et S. Ulam, « On certain sequences of integers defined by sieves », Mathematics Magazine, vol. 29, n^o 3,‎ 1956, p. 117-122 (DOI 10.2307/3029719, zbMATH 0071.27002).

[:2-18] (de) Mats Erik Andersson, « Das Flaviussche Sieb », Acta Arithmetica, vol. 85, n^o 4,‎ 1998 (lire en ligne).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]