La récurrence cachée derrière J

Pourquoi le cas k = 2 est spécial

On élimine désormais de deux en deux, et on note J(n) le rang du dernier survivant pour un groupe de n personnes.

Le premier tour de cercle élimine toutes les personnes de rang pair : 2, puis 4, puis 6… C'est la clé de tout. Deux conséquences immédiates :

• le survivant est nécessairement de rang impair ;
• après ce premier tour, il reste exactement les rangs impairs, et le problème se ramène à un problème identique avec deux fois moins de personnes.

La récurrence

Distinguons selon la parité du nombre de départ.

Cas de 2n personnes. Le premier tour élimine les n personnes de rang pair et se termine juste avant la personne 1. Il reste les n personnes de rangs 1, 3, 5, …, 2n−1, et le comptage repart de la première : c'est le problème à n personnes, où la j-ième renumérotée occupe le rang 2j − 1.

   J(2n) = 2·J(n) − 1

Cas de 2n + 1 personnes. Le premier tour élimine les rangs pairs, puis, revenant au début, élimine aussi la personne 1 (car le nombre de départ est impair, le comptage « boucle » sur elle). Il reste n personnes, de rangs 3, 5, …, 2n + 1, et la j-ième renumérotée occupe le rang 2j + 1.

   J(2n + 1) = 2·J(n) + 1

Avec J(1) = 1, ces deux relations déterminent J entièrement.

Ce qu'elles racontent en binaire

Doubler n, c'est ajouter un 0 à droite de son écriture binaire ; doubler et ajouter 1, c'est ajouter un 1. Les relations ci-dessus font donc la même chose sur J que sur n, à ceci près qu'un 0 devient −1 et un 1 devient +1. C'est ce parallélisme que la formule finale exprime : J(n) s'obtient en déplaçant le 1 de tête de n à la fin de son écriture binaire.

   41 = 101001₂   →   J(41) = 010011₂ = 10011₂ = 19