Élimination de jetons sur un cercle

Publié le 11/04/17

(cet exercice est issu de l’oral Ensam Psi 2015)
On dispose en cercle {n} jetons numérotés de {0} à {n- 1} (comme sur le cadran d’une horloge). On retire le jeton numéro {0}, puis un sur deux en parcourant le cercle jusqu’à ce qu’il ne reste plus qu’un seul jeton. Par exemple, pour {n = 5}, on retire le jeton numéro {0}, puis le {2}, puis le {4}, puis le {3}: il reste donc le numéro {1}.
On représente la situation par une liste de booléens : \texttt{False} si le jeton est encore présent dans le cercle, et \texttt{True} s’il a été retiré.

  1. Écrire une fonction \texttt{suivant} prenant en argument une liste de booléens et un entier {p}, qui donne le rang du premier \texttt{False} à partir du rang {p+1} dans la liste parcourue de manière circulaire.
    Cette fonction doit renvoyer {-1} si \texttt{False} est absent de la liste. Par exemple :
    \texttt{suivant([True, True, False, True, False], 0)} donne 2
    \texttt{suivant([True, True, False, True, False], 2)} donne 4
    \texttt{suivant([True, True, False, True, False], 4)} donne 2
  2. Simuler le processus pour {n = 5} à l’aide de la fonction \texttt{suivant}.
  3. Écrire une fonction \texttt{reste} prenant en argument un entier naturel {n}, qui donne le numéro du dernier jeton restant à la fin du processus.
  4. Émettre une conjecture sur le numéro restant en fonction de {n}, et la vérifier pour pour {n = 256}, {512}, {1024}, etc.
  5. Ajouté à l’énoncé: démontrer la conjecture pour les {n} de la forme {n=2^{k}}.

  1. Voici une solution commentée :

    On vérifie avec les exemples de l’énoncé:

  2. On utilise une variable \texttt{p} pour désigner la position à laquelle on pense retirer un jeton.

    Au départ \texttt{p} contient {0}. Ensuite (et c’est déjà presque un programme) on appelle deux fois la fonction \texttt{suivant}, en actualisant la variable \texttt{p}, et on retourne le jeton (on met la case d’indice \texttt{p} de \texttt{L} à la valeur \texttt{true}).

    Voici la simulation demandée :

  3. Voici la fonction demandée :

    On reprend l’exemple de {n=5}. Le dernier jeton restant est en position 1 :

  4. On écrit \texttt{listerestes(n)} renvoyant la liste {L} des résultats de \texttt{k} pour {1\le k\le n}.

    On écrit \texttt{tracerestes(n)} qui trace le nuage des points {(k,L_{k})}, pour {1\le k\le n}.

    On remarque les restes successifs sont constituées de sous-suites de nombres impairs consécutifs de {1} à {2^{k}-1}, avec {k=1}, {k=2}, {k=3}, etc.
    On a fait ressortir cette observation sur l’exemple ci-dessous (où {n=32}) en intercalant une espace à chaque redémarrage de sous-suite:

    Pour tout {n\ge1}, il existe un unique entier {k\ge0} tel que {2^{k}\lt n\le 2^{k+1}}.

    Si on pose {n=2^{k}+r}, avec {1\le r\le 2^{k}}, on voit que le résultat de \texttt{reste(n)} est {2r-1}.

    On trouve par exemple :
    {\texttt{reste}(2^{k})=2^{k}-1}, {\texttt{reste}(2^{k}+1)=1}, {\texttt{reste}(2^{k}+2)=3}, etc., {\texttt{reste}(2^{k+1})=2^{k+1}-1}.

    Le graphiques, obtenu par \texttt{tracerestes(128)}, montre bien les montées successives.
    Ensam2015-fig02
    Enfin l’instruction suivante confirme l’égalité {\texttt{reste}(2^{k})=2^{k}-1}:

  5. On peut ébaucher une démonstration par récurrence pour montrer que {\texttt{reste}(2^{k})=2^{k}-1}.

    La propriété est vraie si {k=0} car {\texttt{reste}(1)=0}.

    On suppose qu’elle est vraie au rang {k}.

    On considère le cadran de {2^{k+1}} jetons, numérotés de {0} à {2^{k+1}-1}.

    Un premier « tour du cadran » élimine les jetons de positions {p} paires.

    Il ne reste que les jetons de position {p=2p'+1}, où {0\le p'\le 2^{k}-1}.

    Le prochain à retirer est alors en position {p=1} ({p'=0}).

    Si on renumérote ces jetons par {p'}, on revient à la situation initiale pour un cadran de taille {2^{k}}.

    Par hypothèse de récurrence, le dernier jeton restant est en position {p'=2^{k}-1} (nouvelle numérotation) donc la position {p=2p'+1=2^{k+1}-1} (numérotation initiale), ce qui prouve la propriété au rang {k+1} et achève la récurrence.