Additive Subtraction Games

Questo articolo determina la struttura completa dei valori nim per i giochi di sottrazione additiva nel regime quadratico primitivo, fornendo una dimostrazione completa della formula chiusa basata su espressioni di tipo Beatty per le posizioni P, che era stata precedentemente enunciata senza prova nella letteratura.

L'essenziale

Immagina di essere in una sala giochi con due amici. Avanti a voi c'è una pila di gettoni (o fiammiferi, o caramelle). Il gioco è semplice: a turno, ognuno deve togliere un certo numero di gettoni dalla pila. Ma c'è una regola d'oro: puoi togliere solo un numero specifico di gettoni, scelto da una lista fissa. Se non riesci a toglierne nessuno perché la pila è troppo piccola o vuota, hai perso.

Questo è il gioco di base, chiamato "Gioco di Sottrazione". Ma gli autori di questo articolo, Urban Larsson e Hikaru Manabe, non si sono fermati alle regole semplici. Hanno guardato un caso particolare, un po' più complicato, che assomiglia a un labirinto matematico.

Ecco la spiegazione di cosa hanno scoperto, raccontata come una storia.

1. Il Labirinto dei Gettoni

Immagina che la lista dei numeri che puoi togliere sia composta da tre numeri speciali: $a$, $b$ e $a+b$.
Per esempio, se $a=3$ e $b=5$, puoi togliere 3, 5 o 8 gettoni.

Il problema è: come fai a sapere se sei in una posizione vincente o perdente?

• Se sei in una posizione perdente (P), non importa cosa fai, il tuo avversario può sempre rispondere in modo da portarti alla vittoria.
• Se sei in una posizione vincente, c'è almeno una mossa che ti porta a una posizione perdente per l'avversario.

In matematica, questi numeri vincenti e perdenti hanno dei "nomi segreti" chiamati nim-value (valori di nim). Possono essere 0 (perdita certa), 1, 2 o 3. Il gioco è così strutturato che non ci sono mai valori più alti di 3.

2. La Formula Magica (La "Ricetta" per la Perdita)

Per decenni, i matematici sapevano che c'era una formula strana per trovare le posizioni perdenti (quelle con valore 0), ma nessuno era riuscito a dimostrarla con certezza. Era come avere la ricetta di un dolce famoso scritta su un foglietto stropicciato, ma senza le istruzioni passo-passo.

La formula diceva: "Prendi un numero $n$, fai un po' di calcoli con delle parti intere (come arrotondare per difetto) e ottieni un numero speciale $w_n$".
Se il numero di gettoni nella pila è uno di questi $w_n$, sei in pericolo (posizione perdente).

Gli autori di questo articolo hanno finalmente scritto il manuale di istruzioni. Hanno dimostrato che la formula funziona davvero. Ma non si sono fermati lì. Hanno scoperto che la mappa del gioco è divisa in quattro zone distinte, come se il pavimento fosse piastrellato con quattro colori diversi:

1. Zona Rossa (Valore 0): Le posizioni perdenti. La formula magica ti dice esattamente dove sono.
2. Zona Blu (Valore 1): Sono posizioni vincenti. Basta spostarsi di un certo passo dalla Zona Rossa per arrivarci.
3. Zona Verde (Valore 2): Un'altra zona vincente, ma con regole diverse.
4. Zona Gialla (Valore 3): La zona più strana. È come un "vuoto" che rimane quando si spostano le altre zone.

3. L'Analogia del Trenino e dei Salti

Per capire come funziona, immagina un trenino che viaggia su un binario infinito.

• I gettoni sono le stazioni.
• Le mosse sono i salti che il trenino può fare (3, 5 o 8 stazioni).

La formula magica disegna delle "isole" speciali (la Zona Rossa) sul binario. La cosa incredibile è che queste isole non sono messe a caso. Hanno un ritmo preciso, come un battito cardiaco che accelera e rallenta seguendo un pattern matematico.

Gli autori hanno scoperto che:

• Se sei su un'isola Rossa, qualsiasi salto fai, atterrerai in una zona "sicura" per il tuo avversario.
• Se sei vicino a un'isola Rossa (ma non sopra), puoi saltare su di essa per vincere.
• Le zone Verdi e Gialle sono come "spazi residui": sono i posti che rimangono quando hai coperto tutto il binario con le zone Rosse, Blu e Verdi.

4. Il Mistero delle "Collisioni"

La parte più difficile della ricerca era capire quanto spazio occupava la Zona Gialla (Valore 3).
Immagina di prendere la mappa della Zona Rossa e di spostarla leggermente (di un passo chiamato $\delta$).

• Dove la mappa originale e quella spostata si sovrappongono, non succede nulla di speciale.
• Ma dove la mappa spostata "sbatte" contro la mappa originale (una collisione), si crea un buco.

Gli autori hanno usato la matematica dei numeri (teoria dei numeri) per contare esattamente quante volte questi "buchi" si formano. Hanno scoperto che il numero di collisioni dipende da quanto sono vicini i due numeri $a$ e $\delta$. È come se avessero calcolato quante volte due treni che viaggiano su binari paralleli si incrociano in un viaggio infinito.

Hanno dimostrato che, in un ciclo completo, il numero di queste collisioni è esattamente uguale a $a \times (\delta - a)$. Questo numero è la chiave per chiudere il cerchio e dimostrare che le quattro zone coprono tutti i numeri possibili, senza buchi e senza sovrapposizioni.

5. Perché è Importante?

Prima di questo lavoro, sapevamo che il gioco aveva un ritmo (era periodico), ma non sapevamo esattamente come era fatto il ritmo. Era come sapere che la musica ha un ritmo, ma non poter leggere lo spartito.

Ora abbiamo lo spartito completo.

• Abbiamo la formula esatta per le posizioni perdenti.
• Sappiamo dove sono le posizioni vincenti di valore 1, 2 e 3.
• Abbiamo dimostrato che queste regole funzionano per una classe di giochi che è considerata la più complessa ("regime quadratico primitivo").

In Sintesi

Gli autori hanno preso un gioco da tavolo matematico che sembrava un labirinto senza uscita, trovato la mappa esatta delle quattro zone in cui si può stare, e dimostrato che la mappa è perfetta e completa. Hanno trasformato una formula misteriosa in una verità matematica solida, usando un mix di logica, calcoli precisi e un'analisi creativa di come i numeri "collidono" tra loro.

È come se avessero scoperto che, in un gioco apparentemente caotico, c'è un ordine geometrico perfetto nascosto sotto la superficie, e ora possiamo vederlo chiaramente.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del documento "Additive Subtraction Games" di Urban Larsson e Hikaru Manabe, redatta in italiano.

Sintesi Tecnica: Giochi di Sottrazione Additivi nel Regime Quadratico Primitivo

1. Il Problema e il Contesto

Il lavoro si concentra sui giochi di sottrazione additivi, una classe di giochi combinatori a due giocatori giocati su mucchi di gettoni. In un gioco di sottrazione standard, i giocatori rimuovono alternativamente un numero $s$ di gettoni, dove $s$ appartiene a un insieme fisso $S$ di interi positivi. Il giocatore che non può muovere (perché ogni sottrazione porterebbe a un numero negativo) perde.

L'obiettivo è determinare la struttura completa dei valori di Nim (o nimber) per l'insieme di mosse $S = \{a, b, a+b\}$, dove $b = a + \delta$.
Il paper si focalizza specificamente sul regime quadratico primitivo, definito dalle condizioni:

• $a < \delta < 2a$
• $\gcd(a, \delta) = 1$

Questo regime è considerato il caso fondamentale che cattura la complessità quadratica del problema, in cui le due scale $a$ e $\delta$ interagiscono in modo non banale. Il problema era stato menzionato nel testo classico Winning Ways (Berlekamp et al., 1982) con una formula chiusa proposta per le posizioni $P$ (posizioni perdenti, valore di Nim 0), ma una dimostrazione completa di tale affermazione non era mai apparsa in letteratura fino a questo lavoro.

2. Metodologia

Gli autori adottano un approccio che combina teoria dei giochi combinatori e teoria dei numeri elementare.

• Definizione delle Posizioni Candidato: Si definisce una sequenza di posizioni candidate per le posizioni $P$ (valore 0) tramite una formula chiusa di tipo "espressione a parentesi" (bracket expression):
  $$w_n = n + a \left\lfloor \frac{n}{a} \right\rfloor + b \left\lfloor \frac{n}{\delta} \right\rfloor$$
  L'insieme delle posizioni $P$ è $W_0 = \{w_n : n \ge 0\}$.

• Verifica della Regola del Mex: Per confermare che $W_0$ sono effettivamente le posizioni con valore 0, e per classificare i valori 1, 2 e 3, gli autori utilizzano un'induzione forte sulla dimensione della posizione. Devono verificare due condizioni per ogni insieme di valori $W_i$:

  1. Anti-collisione (Anti-collision): Non esiste alcuna mossa legale tra due posizioni dello stesso insieme $W_i$.
  2. Raggiungibilità (Reachability): Da ogni posizione in $W_i$, è possibile raggiungere posizioni con tutti i valori minori (da 0 a $i-1$).

• Analisi Strutturale:

  • Per i valori 1, si utilizza il principio di accoppiamento di Ferguson.
  • Per i valori 2 e 3, si analizzano le traslazioni affini di $W_0$.
  • Il cuore della dimostrazione risiede nello studio delle collisioni tra l'insieme $W_0$ e la sua traslazione $W_0 - \delta$. Questo richiede un'analisi dettagliata della struttura delle "lacune" (gap) nella sequenza $w_n$.

3. Risultati Chiave e Contributi

A. Dimostrazione della Formula Chiusa per le Posizioni $P$
Gli autori dimostrano che, nel regime quadratico primitivo, l'insieme $W_0$ definito dalla formula sopra è esattamente l'insieme delle posizioni perdenti (valore di Nim 0). Questo risolve una congettura aperta presente in Winning Ways.

B. Classificazione Completa dei Valori di Nim
Il teorema principale (Teorema 1) stabilisce che l'insieme dei numeri naturali $\mathbb{N}_0$ è partizionato in quattro insiemi disgiunti, ciascuno corrispondente a un valore di Nim specifico:

• Valore 0: $W_0 = \{w_n\}$
• Valore 1: $W_1 = W_0 + a$
• Valore 2: $W_2 = W_0 - b$
• Valore 3: $W_3 = (W_0 - \delta) \setminus W_0$

C. Struttura delle Lacune e Conteggio delle Collisioni
Un contributo metodologico significativo è l'analisi della sequenza delle lacune $g_n = w_{n+1} - w_n$.

• La sequenza delle lacune assume solo quattro valori possibili: $\{1, a+1, b+1, b+a+1\}$.
• Gli autori introducono il concetto di "finestra di collisione" (collision window): una sequenza di lacune consecutive la cui somma è esattamente $\delta$.
• Viene dimostrato un teorema di conteggio (Teorema 7) che stabilisce il numero di collisioni $|C|_p$ in un periodo dell'heap (heap-period). Il risultato è:
  $$|C|_p = a \cdot d$$
  dove $d = \delta - a$.
• Questa analisi permette di calcolare la densità esatta delle posizioni con valore 3, confermando che la partizione è completa.

D. Periodicità
Il lavoro chiarisce la distinzione tra periodo dell'indice e periodo dell'heap:

• Periodo dell'indice: $a\delta$
• Periodo dell'heap (lunghezza del ciclo delle posizioni): $(3\delta + a)a$

4. Significato e Implicazioni

• Risoluzione di un Problema Storico: Il paper fornisce la prima dimostrazione rigorosa della formula chiusa per le posizioni $P$ in questo contesto, un risultato che era stato solo ipotizzato per decenni.
• Complessità Quadratica: Dimostra che il regime $a < \delta < 2a$ è la fonte della complessità quadratica del problema. Al di fuori di questo regime, il problema si riduce a complessità lineare o mantiene la struttura quadratica in modo banale.
• Nuovi Strumenti Analitici: L'introduzione dell'analisi delle "finestre di collisione" e la classificazione delle residue in tre regioni (limitate a sinistra, illimitate, limitate a destra) offre un nuovo strumento per studiare le espressioni a parentesi con moduli razionali.
• Connessione con la Teoria di Beatty: Sebbene la sequenza $w_n$ non sia una sequenza di Beatty classica (che coinvolge moduli irrazionali), il lavoro si collega alla congettura di Fraenkel e ai problemi di partizione dei numeri interi, mostrando come le espressioni a parentesi con moduli razionali possano generare partizioni complesse non omogenee.

In conclusione, Larsson e Manabe non solo risolvono un problema aperto nei giochi combinatori, ma forniscono anche una mappa dettagliata della struttura aritmetica sottostante, dimostrando che i valori di Nim per questo gioco sono distribuiti in modo prevedibile e descrittibile tramite formule chiuse basate su funzioni parte intera.