«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 1111002 = 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 = 8 + 2 + 1
22 = 16 + 4 + 2
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
«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».
