The Ordered Zeckendorf Game

Titolo: Il Gioco Ordinato di Zeckendorf

Autori: Ivan Bortnovskyi, Michael Lucas, Steven J. Miller, Iana Vranesko, Ren Watson, e Cameron White.

---

1. Il Problema e la Motivazione

Il lavoro si concentra sull'introduzione e l'analisi di una nuova variante combinatoria a due giocatori ispirata al Teorema di Zeckendorf.

• Contesto: Il Teorema di Zeckendorf afferma che ogni intero positivo può essere rappresentato in modo unico come somma di numeri di Fibonacci non consecutivi ($F_1=1, F_2=2, F_{i+1}=F_i+F_{i-1}$).
• Gioco Classico: Nella versione precedente (non ordinata), i giocatori operano su un multiset non ordinato di numeri di Fibonacci. È stato dimostrato che in questo scenario, per ogni $n > 2$, il Giocatore 2 possiede una strategia vincente dominante, limitando la complessità strategica.
• Nuova Sfida: Gli autori introducono il Gioco Ordinato di Zeckendorf, dove l'ordine degli addendi è vincolante. Le mosse sono limitate agli elementi adiacenti e viene introdotta una nuova mossa di "scambio" (switch). L'obiettivo è analizzare come queste restrizioni e nuove regole alterino la dinamica del gioco, rendendolo più bilanciato e strategicamente profondo.

2. Metodologia

L'approccio combina dimostrazioni teoriche rigorose con simulazioni computazionali estese.

• Definizione del Gioco:

  • Stato Iniziale: Una lista ordinata di $n$ copie di $F_1$ (tutti 1).
  • Mosse Permesse:
    1. Fusione (Merge): Sostituire $(F_i, F_{i+1})$ con $F_{i+2}$.
    2. Fusione di Uno: Sostituire $(F_1, F_1)$ con $F_2$.
    3. Divisione (Split): Sostituire $(F_i, F_i)$ con $(F_{i-2}, F_{i+1})$ per $i > 2$.
    4. Divisione di Due: Sostituire $(F_2, F_2)$ con $(F_1, F_3)$.
    5. Scambio (Switch): Scambiare elementi adiacenti $(F_i, F_j)$ in $(F_j, F_i)$ se $i > j$ (per ripristinare l'ordine crescente).
  • Condizione di Terminazione: Il gioco termina quando la lista è strettamente crescente e non sono possibili né fusioni né divisioni (ovvero, si raggiunge la decomposizione di Zeckendorf ordinata).

• Strumenti Teorici:

  • Monovariante: Costruzione di una funzione che diminuisce strettamente ad ogni mossa per dimostrare la terminazione e l'assenza di cicli.
  • Analisi Asintotica: Stima dei limiti superiori e inferiori per la lunghezza massima del gioco ($M(n)$).
  • Simulazioni: Esecuzione di migliaia di partite casuali e analisi delle distribuzioni statistiche (convergenza log-normale) e delle strategie vincenti per $n \le 25$.

3. Risultati Chiave e Contributi

A. Terminazione e Stato Finale

• Teorema 1.3: Il gioco termina sempre in un numero finito di mosse. Lo stato finale è univoco e corrisponde alla decomposizione di Zeckendorf di $n$ espressa come sequenza strettamente crescente di numeri di Fibonacci.
• Dimostrazione: Si utilizza un monovariante $f(S) = \sum (k+1-j)F_{i_j}$ che diminuisce ad ogni mossa legale (fusione, divisione o scambio), garantendo che il gioco non possa ciclare e debba convergere all'unica configurazione stabile.

B. Lunghezza del Gioco (Bounds)

Gli autori analizzano la lunghezza minima e massima del gioco:

• Lunghezza Minima (Proposizione 1.4): La lunghezza minima è esattamente $n - Z(n)$, dove $Z(n)$ è il numero di termini nella decomposizione di Zeckendorf di $n$. Questo si ottiene con una strategia "greedy" che massimizza le fusioni senza mosse di scambio.
• Lunghezza Massima (Teorema 1.5 e 1.11):
  • Viene stabilito un limite superiore: $M(n) \le \frac{n(n-1)}{2}$.
  • Viene introdotto un limite inferiore basato sulla "Strategia di Gioco Lungo" (LGS), che priorizza scambi, fusioni di 1, divisioni e fusioni in un ordine specifico.
  • Comportamento Asintotico (Corollario 1.12): La lunghezza massima cresce quadraticamente:
    $$M(n) = \frac{n^2}{2} - \Theta(n \log_\phi n)$$
    dove $\phi$ è il numero aureo. Questo risultato è ottenuto combinando limiti superiori e inferiori raffinati che tengono conto del numero di manipolazioni necessarie per gli indici più alti.

C. Strategie Vincenti e Dinamiche

• Cambiamento di Paradigma: A differenza del gioco classico (dove il Giocatore 2 vince sempre per $n>2$), nella versione ordinata il Giocatore 1 ha un vantaggio significativo.
• Risultati Computazionali: Per $n \le 25$, il Giocatore 1 vince in tutti i casi tranne che per $n=18$ (dove il Giocatore 2 può forzare la vittoria). Questo suggerisce che l'introduzione dell'ordine e della mossa di scambio bilancia il gioco a favore del primo giocatore per la maggior parte dei valori.
• Comportamento Probabilistico: Le simulazioni su partite giocate casualmente suggeriscono che la distribuzione del numero di mosse converge a una distribuzione log-normale (Congettura 3.2). Inoltre, sotto gioco casuale, la probabilità di vittoria sembra essere equamente distribuita tra i due giocatori.

4. Significato e Implicazioni

Questo lavoro arricchisce il panorama dei giochi combinatori basati sulla teoria dei numeri:

1. Complessità Strategica: Dimostra che vincoli di ordine e nuove mosse (switch) possono trasformare un gioco con strategia dominante banale in uno con un albero di gioco complesso e risultati imprevedibili.
2. Nuove Sfide Algoritmiche: Pone problemi aperti sulla caratterizzazione esatta delle strategie ottimali per $n > 25$ e sulla prova formale della strategia "Long Game" (LGS) come massimizzante assoluta.
3. Generalizzazioni: Apre la strada a studi su sequenze di ricorrenza generalizzate (es. k-bonacci) e varianti con più giocatori o alleanze.
4. Connessioni Matematiche: Collega la teoria dei giochi, la teoria dei numeri (decomposizioni di Zeckendorf) e l'analisi probabilistica (distribuzioni log-normali).

5. Conclusioni e Lavori Futuri

Gli autori identificano diverse direzioni per ricerche future:

• Dimostrare rigorosamente l'esistenza di una strategia vincente generale per $n$ grandi.
• Sviluppare euristiche di ricerca (es. Minimax con potatura alpha-beta) per esplorare alberi di gioco più profondi.
• Analizzare le proprietà ergodiche e probabilistiche delle dinamiche casuali.
• Esplorare generalizzazioni a ricorrenze non costanti e giochi multiplayer.

Il codice sorgente per le simulazioni e le visualizzazioni è reso pubblico, facilitando ulteriori indagini nella comunità scientifica.