🔢 mathematics

Structural Conjectures for 4 x n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry

Cet article présente une étude computationnelle approfondie du jeu de Chomp 4 x n, tabulant plus de 4,3 millions de positions perdantes pour proposer quatre conjectures structurelles concernant les extensions uniques, les rapports asymptotiques, les motifs modulaires de période 112 et la géométrie des cônes linéaires, révélant ainsi une structure déterministe plus riche dans le jeu que ce qui était précédemment soupçonné.

Auteurs originaux : Arnav Garg

Publié 2026-04-30

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Arnav Garg

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un jeu appelé Chomp joué sur une barre de chocolat rectangulaire. La barre est constituée d'une grille de carrés. Deux joueurs se relaient. À votre tour, vous choisissez un carré et le « mangez », ainsi que tout ce qui se trouve au-dessus et à droite de celui-ci. Le hic ? Le carré en haut à gauche est empoisonné. Si vous êtes forcé de manger ce dernier carré, vous perdez.

Les mathématiciens ont déterminé la stratégie gagnante pour des barres de chocolat très petites ou très spécifiques, mais pour une barre large de 4 carrés et longue de n carrés, le motif restait un mystère jusqu'à présent.

Cet article est comme une histoire de détective massive et ultra-rapide où l'auteur a utilisé un ordinateur ultra-rapide pour cartographier chaque « position perdante » (un endroit où le joueur dont c'est le tour perdra si l'adversaire joue parfaitement) pour des barres de chocolat allant jusqu'à 500 carrés de long.

Voici ce que l'auteur a découvert, expliqué simplement :

1. La règle « Un et c'est tout » (Extension unique)

Imaginez la barre de chocolat comme ayant quatre rangées. Les trois rangées du haut ont certaines longueurs (appelons-les A, B et C).

La découverte : L'auteur a trouvé que pour toute combinaison spécifique de longueurs pour les trois rangées du haut, il existe au plus une longueur spécifique pour la quatrième rangée qui crée une « position perdante ».
L'analogie : Imaginez que vous construisez une tour avec trois blocs de tailles spécifiques. Si vous voulez que la tour soit « instable » (une position perdante), il n'y a qu'une taille spécifique pour le quatrième bloc qui la rendra instable. Vous ne pouvez pas simplement choisir n'importe quel quatrième bloc ; les mathématiques imposent une réponse unique et singulière. Cela suggère que le jeu est beaucoup plus prévisible et « déterministe » que quiconque ne le pensait.

2. Le « Nombre d'or » du chocolat (Ratios asymptotiques)

À mesure que la barre de chocolat devient de plus en plus longue (imaginez l'étirer à l'infini), l'auteur a remarqué que les rangées se stabilisent dans une forme spécifique.

La découverte : Les longueurs des rangées cessent de changer au hasard et commencent à suivre un motif fixe. Si la rangée du haut a une longueur de 100, la deuxième rangée aura toujours environ 76 unités de long, la troisième environ 50, et la quatrième environ 22.
L'analogie : C'est comme un arbre qui pousse. Peu importe la hauteur de l'arbre, les branches poussent toujours dans les mêmes proportions relatives. L'auteur a calculé ces « taux de croissance » mais n'a pas encore trouvé de formule mathématique simple (comme une fraction) pour les décrire exactement. Ils sont proches de certains nombres célèbres, mais le secret exact reste caché.

3. Le « Rythme caché » (Période 112)

L'auteur a cherché un motif répétitif dans les données, comme un battement dans une chanson.

La découverte : Les données répètent un motif spécifique tous les 112 pas.
L'analogie : Imaginez une horloge qui ne fait pas tic-tac chaque seconde, mais qui a un rythme complexe qui se réinitialise tous les 112 tic-tac. L'auteur a découvert que ce rythme est probablement un mélange de deux rythmes plus petits : l'un qui se répète tous les 7 pas (hérité de la version du jeu à 3 rangées) et un autre mystérieux qui se répète tous les 8 pas. Le nombre 112 est simplement le « plus petit commun multiple » où ces deux rythmes se synchronisent parfaitement.

4. La forme « Entonnoir » (Géométrie du cône linéaire)

Si vous tracez toutes les « positions perdantes » possibles sur un graphique, elles ne ressemblent pas à un nuage de points aléatoire.

La découverte : Elles forment une forme nette, semblable à un entonnoir (un cône). À mesure que les rangées s'allongent, la « largeur » des positions perdantes valides croît selon une ligne droite et prévisible.
L'analogie : Imaginez verser du sable dans un entonnoir. Le sable ne s'accumule pas au hasard ; il forme un cône lisse et élargi. L'auteur a découvert que les positions perdantes « valides » dans ce jeu s'inscrivent dans une forme similaire, lisse et élargie, avec un tout petit balancement causé par ce rythme de 112 pas mentionné plus tôt.

Pourquoi cela importe-t-il ?

Avant cet article, la version à 4 rangées de Chomp était une boîte noire. Nous savions que le premier joueur gagnait généralement, mais nous ne savions pas pourquoi ni comment les positions perdantes étaient disposées.

L'auteur a trouvé 4,3 millions de positions perdantes spécifiques.
Ils ont prouvé que le jeu est probablement régi par des règles strictes (l'« Extension unique ») plutôt que par le chaos.
Ils ont découvert un rythme caché (112) qui contrôle la structure du jeu.

Ce que l'article NE dit PAS :

Il ne prétend pas que cela aide à résoudre d'autres jeux (comme les Échecs ou le Go).
Il ne prétend pas que cela a des applications médicales ou réelles.
Il ne prouve pas que ces règles sont vraies à 100 % pour des plateaux infinis ; il prouve seulement qu'elles sont vraies pour la plage de 500 pas qu'ils ont testée. L'auteur les appelle des « conjectures » (de fortes hypothèses basées sur des preuves) plutôt que des lois prouvées.

En bref, l'auteur a pris un jeu désordonné et complexe, a lancé une simulation informatique massive, et a découvert que sous le chaos, il existe une structure très ordonnée, rythmée et prévisible attendant d'être pleinement comprise.

1. Énoncé du problème

Le papier étudie le jeu combinatoire Chomp joué sur une grille rectangulaire de taille $4 \times n$ .

Règles du jeu : Les joueurs retirent tour à tour un carré ainsi que tous les carrés situés au-dessus et à droite de celui-ci. Le carré en haut à gauche $(1,1)$ est « empoisonné » ; le joueur contraint de le prendre perd.
Objectif : Identifier les positions P (positions gagnantes pour le joueur précédent, ou positions perdantes pour le joueur dont c'est le tour).
Contexte : Alors que les cas $1 \times n$ et $2 \times n$ sont entièrement résolus, et que le cas $3 \times n$ dispose de solutions algorithmiques partielles, le cas $4 \times n$ manquait d'une analyse computationnelle systématique. Le papier vise à combler cette lacune en tabulant les positions P et en identifiant des motifs structurels sous-jacents.

2. Méthodologie

L'auteur a développé un solveur rétrograde optimisé en C++ pour calculer les positions P pour des largeurs de plateau allant jusqu'à $n = 500$ .

Représentation de l'état :
- Les positions sont représentées par des tuples non décroissants $(a, b, c, d)$ où $a \ge b \ge c \ge d \ge 0$ , désignant le nombre de carrés dans chaque rangée.
- Emballage de bits : Chaque tuple est encodé dans un seul entier uint64 utilisant quatre champs de 16 bits pour minimiser l'utilisation de la mémoire et maximiser la vitesse de hachage.
Conception de l'algorithme :
- Stockage épars : Seules les positions P sont stockées dans un ensemble haché. Le solveur court-circuite les positions N (gagnantes pour le joueur actuel) dès qu'un mouvement vers une position P connue est trouvé.
- Évaluation ascendante : Les états sont traités par ordre croissant du nombre total de cellules, garantissant que tous les successeurs sont résolus avant l'évaluation d'un état.
Performance :
- Calcul de 4 316 097 positions P pour $n \le 500$ .
- Temps d'exécution : environ 70 minutes sur un processeur Apple M4.
- Utilisation de la mémoire : pic à 45 Mo.
Vérification :
- Validation par rapport à la formule connue pour $2 \times n$ (où $c=d=0$ implique $b=a-1$ ).
- Vérification croisée avec un solveur Python indépendant pour le sous-cas $3 \times n$ ( $d=0$ ) jusqu'à $n=50$ .
- Correction d'un bug initial d'alignement de colonnes dans la sortie des données.

3. Contributions et résultats clés

L'analyse de l'ensemble de données calculé a conduit à quatre conjectures structurelles principales :

A. Conjecture 1 : Propriété d'extension unique

Énoncé : Pour tout triplet valide de longueurs de rangées $(a, b, c)$ , il existe au plus un entier $d$ tel que $(a, b, c, d)$ soit une position P.
Implication : L'application de projection $\pi: (a, b, c, d) \to (a, b, c)$ est injective sur l'ensemble des positions P.
Signification : Cela suggère que le jeu $4 \times n$ est un « relèvement déterministe » du jeu $3 \times n$ . Bien que chaque $(a, b, c)$ ne s'étende pas vers une position P (seulement environ 20 % le font), si une extension existe, la longueur de la quatrième rangée $d$ est unique et forcée. Cela contraste avec le cas $3 \times n$ , où aucune telle application injective simple n'avait été précédemment établie.

B. Conjecture 2 : Rapports asymptotiques

Énoncé : À mesure que la largeur du plateau $a \to \infty$ $a \to \infty$ , les rapports des longueurs de rangées dans les positions P convergent vers des constantes fixes :
- $b/a \to L_1 \approx 0,762$
- $c/a \to L_2 \approx 0,499$
- $d/a \to L_3 \approx 0,224$
Méthodologie : Estimation via médianes fenêtrées, fenêtres glissantes et ajustement de courbes de loi de puissance.
Observation : Aucune identité algébrique exacte n'a été trouvée pour ces constantes. Cependant, $L_3 \approx 0,224$ est remarquablement proche de $\cos(3\pi/7) \approx 0,2225$ , suggérant une relation algébrique potentielle cachée.

C. Conjecture 3 : Structure modulaire de période 112

Énoncé : L'ensemble des triplets $(a, b, c)$ qui s'étendent vers des positions P présente une structure modulaire avec une période fondamentale de 112.
Preuves :
- L'analyse d'autocorrélation de la séquence des valeurs de $d$ montre un pic net au décalage 112.
- Un classificateur logistique utilisant uniquement $c$ et $(a-b) \pmod{112}$ prédit l'extensibilité avec une précision de 79 %.
- Les tests du khi-deux confirment que le module 112 fournit la séparation statistique la plus forte ( $\chi^2 = 12 433$ ) par rapport aux autres modules.
Interprétation : $112 = \text{ppcm}(7, 8) \times 2$ . Le facteur 7 provient probablement de la périodicité du sous-jeu $3 \times n$ , tandis que le facteur 8 reste inexpliqué (écartant les artefacts d'emballage de bits).

D. Conjecture 4 : Géométrie de cône linéaire

Énoncé : L'ensemble des triplets s'étendant $(a, b, c)$ forme un cône linéaire dans $\mathbb{R}^3$ .
Géométrie : Pour une $c$ fixe, la plage valide de $(a, b)$ forme une bande contiguë. La largeur de cette bande croît linéairement avec $c$ :
$\text{largeur}(c) \approx \frac{11}{8} \cdot c + f(c \pmod{112})$
où $f$ est une fonction périodique bornée. La pente $11/8 = 1,375$ a été déduite de mesures basées sur des tranches.

4. Importance et perspectives futures

Insight structurel : Les résultats suggèrent que Chomp $4 \times n$ possède une structure plus riche et plus déterministe que soupçonné précédemment, potentiellement plus simple que le cas $3 \times n$ en raison de la propriété d'« Extension unique ».
Généralisation : L'auteur émet l'hypothèse que la propriété d'extension unique peut se généraliser à Chomp $k \times n$ pour tout $k$ , impliquant que tous les jeux de Chomp sont déterminés récursivement par le cas résolu $2 \times n$ .
Questions ouvertes :
1. Preuve : La propriété d'extension unique peut-elle être prouvée de manière combinatoire ?
2. Limites algébriques : Les rapports asymptotiques sont-ils les racines d'un polynôme commun ?
3. Dimensions supérieures : Cela vaut-il pour $5 \times n$ ? (Nécessite un espace d'état en $O(n^5)$ ).
4. Origine de la période : Quelle est la source de la composante de période 8 dans le cycle 112 ?
5. Forme close : Les ~20 % de triplets extensibles peuvent-ils être décrits par un masque sous forme close ?

Le papier note également la soumission de la séquence des valeurs de $d$ à l'Encyclopédie en ligne des suites d'entiers sous le numéro A395126. Le code et les données sont disponibles publiquement via le dépôt GitHub de l'auteur.