🔢 mathematics

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

Questo articolo presenta un'estesa analisi computazionale del gioco Chomp 4 x n, tabulando oltre 4,3 milioni di posizioni P per proporre quattro congetture strutturali riguardanti estensioni uniche, rapporti asintotici, pattern modulari di periodo 112 e geometria del cono lineare, che rivelano una struttura deterministica più ricca nel gioco di quanto precedentemente sospettato.

Autori originali: Arnav Garg

Pubblicato 2026-04-30

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Arnav Garg

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina un gioco chiamato Chomp giocato su una tavoletta di cioccolato rettangolare. La tavoletta è composta da una griglia di quadratini. Due giocatori si alternano. Al tuo turno, scegli un quadratino e lo "mangi", insieme a tutto ciò che si trova sopra di esso e alla sua destra. Il punto cruciale? Il quadratino in alto a sinistra è avvelenato. Se sei costretto a mangiare quell'ultimo quadratino, perdi.

I matematici hanno individuato la strategia vincente per tavolette di cioccolato molto piccole o molto specifiche, ma per una tavoletta larga 4 quadratini e lunga n quadratini, il modello rimaneva un mistero fino a ora.

Questo articolo è come una storia investigativa massiccia e ad alta velocità, in cui l'autore ha utilizzato un computer velocissimo per mappare ogni singola "posizione perdente" (una posizione in cui il giocatore di turno perderà se l'avversario gioca perfettamente) per tavolette di cioccolato lunghe fino a 500 quadratini.

Ecco cosa ha scoperto l'autore, spiegato in modo semplice:

1. La Regola "Uno e Finito" (Estensione Unica)

Immagina la tavoletta di cioccolato come avente quattro file. Le prime tre file hanno determinate lunghezze (chiamiamole A, B e C).

La Scoperta: L'autore ha scoperto che per qualsiasi combinazione specifica di lunghezze delle prime tre file, esiste al massimo una specifica lunghezza per la quarta fila che crea una "posizione perdente".
L'Analogia: Immagina di costruire una torre con tre blocchi di dimensioni specifiche. Se vuoi che la torre sia "instabile" (una posizione perdente), esiste una sola dimensione specifica per il quarto blocco che la renderà instabile. Non puoi scegliere un quarto blocco qualsiasi; la matematica impone una singola risposta unica. Questo suggerisce che il gioco è molto più prevedibile e "deterministico" di quanto chiunque pensasse.

2. La "Sezione Aurea" del Cioccolato (Rapporti Asintotici)

Man mano che la tavoletta di cioccolato diventa sempre più lunga (immagina di allungarla all'infinito), l'autore ha notato che le file si stabilizzano in una forma specifica.

La Scoperta: Le lunghezze delle file smettono di cambiare in modo casuale e iniziano a seguire un modello fisso. Se la fila superiore ha lunghezza 100, la seconda fila sarà sempre lunga circa 76 unità, la terza circa 50 e la quarta circa 22.
L'Analogia: È come un albero che cresce. Non importa quanto alto diventi l'albero, i rami crescono sempre nelle stesse proporzioni relative. L'autore ha calcolato questi "tassi di crescita" ma non è ancora riuscito a trovare una semplice formula matematica (come una frazione) per descriverli esattamente. Sono vicini ad alcuni numeri famosi, ma il segreto esatto rimane nascosto.

3. Il "Ritmo Nascosto" (Periodo-112)

L'autore ha cercato un modello ricorrente nei dati, come un battito in una canzone.

La Scoperta: I dati ripetono un modello specifico ogni 112 passi.
L'Analogia: Immagina un orologio che non ticchetta ogni secondo, ma ha un ritmo complesso che si resetta ogni 112 tic. L'autore ha scoperto che questo ritmo è probabilmente una miscela di due ritmi più piccoli: uno che si ripete ogni 7 passi (ereditato dalla versione del gioco a 3 file) e un altro misterioso che si ripete ogni 8 passi. Il numero 112 è semplicemente il "minimo comune multiplo" in cui questi due ritmi si sincronizzano perfettamente.

4. La Forma a "Imbuto" (Geometria del Cono Lineare)

Se si tracciano tutte le possibili "posizioni perdenti" su un grafico, non sembrano una nuvola casuale di punti.

La Scoperta: Formano una forma ordinata, simile a un imbuto (un cono). Man mano che le file diventano più lunghe, la "larghezza" delle posizioni perdenti valide cresce in una linea retta e prevedibile.
L'Analogia: Immagina di versare sabbia in un imbuto. La sabbia non si accumula in modo casuale; forma un cono liscio e allargante. L'autore ha scoperto che le posizioni perdenti "valide" in questo gioco si adattano a una forma simile, liscia e allargante, con un piccolo oscillazione causata dal ritmo di 112 passi menzionato in precedenza.

Perché è Importante?

Prima di questo articolo, la versione a 4 file di Chomp era una scatola nera. Sapevamo che il primo giocatore vinceva di solito, ma non sapevamo perché o come fossero disposte le posizioni perdenti.

L'autore ha trovato 4,3 milioni di posizioni perdenti specifiche.
Ha dimostrato che il gioco è probabilmente governato da regole rigide (l'"Estensione Unica") piuttosto che dal caos.
Ha trovato un ritmo nascosto (112) che controlla la struttura del gioco.

Cosa l'articolo NON afferma:

Non sostiene che questo aiuti a risolvere altri giochi (come Scacchi o Go).
Non sostiene che abbia applicazioni mediche o nel mondo reale.
Non dimostra che queste regole siano vere al 100% per bacheche infinite; dimostra solo che valgono per l'intervallo di 500 passi che hanno testato. L'autore le definisce "congetture" (ipotesi forti basate su prove) piuttosto che leggi dimostrate.

In breve, l'autore ha preso un gioco disordinato e complesso, eseguito una massiccia simulazione al computer e scoperto che sotto il caos c'è una struttura molto ordinata, ritmica e prevedibile in attesa di essere pienamente compresa.

1. Enunciato del Problema

Il paper esamina il gioco combinatorio Chomp giocato su una griglia rettangolare $4 \times n$ .

Regole del Gioco: I giocatori si alternano rimuovendo un quadrato e tutti i quadrati sopra e a destra di esso. Il quadrato in alto a sinistra $(1,1)$ è "avvelenato"; il giocatore costretto a prenderlo perde.
Obiettivo: Identificare le posizioni P (posizioni vincenti per il giocatore precedente, o posizioni perdenti per il giocatore di turno).
Contesto: Mentre i casi $1 \times n$ e $2 \times n$ sono completamente risolti, e il caso $3 \times n$ ha soluzioni algoritmiche parziali, il caso $4 \times n$ mancava di un'analisi computazionale sistematica. Il paper mira a colmare questa lacuna tabulando le posizioni P e identificando modelli strutturali sottostanti.

2. Metodologia

L'autore ha sviluppato un risolutore retrogrado ottimizzato in C++ per calcolare le posizioni P per larghezze di scacchiera fino a $n = 500$ .

Rappresentazione dello Stato:
- Le posizioni sono rappresentate come tuple non decrescenti $(a, b, c, d)$ dove $a \ge b \ge c \ge d \ge 0$ , che denotano il numero di quadrati in ogni riga.
- Bitpacking: Ogni tuple è codificata in un singolo intero uint64 utilizzando quattro campi da 16 bit per minimizzare l'uso di memoria e massimizzare la velocità di hashing.
Progettazione dell'Algoritmo:
- Archiviazione Sparsa: Solo le posizioni P sono memorizzate in un insieme hash. Il risolutore scarta le posizioni N (vincenti per il giocatore corrente) non appena viene trovata una mossa verso una posizione P nota.
- Valutazione dal Basso verso l'Alto: Gli stati sono elaborati in ordine crescente di conteggio totale delle celle, garantendo che tutti i successori siano risolti prima di valutare uno stato.
Prestazioni:
- Calcolate 4.316.097 posizioni P per $n \le 500$ .
- Tempo di esecuzione: ~70 minuti su un processore Apple M4.
- Uso di memoria: Picco di utilizzo di 45 MB.
Verifica:
- Validato contro la formula nota per $2 \times n$ (dove $c=d=0$ implica $b=a-1$ ).
- Incrociato con un risolutore Python indipendente per il sottocaso $3 \times n$ ( $d=0$ ) fino a $n=50$ .
- Corretto un bug iniziale di allineamento delle colonne nell'output dei dati.

3. Contributi Chiave e Risultati

L'analisi del dataset calcolato ha portato a quattro congetture strutturali principali:

A. Congettura 1: Proprietà di Estensione Unica

Enunciato: Per qualsiasi terna valida di lunghezze delle righe $(a, b, c)$ , esiste al più un intero $d$ tale che $(a, b, c, d)$ sia una posizione P.
Implicazione: La mappa di proiezione $\pi: (a, b, c, d) \to (a, b, c)$ è iniettiva sull'insieme delle posizioni P.
Significato: Ciò suggerisce che il gioco $4 \times n$ è un "sollevamento deterministico" del gioco $3 \times n$ . Sebbene non ogni $(a, b, c)$ si estenda a una posizione P (solo circa il 20% lo fa), se un'estensione esiste, la lunghezza della quarta riga $d$ è univocamente forzata. Ciò contrasta con il caso $3 \times n$ , dove non era stata precedentemente stabilita alcuna semplice mappa iniettiva di questo tipo.

B. Congettura 2: Rapporti Asintotici

Enunciato: Man mano che la larghezza della scacchiera $a \to \infty$ $a \to \infty$ , i rapporti delle lunghezze delle righe nelle posizioni P convergono a costanti fisse:
- $b/a \to L_1 \approx 0,762$
- $c/a \to L_2 \approx 0,499$
- $d/a \to L_3 \approx 0,224$
Metodologia: Stimati tramite mediane a finestra, finestre scorrevoli e adattamento di curve a legge di potenza.
Osservazione: Non è stata trovata un'identità algebrica esatta per queste costanti. Tuttavia, $L_3 \approx 0,224$ è notevolmente vicino a $\cos(3\pi/7) \approx 0,2225$ , suggerendo una potenziale relazione algebrica nascosta.

C. Congettura 3: Struttura Modulare Period-112

Enunciato: L'insieme delle terne $(a, b, c)$ che si estendono a posizioni P esibisce una struttura modulare con un periodo fondamentale di 112.
Evidenza:
- L'analisi di autocorrelazione della sequenza dei valori di $d$ mostra un picco netto a ritardo 112.
- Un classificatore logistico che utilizza solo $c$ e $(a-b) \pmod{112}$ prevede l'estendibilità con un'accuratezza del 79%.
- I test chi-quadrato confermano che il modulo 112 fornisce la separazione statistica più forte ( $\chi^2 = 12.433$ ) rispetto ad altri moduli.
Interpretazione: $112 = \text{mcm}(7, 8) \times 2$ . Il fattore 7 deriva probabilmente dalla periodicità del sottogioco $3 \times n$ , mentre il fattore 8 rimane inspiegato (escludendo artefatti del bit-packing).

D. Congettura 4: Geometria del Cono Lineare

Enunciato: L'insieme delle terne estendibili $(a, b, c)$ forma un cono lineare in $\mathbb{R}^3$ .
Geometria: Per un $c$ fisso, l'intervallo valido di $(a, b)$ forma una banda contigua. La larghezza di questa banda cresce linearmente con $c$ :
$\text{larghezza}(c) \approx \frac{11}{8} \cdot c + f(c \pmod{112})$
dove $f$ è una funzione periodica limitata. La pendenza $11/8 = 1,375$ è stata derivata da misurazioni basate su sezioni.

4. Significato e Direzioni Future

Intuito Strutturale: I risultati suggeriscono che Chomp $4 \times n$ possiede una struttura più ricca e deterministica di quanto sospettato in precedenza, potenzialmente più semplice del caso $3 \times n$ a causa della proprietà di "Estensione Unica".
Generalizzazione: L'autore ipotizza che la proprietà di Estensione Unica possa generalizzarsi a Chomp $k \times n$ per ogni $k$ , implicando che tutti i giochi Chomp sono determinati ricorsivamente dal caso risolto $2 \times n$ .
Domande Aperte:
1. Dimostrazione: La proprietà di Estensione Unica può essere dimostrata combinatoriamente?
2. Limiti Algebrici: I rapporti asintotici sono radici di un polinomio comune?
3. Dimensioni Superiori: Vale questo per $5 \times n$ ? (Richiede uno spazio di stati $O(n^5)$ ).
4. Origine del Periodo: Qual è la fonte della componente periodo-8 nel ciclo 112?
5. Forma Chiusa: Le circa il 20% delle terne estendibili possono essere descritte da una maschera in forma chiusa?

Il paper nota inoltre la sottomissione della sequenza dei valori di $d$ all'On-Line Encyclopedia of Integer Sequences come A395126. Il codice e i dati sono pubblicamente disponibili tramite il repository GitHub dell'autore.