The Nim-Sum of a Random Integer Partition

Immaginate un gioco giocato con pile di pietre, dove due giocatori si alternano nel rimuovere un numero qualsiasi di pietre da una singola pila. L'obiettivo è essere l'ultimo a compiere una mossa, o viceversa, costringere l'avversario in una posizione in cui non ha una mossa vincente. Questo è il gioco del Nim, un classico enigma di strategia che è stato studiato per oltre un secolo. Il segreto per vincere non risiede nel contare il numero totale di pietre, ma in un modo specifico di combinare le dimensioni delle pile utilizzando una regola che mescola addizione e sottrazione in modo binario. Se questa combinazione risulta in zero, il giocatore il cui turno è quello di muovere è destinato a perdere, assumendo che il suo avversario giochi perfettamente. Per decenni, i matematici hanno saputo come identificare queste posizioni perdenti per ogni specifica disposizione di pile. Ma una domanda più profonda ed elusiva rimaneva: se si raccoglie un numero fisso di pietre e si dividono in pile in modo casuale, quanto spesso una tale disposizione casuale risulterà essere una posizione perdente?

Questa domanda si colloca all'intersezione tra la teoria dei giochi e lo studio delle partizioni intere, che è il campo matematico concernente il modo in cui un numero può essere scomposto in numeri interi più piccoli. Mentre le regole per vincere un singolo gioco sono precise e deterministiche, il comportamento di questi giochi quando la posizione iniziale è scelta casualmente è sorprendentemente complesso. Una domanda naturale è se la frequenza di queste posizioni perdenti si stabilizzi in un semplice modello asintotico all'aumentare del numero totale di pietre. Tuttavia, il nuovo lavoro di Daewon Kim, dell'Università di Hawai'i a Mānoa, rivela che la risposta è molto più intricata di un semplice assestamento. Sebbene la probabilità assoluta di trovare una posizione perdente diminuisca progressivamente verso lo zero all'aumentare delle pietre, la sua densità normalizzata, ovvero il valore della probabilità riscalato rispetto al suo andamento naturale, non si stabilizza mai. Invece, oscilla in un modello dentato e ripetitivo che non converge mai, indipendentemente da quanto diventi grande il numero di pietre.

La ricerca di Kim si concentra sul caso specifico in cui il numero totale di pietre è pari, poiché le regole del gioco rendono impossibile che un totale dispari formi mai una posizione perdente. Attraverso un metodo di conteggio esatto, lo studio determina come si comporta la probabilità di una posizione perdente all'aumentare del numero totale di pietre. Le scoperte mostrano che la densità normalizzata di questa probabilità non si avvicina a un singolo valore costante. Invece, fluttua in un modello a dente di sega che si ripete ogni volta che la scala naturale associata alla dimensione del problema attraversa una potenza di due. Se si dovesse graficare la densità normalizzata rispetto alla dimensione della pila, si vedrebbe una linea che sale costantemente da un punto basso a un punto alto, per poi scendere bruscamente e ricominciare a salire. Questo ciclo si ripete all'infinito, il che significa che la densità normalizzata può variare tra uno e due volte un valore di base specifico, a seconda di in quale fase di questo ciclo ci si trovi.

Il meccanismo che guida questo comportamento è radicato nella natura binaria della regola vincente del gioco. Quando un numero grande viene scomposto in parti più piccole, le parti più piccole agiscono come una fonte di casualità che rimescola i bit inferiori dei numeri binari, facendoli apparire uniformi e imprevedibili. Le parti più grandi sono così rare che raramente influenzano l'esito. Tuttavia, esiste un intervallo specifico di dimensioni delle parti che agisce come un collo di bottiglia critico. In questo intervallo, le parti sono abbastanza grandi da essere significative, ma non così grandi da scomparire. Il numero di parti che cadono in questo intervallo specifico determina l'esito. Poiché questo intervallo si sposta man mano che il numero totale di pietre cresce, l'equilibrio del gioco oscilla. Quando la scala naturale è appena sotto una potenza di due, l'equilibrio pende da un lato; quando attraversa quella soglia, l'equilibrio si ribalta, causando un salto nella densità.

Per capire questo, si potrebbe paragonare il processo a un orologio che si resetta ogni volta che raggiunge una certa ora, ma le cui lancette si muovono a una velocità che cambia con la dimensione dell'orologio stesso. Man mano che il numero totale di pietre aumenta, l'intervallo critico delle dimensioni delle parti si sposta verso l'alto. La probabilità di una posizione perdente dipende da questo spostamento, e la parità del numero di parti in questo intervallo critico agisce come il principale motore dell'oscillazione. Poiché la distribuzione delle parti è governata da una legge che assomiglia a una distribuzione di Poisson, la probabilità di avere un numero pari di parti in questo intervallo critico oscilla. Questa oscillazione crea il modello a dente di sega. La ricerca conferma che l'insieme di tutti i valori possibili a cui la densità normalizzata si avvicina riempie l'intero intervallo tra uno e due volte un fattore di scala specifico.

Lo studio si estende anche oltre le sole posizioni perdenti. Mostra che questo stesso comportamento oscillante si applica a qualsiasi esito specifico, purché l'obiettivo sia un valore fisso e non cresca con il numero di pietre. Per ogni target nim-sum fisso, la densità ha lo stesso decadimento di primo ordine e, dopo la stessa normalizzazione, segue lo stesso profilo a dente di sega diacritico. Ciò suggerisce che la struttura binaria del gioco lascia una firma permanente sulla distribuzione casuale delle pile, una firma che rifiuta di essere smussata dalla sola grandezza dei numeri coinvolti.

Per verificare queste previsioni teoriche, l'autore ha eseguito calcoli esatti per ogni possibile disposizione di pietre fino a un totale di ventimila. Questo ha richiesto un approccio computazionale sofisticato che ha trattato il problema come un enorme esercizio di conteggio, utilizzando algoritmi specializzati per gestire le combinazioni possibili senza dover enumerare ogni singola partizione. I risultati di questi calcoli hanno corrisposto alle previsioni teoriche con una precisione sorprendente, confermando che il modello a dente di sega è reale e non un artefatto del modello matematico. I dati hanno mostrato che la densità normalizzata sale e scende esattamente come previsto dalla teoria, con le transizioni nette che avvengono nei momenti precisi in cui la scala naturale attraversa una potenza di due.

La ricerca approfondisce anche la natura della transizione tra questi picchi e valli. Sebbene il grafico appaia avere salti netti e discontinui, l'analisi delle dimensioni finite indica che il salto apparente non è un cambiamento istantaneo, ma viene smussato in una finestra sempre più stretta in un passaggio graduale, governato dalla parità del numero di parti nell'intervallo critico. Man mano che il numero totale di pietre aumenta, la finestra in cui avviene questo smorzamento diventa più stretta, facendo apparire i salti sempre più netti all'occhio nudo, anche se rimangono matematicamente continui. Questo fenomeno spiega perché il modello appare così irregolare nei dati, nonostante la matematica sottostante sia fluida.

In definitiva, questo lavoro fornisce una descrizione completa di come siano distribuite le posizioni perdenti nel gioco del Nim quando la configurazione iniziale è scelta casualmente. Risolve una questione di lunga data sulla frequenza di queste posizioni, mostrando che la loro densità non segue un andamento semplice e costante. Al contrario, è governata da un complesso intreccio tra la dimensione delle pile e la struttura binaria del gioco. Le scoperte evidenziano un principio più ampio in matematica: anche in sistemi che appaiono casuali e fluidi, profonde strutture aritmetiche possono creare modelli persistenti e netti che resistono alla mediazione. La natura binaria del gioco assicura che un blocco specifico di informazioni rimanga visibile e influente, indipendentemente da quanto il sistema cresca, creando un ritmo che si ripete per sempre man mano che i numeri aumentano.