Techetechetè -- Il NIM e il teorema di Sprague-Grundy

rubrica: 

 

 

 

 

... un Gioco Matematico in cui si può trovare la regola vincente...

Il Leone d’Oro della Mostra del Cinema di Venezia del 1961 andò a un film apparentemente incomprensibile a quell’epoca: L’anno scorso a Marienbad.
Alain Resnais aveva conquistato la giuria con una pellicola a metà strada tra la realtà, il sogno e l’immaginazione, sull'onda della Nouvelle Vague di cui era stato ispiratore teorico.
 
Quel premio fece scalpore perché non si era veramente capito che cosa avesse realmente spinto la giuria a conferire quel riconoscimento: solo più tardi ci si rese conto che il regista aveva realizzato la metafora della società e della noia, quella che trasforma gli individui in spettrali automi in bianco e nero, tutti uguali e indistinguibili.
Alain Resnais (Vannes 1922 - live) era uscito solo due anni prima da un grande successo con Hiroshima mon amour(1959) e il pubblico aveva imparato ad apprezzare quel linguaggio nuovo e misterioso che il regista riusciva a trasmettere.
L'anno scorso a Marienbad (L'année dernière à Marienbad) è tratto da un'opera di Alain Robbe-Grillet (Brest 1922 – Caen 2008) uno scrittore che prima di approdare al cinema era stato professore di matematica, da cui tutta la struttura del racconto cinematografico che appoggia su intricate forme di simmetrie e labirinti molto simili alle fantasie di Escher di cui abbiamo già parlato a proposito del Nastro di Moebius.
La storia è ambientata in un lussuoso albergo dentro a una reggia barocca contornata da giardini stupefacenti: le porte delle camere sono identiche, i camerieri sostano immobili come statue e i clienti alto-borghesi appaiono silenziosi, gelidi e spettrali. Anche le conversazioni procedono a rilento, quasi come se le frasi non dovessero significare niente.
In questa atmosfera surreale si muove un uomo simile a un’ombra (il Signor XGiorgio Albertazzi) che si avvicina a una donna (la Signora A - Delphine Seyrig) sostenendo di averla già conosciuta in passato.
In uno strano universo in cui i dialoghi cadono nel vuoto, soltanto A e X sembrano capirsi e si interrogano sul significato della realtà davanti a un terzo personaggio (il Signor MSacha Pitoef) il vero ‘Guardiano del mondo’, un mondo fatto di un Gioco Matematico in cui si può anche perdere ma dove, volendo, si può trovare la regola per essere sempre vincitori.
Per il gioco in questione, al quale il Signor M risulta praticamente invincibile, servono solo alcuni gettoni (come nel film) oppure dei semplici fiammiferi che vengono disposti su più file. Due giocatori, a turno, possono prelevare una parte o tutti i fiammiferi di una fila, e soltanto di una fila. Perde il giocatore al quale rimane l'ultimo fiammifero.
Pitoef continua a sfidare Albertazzi al gioco e questo diventa il vero motivo ossessionante del film.
Gli avventori discutono le conclusioni matematiche più disparate ... "chi fa la prima mossa vince sempre - Si deve prendere sempre un numero pari di fiammiferi - Il più piccolo numero intero dispari - E' una serie logaritmica - Si sceglie ogni volta una riga diversa, si divide per tre ... sette per sette quarantanove" ... ma questi sono solo frammenti di un discorso volutamente oscuro e che non ci aiuta certo a capire il vero meccanismo del gioco.
In realtà stiamo parlando del NIM,un gioco originario dell'antica Cina che comparve per la prima volta in Europa nel Cinquecento. Probabile che il nome derivi dal tedesco Nimm (prendere) ma è anche conosciuto come Tactix o anche Fan-tan.
La particolarità del NIM è quella di essere il capostipite dei cosiddetti Giochi Combinatori Imparziali attentamente studiati già all’inizio del 900 da Charles Leonard Bouton, docente di analisi matematica all’Università di Harvard.
Le proprietà dei Giochi Combinatori Imparziali debbono soddisfare a queste 6 regole precise:
 
1) Il gioco si svolge a 2 persone.
2) Le posizioni possibili sono in numero finito.
3) E' definito un insieme di regole - uguali per i 2 giocatori - che, data una configurazione, stabiliscono le configurazioni cui è lecito passare.
4) I due giocatori alternano le mosse.
5) Esistono configurazioni, dette terminali, dalle quali non è più possibile effettuare alcuna mossa, cioè non è lecito passare a nessun’altra configurazione.
6) Si arriva sempre ad una configurazione terminale in un numero finito di passi.
 
Perde chi al momento di giocare si trova in una situazione terminale, cioè non può fare alcuna mossa. Viceversa, vince chi arriva per primo in una posizione terminale.
Ma vediamo nella pratica di cosa realmente si tratta:
 
Regola.
Due giocatori, a turno, tolgono da una fila (il numero delle file ed il loro contenuto viene concordato all'inizio del gioco), un numero d'elementi a piacere. Vince chi toglie l'ultimo elemento presente sul campo di gara.
Non è possibile passare (saltare la mossa).
Nella versione Marienbad del gioco (cioè quella del film) si applica questo schema:
·         Numero delle File              4
·         Contenuti                       rispettivamente: 1, 3, 5, 7.
Facciamo subito un esempio pensando a 4 mucchietti di fiammiferi:
 
  
 
Abbiamo 4 file rispettivamente di 1, 3, 5, 7 fiammiferi (partendo dall’alto).
Ora i giocatori cominciano ad alternarsi (senza mai passare) togliendo sempre dalla stessa fila un numero di fiammiferi a piacere (da uno a tutti).
Vince chi per ultimo riesce a sgomberare il campo.
La strategia per vincere al gioco, valida anche nel caso di un numero diverso di righe e di fiammiferi, si fonda sul sistema binario, il sistema di numerazione usato dai computer.
La soluzione del gioco sta nel far cadere ogni volta l’avversario in una posizione Perdente, assicurandone a se stesso una Vincente.
Ma prima di procedere, vediamo di ripassare brevemente i Sistemi di numerazione.
Oltre al Sistema Decimale (conosciuto fin dalla nostra infanzia, probabilmente perché proprio dieci sono le dita delle mani e dei piedi), esistono altri Sistemi per rappresentare i numeri.
Se per esempio cambiamo la Base di numerazione da 10 (decimale) a 2 otteniamo il Sistema Binario.
La tabella che segue riporta la conversione da un Sistema all’altro dei primi 7 numeri naturali.
Nel Sistema binario si utilizzano delle celle (digit, da cui la locuzione oggi usata: digitale) che vanno lette da destra verso sinistra (secondo il verso della freccia gialla) tramite questa regola:
  • Il primo digit (verde)          rappresenta 2 elevato alla potenza 0
  • Il secondo digit (rosso)       rappresenta 2 elevato alla potenza 1
  • Il terzo digit (blu)              rappresenta 2 elevato alla potenza 2.
Ricordando che 2 elevato alla potenza 0 dà come risultato il numero 1, si capisce che:
Il decimale 1 è uguale a: Digit verde in stato 1 + digit rosso in stato 0 + digit blu in stato 0
Il decimale 2 è uguale a: Digit verde in stato 0 + digit rosso in stato 1 + digit blu in stato 0
Il decimale 3 è uguale a: Digit verde in stato 1 + digit rosso in stato 1 + digit blu in stato 0
...
Il decimale 6 è uguale a: Digit verde in stato 0 + digit rosso in stato 1 + digit blu in stato 1
Il decimale 7 è uguale a: Digit verde in stato 1 + digit rosso in stato 1 + digit blu in stato 1
 


 

La numerazione binaria è fondamentale nel linguaggio del computer per il semplice fatto che in elettronica gli stati di un circuito sono sempre e solo 2, cioè: 1 oppure 0 (o anche: Sì/No oppure: Vero /Falso).
I computer dunque ragionano in logica binaria.
Il vero limite di tutta la faccenda è che per rappresentare i numeri in binario servono molti più digit che non in decimale, tanto che con 3 digit si riesce ad arrivare solamente al numero 7 ... ma questo è un falso problema poiché oggi con l’elettronica integrata si possono concentrare anche diversi miliardi di digit in uno stesso chip.
 
Ma torniamo al NIM:
Nel NIM le posizioni Perdenti e/o Vincenti sono, per così dire, predeterminate, proprio per il fatto che questo è un Gioco Combinatore Imparziale.
In pratica, guardando attentamente la combinazione di fiammiferi che abbiamo in mano in un certo momento, possiamo sapere con certezza se è Perdente o Vincente: nel primo caso la trasformeremo in Vincente, nel secondo la lasceremo come sta.
Ma qual è realmente questa regola? Rientra forse tra qualcuna delle disparate conclusioni degli avventori dell’albergo di Marienbad?
La soluzione che definisce se una qualsiasi delle combinazioni del Nim è di tipo P (perdente) oppure di tipo V (vincente) esce dal teorema di Sprague-Grundy, due matematici che per vie diverse arrivarono insieme allo stesso risultato (Roland Sprague nel 1935 e P. Grundy nel 1939).
Il gioco del Nim è così utilizzato come illustrazione semplice del teorema di Sprague-Grundy.
Teorema: Nel NIM sono Vincenti le posizioni in cui (scritti i numeri dei fiammiferi in notazione binaria) in ogni colonna della tabella binaria c’è un numero pari di 1. Sono Perdenti tutte le altre.
Per prima cosa, si devono contare i fiammiferi di ogni fila e si trasformano in notazione binaria.
Poi si sommano i numeri binari così trovati.
Se le cifre della somma sono tutte uguali a zero oppure pari, la configurazione è vincente altrimenti, se c’è anche una sola cifra dispari, è perdente. In quest’ultimo caso, si procederà con una sottrazione di fiammiferi, in modo da trasformare la configurazione in vincente.
Vediamo un esempio:
La somma dei fiammiferi sulle tre file è 132.
La cifra dispari 3 ci segnala che la configurazione di sinistra è perdente e possiamo trasformarla in vincente sottraendo sei fiammiferi dalla terza fila. In questo modo infatti la somma diventa 22, con le cifre tutte pari.
In chiusura del gioco, per vincere, sarà sufficiente lasciare un numero dispari di file con un solo fiammifero.
 
 
 
 
Questa strategia è valida anche nel caso in cui il gioco preveda che il vincitore sia il giocatore che prende l'ultimo fiammifero. Cambia soltanto il finale: si procede in modo da avere due file con lo stesso numero di fiammiferi, cercando poi di mantenerle sempre con un numero uguale di fiammiferi.
... e così il Signor M dell’albergo di Marienbad aveva sempre la meglio sul più sprovveduto Signor X e tutte le sue mosse risultavano sempre vincenti.
Resnais era stato ben indottrinato da Grillet che in fatto di numeri e di teoremi sapeva certamente il fatto suo.
 
... una pellicola un po’ datata ma che da qualche parte ancora si può trovare in qualche cineteca e che può valer la pena di essere rivista.
 
Francesco Caranti