The Ordered Zeckendorf Game

1. Problématique et Contexte

Le papier introduit et analyse une nouvelle variante combinatoire à deux joueurs du jeu de Zeckendorf, inspirée du théorème de Zeckendorf. Ce théorème stipule que tout entier positif peut être décomposé de manière unique en une somme de nombres de Fibonacci non consécutifs (avec $F_1=1, F_2=2$).

• Contexte : La version classique du jeu (étudiée précédemment par Baird-Smith et al.) opère sur des multisets non ordonnés de nombres de Fibonacci. Dans cette version, le joueur 2 possède une stratégie gagnante pour tout $n > 2$, ce qui rend le jeu stratégiquement pauvre.
• Problème : Les auteurs proposent une variante ordonnée où les termes sont disposés dans une séquence ordonnée. Les mouvements sont restreints aux éléments adjacents et incluent une nouvelle opération : l'échange (switch). L'objectif est d'étudier comment l'imposition de contraintes d'ordre et de voisinage modifie la dynamique du jeu, la complexité stratégique et les résultats de victoire.

2. Méthodologie

L'approche combine l'analyse théorique rigoureuse (théorie des jeux combinatoires, monovariants) et des simulations computationnelles massives.

• Définition du Jeu :

  • État initial : Une liste ordonnée de $n$ copies de $F_1$.
  • Mouvements autorisés :
    1. Fusion (Merging) : Remplacer $(F_i, F_{i+1})$ par $F_{i+2}$.
    2. Fusion des uns : Remplacer $(F_1, F_1)$ par $F_2$.
    3. Division (Splitting) : Remplacer $(F_i, F_i)$ par $(F_{i-2}, F_{i+1})$ pour $i > 2$.
    4. Division des deux : Remplacer $(F_2, F_2)$ par $(F_1, F_3)$.
    5. Échange (Switching) : Échanger deux éléments adjacents $(F_i, F_j)$ si $i > j$ (pour rétablir l'ordre croissant).
  • Condition de fin : Le jeu s'arrête lorsque la liste est strictement croissante et qu'aucune fusion ou division n'est possible (correspondant à la décomposition de Zeckendorf).

• Outils Théoriques :

  • Monovariant : Construction d'une fonction $f(S)$ pondérée par les indices des termes pour prouver la terminaison et l'absence de cycles.
  • Analyse des états : Utilisation de graphes d'états pour modéliser les transitions entre configurations, en particulier concernant les répétitions de termes à haut indice.
  • Simulations : Exécution de milliers de parties aléatoires et de stratégies optimales (via recherche en profondeur) pour $n \le 25$ et au-delà pour estimer les distributions.

3. Contributions Clés et Résultats Principaux

A. Terminaison et État Final

• Théorème 1.3 : Le jeu ordonné termine toujours en un nombre fini de coups. L'état final est unique et correspond à la décomposition de Zeckendorf de $n$ sous forme de suite strictement croissante.
• Preuve : Basée sur un monovariant $f(S) = \sum (k+1-j)F_{i_j}$ qui décroît strictement à chaque mouvement, garantissant l'absence de cycles.

B. Longueur du Jeu (Bornes)

Les auteurs établissent des bornes asymptotiques pour la longueur maximale $M(n)$ et minimale du jeu.

• Longueur Minimale (Proposition 1.4) : La longueur minimale est exactement $n - Z(n)$, où $Z(n)$ est le nombre de termes dans la décomposition de Zeckendorf. Cela correspond à une stratégie "gourmande" (greedy) sans échanges.
• Longueur Maximale (Théorèmes 1.5, 1.10, 1.11) :
  • Une borne supérieure est donnée par $M(n) \le \frac{n(n-1)}{2}$.
  • Une borne inférieure est établie via une stratégie spécifique (LGS - Long Game Strategy) qui privilégie les échanges, puis les fusions/divisions dans un ordre précis.
  • Résultat Asymptotique (Corollaire 1.12) : La longueur maximale croît quadratiquement :
    $$M(n) = \frac{n^2}{2} - \Theta(n \log_\phi n)$$
    où $\phi$ est le nombre d'or. Les simulations suggèrent que le terme correctif est significatif mais inférieur à 1.

C. Stratégies de Victoire

• Résultat Empirique Majeur : Contrairement au jeu classique où le joueur 2 gagne systématiquement, dans le jeu ordonné, le joueur 1 gagne pour presque toutes les valeurs de $n \le 25$, à l'exception notable de $n=18$ où le joueur 2 gagne.
• Implication : L'introduction de l'ordre et des mouvements d'échange rétablit un équilibre stratégique et augmente la complexité, favorisant le premier joueur pour la plupart des petits entiers. La résolution complète pour $n > 25$ reste un problème ouvert en raison de l'explosion combinatoire de l'arbre de jeu.

D. Comportement Probabiliste

• Conjecture 3.2 : Pour des jeux joués aléatoirement (choix uniforme des coups légaux), la distribution du nombre de coups converge vers une distribution log-normale lorsque $n \to \infty$.
• Équilibre : Sous un jeu aléatoire, les probabilités de victoire pour les deux joueurs semblent égales, suggérant une symétrie dynamique dans l'espace des états.

4. Signification et Perspectives

Ce travail enrichit considérablement le paysage des jeux théoriques liés aux nombres et aux décompositions entières :

1. Complexité Stratégique : Il démontre que l'imposition de contraintes d'ordre (adjacence) transforme un jeu trivial (gagné par le joueur 2) en un jeu riche et équilibré, posant de nouveaux défis algorithmiques pour la détermination des stratégies optimales.
2. Outils Mathématiques : La construction de monovariants adaptés aux permutations et aux opérations de fusion/division offre de nouvelles perspectives pour l'analyse des systèmes de réécriture combinatoires.
3. Ouvertures :
   • La preuve rigoureuse de la stratégie gagnante pour le joueur 1 (ou l'identification d'autres exceptions).
   • La démonstration formelle de la conjecture sur la distribution log-normale.
   • La généralisation à d'autres suites de récurrence (k-bonacci, suites non constantes).
   • L'extension à des jeux à plusieurs joueurs ou avec alliances.

En résumé, le jeu de Zeckendorf ordonné sert de plateforme fertile pour explorer l'interaction entre la théorie des nombres, la théorie des jeux combinatoires et les systèmes dynamiques, tout en soulevant des questions fondamentales sur la complexité computationnelle des stratégies optimales dans des espaces d'états contraints.