Olympiades · Académique Nantes · 11 mars 2020
\(n\ge2\) personnes numérotées de 1 à \(n\) sont assises en cercle. On retire la personne 1, on laisse son voisin de droite, on retire le suivant, etc., jusqu'à ce qu'il n'en reste plus qu'une, notée \(D(n)\) (exemple : \(D(5)=2\), \(D(6)=4\)).
1. Justifier que pour \(n=6\), la 4e personne retirée porte le numéro 2 et la dernière restante le numéro 4.
2. Donner \(D(n)\) pour \(n\) de 2 à 16 (sans justification).
3. Pour \(n=1024\) : justifier qu'après le premier tour il reste 512 personnes (et que \(1024=2\times512\)), puis calculer \(D(1024)\).
4. Pour \(n=63\) : justifier qu'après le premier tour il reste 31 personnes (et que \(63=2\times31+1\)), puis calculer \(D(63)\).
5. Calculer \(D(65)\).
6. Pour \(n=2020\) : calculer \(D(2020)\), puis (en inversant le sens de parcours à partir du numéro 1) combien de personnes quittent la table avant celle initialement positionnée pour gagner.
7. Démontrer que \(D(2k)=2D(k)\) pour tout \(k<2^n\) (formule générale de récurrence).
8. Déterminer les \(n<2020\) tels que \(D(n)=100\).
9. Déterminer tous les \(n\) tels que \(D(n)=n\).
C'est une variante du problème classique de Josèphe (« Josephus problem »). En notant \(D(n)\) le survivant : si \(n=2m\) est pair, après le premier tour il ne reste que les \(m\) personnes de numéro pair, renumérotées 1 à \(m\) dans le même ordre — on peut montrer que \(D(2m)=2D(m)\). Le cas \(n\) impair demande un peu plus de soin sur le recollement du cercle après le premier tour (attention, ce n'est pas une simple généralisation de la relation précédente : à traiter directement question par question, en particulier pour la question 4).
Pour la question 9 (\(D(n)=n\)) : essayer d'abord les petites valeurs de \(n\) une par une pour repérer une famille de solutions évidente, avant de chercher à démontrer qu'il n'y en a pas d'autre.
1. Premier tour : on retire 1, 3, 5 (dans cet ordre), il reste 2, 4, 6. On reprend après 5 : la personne 2 reste assise (4e action), puis la personne 4 est retirée (5e action). Ordre des retraits : 1, 3, 5, 2, 4 — la 4e personne retirée est bien 2, et 4 reste seule : \(D(6)=4\).
2.
| n | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| D(n) | 2 | 2 | 4 | 2 | 4 | 6 | 8 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 |
3. Après le 1er tour de 1024 personnes, les 512 impairs ont été retirés (1, 3, …, 1023) ; il reste les 512 pairs, et la prochaine personne retirée est 2. En renumérotant les survivants \(2,4,\ldots,1024\) par \(i\mapsto 2i\), le processus redevient identique à celui sur 512 personnes : \(D(1024)=2\,D(512)\). En itérant : \(D(1024)=2D(512)=4D(256)=\cdots=1024\,D(1)=1024\times1=\boxed{1024}\) (1024 étant une puissance de 2).
4. Après le 1er tour de 63 personnes (impaires 1..63 retirées), il reste les 31 pairs \(2,4,\ldots,62\) et la prochaine personne retirée est 4 ; on a bien \(63=2\times31+1\). En utilisant la relation générale \(D(2k+1)=2D(k+1)-2\) (voir question 7 pour l'esprit de la preuve, appliquée ici avec \(k=31\)) : \(D(63)=2D(32)-2=2\times32-2=\boxed{62}\) (32 étant une puissance de 2, \(D(32)=32\)).
5. \(65=2\times32+1\), donc \(D(65)=2D(33)-2\). En descendant : \(33=2\times16+1\Rightarrow D(33)=2D(17)-2\) ; \(17=2\times8+1\Rightarrow D(17)=2D(9)-2\) ; \(9=2\times4+1\Rightarrow D(9)=2D(5)-2\) ; \(5=2\times2+1\Rightarrow D(5)=2D(3)-2\) ; \(3=2\times1+1\Rightarrow D(3)=2D(2)-2=2\times2-2=2\). En remontant : \(D(5)=D(9)=D(17)=D(33)=D(65)=2\times2-2=2\). Donc \(D(65)=\boxed{2}\).
6a. \(2020=2\times1010\Rightarrow D(2020)=2D(1010)\) ; \(1010=2\times505\Rightarrow D(1010)=2D(505)\) ; \(505=2\times252+1\Rightarrow D(505)=2D(253)-2\) ; \(253=2\times126+1\Rightarrow D(253)=2D(127)-2\) ; \(127=2\times63+1\Rightarrow D(127)=2D(64)-2=2\times64-2=126\). En remontant : \(D(253)=2\times126-2=250\), \(D(505)=2\times250-2=498\), \(D(1010)=2\times498=996\), \(D(2020)=2\times996=\boxed{1992}\).
6b. La personne positionnée pour gagner est donc au numéro 1992. En sens inversé (on retire toujours 1 en premier, mais on progresse ensuite dans l'autre sens du cercle), la personne 1992 n'est plus la gagnante : elle est retirée au 1018e retrait. 1017 personnes quittent donc la table avant elle.
7. Pour \(n=2k\) personnes, le premier tour retire tous les impairs \(1,3,\ldots,2k-1\) ; il reste les \(k\) pairs \(2,4,\ldots,2k\), et la prochaine personne retirée est 2 (la première du sous-cercle restant). En renumérotant \(2,4,\ldots,2k\) par \(i\mapsto 2i\) (\(i=1,\ldots,k\)), le processus sur ce sous-cercle de \(k\) personnes est rigoureusement identique au processus de départ sur \(k\) personnes (on repart en retirant la nouvelle personne 1, qui correspond à l'ancienne personne 2). Le survivant du sous-cercle est donc \(D(k)\) en nouvelle numérotation, soit \(2D(k)\) en numérotation d'origine : \(D(2k)=2D(k)\).
8. La recherche des antécédents de 100 par la fonction \(D\) (en remontant l'arbre des relations \(D(2k)=2D(k)\) et \(D(2k+1)=2D(k+1)-2\)) donne exactement cinq solutions inférieures à 2020 : \(n\in\{114,\ 178,\ 306,\ 562,\ 1074\}\). On remarque que ces valeurs suivent le motif \(n=64\times2^k+50\) pour \(k=0,1,2,3,4\) (le terme suivant, \(k=5\), donnerait \(2098>2020\), donc exclu).
9. D'après la question 7, si \(n=2k\) et \(D(n)=n\) alors \(D(k)=k\) : la propriété se transmet en divisant par 2. Si \(n\) est impair, \(n=2k+1\) et l'égalité \(D(2k+1)=2D(k+1)-2=2k+1\) donnerait \(D(k+1)=k+1{,}5\), impossible pour un entier : \(n\) ne peut donc pas être impair. Ainsi \(n\) est nécessairement divisible par 2 autant de fois que possible jusqu'à atteindre 1 : \(n\) est une puissance de 2 (\(n=2,4,8,16,32,\ldots\)), et réciproquement chaque puissance de 2 vérifie bien \(D(n)=n\) (récurrence immédiate à partir de \(D(2)=2\)).