backup del Post

Nim e gioco di Wythoff

Il gioco del Nim è probabilmente l’archetipo dei giochi matematici in senso stretto; quelli cioè a cui si può giocare penso fino a non oltre i sette anni d’età e che però sono amati dai matematici perché possono far vedere quanto sono bravi a risolverlo. Spero che abbiate qualche figlio o nipotino dell’età giusta, per potere apprezzare appieno il gioco, e che siate abbastanza seri da lasciarlo vincere qualche volta, anche se conoscete la strategia perfetta.

Il Nim si gioca ponendo sul tavolo alcune pile di monete, bastoncini, fagioli o quello che vi pare. Ci può essere un numero qualunque di pile, anche se con meno di tre il gioco è troppo semplice, e ciascuna pila può avere un numero qualunque di oggetti. A ogni mossa, ciascun giocatore toglie un certo numero di oggetti a sua scelta da una delle pile, anch’essa a sua scelta; se vuole può anche prenderseli tutti. Vince chi raccatta l’ultimo oggetto oppure, nella versione misère, chi è costretto a prenderlo perde. Per la cronaca, in questo tipo di giochi la strategia nella versione misére è generalmente più complicata di quella del gioco standard.

Per trovare la strategia vincente, il passaggio è semplice, ma richiede di conoscere la numerazione binaria, quella cioè dei computer che usa solo le cifre 0 e 1. Bisogna convertire in formato binario il numero di oggetti nelle varie pile e poi sommare (in base 10, stavolta) i numeri ricavati. Se con la vostra mossa riuscite a fare in modo che le cifre di questa somma siano tutte pari, allora siete in una botte di ferro, e vincerete. L’unica differenza nella versione misére è che se rimangono solo pile con un elemento allora ce ne devono essere un numero dispari; diciamo però che ci si può ricordare di questa eccezione. Esempio pratico: partendo da tre pile di 7, 11 e 13 oggetti, i numeri corrispondenti in base 2 sono rispettivamente 111, 1011 e 1101 la cui somma è 2223. Per arrivare a un numero pari basterà togliere un singolo oggetto da una pila qualunque, visto che in tutti e tre i casi i numeri binari finiscono per 1 e quindi non c’è nessun riporto da fare.

Il bello del Nim – beh, almeno dal punto di vista di un matematico – è l’essere il mattone fondamentale nella teoria delle partite a due persone; seondo il teorema di Sprague–Grundy ogni gioco a due persone in formato standard (cioè dove chi non può muovere ha perso) può essere visto come la somma di varie partite a Nim, giocate su tavoli diversi. Detto in altro modo, ogni giocatore al suo turno sceglie su quale tavolo giocare e fa la sua mossa, e vince chi raccoglie l’ultimo oggetto nell’ultimo tavolo. (Tra l’altro noi in italiano siamo fregati con il nome; gli americany parlano di “play”, solo che nel nostro caso dire “gioco” ci fa cascare nella teoria dei giochi che si studia in economia, e che è tutta un’altra cosa). Si parla addirittura di addizione Nim; indicata dal simbolo ⊕, è associativa e commutativa proprio come quella usuale, ma ha in più la caratteristica che a ⊕ a è sempre uguale a zero. Come ricordate, nella strategia i numeri pari contano zero, e per definizione sommare (in base dieci) un numero (scritto in base due) a sé stesso dà tutte cifre pari a zero o due. Qui a fianco c’è una tabellina di addizione Nim; un po’ strana, ma perlomeno coerente. Gli anglofoni chiamano nimbers i numeri Nim; a quanto pare nessun italiano ha parlato di “nimeri”, il che è triste perché dimostra che non ci sono abbastanza persone seriamente giocose… a parte naturalmente i Rudi Mat(h)ematici.

Il gioco di Wythoff, dal nome di un matematico olandese assolutamente ignoto a chi non fa matematica ricreativa e il cui cognome sbaglio sempre a scrivere, è simile ma non uguale al Nim. Le pile sono infatti solo due; in compenso però le mosse a disposizione sono di tre tipi fondamentalmente diversi. Si può prendere quanti oggetti si vuole dalla prima pila, oppure se ne possono prendere quanti se ne vuole dalla seconda, o ancora si possono prendere oggetti da entrambe le pile, ma in questo caso occorre prenderne in numero uguale. Un modo alternativo per giocare è immaginare di avere una scacchiera (m+1)·(n+1) dove si mette nell’angolo in alto a destra una pedina; le mosse sono quelle della regina, ma ci si può muovere solo a sinistra o verso il basso.

La strategia vincente non è così semplice come nel Nim. Il modo più semplice per definirla è quello di indicare le posizioni che garantiscono la vittoria al giocatore che riesce a raggiungerle; le prime sono (0, 0), (1, 2), (3, 5), (4, 7), e (6, 10), oltre naturalmente alle simmetriche come (2, 1), (5, 3) e così via. Nella figura qui a fianco si vede come si possono trovare graficamente e ricorsivamente le posizioni vincenti; scelte le due posizioni più a sinistra e più in basso rimaste ancora libere, si disegnano tre semirette che partono da quelle posizioni e si cancellano tutte le caselle toccate, continuando a piacere con un minimo di pazienza. In realtà esiste una formulazione diversa per calcolare le posizioni vincenti; ma per spiegarla devo prima raccontarvi varie altre cose. Prima o poi ce la faremo, fidatevi.