Le jeu de Josèphe - Un problème ancien

Corrigé

Commençons par construire la liste initial des 41 numéros (de 1 à 41) attribués aux personnes en cercle. Dans cette liste, on supprime un numéro sur 3 avec la fonction pop(rg) qui élimine le numéro de rang rg et on enregistre ce numéro dans la liste ordre. La longueur de la liste len(initial) changeant à chaque suppression d'une personne, pour savoir le rang rg de la prochaine personne à supprimer, on ajoute p‒1 à l'ancien rang (le nombre de personnes sautées) et on se ramène au début de la liste en examinant le reste de la division par len(initial). En effet, arrivés en fin de la liste, il faut continuer comme si le 1er était derrière le dernier. La boucle while qui contient ces deux instructions assure que le processus ne s'achève qu'avec la suppression de la dernière personne. En remplaçant 41 et 3 par les lettres n et p, ce programme pourra être réutilisé avec d'autres valeurs.

n,p,rg=41,3,0
initial=list(range(1,n+1))
ordre=[]
while len(initial) > 0:
  rg=(rg+p-1) % len(initial)
  ordre.append(initial.pop(rg))
print('Ordre de decimation :', ordre)
# pour savoir dans quel ordre seront supprimees les personnes
passage=n*[0]
for i in range(n):
  passage[ordre[i]-1]=i+1
print('Ordre de passage:',passage)

D'après le résultat, Josèphe doit se mettre en 31ème position pour avoir le privilège d'être le dernier à s'autodétruire comme le capitaine d'un navire en perdition qui met un point d'honneur à être le dernier à le quitter. La liste passage qui a été ajoutée à la fin du programme nous donne le rang de l'exécution de chaque personne : le 1er est tué en 14ème, le 2ème est tué en 36ème, le 3ème en 1er, etc.

Ce problème me fait penser à ces ritournelles enfantines où l'on se met en cercle pour désigner celui qui sera le chat (ou que sais-je d'autre) au début de la partie : " plouf plouf, une poule en or c'est toi qui sort " ou bien la plus obscure formule " amstragram pic et pic et colegram bour et bour et ratatam, mistramgram " (je ne suis pas bien sûr de la fin, je cite de mémoire, j'ai trouvé sur internet cette comptine qui termine par "pic" au lieu de "mistramgram"). Tout ça pour dire que le problème de Josèphe se retrouve, de façon moins dramatique, dans nos vies d'enfant.

A quel rang faut-il être pour être choisi (équivalent de supprimé en dernier) ? Supposons donc que nous sommes 5 joyeux bambins et que nous faisions la "plouf", une comptine qui fait 10 pieds si je ne m'abuse. J'entre $n=5$ et $p=10$ dans le programme et trouve qu'il faut me mettre en avant-dernier (la position 4).

Une question intéressante : se peut-il toujours que cette procédure de sélection commence et finisse sur la même personne ? Le nombre $n$ de personnes étant connu, comment choisir le pas $p$ pour que le 1er soit le dernier ? La réponse n'est pas évidente sans le programme. Prenons $n=5$ personnes, cela arrive pour la 1ère fois pour $p=4$.

Mais si on augmente la valeur de $p$, d'autres valeurs possibles continuent à arriver. La suivante est $p=8$, ensuite il faut attendre jusqu'à $p=15$, etc. Pour éviter de relancer le programme à chaque fois, j'écris une boucle qui le fait automatiquement. Je trouve alors la liste des valeurs possibles pour $p$ quand $n=5$, qui semble ne pas avoir de fin : 4, 8, 15, 18, 19, 22, 29, 33, 37, 47, …

Et pour les autres valeurs de $n$ ? Il semble que ce soit toujours possible, parfois le plus petit pas possible est plus grand que $n$ (pour $n=3$, 7, 11, 13, 18, 19, 27, 34, 35, ...), la liste est fort irrégulière. Je regarde par curiosité si cette liste est répertoriée dans l'Encyclopédie des suites d'entiers de Sloane. Non, pas encore. D'autres y sont, comme 2, 5, 2, 4, 3, 11, 2, 3, 8, etc. qui est la liste des premières valeurs de $p$ pour que le premier soit le dernier (liste est référencée A187788).

Les références de cette histoire sont complexes : il y eu tout d'abord ce qu'en dit Josèphe lui-même. Ce personnage du 1er siècle parle de tirer au sort l'ordre des tués et mentionne que c'est le voisin qui procède à l'exécution (et non pas un sur trois, ce qui paraît plus logique). Si Josèphe se retrouve en dernier c'est le fruit du hasard…

Ensuite, il y eut ce livre de Bachet, Problèmes plaisants et délectables qui se font par les nombres (1612) qui présente une situation différente mais qui repose sur le même algorithme : 15 chrétiens et 15 turcs dans un bateau trop chargé ; il faut jeter 15 hommes à la mer et on se fie au sort en jetant un homme sur neuf à la mer, les hommes étant rangés en cercle. La question : "A quelles places mettre les chrétiens, pour qu'aucun d'eux ne soit jeté à la mer ?" se traite par le même algorithme.

Bachet de Méziriac (1581-1638) aurait reformulé dans son livre ce que Nicolas Chuquet (1445-1487) avait publié en 1484 (problème 146 de son livre, édité pour la 1ère fois en 1880). L'idée de sauter deux hommes sur trois daterait de Cardan, Practica Arithmeticae, publié en 1536 (On connaît le jeu de Josèphe, qui avec celui-ci infligea la mort à ses compagnons de telle sorte que, dit-on, ceux-ci pensaient qu'elle leur arrivait par le sort, tandis que lui-même, vu que ceux-ci étaient pris au dépourvu, a été sauvé avec un compagnon seulement ; on dispose en cercle autant de petits cailloux qu'on le souhaite et pour deux comptés on en fait sortir un que l'on a choisi"). J'ai tiré ces informations d'un article de Laurent Signac.