Quarante et un rebelles en cercle

L'histoire

Flavius Josèphe, historien juif du Iᵉʳ siècle, raconte lui-même comment il eut la vie sauve. Piégé dans une cave par les Romains avec quarante autres rebelles, le groupe refuse de se rendre et décide d'un suicide collectif, selon un protocole précis :

• les quarante et une personnes se placent en cercle et se numérotent de 1 à 41 ;
• on parcourt le cercle de trois en trois — la première personne désignée est donc la numéro 3 ;
• la personne désignée est mise à mort, puis retirée du cercle ;
• le comptage reprend à partir de la suivante, sur les survivants ;
• la dernière personne se suicide par ses propres moyens.

Josèphe et un ami n'étaient pas d'accord. La question devient donc : à quelles places se mettre pour être les deux derniers ? Josèphe ayant survécu, on suppose qu'il avait trouvé la réponse.

Ce que le devoir en fait

Le cas général — n personnes, élimination de k en k — n'admet pas de formule simple. Le devoir procède donc en deux temps :

1. une étude informatique qui répond à n'importe quelle configuration par simulation ;
2. une étude mathématique limitée au cas k = 2, où une formule exacte existe et se lit sur l'écriture binaire de n.

On note J(n) le rang du dernier survivant lorsque n personnes sont éliminées de deux en deux.

Le piège de la numérotation

Attention dès le départ : les personnes sont numérotées à partir de 1, alors que les listes Python sont indexées à partir de 0. Confondre les deux fait décaler toutes les réponses d'un rang — c'est l'erreur la plus fréquente sur ce problème.