TCA 101
Jeu de Fibonacci

J'ignore le nom officiel de ce jeu, qui a été introduit comme (excellent) exemple d'algorithme pour le cours de TCA 101 par Jean-Michel Couvreur.

C'est un jeu qui utilise un tas de jetons (c'est plus prudent que des allumettes) et un seul (contrairement au jeu de Nim, qui utilise plusieurs tas). Chaque joueur, à tour de rôle, prend un ou plusieurs jetons ; le gagnant est celui qui vide le tas (autrement dit celui qui prend le dernier jeton). Il y a une règle essentielle, et une règle accessoire pour éviter un horrible biais en faveur du premier joueur :

Une position du jeu est donc définie par un couple (n, p), où n désigne le nombre de jetons présents dans le tas (autrement dit n est la taille du tas), et p le nombre maximal de jetons que le joueur peut prendre.

Positions gagnantes et positions perdantes

  1. Il est clair que toute position (n, n) est gagnante (mais ce ne peut pas être la position initiale, d'après la seconde règle du jeu, qui interdit au premier joueur de tout rafler).
  2. Une position est perdante si, quel que soit le coup autorisé, celui-ci transforme la position en une position gagnante.
  3. Symétriquement une position est gagnante s'il existe un coup autorisé qui la transforme en une position perdante.
Les deux derniers principes suffisent, pour tout jeu, à calculer de façon récursive quelles sont les positions gagnantes et perdantes, pourvu qu'on dispose d'une initialisation convenable, comme en 1. ci-dessus.

Questions

  1. Déterminer les positions gagnantes et les positions perdantes pour des jeux de petite taille : n = 2, 3, ... 8.
  2. Soit gn la plus petite valeur de p telle que la position (n, p) soit gagnante. Les premières valeurs de la suite g sont :

    n 1 2 3 4 5 6
    gn 1 2 3 1 5 1

    Calculer les valeurs suivantes de la suite g , jusqu'à n = 15.

  3. Ecrire une procédure Maple qui calcule les n premières valeurs de la suite g.
  4. La suite de Fibonacci Fi est définie par :

    Calculer les termes de cette suite inférieurs à 100. Automatiser ce calcul : écrire une procédure Maple qui, pour un entier n donné, calcule les premières valeurs F1 , F2 , ... Fk de cette suite, où k désigne le plus grand indice tel que Fk ≤ n.

  5. Montrer que tout nombre s'écrit de façon unique comme somme de nombres de Fibonacci non consécutifs. Compléter la table suivante jusqu'à n = 25 :

    n 1 2 3 4 5 6 7 8 9 10
    1 2 3 3 + 1 5 5 + 1 5 + 2 8 8 + 1 8 + 2

    En comparant cette table et la suite g , deviner une règle simple de calcul de gn. Quelles sont les positions initiales perdantes dans ce jeu ?

Corrigé

Un corrigé est disponible sous forme de feuille de calcul Maple.