Une Variante du Jeu de Wythoff Définie par la Séquence G de Hofstadter

Informations Fondamentales

• ID de l'article : 2510.11767
• Titre : A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence
• Auteurs : Kahori Komaki, Ryohei Miyadera, Aoi Murakami
• Classification : math.CO (Mathématiques Combinatoires)
• Date de publication : 13 octobre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2510.11767

Résumé

Cet article étudie une variante du jeu classique de Wythoff. Le jeu classique de Wythoff implique deux tas de pierres, où deux joueurs alternent en retirant des pierres d'un ou deux tas, et lorsqu'ils retirent des deux tas simultanément, ils doivent retirer le même nombre. Le joueur qui retire la dernière ou les dernières pierres gagne. De manière équivalente, on peut le considérer comme le déplacement d'une reine d'échecs sur une grille infinie, où chaque joueur peut déplacer la reine un nombre arbitraire de cases verticalement, horizontalement ou diagonalement vers le coin supérieur gauche (0,0).

Dans la variante présentée dans cet article, l'ensemble des positions terminales est étendu à {(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)}. Les positions P de cette variante sont décrites par les positions P du jeu de Wythoff et la séquence G de Hofstadter. La variante possède deux propriétés remarquables : pour les positions (x,y) avec x≥8 ou y≥8, le nombre de Grundy de la position (x,y) dans cette variante est 1 si et seulement si (x,y) est une position P du jeu de Wythoff ; pour les positions (x,y) avec x≥8 ou y≥8, (x,y) est une position P de la version misère de cette variante si et seulement si (x,y) est une position P du jeu de Wythoff.

Contexte de Recherche et Motivation

Définition du Problème

Cette recherche vise à analyser et résoudre une nouvelle variante du jeu classique de Wythoff, où les conditions terminales s'étendent d'une position unique (0,0) à un ensemble contenant six positions. Cette extension, bien qu'apparemment simple, modifie considérablement la complexité et la structure stratégique du jeu.

Importance

1. Signification théorique : Le jeu de Wythoff est un problème classique de la théorie des jeux combinatoires, et ses positions P sont étroitement liées au nombre d'or φ=(1+√5)/2. L'étude de ses variantes contribue à une compréhension plus approfondie des propriétés structurelles des jeux combinatoires.
2. Connexions mathématiques : Cette recherche établit de nouvelles connexions entre la séquence G de Hofstadter et la théorie des jeux combinatoires, ce qui a été peu exploré dans les recherches antérieures.
3. Innovation méthodologique : En introduisant la fonction g(n) et la séquence G de Hofstadter, elle fournit de nouveaux outils mathématiques pour analyser les jeux combinatoires avec des conditions terminales complexes.

Limitations des Méthodes Existantes

Les positions P du jeu classique de Wythoff possèdent une expression en forme fermée explicite, mais lorsque les conditions terminales deviennent un ensemble de plusieurs positions, les méthodes d'analyse traditionnelles ne s'appliquent pas directement. La théorie des jeux combinatoires existante manque d'une approche systématique pour traiter ces conditions terminales étendues.

Contributions Principales

1. Définition d'une nouvelle variante de jeu : Extension des positions terminales du jeu de Wythoff d'un point unique (0,0) à l'ensemble {(x,y) : x+y≤2}
2. Établissement d'une caractérisation complète des positions P : Par l'introduction de la fonction g(n) et de la séquence G de Hofstadter, fourniture d'une formule précise pour les positions P de cette variante
3. Découverte de deux propriétés importantes :
   • Pour les positions avec x≥8 ou y≥8, le nombre de Grundy de cette variante est 1 si et seulement si la position est une position P du jeu de Wythoff original
   • Pour les positions avec x≥8 ou y≥8, une position est une position P de la version misère si et seulement si elle est une position P du jeu de Wythoff original
4. Établissement de connexions avec la séquence G de Hofstadter : Preuve que la fonction g(n) peut être définie récursivement par la séquence G de Hofstadter

Détails de la Méthode

Définition de la Tâche

Entrée : Position de jeu (x,y), où x,y∈ℤ≥0 Sortie : Déterminer si la position est une position P (position gagnante pour le joueur précédent) ou une position N (position gagnante pour le joueur suivant) Contraintes : Les règles de mouvement sont identiques au jeu classique de Wythoff, mais l'ensemble terminal est {(x,y) : x+y≤2}

Cadre Mathématique Principal

1. Définition de la Fonction g(n)

g(0) = 1, g(1) = 0
g(n) = {
  1 - g(m)  si ⌊nφ⌋ = ⌊m(φ+1)⌋ + 1 pour un certain m∈ℤ≥0
  1         autrement
}

2. Caractérisation de l'Ensemble des Positions P

P₁ = P₁,₁ ∪ P₁,₂ ∪ {(0,0)}, où :

• P₁,₁ = {(⌊nφ⌋ + g(n) - 1, ⌊n(φ+1)⌋ + g(n)) : n ∈ ℤ≥0}
• P₁,₂ = {(⌊n(φ+1)⌋ + g(n), ⌊nφ⌋ + g(n) - 1) : n ∈ ℤ≥0}

3. Connexion avec la Séquence G de Hofstadter

Pour n≥2 :

g(n) = {
  1 - g(h(n-1))  si h(n-2) < h(n-1)
  1              autrement
}

où h est la séquence G de Hofstadter : h(0)=0, h(n)=n-h(h(n-1))

Points d'Innovation Technique

1. Technique de Décomposition de Séquences : Par la décomposition des nombres naturels en séquence de Wythoff inférieure A₁={⌊nφ⌋} et séquence de Wythoff supérieure A₂={⌊n(φ+1)⌋}, établissement d'un cadre d'analyse systématique.
2. Conception de Fonctions Récursives : La conception de la fonction g(n) capture astucieusement l'impact de l'extension de l'ensemble terminal sur la distribution des positions P.
3. Analyse des Nombres de Grundy : Par le calcul des nombres de Grundy, établissement de connexions profondes entre cette variante et le jeu original.

Configuration Expérimentale

Méthode de Vérification Théorique

Cet article emploie une méthode de preuve purement théorique, en procédant selon les étapes suivantes :

1. Preuve de Complétude : Preuve que de toute position non-P, on peut se déplacer vers une position P
2. Preuve de Cohérence : Preuve que d'une position P, on ne peut pas se déplacer vers une autre position P
3. Vérification Computationnelle : Analyse exhaustive pour les cas de petite taille

Plage de Vérification Spécifique

• Analyse exhaustive complète pour toutes les positions avec coordonnées x,y≤7
• Pour les cas avec x≥8 ou y≥8, établissement de relations d'équivalence avec le jeu de Wythoff original par preuve théorique

Résultats Expérimentaux

Résultats Théoriques Principaux

Théorème 1 : Caractérisation Complète des Positions P

L'ensemble P₁ est l'ensemble des positions P pour cette variante de jeu, prouvé par les Lemmes 8 et 12 :

• Lemme 8 : D'une position dans P₁, on ne peut pas se déplacer vers une autre position dans P₁
• Lemme 12 : De toute position n'étant pas dans P₁, on peut se déplacer vers une certaine position dans P₁

Théorème 2 : Relation avec le Jeu de Wythoff Original

Pour les positions (x,y) avec x≥8 ou y≥8 :

• G₂(x,y,1)=0 dans cette variante si et seulement si G₀(x,y)=0 dans le jeu original
• Ceci établit l'équivalence des deux jeux pour les positions « grandes »

Théorème 3 : Propriétés de la Version Misère

Les positions P de la version misère (le joueur qui entre dans l'ensemble terminal perd) sont identiques aux positions P du jeu original augmenté d'un tas de pierre unique.

Résultats de Vérification à Petite Échelle

Par vérification exhaustive, les ensembles de positions P à petite échelle suivants ont été déterminés :

• Ensemble A : {(0,0,1), (0,1,1), (0,2,1), (1,0,1), (1,1,1), (2,0,1), (3,6,1), (6,3,1), (4,8,1), (8,4,1)}
• Ensemble B : {(0,3,1), (1,2,1), (2,1,1), (3,0,1), (4,4,1), (5,7,1), (7,5,1)}
• Ensemble C : {(0,0), (1,2), (2,1), (3,5), (5,3), (4,7), (7,4)}

Découvertes Clés

1. Effets de Frontière : Dans la plage x,y≤7, la distribution des positions P diffère significativement du jeu de Wythoff original
2. Comportement Asymptotique : Lorsque les coordonnées sont suffisamment grandes, le comportement de cette variante converge vers le jeu de Wythoff original
3. Propriétés de Séquence : Le modèle de valeurs de la fonction g(n) est étroitement lié aux propriétés de croissance de la séquence G de Hofstadter

Travaux Connexes

Théorie du Jeu de Wythoff

Le jeu classique de Wythoff a été proposé par W.A. Wythoff en 1907, et la relation entre ses positions P et le nombre d'or est un résultat classique des mathématiques combinatoires. Les recherches connexes incluent :

• Théorème de Rayleigh : établissement des propriétés de partition des séquences de Wythoff inférieure et supérieure
• Recherches sur diverses variantes du jeu de Wythoff

Théorie des Séquences de Hofstadter

Hofstadter a défini plusieurs séquences récursives dans « Gödel, Escher, Bach », parmi lesquelles la séquence G possède des propriétés théoriques des nombres particulières :

• Recherche sur les fonctions récursives par Gault et Clint (1988)
• Analyse des relations récursives singulières par Granville et Rasson (1988)

Théorie des Jeux Combinatoires

Cet article appartient au domaine de la théorie des jeux combinatoires impartiaux :

• Théorème de Sprague-Grundy et ses applications
• Méthodes de détermination des positions P et N
• Cadre théorique des jeux misère

Conclusions et Discussion

Conclusions Principales

1. Solution Complète : Fourniture d'une caractérisation complète des positions P pour la variante du jeu de Wythoff avec conditions terminales étendues
2. Connexions Profondes : Révélation des connexions essentielles entre cette variante et la séquence G de Hofstadter
3. Équivalence Asymptotique : Preuve de la relation d'équivalence entre cette variante et le jeu original pour les coordonnées grandes

Limitations

1. Complexité : La définition de la fonction g(n) est relativement complexe, moins élégante que la solution en forme fermée du jeu de Wythoff original
2. Efficacité Computationnelle : La détermination des positions P nécessite le calcul de la séquence de Hofstadter, ce qui peut présenter des problèmes de complexité computationnelle
3. Généralisation : Il reste incertain si la méthode peut être généralisée à d'autres ensembles terminaux

Directions Futures

1. Ensembles Terminaux Plus Généraux : Étude des variantes du jeu de Wythoff avec des ensembles terminaux arbitraires
2. Optimisation Algorithmique : Développement d'algorithmes plus efficaces pour la détermination des positions P
3. Autres Séquences Récursives : Exploration de l'application d'autres séquences récursives célèbres dans les jeux combinatoires

Évaluation Approfondie

Avantages

1. Profondeur Théorique : Établissement de nouvelles connexions entre la théorie des jeux combinatoires et la théorie des séquences récursives, possédant une valeur théorique importante
2. Innovation Méthodologique : La conception de la fonction g(n) est astucieuse, capturant la structure de jeu complexe par définition récursive
3. Preuves Complètes : Fourniture de preuves mathématiques complètes, incluant des arguments détaillés pour de nombreux lemmes techniques
4. Résultats Profonds : La propriété d'équivalence asymptotique découverte fournit une nouvelle perspective pour la compréhension des jeux combinatoires complexes

Insuffisances

1. Expression Complexe : La définition de la fonction g(n) est relativement abstraite, pouvant affecter la compréhension intuitive des résultats
2. Applicabilité Pratique Limitée : Bien que théoriquement complète, la valeur dans les applications pratiques reste incertaine
3. Difficulté de Généralisation : La spécificité de la méthode peut limiter son application à d'autres problèmes

Impact

1. Valeur Académique : Ouverture de nouvelles directions pour la recherche interdisciplinaire entre la théorie des jeux combinatoires et les séquences récursives
2. Contribution Méthodologique : Fourniture de nouveaux outils pour l'analyse des jeux combinatoires avec des conditions terminales complexes
3. Complétude Théorique : Enrichissement du système théorique des variantes du jeu de Wythoff

Scénarios Applicables

1. Recherche Théorique : Approprié pour la recherche théorique en mathématiques combinatoires et théorie des jeux
2. Conception d'Algorithmes : Fourniture de fondations théoriques pour la conception d'algorithmes de stratégies optimales pour les jeux connexes
3. Applications Pédagogiques : Peut servir d'excellent cas d'étude pour démontrer les connexions entre les séquences récursives et les problèmes combinatoires

Références

1. M.H. Albert, R.J. Nowakowski, and D. Wolfe: Lessons In Play, A K Peters/CRC Press, 2007
2. D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, 1980
3. W.A. Wythoff: A modification of the game of Nim, Nieuw Arch. Wiskd, 7 (1907), 199-202
4. V. Granville and J.-P. Rasson, A strange recursive relation, J. Number Theory 30 (1988), 238–241

Cet article apporte une contribution théorique importante au domaine de la théorie des jeux combinatoires. En combinant astucieusement la séquence G de Hofstadter, il fournit un cadre mathématique complet pour l'analyse des variantes du jeu de Wythoff avec des conditions terminales complexes. Bien que présentant certaines limitations en termes d'applicabilité pratique, sa profondeur théorique et son innovation méthodologique en font un résultat de recherche important dans ce domaine.