Exercice 2 — Saut de jetons

Sujet

On dispose \(N\) jetons numérotés de 1 à \(N\) en cercle dans l'ordre croissant en tournant dans le sens des aiguilles d'une montre. En se plaçant sur le jeton numéro 1 au départ, le jeu consiste à éliminer successivement un jeton sur deux en commençant par le numéro 2 et de s'intéresser au dernier jeton restant.

Ainsi pour \(N=7\), on élimine dans l'ordre les jetons numéros : \(2,4,6,1,5,3\) et le numéro 7 est le dernier jeton restant.

Partie A

1. Déterminer le numéro du dernier jeton restant pour \(N=8\) et pour \(N=16\).
2. Quel serait le dernier jeton restant dans le cas où \(N\) est une puissance de 2 ? ( \(N=2^{p}\) avec \(p\) entier naturel)?
3. Déterminer le dernier jeton restant pour \(N=21\) et pour \(N=26\).
4. Soit \(p\) l'entier tel que \(2^{p}\) est la plus grande puissance de 2 inférieure ou égale à \(N\). On suppose qu'on a entamé le processus et qu'on a déjà retiré \(\left(N-2^{p}\right)\) jetons.
   a) Justifier que l'on n'a pas encore fait le tour du cercle.
   b) Montrer que le numéro du dernier jeton retiré est \(2 \times\left(N-2^{p}\right)\).
   c) Quel sera le numéro du dernier jeton restant?
5. Déterminer le numéro du dernier jeton restant pour \(N=2014\) et pour \(N=2015\).

Partie B

Soit \(N\) un entier naturel, on note \(\overline{\left(a_{n} a_{n-1} a_{n-2} \ldots a_{1} a_{0}\right)}\) son écriture en base deux, c'est-à-dire \(N=a_{n} 2^{n}+a_{n-1} 2^{n-1}+\cdots+2 a_{1}+a_{0}\) tel que \(a_{i}=0\) ou \(a_{i}=1\) pour tout \(0 \leqslant i \leqslant n-1\) et \(a_{n}=1\). Pour faciliter la conversion entre la base deux et la base dix on utilise le tableau suivant: