Voir la source de Problème de Josèphe

[[Fichier:Josephusbust.jpg|vignette|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'''<ref>{{Article|auteur1=E. Lucas|titre=Problème de Caligula|périodique=L'intermédiaire des mathématiciens|volume=1|date=1897|lire en ligne={{Google Livres|NLM5AAAAMAAJ}}|pages=9, 30, 31, 189}}.</ref> est un problème [[Formulette d'élimination|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]]<ref>On trouvera une étude historique dans {{Article|auteur1=Laurent Signac|titre=Autour du problème de Josèphe|périodique=Bibnum|date=2012|lire en ligne=http://www.bibnum.education.fr/sites/default/files/flavius-analyse-1.pdf}}.</ref>.

== 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<ref>{{Ouvrage|langue=en|auteur1=W. W. Rouse Ball|titre=Mathematical Recreations and Essays|passage=23-27|éditeur=Cambridge|date=1937|numéro édition=10}}.</ref>{{,}}<ref>{{Article|langue=en|auteur1=Peter Guthrie Tait|titre=On generalization of Josephus' problem|périodique=Collected Scientific Papers|volume=2|date=1900|lire en ligne=https://gallica.bnf.fr/ark:/12148/bpt6k99440b/f457.item.texteImage|pages=432-435}}.</ref>{{,}}<ref>{{Article|auteur1=A. Sainte-Laguë|titre=Géométrie de situation et jeux|périodique=Mémorial des sciences mathématiques|volume=41|date=1929|lire en ligne=http://www.numdam.org/item/MSM_1929__41__1_0.pdf|pages=44-45}}.</ref> ?

L'histoire se serait déroulée lors du siège de [[Jotapata]] par [[Vespasien]], en {{Ap JC|67}}{{Sfn|Signac|2012}}.

== Problème général ==
Les soldats sont au nombre de {{Mvar|n}}, numérotés de 1 à {{Mvar|n}} ; les premiers soldats éliminés sont ceux dont le numéro est multiple d'un entier <math>k\geqslant2</math> (<math>k=3</math> dans le problème originel) ; après un tour, les éliminations de {{Mvar|k}} en {{Mvar|k}} des soldats restants se poursuivent jusqu'à ce qu'il n'en reste qu'un. On demande le numéro <math>J_k(n)</math> de ce soldat<ref>{{Article|auteur1=Jean Lefort|titre=Le problème de Flavius Josèphe|périodique=L'ouvert|volume=109|date=2004|lire en ligne=https://publimath.univ-irem.fr/numerisation/ST/IST04035/IST04035.pdf|pages=31-42}}.</ref>{{,}}<ref>{{Article|langue=en|auteur1=L. Halbeisen, N. Hungerbühler|titre=The Josephus Problem|périodique=Journal de Théorie des Nombres de Bordeaux|volume=9, fascicule 2|date=1997|lire en ligne=https://jtnb.centre-mersenne.org/item/10.5802/jtnb.204.pdf}}.</ref>{{,}}<ref name=":3">{{Ouvrage|auteur=[[Ronald Graham|R. L. Graham]]|auteur2=[[Donald Knuth|D. E. Knuth]]|auteur3=[[Oren Patashnik|O. Patashnik]]|titre=[[Concrete Mathematics|Mathématiques concrètes]]|passage=9-18 (k = 2) et 86-88 (cas général)|lieu=Paris|éditeur=International Thomson Publishing France|date=1998}}.</ref>.

Voici par exemple, pour <math>n=10,k=3</math>, les différents ordres d'élimination des soldats :
{| class="wikitable"
|<math>i</math>
|1
|2
|3
|4
|5
|6
|7
|8
|9
|10
|-
|Ordre d'élimination
|6
|4
|1
|'''10'''
|8
|2
|5
|7
|3
|9
|}
Donc <math>J_3(10)=4</math>.

Il est remarquable que le calcul de <math>J_k(n)</math> se programme très facilement, mais qu'on ne connait de formule simple que pour <math>k=2</math>{{sfn|Signac|2012}}.

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

Voir les suites {{OEIS2C|A006257}},  {{OEIS2C|A054995}}, {{OEIS2C|A088333}},  {{OEIS2C|A181281}} donnant les valeurs de <math>J_k(n)</math> pour <math>k=2,3,4,5</math>.

== 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 {{2e}} est exécuté, puis le nouveau {{4e}}, etc.

Si le nombre initial de personnes est pair, alors le soldat à la position {{mvar|x}} au {{2e|tour}} est à la position {{math|2''x'' – 1}} au {{1er|tour}} (peu importe la valeur de {{mvar|x}}). Donc, la personne à la position <math>J_2(n)</math> était auparavant à la position <math>2J_2(n)-1</math> . Cela nous permet de trouver la {{1re|formule}} de récurrence :

: <math>J_2(2n) = 2J_2(n) - 1 \,</math>.

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 {{mvar|x}} était auparavant à la position {{math|2''x'' + 1}}. Cela nous permet de trouver la {{2e|formule}} de récurrence :

: <math>J_2(2n+1) = 2J_2(n) + 1 \,</math>.

On peut réunir les deux formules en : <math>J_2(n) = 2J_2(\left \lfloor n/2\right \rfloor ) -(-1)^n</math>, avec <math>J_2(1)=1</math>.

Les valeurs tabulées de {{mvar|n}} et <math>J_2(n)</math> font apparaître un schéma :
{| class="wikitable"
|<math>n</math>
|1
|2
|3
|4
|5
|6
|7
|8
|9
|10
|11
|12
|13
|14
|15
|16
|-
|<math>J_2(n)</math>
|1
|1
|3
|1
|3
|5
|7
|1
|3
|5
|7
|9
|11
|13
|15
|1
|}
Les <math>J_2(n)</math> forment une suite de valeurs impaires croissantes qui recommence à 1 lorsque {{mvar|n}} est une puissance de 2.

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

{{Théorème|nom=Théorème<ref>On trouvera des prolongements pour l'étude de ce cas dans {{Lien web |titre=G204. Le problème de Josèphe |url=http://www.diophante.fr/problemes-par-themes/g-probabilites/g2-combinatoire-denombrements/660-g204-le-probleme-de-josephe |éditeur=Les jeux mathématiques de Diophante, plus de 800 problèmes mathématiques |année=2009}} et {{Harvsp|Graham|Knuth|Patashnik|1998}}.</ref>|énoncé=Si {{math|''n'' {{=}} 2{{exp|''m''}} + ''l''}} et {{math|0 ≤ ''l'' < 2{{exp|''m''}}}}, alors <math>J_2(n)=2l+1</math>.
}}

{{Démonstration|titre=[[Démonstration par récurrence]]|contenu=
Le cas {{math|''n''{{=}}1}} est vrai. Analysons de façon séparée les cas {{mvar|n}} pair et {{mvar|n}} impair.

Quand {{mvar|n}} est pair, on peut choisir {{math|''l''{{ind|1}}}} et {{math|''m''{{ind|1}}}} de sorte que <math>n/2 = 2^{m_1}+l_1</math> et  {{math|0 ≤ ''l''{{ind|1}} < 2{{exp|''m''{{ind|1}}}}}}. On a alors {{math|''l''{{ind|1}}{{=}}''l''/2}}.

Nous avons <math>J_2(n) = 2J_2(n/2)-1 = 2((2l_1)+1) - 1 = 2l+1</math>, où la deuxième égalité suit de l'hypothèse d'induction.

Quand {{mvar|n}} est impair,on peut choisir {{math|''l''{{ind|1}}}} et {{math|''m''{{ind|1}}}} de sorte que <math>(n-1)/2 = 2^{m_1}+l_1 \,</math> et {{math|0 ≤ ''l''{{ind|1}} < 2{{exp|''m''{{ind|1}}}}}}. On a alors {{math|''l''{{ind|1}}{{=}}(''l''–1)/2}}.

Nous avons <math>J_2(n) = 2J_2((n-1)/2)+1 = 2((2l_1)+1) + 1 = 2l+1</math>, 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 : <math>J_2(n)=2n+1-2^{\left \lfloor \log_2(n)\right \rfloor+1}</math>.

== Cas général ==
En numérotant les positions de 0 à {{math||§=''n'' – 1}}, on a la formule de récurrence permettant d'obtenir <math>J_k(n)</math>  :

: <math>J_k(n)=(J_k(n-1)+k) \bmod n</math> avec <math>J_k(1)=0</math>

Elle apparaît lorsque nous observons comment le nombre de survivants change en passant de {{math||§=''n'' – 1}} à {{mvar|n}}.

Avec une [[programmation dynamique]], elle a un [[Comparaison asymptotique|temps d'exécution asymptotique]] en <math>O(n) \,</math>.

Pour de petites valeurs de {{mvar|k}} et de grandes valeurs de {{mvar|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 <math>O(k\log n) \,</math>. Elle s'appuie sur l'idée de tuer le {{Mvar|k}}{{e}}, 2{{Mvar|k}}{{e}}..., <math>\lfloor n/k \rfloor</math>{{e}} soldat d'un seul coup, puis de changer la numérotation {{Référence souhaitée|date=25 février 2022}}.

== Crible de (Flavius) Josèphe ==
[[Stanislaw Ulam|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 [[Entier naturel|entiers naturels]] non nuls, avec des passages successifs d'éliminations de {{Mvar|k}} en {{Mvar|k}}, où {{Mvar|k}} est la valeur d'un entier non éliminé déterminé. Pour cette raison, il a baptisé ce crible "crible de Flavius Josèphe"<ref name=":1">{{Article|lang=en|prénom=Verna|nom=Gardiner|prénom2=R.|nom2=Lazarus|prénom3=N.|nom3=Metropolis|prénom4=S.|nom4=Ulam|titre=On certain sequences of integers defined by sieves|revue=[[Mathematics Magazine]]|vol=29|numéro=3|année=1956|doi=10.2307/3029719|zbl=0071.27002|p.=117-122}}.</ref>{{,}}<ref name=":2">{{Article|langue=de|auteur1=Mats Erik Andersson|titre=Das Flaviussche Sieb|périodique=[[Acta Arithmetica]]|vol=85|numéro=4|date=1998|lire en ligne=http://matwbn.icm.edu.pl/ksiazki/aa/aa85/aa8542.pdf}}.</ref>.

=== 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 : <code>1, 3, 7, 13, 19, 27, 39, 49, 63, 79,...</code>

Elle est répertoriée comme {{OEIS|A000960}}.

Ce qui est remarquable est que le {{Mvar|n}}-ième nombre restant est équivalent à <math>\pi\frac{n^2}4</math> et que le nombre de nombres restants inférieurs à {{Mvar|n}} équivaut à <math>2\sqrt{\frac{n}{\pi}}</math><ref name=":2" />.

=== Autres cribles similaires ===
Un autre crible imaginé par Ulam et ses compères<ref name=":1" />, semblable mais donnant des résultats différents, est celui dont les survivants sont les [[Nombre chanceux|nombres chanceux]].

Un troisième crible du même type est celui dit de Tchoukaillon, voir la {{OEIS|A007952}}, et un quatrième est celui donnant les nombres pseudo-chanceux, voir la {{OEIS|A249876}}.

== Notes et références ==
{{Traduction/référence|en|Josephus problem|323765939|type=n}}
{{Références}}

== Voir aussi ==
=== Liens externes ===
* {{en}} [http://www.cut-the-knot.org/recurrence/flavius.shtml ''Josephus Flavius Game''] ([[applet Java]]), sur ''[[cut-the-knot]]'' 
* {{MathWorld|nom_url=JosephusProblem|titre=Josephus Problem}}

=== Bibliographie ===
{{Cormen2en}}, chap. 14 (« Augmenting Data Structures »), p. 318

{{Portail|mathématiques|informatique}}

[[Catégorie:Mathématiques récréatives]]
[[Catégorie:Théorie des cribles]]
[[Catégorie:Flavius Josèphe]]