mercoledì 7 agosto 2013

Nim — 14. La strategia vincente

«Alcuni libri, tra cui anche quello di Martin Gardner, suggeriscono di fare i conti con i nimeri in modo diverso rispetto a quello che abbiamo usato noi».

«E perché?».

«Mah, non saprei dirlo esattamente. Forse perché danno il metodo bello e pronto, senza spiegare niente, o forse perché in origine lo studio del Nim è stato fatto proprio in questo modo».

«Uh, un articolo del 1901».

«Sì, la teoria di Sprague-Grundy è venuta dopo».

«Ah, ecco. E come faceva l'autore…».

«Charles L. Bouton».

«Come faceva Bouton a vincere al Nim?».

«La regola base per le operazioni era questa: scrivi i numeri in binario e fai la somma senza riporto».

«Cosacosa?».

«Ti faccio vedere con i calcoli che abbiamo fatto l'altra volta. Abbiamo visto, per esempio, che *5 + *3 = *6. Bouton diceva di trasformare 5 e 3 in binario…».

«Cioè 510 = 1012 e 310 = 112».

«Sì. Poi metti in colonna e fai la somma senza tener conto del riporto. In pratica usi queste regole: 0 + 0 = 0, 1 + 0 = 1 e 1 + 1 = 0».

«Vediamo, ecco qua:».

1 0 1
  1 1
-----
1 1 0

«Molto bene. Quanto fa 1102?».

«Fa 4 + 2 = 6, giusto!».

«Prova anche con *11 + *22 + *33».

«Pronti:».

11 =     1 0 1 1
22 =   1 0 1 1 0
33 = 1 0 0 0 0 1
----------------
     1 1 1 1 0 0

«E 111100= 6010».

«Giusto anche questo. Come mai funziona?».

«Bé, sono le regole che abbiamo scoperto l'altra volta: due numeri uguali si cancellano quando vengono sommati, no?».

«Sì».

«E questo significa che quando sommi trascuri il riporto: 1 + 1 = 0 è una cancellazione, in pratica».

«Ah, già. E l'altra regola diceva che le potenze di 2 si sommano normalmente, come se usassimo la somma usuale».

«E infatti quando passiamo da forma binaria a forma decimale sommiamo potenze di 2, tutto qua».

«Bella roba. Ma questo cosa ha a che fare con la strategia vincente?».

«Ci arriviamo subito: ricorderai la nostra partita a Nim (3,2,1)».

«Certo, ho cominciato io, ma dato che *3 + *2 + *1 = 0 hai vinto tu».

«Ottimo riassunto: se tu giochi a un gioco nullo, hai perso. Io, per vincere, devo fare in modo che tu abbia sempre a che fare con un gioco nullo».

«E come fai?».

«Ti faccio vedere con un esempio: inventati un Nim con quante pile vuoi».

«Boh, per esempio (3,14,15,9)».

«Bene, per prima cosa scomponiamo in potenze di 2 tutti i numeri:».

3 = 2+1
14 = 8+4+2
15 = 8+4+2+1
9 = 8+1

«Va bene, poi?».

«Ora faccio i conti, quanto vale la somma-nim di quei quattro numeri?».

«Devo fare la somma in colonna, dopo aver trasformato in binario?».

«Non c'è bisogno: con la scomposizione in somme di potenze di 2 puoi fare a mente, guarda prima cosa si cancella».

«Se non sbaglio, cancellando le cifre a 2 a 2 uguali, mi rimane 8+2+1».

«Che fa 11. Siccome 11 è diverso da 0, comincio io».

«Fai pure, immagino che mi passerai un gioco nullo».

«Naturalmente. Il problema è: come faccio a farlo diventare nullo?».

«Come fai?».

«Visto che dopo le semplificazioni avanzano i numeri 8, 2 e 1, li cancello: sottraggo 11 dalla terza pila».

3 = 2+1
14 = 8+4+2
4 = 4
9 = 8+1

«Ah, adesso il gioco fa zero. Ora tocca a me?».

«Sì. Qualunque mossa tu farai, il gioco non potrà valere ancora zero».

«Perché?».

«Perché puoi togliere pedine solo da una pila, quindi sbilancerai certamente le coppie che prima si cancellavano».

«Ah, già. Bé, allora cancello tutta la pila da 14».

3 = 2+1
4 = 4
9 = 8+1

«Siamo a 8 + 4 + 2 = 14».

«Ora come fai a tornare a zero? Non puoi cancellare l'otto, il quattro e il due, sono in pile diverse!».

«Sottraggo due pedine dalla terza pila».

«Perché?».

«Pensa all'8 che vedi nella terza pila: se sottrai due pedine diventa 6, cioè 4 + 2, che è quello che mi serve per bilanciare tutto:».

3 = 2+1
4 = 4
7 = 4+2+1

«Ah, ecco! Ancora una volta è 0. Se ora togliessi 5 pedine dalla terza pila?».

3 = 2+1
4 = 4
2 = 2

«Dimmi tu cosa dovrei fare».

«Hai 2+1 sopra, hai 2 sotto, ti basta trasformare il 4 in 1».

3 = 2+1
1 = 1
2 = 2

«Già. E siamo arrivati al nostro vecchio conoscente: (3,2,1). Direi che possiamo concludere la partita, no?».

«Eh, sì. Ma ci si riesce sempre a far diventare nullo un gioco non nullo?».

«Sì, pensa a come fai i calcoli: se il gioco non è nullo significa che nelle semplificazioni c'è qualche potenza di 2 sbilanciata. Se queste potenze sbilanciate si trovano su una pila sola, le cancelli tutte».

«E se si trovano su pile diverse?».

«Cerchi la più grande, e la diminuisci fino a farla diventare uguale alla somma delle altre».

«Uh, possiamo vedere un altro esempio?».

«Eccolo qua: (11,22,33)».

«Chi comincia?».

«Vai, per questa volta comincia tu. Devi vincere, visto che abbiamo già calcolato la somma-nim di questo gioco e sappiamo che vale 60».

«Allora, mi scrivo i numeri come somme di potenze di 2:».

11 = 8 + 2 + 1
22 = 16 + 4 + 2
33 = 32 + 1

«Bene, ho visto che hai messo anche i termini che si semplificano. Adesso?».

«Scelgo la potenza più alta, che è 32, e devo trasformarla in 16+8+4, che fa 28. Tolgo 4 pedine dalla terza pila:».

11 = 82 + 1
22 = 16 + 42
29 = 16 + 8 + 4  + 1

«Molto bene, ora tutto è bilanciato e tocca a me: siamo sicuri che io non possa passare a un'altra configurazione nulla?».

«Uh, ma cadrebbe tutta la teoria che abbiamo sviluppato!».

«Ottima risposta, ma riesci a darmene una più pratica? Perché non posso diminuire una qualche pila fino a bilanciare di nuovo tutto?».

«Mh, non saprei dirlo».

«Diciamo che scelgo la pila più grande, quella da 29. Se tolgo il 16, rimane un 16 sbilanciato».

«Ma non sei obbligato a togliere proprio 16, no?».

«No, ma se comunque tolgo almeno una pedina da quella pila, succede che almeno una delle potenze di 2 che la compongono deve diminuire».

«Già».

«E allora la sua gemella, che necessariamente si trova in un'altra pila, sarà sbilanciata».

«Ah, certo, non posso avere due potenze di 2 uguali nella stessa pila!».

«Potenza della notazione posizionale, se mi concedi la battuta».

«Battuta?».

«Ehm, ok, non faceva ridere. Comunque, andiamo avanti, tolgo 5 pedine dalla pila da 29:».

11 = 8 + 2 + 1
22 = 16 + 4 + 2
24 = 16 + 8

«Avanzano un 4 e un 1. Qui ho molte scelte, posso prendere uno dei due 16 e diminuirlo fino a farlo diventare 4+1».

«No, no, 16 è già bilanciato! Devi prendere la potenza più alta tra quelle non bilanciate».

«Ah, ecco. Allora devo trasformare il 4 della seconda fila in 1: sottraggo 3 dalla seconda pila:».

11 = 8 + 2 + 1
19 = 16 + 2 + 1
24 = 16 + 8

«Ormai hai capito, no? Ogni volta che io sbilancio, tu ribilanci.».

«Direi proprio di aver capito tutto».

«Perfetto, a questo punto allora direi che possiamo fermarci».

«Fine degli studi sul Nim?».

«Fine, ora si tratta di giocare».

lunedì 5 agosto 2013

Nim — 13. Variazioni sulla regola della somma

«Ora vediamo di capire come mai ci sono colori diversi nella tabella della somma di nimeri».

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1| 0| 3| 2| 5| 4| 7| 6| 9| 8|11|10|13|12|15|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3| 0| 1| 6| 7| 4| 5|10|11| 8| 9|14|15|12|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3| 2| 1| 0| 7| 6| 5| 4|11|10| 9| 8|15|14|13|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4| 5| 6| 7| 0| 1| 2| 3|12|13|14|15| 8| 9|10|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5| 4| 7| 6| 1| 0| 3| 2|13|12|15|14| 9| 8|11|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 7| 4| 5| 2| 3| 0| 1|14|15|12|13|10|11| 8| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7| 6| 5| 4| 3| 2| 1| 0|15|14|13|12|11|10| 9| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8| 9|10|11|12|13|14|15| 0| 1| 2| 3| 4| 5| 6| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9| 8|11|10|13|12|15|14| 1| 0| 3| 2| 5| 4| 7| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10|11| 8| 9|14|15|12|13| 2| 3| 0| 1| 6| 7| 4| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11|10| 9| 8|15|14|13|12| 3| 2| 1| 0| 7| 6| 5| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12|13|14|15| 8| 9|10|11| 4| 5| 6| 7| 0| 1| 2| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13|12|15|14| 9| 8|11|10| 5| 4| 7| 6| 1| 0| 3| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14|15|12|13|10|11| 8| 9| 6| 7| 4| 5| 2| 3| 0| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15|14|13|12|11|10| 9| 8| 7| 6| 5| 4| 3| 2| 1| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

«Oh, finalmente».

«Ho aspettato tanto perché così nel frattempo siamo diventati pratici nel calcolare somme di nimeri e Mex».

«Bene, ti ascolto».

«Allora, partiamo dal semplice: se avessimo a disposizione solo il nimero *0, cioè il gioco nullo, la tabella sarebbe molto facile da fare».

«Già, avrebbe una casellina sola, quella rossa».

«Infatti. Ora complichiamo un pochino, aggiungiamo *1. Ora abbiamo due nimeri, *0 e *1, che possiamo combinare in tre modi diversi: *0 + *0, *0 + *1 e *1 + *1. Di questa somma sappiamo già tutto, la regola del Mex ci dice che non usciamo dall'insieme {*0, *1}, e tutte le possibili somme si esauriscono qui».

«Abbiamo fatto la cornice blu».

«Sì. Ora le cose si complicano: se aggiungiamo un nuovo nimero, e cioè *2, ci accorgiamo che possono capitare casi in cui si deve calcolare il Mex di {*0, *1, *2}».

«Giusto, per esempio se dobbiamo calcolare *1 + *2».

«Ottimo. Vale la pena perdere un po' di tempo sui calcoli, per capire cosa c'è sotto: quando calcoliamo il risultato di *1 + *2, stiamo analizzando tutto quello che potrebbe succedere quando un giocatore muove o nel primo gioco o nel secondo».

«Vero».

«Quindi, dato che *1 = {*0} e *2 = {*0, *1}, le possibili mosse sono queste:».

*0 + *2 (muovo nel primo gioco, togliendo l'unica pedina)
*1 + *1 (muovo nel secondo gioco, togliendo una pedina)
*1 + *0 (muovo nel secondo gioco, togliendo due pedine)

«Sì, i possibili risultati sono stati calcolati in precedenza, sono *2, *0 e *1».

«E quindi il Mex vale *3».

«E infatti abbiamo detto che se aggiungiamo *2, abbiamo bisogno anche di *3 per completare la tabella, che sarebbe la nuova cornice colorata di giallo».

«Sì. Ora la domanda: perché dobbiamo aggiungere un nuovo nimero?».

«Ma l'abbiamo appena detto!».

«Aspetta: perché proprio uno solo, e non due o tre o chissà quanti?».

«Ah… uhm».

«Ragioniamo: la regola del Mex è tale per cui ogni riga e ogni colonna sono composte tutte da nimeri diversi».

«Eh, sì, questo lo capisco: il Mex è il più piccolo intero non negativo non presente a sinistra e sopra la casella che vogliamo riempire, quindi non ne posso mai scrivere due uguali».

«Benissimo. Ora osserva la griglia che contiene solo *0 e *1».

«Quella blu».

«Quella: è composta da due righe e due colonne; se voglio allargarla succederà prima o poi che i due nimeri che la compongono, *0 e *1, si devono trovare al di fuori della zona blu».

«Senza dubbio: *0 e *1 sono i due nimeri più piccoli, nella regola del Mex saltano fuori in fretta».

«E allora quando mi capiterà di avere *0 e *1 fuori dalla zona blu, nella zona blu dovranno esserci altri due nuovi nimeri».

«Ah! Ecco perché devo aumentare di due caselle! E dopo avrò a disposizione quattro nimeri, e se vorrò allargare la zona gialla ce ne vorranno altri quattro, poi otto, sedici, trentadue…».

«Perfetto, hai capito. Non ti spaventerà dunque questa regola:».

1. Se a e b sono minori di 2k, allora lo sarà anche *a + *b.

«Non mi spaventa, è quello che abbiamo detto finora. La regola dei colori, insomma».

«Benissimo. Un'ultima considerazione: osserva la prima riga (o la prima colonna) di ogni nuova cornice».

«Cioè quando cambiano colore?».

«Sì, esatto».

«Boh, la prima riga blu è *1, *0».

«Poi?».

«La prima riga gialla è *2, *3, *0, *1».

«Poi la prima riga viola è *4, *5 , *6, *7, *0, *1, *2, *3».

«E la prima riga fucsia è *8, *9, *10, *11, *12, *13, *14, *15, *0, *1, *2, *3, *4, *5, *6, *7, quindi?».

«Quindi succedono varie cose. Prima di tutto, ogni riga di un colore nuovo parte da una potenza di 2».

«Ok, un altro modo di dire quello che abbiamo visto prima».

«Già. Poi, grazie alla regola del Mex, le righe di un nuovo colore proseguono in ordine crescente fino a metà lunghezza».

«Vero anche questo, prima ci sono i nuovi nimeri, poi quelli vecchi».

«Quindi, riassumendo, se prendiamo come esempio la prima riga viola, quella che comincia con *4, *5, *6, *7, e ci ricordiamo che quei nimeri sono il risultato di una somma, possiamo dire questo:».

*4 + *0 = *4
*4 + *1 = *5
*4 + *2 = *6
*4 + *3 = *7

«E poi ci fermiamo, perché *4 + *4 non fa *8 ma *0».

«Bene. Generalizzando, cosa possiamo dire?».

«Uhm, forse possiamo dire che se prendiamo una potenza di 2 e sommiamo dei nimeri, è come se facessimo una somma normale?».

«Quasi. La regola vale solo fino a metà riga, nel nostro esempio fino a *4 + *4 escluso».

«Ok, allora ho capito, provo a formulare la regola: se sommo una potenza di 2 con un nimero minore di essa, è come se stessi facendo una somma tra normali numeri».

«Bene, in formule è così:».

2. Se a < 2k, allora *a + *2k = *(a + 2k).

«Capito».

«Da cui deduciamo subito queste regole pratiche:».

3. La somma-nim di due diverse potenze di 2 è uguale alla loro somma ordinaria, e la somma-nim di due numeri uguali è 0.

«Perché dici somma-nim?».

«Per non mettere tutti gli asterischi, e per non dover specificare ogni volta che le potenze di 2 che consideriamo sono dei nimeri».

«Ah, ok. E come mai le hai chiamate regole pratiche?».

«Perché ci permettono di fare molto in fretta i calcoli. Ti faccio qualche esempio: vogliamo calcolare il risultato di questa operazione:».

5 ⊕ 3

«Cos'è quello strano simbolo?».

«Significa che stiamo addizionando nimeri, è come se avessi scritto *5 + *3. Dato che dobbiamo fare un po' di calcoli, mi pare che sia più comodo. Tieni presente che quando scrivo ⊕ intendo l'addizione tra nimeri, mentre quando scrivo + intendo la normale addizione tra numeri».

«Ah, va bene. Allora, dobbiamo calcolare 5 ⊕ 3».

«Sì, utilizzando solo la regola pratica, cioè quella che abbiamo indicato col numero 3».

«Ma è una regola che parla di potenze di 2, o di numeri uguali».

«Vorrà dire che dobbiamo trasformare quei numeri in potenze di 2».

«Come se stessimo facendo un cambiamento di base?».

«Esattamente, ottimo! 5 in base 2 è uguale a 101, cioè 4 + 1».

«Mentre 3 è uguale a 11, cioè 2 + 1».

«E quindi il nostro calcolo diventa questo:».

5 ⊕ 3 = (4 + 1) ⊕ (2 + 1)

«E adesso come facciamo? Abbiamo due diversi simboli di somma».

«La somma-nim di due diverse potenze di 2 è uguale alla loro somma ordinaria, quindi scrivere 4 + 1 è come scrivere 4 ⊕ 1».

«Ah, allora possiamo togliere le parentesi e usare solo il simbolo della somma-nim:».

5 ⊕ 3 = 4 ⊕ 1 ⊕ 2 ⊕ 1

«Ora ricordati che la somma-nim di due numeri uguali è uguale a 0».

«E quindi posso scrivere questo:».

5 ⊕ 3 = 4 ⊕ 1 ⊕ 2 ⊕ 1 = 4 ⊕ 2

«Ora hai due potenze di 2 da sommare, quindi…».

Quindi posso calcolare il risultato: 4 ⊕ 2 = 4 + 2 = 6

«Benissimo. Se vogliamo utilizzare la notazione a cui siamo abituati, abbiamo calcolato che *5 + *3 = *6».

«Concorda con la tabella».

«Col vantaggio che non abbiamo avuto bisogno di consultarla per poter calcolare il Mex».

«Bello, si dovrebbe riuscire a fare i calcoli più in fretta».

«È così. Prova per esempio a calcolare questo:».

11 ⊕ 22 ⊕ 33

«Uh, questi sono numeri fuori dalla tabella. Allora, prima scompongo in potenze di 2 i vari numeri».

11 = 8 + 2 + 1
22 = 16 + 4 + 2
33 = 32 + 1

«E fin qua ci siamo».

«Poi addiziono tutto».

«Sì, ma ti conviene già scartare le coppie di numeri uguali».

«Ah, giusto: si annullano. Allora mi rimane questo:».

8 ⊕ 16 ⊕ 4 ⊕ 32 = 60

«Molto bene. Ora che hai capito, puoi anche abbreviare i calcoli e, se vuoi, usare l'altra notazione. Per esempio:».

*9 + *25 + *49 = (*8 + *1) + (*16 + *8 + *1) + (*32 + *16 + *1) = *32 + *1 = *33

«Ah, hai colorato le potenze che si semplificano».

«Sì, come vedi è molto comodo. Ora, una domanda: se noi facessimo la somma normale, otterremmo un numero certamente più grande o più piccolo di quello che otterremmo facendo la somma-nim?».

«Mh, a volte viene uguale, mentre altre volte più grande, dato che nella somma-nim ci sono delle possibili semplificazioni».

«Molto bene, quindi potremmo dire che a ⊕ b ≤ a + b».

«Direi proprio di sì».

«Un'ultima domanda: quando le due somme sono diverse, per cosa differiscono?».

«Per le potenze di 2 che ho semplificato».

«Bene, e posso dire che ogni volta che faccio una semplificazione tolgo due copie dello stesso numero?».

«Certo».

«E quindi tolgo un numero pari ogni volta».

«Ho capito: le due somme differiscono per un numero pari (o per 0, quando non ci sono semplificazioni, ma tanto anche 0 è pari)».

«Perfetto. Ecco l'ultima regola di oggi:».

4. La somma-nim è minore o uguale della somma usuale, ed esse differiscono per un numero pari.

«E quindi?».

«E quindi ora possiamo parlare di una strategia vincente per il Nim».

venerdì 2 agosto 2013

Nim — 12. Il Cavaliere Distratto

«Ora studiamo un nuovo gioco, così capiamo la potenza della teoria di Sprague-Grundy. Il gioco si chiama Il Cavaliere Distratto».

«Bel nome».

«Abbiamo un cavaliere (cioè un cavallo degli scacchi) che si può muovere su una scacchiera, che possiamo immaginare infinita andando a destra e verso il basso».

«Ok, e perché è distratto?».

«Perché perde le cose. Al momento ha perso sei scatole, che abbiamo messo da parte. Scopo del gioco è quello di fare arrivare il cavaliere in una delle quattro caselle d'angolo in alto a sinistra e raccogliere tutte le scatole. Le caselle in questione sono queste:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 2 | 5 | 4 | 7 | 6 |
+---+---+---+---+---+---+---+---+
| 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
+---+---+---+---+---+---+---+---+
| 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
+---+---+---+---+---+---+---+---+
| 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+
| 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
+---+---+---+---+---+---+---+---+
| 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+---+---+---+---+---+---+---+---+

«Lo zero all'interno cosa significa?».

«Ho già messo il nimero corrispondente a quella posizione: lì il gioco relativo alle mosse del cavaliere è finito».

«Ma si possono ancora raccogliere scatole?».

«Sì, in pratica abbiamo due giochi: una pila di 6 scatole, e il cavaliere sulla scacchiera. Ogni giocatore può muovere in uno dei due giochi, o prende delle scatole o muove il cavaliere».

«Ok».

«E, naturalmente, del gioco riguardante la presa delle scatole sappiamo tutto, è un Nim composto da una pila di sei elementi, quindi vale *6».

«Bene».

«Il problema è capire quali nimeri associare alle posizioni del cavallo sulla scacchiera, ma con la teoria di Sprague-Grundy non abbiamo problemi a fare i calcoli. Rispetto agli scacchi, però, c'è una restrizione: il cavallo non può muovere dove vuole, ma solo nelle due caselle sopra di lui e nelle due alla sua sinistra. Questo per fare in modo che il gioco prima o poi termini».

«Insomma, se il cavallo si trova nella casella blu, può solo andare sulle caselle rosse, giusto?».

+---+---+---+---+---+
|   |   | 2 |   | 4 |
+---+---+---+---+---+
|   |   | 3 | 2 | 5 |
+---+---+---+---+---+
| 2 | 3 | X | 1 | 6 |
+---+---+---+---+---+
|   | 2 | 1 | 0 | 7 |
+---+---+---+---+---+
| 4 | 5 | 6 | 7 | 0 |
+---+---+---+---+---+

«Giusto. Ora proviamo a calcolare il nimero corrispondente alla casella rossa».

+---+---+---+---+---+---+---+---+
| 0 | 0 |   | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 2 | 5 | 4 | 7 | 6 |
+---+---+---+---+---+---+---+---+
| 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
+---+---+---+---+---+---+---+---+
| 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
+---+---+---+---+---+---+---+---+
| 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+
| 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
+---+---+---+---+---+---+---+---+
| 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+---+---+---+---+---+---+---+---+

«E come facciamo?».

«Facciamo un elenco delle caselle in cui il cavallo può muoversi».

«Ce n'è una sola, quella arancione in seconda riga, prima colonna».

«Bene, quindi il cavallo nella casella rossa corrisponde a un gioco fatto così: G = {*0}».

«Uhm».

«Ricorda che un gioco è definito dalle sue mosse, se il cavallo si trova nella casella rossa c'è una sola mossa possibile, il cui valore è 0».

«Ah, già».

«Ora, applicando la regola del Mex, possiamo calcolare il valore della casella: quanto vale Mex({*0})?».

«È il minimo intero non negativo non compreso nell'elenco delle mosse del gioco, quindi direi 1».

«Più precisamente, *1. Ma nella tabella mettiamo solo 1. Per simmetria mettiamo 1 anche nella casella alla terza riga, prima colonna».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| 0 | 0 |   | 2 | 5 | 4 | 7 | 6 |
+---+---+---+---+---+---+---+---+
| 1 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
+---+---+---+---+---+---+---+---+
| 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
+---+---+---+---+---+---+---+---+
| 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+
| 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
+---+---+---+---+---+---+---+---+
| 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+---+---+---+---+---+---+---+---+

«Sì, giusto, i calcoli sono gli stessi. Ora calcoliamo il valore della nuova casella rossa?».

«Sì, vai».

«Vediamo: ci sono due caselle verso le quali il cavallo può muoversi: quella nell'angolo in alto a sinistra, di valore 0, e quella in terza riga, prima colonna, di valore 1».

«Vuoi dire *1».

«Ah, già. Quindi se il cavallo si trova nella casella rossa siamo di fronte a un gioco G = {*0, *1}. Quindi il Mex dovrebbe essere 2».

«Dici bene: mettiamo il valore nella tabella. Già che ci sono te la riempio un po' io, e ti faccio fare un altro calcolo. Cosa mettiamo ora nella casella rossa?».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 7 | 4 | 5 |
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 |   | 7 | 6 | 5 | 4 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 7 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 7 | 6 | 1 | 0 | 3 | 2 |
+---+---+---+---+---+---+---+---+
| 1 | 1 | 4 | 5 | 2 | 3 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 1 | 5 | 4 | 3 | 2 | 1 | 0 |
+---+---+---+---+---+---+---+---+


«Ah, ora sono possibili tutte e quattro le mosse del cavallo. Stiamo giocando a un gioco G = {*0, *2, *2, *0}; ho scritto i nimeri due volte perché anche se a due a due sono uguali, le caselle su cui posso muovere sono diverse».

«Va bene, non c'è problema. Ora il Mex: quanto vale?».

«Mex(G) =  *1, quindi in quella casella ci va un 1, vero?».

«Molto bene! Ecco la tabella completa:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 2 | 2 |...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 1 | 4 | 3 | 2 |...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 4 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 |...|...|...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 |...|...|...|...|...|...|
+---+---+---+---+---+---+---+---+

«Non è proprio completa, eh».

«Eh, no, per sapere cosa mettere nelle caselle coi puntini dovrei prolungare un po' le prime righe e le prime colonne».

«E perché hai colorato quelle quattro caselle con un colore diverso?».

«Perché, anche se ancora non si vede tanto, la tabella ricomincia uguale a sé stessa a partire da quelle quattro caselle».

«Ah, Ma ora giochiamo anche?».

«Sì, ti lascio scegliere dove posizionare il cavallo, e io farò la prima mossa.».

«Vabbé, tanto so già che perderò».

«Ehm».

«Diciamo che metto il cavallo qua:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 2 | 2 |...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 1 | 4 | 3 | 2 |...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 4 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 |...|...|...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 |...|...|...|...|...|...|
+---+---+---+---+---+---+---+---+

«Allora io tolgo 3 elementi dalla pila delle scatole: ora ne rimangono 3».

«Uhm, allora tolgo un elemento anche io dalla pila delle scatole».

«Ok, allora rimangono due elementi, e io muovo qua:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 2 | 2 |...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 1 | 4 | 3 | 2 |...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 4 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 |...|...|...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 |...|...|...|...|...|...|
+---+---+---+---+---+---+---+---+

«Allora io muovo in questa casella:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 2 | 2 |...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 1 | 4 | 3 | 2 |...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 4 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 |...|...|...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 |...|...|...|...|...|...|
+---+---+---+---+---+---+---+---+

«E io tolgo una scatola, ora ne rimane una».

«E io ho perso: se prendo la scatola, tu muovi il cavallo in una delle quattro caselle di valore zero, se invece faccio io quella mossa, tu prendi la scatola. Come hai fatto?».

«Ho usato la teoria di Sprague-Grundy. Quando tu hai scelto la posizione del cavallo, in pratica mi hai lasciato un gioco G1 = {*0, *1, *2, *2}».

«Corrispondente alle quattro possibili mosse che poteva fare il cavallo, giusto».

«E poi mi hai lasciato anche le sei scatole, cioè un gioco G2 = *6».

«Una pila Nim da 6 elementi, giusto».

«Per la teoria di Sprague-Grundy, anche G1 è equivalente a una pila Nim, no?».

«Vero anche questo, si usa il Mex: G1 = *3, il valore scritto nella casella».

«Perfetto. In pratica stavamo giocando a un Nim con due pile: (3,6)».

«Ah! Sappiamo che vince il primo giocatore».

«Certo, per questo ho cominciato. E la strategia è stata quella di passarti sempre due pile uguali. Se riguardi le mosse, ho fatto in modo che G1 e G2 avessero sempre lo stesso valore».

«E siccome un Nim con due pile uguali è nullo, ho perso…».

«Infatti».

«Bella roba. Ma qual è la strategia vincente per un Nim un po' più complicato?».

«Bella domanda».