Problème de Josèphe


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.

Sommaire

Description

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[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

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

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

  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

Liens externes

Bibliographie


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de Josèphe de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Josèphe ben Mattatias — Flavius Josèphe Ce buste romain serait celui de Flavius Josèphe[1]. Joseph ben Matthias le Prêtre (hébreu  …   Wikipédia en Français

  • Flavius Josèphe — Pour les articles homonymes, voir Josèphe. Ce buste romain serait celui de Flavius Josèphe[1] …   Wikipédia en Français

  • Flavius Josephe — Flavius Josèphe Ce buste romain serait celui de Flavius Josèphe[1]. Joseph ben Matthias le Prêtre (hébreu  …   Wikipédia en Français

  • Titus-Flavius Josèphe — Flavius Josèphe Ce buste romain serait celui de Flavius Josèphe[1]. Joseph ben Matthias le Prêtre (hébreu  …   Wikipédia en Français

  • Titus Flavius Josèphe — Flavius Josèphe Ce buste romain serait celui de Flavius Josèphe[1]. Joseph ben Matthias le Prêtre (hébreu  …   Wikipédia en Français

  • Marie-Josèphe de Saxe — Cet article concerne la dauphine de France. Pour la reine d Espagne, voir Marie Josèphe de Saxe (1803–1829). Cet article concerne la dauphine de France. Pour la mère de Charles Ier d Autriche, voir Marie Josèphe de Saxe (1867 1944) …   Wikipédia en Français

  • FLAVIUS JOSÈPHE — Né en 37 à Jérusalem, témoin en 70 de la prise de sa ville natale par les Romains et de l’incendie du Temple, Flavius Josèphe est le seul historien juif de cette époque dont l’œuvre ait survécu. À la fois polémiste et mémorialiste, Josèphe reste… …   Encyclopédie Universelle

  • Marie-Josephe de Saxe — Marie Josèphe de Saxe  Cet article concerne la reine de France. Pour pour la reine d Espagne, voir Marie Josèphe de Saxe (1803–1829). Marie Josèphe de Saxe …   Wikipédia en Français

  • Marie-Josèphe De Saxe —  Cet article concerne la reine de France. Pour pour la reine d Espagne, voir Marie Josèphe de Saxe (1803–1829). Marie Josèphe de Saxe …   Wikipédia en Français

  • Marie-Josèphe de Saxe (1731-1767) — Marie Josèphe de Saxe  Cet article concerne la reine de France. Pour pour la reine d Espagne, voir Marie Josèphe de Saxe (1803–1829). Marie Josèphe de Saxe …   Wikipédia en Français