Che cos'è Nim di Fibonacci?
Il Nim di Fibonacci si gioca con un solo mucchio. Il primo giocatore può prendere qualsiasi numero di oggetti tranne l'intero mucchio. Da lì in poi ogni mossa prende almeno un oggetto e al massimo il doppio di quelli appena presi dall'avversario. Vince chi prende l'ultimo oggetto: il gioco si gioca sempre in modo normale, quindi l'opzione misère e quella dei mucchi iniziali del gioco standard non si applicano.
Il mucchio contiene 10 (piccola), 15 (media, il default) o 20 (grande) oggetti, scelti come dimensione nelle impostazioni del tavolo. Il limite cresce e cala con il gioco: una presa grande permette all'avversario di prendere ancora di più, mentre una piccola lo tiene a guinzaglio corto, quindi la partita è una lotta sulla dimensione del limite successivo quanto sul mucchio.
Regole che cambiano
| Regola | Nim standard | Nim di Fibonacci |
|---|---|---|
| Mucchi | Nim standardDiversi mucchi: 1, 3, 5 e 7 oggetti di default, o un altro insieme scelto nelle impostazioni del tavolo. | Nim di FibonacciUn mucchio di 10, 15 (default) o 20 oggetti, scelto come dimensione nelle impostazioni del tavolo. |
| Prima mossa | Nim standardPrendi un numero qualsiasi di oggetti da un mucchio, compreso l'intero mucchio. | Nim di FibonacciPrendi un numero qualsiasi di oggetti tranne l'intero mucchio. |
| Mosse successive | Nim standardPrendi un numero qualsiasi di oggetti da un mucchio, a ogni turno. | Nim di FibonacciPrendi almeno 1 e al massimo il doppio di quanti ne ha presi l'avversario nella mossa prima, e non più di quanti ne restano. |
| Obiettivo | Nim standardDi default si gioca misère: chi prende l'ultimo oggetto perde. Le impostazioni possono passare al gioco normale, in cui prendere l'ultimo oggetto fa vincere. | Nim di FibonacciSempre gioco normale: chi prende l'ultimo oggetto vince. |
| Strategia vincente | Nim standardLascia i mucchi con somma nim (lo XOR bit a bit delle loro dimensioni) pari a zero, con una variante nel finale misère. | Nim di FibonacciScrivi il mucchio come somma di numeri di Fibonacci, mai due consecutivi nella successione, e prendi il più piccolo quando il limite lo permette. Il primo giocatore perde con il gioco migliore esattamente quando il mucchio iniziale è un numero di Fibonacci; 10, 15 e 20 non lo sono, quindi il primo giocatore può vincere. |
Storia
Michael J. Whinihan descrisse il Nim di Fibonacci nel 1963 su The Fibonacci Quarterly e attribuì il gioco a Robert E. Gaskell, matematico della Oregon State University. Il nome viene dal ruolo che i numeri di Fibonacci 1, 2, 3, 5, 8, 13, 21 e così via hanno nella soluzione.
Il metodo vincente si basa su quello che oggi si chiama teorema di Zeckendorf: ogni numero intero positivo è in un solo modo una somma di numeri di Fibonacci, mai due consecutivi. Il teorema prende il nome da Édouard Zeckendorf, anche se Gerrit Lekkerkerker lo aveva già pubblicato nel 1952.