Problème de Josèphe

En mathématiques et en informatique, le problème de Josèphe ou problème de Joséphus est lié à certaines formulettes d'élimination. Il a été énoncé sous différentes formes, mais sa première formulation est due à Flavius Josèphe.

Des soldats juifs, cernés par des soldats romains, décident de former un cercle. Un premier soldat est choisi au hasard et est exécuté, le troisième à partir de sa gauche (ou droite) est ensuite exécuté. Tant qu'il y a des soldats, la sélection continue. Le but est de trouver à quel endroit doit se tenir un soldat pour être le dernier. Josèphe, peu enthousiate à l'idée de mourir, parvint à trouver l'endroit où se tenir. Quel est-il ?

Ce problème de permutations peut être complexifié, par exemple en faisant varier le nombre de soldats à « sauter », en demandant une solution générale pour un nombre fixe de soldats ou en demandant un certain nombre de survivants.

La solution proposée est donnée pour chaque deuxième soldat tué (k = 2). Une solution pour le cas général est également donnée. Les deux s'effectuent de façon récursive.

Soit f(n) qui donne la position du survivant lorsqu'il y a n personne (et k = 2).

Lors du premier tour complet, tous les soldats aux positions paires sont exécutés. Au deuxième tour, le nouveau 2 est exécuté, puis le nouveau 4, etc. Si le nombre initial de personnes est pair, alors le soldat à la position x au 2 tour est à la position 2x − 1 au 1 tour (peu importe la valeur de x). Donc, la personne à la position f(n) était auparavant à la position 2f(n) − 1. Cela nous permet de trouver la 1 formule de récurrence :

$f(2n)=2f(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 tour. Pendant le 2 tour, le soldat à la 2 position est exécuté, puis le 4, etc. Dans ce cas, le soldat à la position x était auparavant à la position 2x + 1. Cela nous permet de trouver la 2 formule de récurrence :

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

Les valeurs tabulées de n et f(n) font apparaître un schéma :

f(n) est une série de valeurs impaires croissantes qui recommence à 1 pour chaque puissance de 2.

Si nous choisissons m et l de façon à ce que n = 2 + l et $0\le l<2^m$, alors $f(n)=2\cdot l+1$. Les valeurs de la table respectent cette équation. Également, après l exécutés, il ne reste que 2 soldats et nous allons au 2l + 1 soldat. Il est le survivant. Donc, f(n) = 2l + 1. Démontrons que cette équation est mathématiquement vraie par induction.

Théorème — Si $n=2^m+l$ et $0\le l<2^m$, alors $f(n)=2l+1$.

Pour le cas général, on peut faire appel à la programmation dynamique. Cette approche done la formule de récurrence :

Elle apparaît lorsque nous observons comment le nombre de survivants change en passant de n − 1 à n. Elle a un temps d'exécution asymptotique $O(n)$, mais pour de petites valeurs de k et de grandes valeurs de n, il existe une autre approche. Cette deuxième 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 k, 2k..., $\lfloor n/k\rfloor$ soldat d'un seul coup, puis de changer la numérotation.