É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}}.

Cliquer ici pour voir (ou cacher) le corrigé