Problème de Josèphe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Description[modifier | modifier le code]

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 enthousiaste à l'idée de mourir, parvint à trouver l'endroit où se tenir[1]. 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[2].

Solution[modifier | modifier le code]

La solution proposée est donnée pour un soldat tué sur deux (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 personnes (et 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 x au 2e tour est à la position 2x - 1 au 1er 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 1re 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 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 :

f(2n+1) = 2f(n) + 1 \,.

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

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

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^m + l et 0 \leq 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^m soldats et nous allons au 2 l + 1e soldat. Il est le survivant. Donc, f(n) = 2 l + 1.

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

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

f(n,k)=(f(n-1,k)+k) \bmod n,\text{ avec }f(1,k)=0,\,, en numérotant les positions de 0 à n-1.

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 ke, 2ke..., \lfloor n/k \rfloore soldat d'un seul coup, puis de changer la numérotation.

Notes et références[modifier | modifier le code]

  1. Grégoire, « Le problème de Flavius Joséphus », Mes Cours de Terminale S,‎ 2006-2007
  2. « G204. Le problème de Joseph », Les jeux mathématiques de Diophante, plus de 800 problèmes mathématiques,‎ 2009

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]