Problème de Josèphe
En mathématiques et en informatique, le problème de (Flavius) Josèphe ou problème de Caligula[1] 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[2].
Problème originel
[modifier | modifier le code]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].
Problème général
[modifier | modifier le code]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 ( 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 de ce soldat[7],[8],[9].
Voici par exemple, pour , les différents ordres d'élimination des soldats :
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
Ordre d'élimination | 6 | 4 | 1 | 10 | 8 | 2 | 5 | 7 | 3 | 9 |
Donc .
Il est remarquable que le calcul de se programme très facilement, mais qu'on ne connait de formule simple que pour [6].
Pour le problème originel, on obtient qui est donc la place prise par Flavius Josèphe.
Voir les suites A006257,
A054995,
A088333,
A181281 donnant les valeurs de pour .
Solution dans le cas où k = 2
[modifier | modifier le code]Lors du premier tour complet, tous les soldats aux positions paires sont exécutés. Au deuxième tour, le nouveau 2e est exécuté, puis le nouveau 4e, etc.
Si le nombre initial de personnes est pair, alors le soldat à la position x au 2e tour est à la position 2x – 1 au 1er tour (peu importe la valeur de x). Donc, la personne à la position était auparavant à la position . Cela nous permet de trouver la 1re formule de récurrence :
- .
Si le nombre initial de soldats est impair, il vaut mieux voir le soldat à la position 1 comme exécuté à la fin du 1er tour. Pendant le 2e tour, le soldat à la 2e position est exécuté, puis le 4e, etc. Dans ce cas, le soldat à la position x était auparavant à la position 2x + 1. Cela nous permet de trouver la 2e formule de récurrence :
- .
On peut réunir les deux formules en : , avec .
Les valeurs tabulées de n et font apparaître un schéma :
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
Les 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 = 2m + l et 0 ≤ l < 2m, alors . Les valeurs de la table respectent cette relation. De même, après l exécutés, il ne reste que 2m soldats et nous allons au 2l+1e soldat. Il est le survivant. Donc .
Théorème[10] — Si n = 2m + l et 0 ≤ l < 2m, alors .
On peut écrire ce résultat sous la forme close : .
Cas général
[modifier | modifier le code]En numérotant les positions de 0 à n – 1, on a la formule de récurrence permettant d'obtenir :
- avec
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 .
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 . Elle s'appuie sur l'idée de tuer le ke, 2ke..., e soldat d'un seul coup, puis de changer la numérotation [réf. souhaitée].
Crible de (Flavius) Josèphe
[modifier | modifier le code]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].
Description du crible
[modifier | modifier le code]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 à et que le nombre de nombres restants inférieurs à n équivaut à [12].
Autres cribles similaires
[modifier | modifier le code]Un autre crible imaginé par Ulam et ses compères[11], 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
[modifier | modifier le code]- E. Lucas, « Problème de Caligula », L'intermédiaire des mathématiciens, vol. 1, , p. 9, 30, 31, 189 (lire en ligne).
- On trouvera une étude historique dans Laurent Signac, « Autour du problème de Josèphe », Bibnum, (lire en ligne).
- (en) W. W. Rouse Ball, Mathematical Recreations and Essays, Cambridge, , 10e éd., p. 23-27.
- (en) Peter Guthrie Tait, « On generalization of Josephus' problem », Collected Scientific Papers, vol. 2, , p. 432-435 (lire en ligne).
- A. Sainte-Laguë, « Géométrie de situation et jeux », Mémorial des sciences mathématiques, vol. 41, , p. 44-45 (lire en ligne).
- Signac 2012.
- Jean Lefort, « Le problème de Flavius Josèphe », L'ouvert, vol. 109, , p. 31-42 (lire en ligne).
- (en) L. Halbeisen, N. Hungerbühler, « The Josephus Problem », Journal de Théorie des Nombres de Bordeaux, vol. 9, fascicule 2, (lire en ligne).
- R. L. Graham, D. E. Knuth et O. Patashnik, Mathématiques concrètes, Paris, International Thomson Publishing France, , p. 9-18 (k = 2) et 86-88 (cas général).
- 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, 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, no 3, , p. 117-122 (DOI 10.2307/3029719, zbMATH 0071.27002).
- (de) Mats Erik Andersson, « Das Flaviussche Sieb », Acta Arithmetica, vol. 85, no 4, (lire en ligne).
Voir aussi
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- (en) Josephus Flavius Game (applet Java), sur cut-the-knot
- (en) Eric W. Weisstein, « Josephus Problem », sur MathWorld
Bibliographie
[modifier | modifier le code](en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, , 2e éd. [détail de l’édition], chap. 14 (« Augmenting Data Structures »), p. 318