Additive Subtraction Games

Cet article établit la structure complète des valeurs de Nim pour les jeux de soustraction additifs dans le régime quadratique primitif, en fournissant une preuve rigoureuse d'une formule fermée existante et en démontrant que chaque séquence de valeurs de Nim correspond à un décalage linéaire des positions P classiques.

L'essentiel

Voici une explication de ce papier de recherche, traduite en langage simple et imagé pour le grand public.

🎮 Le Jeu de la Soustraction : Une Danse Mathématique

Imaginez un jeu de société simple joué avec des tas de jetons. Deux joueurs s'affrontent à tour de rôle. À chaque tour, un joueur doit retirer un certain nombre de jetons, mais il ne peut choisir que parmi trois options précises : $a$, $b$, ou $a+b$ (où $b$ est un peu plus grand que $a$).

Le but ? Être le dernier à pouvoir jouer. Si vous êtes face à un tas de jetons et que vous ne pouvez pas enlever le bon nombre sans dépasser le total, vous perdez.

Les mathématiciens (ici, Urban Larsson et Hikaru Manabe) se demandent : "Qui va gagner si on commence avec un tas de taille $n$ ?"

Pour répondre, ils utilisent un outil appelé la "valeur de Nim". C'est comme une étiquette magique collée sur chaque taille de tas :

• 0 : C'est une position perdante (si vous êtes là, vous êtes condamné si l'adversaire joue bien).
• 1, 2, 3 : Ce sont des positions gagnantes, avec des stratégies différentes.

🧩 Le Problème : Un Motif Caché

Dans ce jeu spécifique, les chercheurs ont découvert que les positions perdantes (les étiquettes "0") ne sont pas aléatoires. Elles suivent une formule très précise, un peu comme une recette de cuisine mathématique.

Cette formule ressemble à une machine à calculer :

Prenez un nombre $n$, ajoutez une partie de $n$ divisée par $a$, ajoutez une partie de $n$ divisée par $b$...

C'est ce qu'on appelle une expression à crochet (ou "bracket expression"). C'est une suite de nombres qui semble un peu chaotique au premier coup d'œil, mais qui cache une structure très ordonnée.

Le problème, c'est que cette formule a été découverte il y a longtemps (dans le célèbre livre Winning Ways en 1982), mais personne n'avait jamais prouvé qu'elle fonctionnait vraiment pour ce cas précis. C'était comme avoir la clé d'un coffre-fort sans savoir si elle ouvrait bien la serrure.

🔍 La Découverte : Le "Régime Quadratique Primitif"

Les auteurs se sont concentrés sur un cas particulier, qu'ils appellent le "régime quadratique primitif". Imaginez que $a$ et la différence entre $a$ et $b$ (appelée $\delta$) soient deux amis qui dansent ensemble.

• Si l'un est trop grand par rapport à l'autre, la danse est simple et prévisible (comme une ligne droite).
• Mais dans ce cas précis, ils sont de tailles comparables mais pas identiques ($a < \delta < 2a$). C'est là que la magie opère : la complexité explose, et la danse devient un motif en spirale complexe.

Leur grande découverte :
Ils ont prouvé que cette formule mystérieuse fonctionne parfaitement. Mais ce n'est pas tout ! Ils ont aussi découvert que les autres positions (celles avec les étiquettes 1, 2 et 3) sont simplement des copies décalées de la première formule.

C'est comme si vous aviez un tapis de sol avec un motif (les positions 0).

• Les positions 1 sont ce même tapis, mais décalé de quelques pas vers la droite.
• Les positions 2 sont le tapis décalé vers la gauche.
• Les positions 3 sont un petit morceau du tapis qui a été coupé et collé ailleurs.

Ensemble, ces quatre tapis recouvrent tous les nombres possibles sans aucun trou et sans aucun chevauchement. C'est un puzzle parfait.

🕵️‍♂️ L'Enquête : Comment ont-ils fait ?

Pour prouver que tout cela fonctionne, les auteurs ont dû résoudre un casse-tête mathématique appelé le "comptage des collisions".

Imaginez que vous marchez sur un chemin où les pas ont des tailles variables (1, 5, 12, etc.). Parfois, vous voulez savoir si une série de pas consécutifs peut former exactement une distance précise (ici, la distance $\delta$).

• L'analogie des fenêtres de collision : Les chercheurs ont imaginé que chaque grand pas (de taille $a+1$) était une fenêtre. Autour de cette fenêtre, il y a des petits pas (de taille 1). Ils ont dû compter de combien de façons différentes on pouvait assembler ces petits pas autour de la grande fenêtre pour atteindre exactement la distance $\delta$.
• Ils ont divisé le problème en trois zones (gauche, milieu, droite) et ont utilisé des outils de théorie des nombres (comme les restes de division) pour compter exactement combien de fois chaque configuration se produit.

Le résultat ? Le nombre de ces "collisions" correspond exactement à la quantité nécessaire pour que les quatre tapis (0, 1, 2, 3) remplissent parfaitement l'univers des nombres.

🏆 Pourquoi c'est important ?

1. Une énigme résolue : Ils ont enfin apporté la preuve formelle d'une formule qui traînait dans les livres depuis 40 ans.
2. Une structure claire : Ils ont montré que même dans un jeu complexe, il existe une logique profonde et élégante. Les positions gagnantes et perdantes ne sont pas du chaos, mais une architecture géométrique précise.
3. Une nouvelle porte : Cette méthode ouvre la voie pour comprendre d'autres jeux plus complexes. Ils se demandent maintenant si on peut trouver des formules similaires pour des jeux avec encore plus d'options de mouvement.

En résumé :
Ce papier est comme la découverte d'un code secret dans un jeu vidéo. Les auteurs ont prouvé que le niveau le plus difficile (le régime quadratique) suit une règle mathématique précise, qu'ils ont décryptée en observant comment les "pas" du jeu s'assemblent. Ils nous ont donné la carte complète pour gagner à ce jeu, peu importe la taille du tas de départ.

Résumé technique

Voici un résumé technique détaillé de l'article « Additive Subtraction Games » d'Urban Larsson et Hikaru Manabe, rédigé en français.

1. Problématique et Contexte

L'article se concentre sur l'analyse des jeux de soustraction additifs, une classe de jeux combinatoires à deux joueurs joués sur des tas de jetons. Dans ce type de jeu, les joueurs retirent alternativement un nombre $s$ de jetons, où $s$ appartient à un ensemble fixe $S$ d'entiers positifs. Le joueur qui ne peut pas jouer (car toute soustraction entraînerait un nombre négatif) perd.

Le problème spécifique traité ici concerne le cas où l'ensemble des soustractions est $S = \{a, b, a+b\}$ avec $b = a + \delta$. Les auteurs se penchent sur le régime quadratique primitif, défini par les conditions :

• $a < \delta < 2a$
• $\text{pgcd}(a, \delta) = 1$

Ce régime est considéré comme la source fondamentale de la complexité quadratique du problème. L'objectif est de déterminer la structure complète des valeurs de nim (ou nimbers) pour toutes les positions du jeu.

Historiquement, une formule fermée pour les positions perdantes (P-positions, valeur de nim 0) a été proposée dans l'ouvrage Winning Ways (Berlekamp et al., 1982), mais une preuve complète de cette affirmation n'avait jamais été publiée. Des travaux récents (Miklós et Post, 2024) ont établi la périodicité des résultats, mais sans fournir la description explicite des classes de valeurs de nim via des expressions de type Beatty.

2. Méthodologie

La démarche des auteurs repose sur une combinaison d'analyse combinatoire, de théorie des jeux et de théorie des nombres élémentaire.

• Hypothèse de travail : Les auteurs partent de la formule conjecturée pour les P-positions ($W_0$) :
  $$w_n = n + a \left\lfloor \frac{n}{a} \right\rfloor + b \left\lfloor \frac{n}{\delta} \right\rfloor$$
  où $b = a + \delta$. Cette expression est une « expression à crochets » (bracket expression) sur trois termes.

• Stratégie de preuve par récurrence forte : La vérification de la règle du mex (minimum excludant) est effectuée par récurrence sur la taille de la position. Pour chaque position $x$, on suppose que les valeurs de nim des positions inférieures sont correctes, puis on vérifie la cohérence pour $x$.

• Analyse structurelle des écarts (Gaps) : Une partie cruciale de la méthodologie consiste à étudier la séquence des écarts entre les positions consécutives de $W_0$, définie par $g_n = w_{n+1} - w_n$. Les auteurs démontrent que cette séquence ne prend que quatre valeurs possibles, déterminées par les classes de résidus de $n+1$ modulo $a$ et $\delta$.

• Comptage des collisions ($\delta$-collisions) : Le cœur technique réside dans l'analyse de l'ensemble d'intersection $C = (W_0 - \delta) \cap W_0$. Compter le nombre de fois où un décalage de $\delta$ relie deux éléments de $W_0$ est essentiel pour déterminer la taille de l'ensemble des positions de valeur 3. Les auteurs introduisent le concept de « fenêtres de collision » (collision windows) et divisent les résidus en trois régions (restreinte à gauche, non restreinte, restreinte à droite) pour calculer précisément le nombre de collisions.

3. Résultats Principaux

Le résultat central est l'établissement d'une partition complète de l'ensemble des entiers naturels $\mathbb{N}_0$ en quatre ensembles disjoints, correspondant aux quatre valeurs de nim possibles (0, 1, 2, 3).

Théorème Principal (Théorème 1) :
Sous les hypothèses $a < \delta < 2a$ et $\text{pgcd}(a, \delta) = 1$, les ensembles suivants forment une partition de $\mathbb{N}_0$ :

1. Valeur 0 (P-positions) : $W_0 = \{w_n : n \ge 0\}$.
2. Valeur 1 : $W_1 = W_0 + a$.
3. Valeur 2 : $W_2 = W_0 - b$.
4. Valeur 3 : $W_3 = (W_0 - \delta) \setminus W_0$.

Points clés des résultats :

• Anti-collision : Il est démontré qu'aucun mouvement autorisé (soustraction de $a$, $b$ ou $a+b$) ne relie deux positions au sein d'un même ensemble $W_i$.
• Accessibilité (Reachability) : Chaque position dans un ensemble $W_i$ ($i>0$) possède au moins une option menant à un ensemble $W_j$ avec $j < i$, satisfaisant ainsi la règle du mex.
• Comptage des collisions : Le nombre de collisions dans une période de tas (heap-period) est exactement $ad$ (où $d = \delta - a$). Cela permet de prouver que la taille de $W_3$ dans une période est $a^2$, ce qui, combiné aux tailles des autres ensembles, correspond exactement à la longueur de la période de l'ensemble du jeu.
• Périodicité : La période des indices est $a\delta$, tandis que la période des positions (heap-period) est $(3\delta + a)a$.

4. Contributions et Signification

• Preuve d'une conjecture ouverte : L'article fournit la première preuve complète de la formule fermée pour les P-positions dans le régime quadratique primitif, une conjecture présente dans la littérature depuis 1982.
• Structure fine des valeurs de nim : Contrairement aux études précédentes qui se contentaient de prouver la périodicité, ce travail offre une description explicite et complète de la répartition de toutes les valeurs de nim (0 à 3) via des translations affines d'une expression à crochets.
• Nouveauté en théorie des nombres : L'analyse des « collisions $\delta$ » et la décomposition en trois régions de résidus pour les expressions à crochets rationnels constituent une avancée méthodologique. Cela va au-delà des séquences de Beatty classiques (généralement irrationnelles) et des conjectures de Fraenkel sur les partitions.
• Complexité fondamentale : L'article soutient l'idée que le régime quadratique primitif capture l'essence de la complexité de la théorie générale des jeux de soustraction additifs, comme le suggèrent également des travaux récents sur le dual (soustraction avec puits).

5. Perspectives et Problèmes Ouverts

Les auteurs concluent en soulevant plusieurs questions pour la recherche future :

• L'extension de ces résultats aux jeux de soustraction additifs génériques.
• La possibilité d'exprimer les P-positions de jeux de degré polynomial supérieur à l'aide d'expressions à crochets avec plus de trois termes.
• L'étude de la structure des collisions pour des décalages $k$ arbitraires ($C(k) = (W-k) \cap W$) et la densité de collision associée, en cherchant à généraliser la structure à trois régions observée ici.

En résumé, cet article résout un problème classique de la théorie des jeux combinatoires en fournissant une preuve rigoureuse et une caractérisation complète des valeurs de nim pour une famille de jeux de soustraction, en s'appuyant sur une analyse arithmétique fine des expressions à crochets.