lunedì 22 luglio 2013

Nim — 7. Manca qualcosa

«Per capire cosa inserire nelle caselle rimaste vuote nella tabella dell'altra volta, dobbiamo studiare un altro gioco».

«Quale?».

«Ecco qua: (6,4,2)».

«Uh, le pedine cominciano ad aumentare».

«Eh, sì. Ma cominciamo a mettere un po' di ordine: il secondo giocatore deve ricordarsi quali sono le posizioni buone per lui. Finora ne abbiamo trovate due, e cioè (3,2,1) e (5,4,1). Se il secondo giocatore riesce a muovere in una di quelle due posizioni, l'altro non ha speranze».

«Vero, quelle posizioni sono nulle, se le passa al suo avversario è sicuro di vincere».

«Ok. Provando a elencare le possibili mosse che si possono fare a partire da (6,4,2), otteniamo uno schema del genere».



«Vedo che non ci sono tutte le possibili mosse».

«No, ho omesso quelle in cui si ottengono due pile uguali, perché sappiamo che sono nulle, e quindi il primo giocatore deve evitarle, se vuole avere qualche speranza. Ho anche tralasciato quelle in cui il primo giocatore cancella una pila intera, perché sappiamo già che sono mosse perdenti».

«Provo a riassumere: se il primo giocatore si trova di fronte a (6,4,2), qualunque mossa egli faccia il secondo giocatore può sempre arrivare a (3,2,1) oppure (5,4,1); a parte i casi ovvi in cui il primo giocatore gli serve la vittoria in mano».

«Giusto. Quindi il gioco (6,4,2) è sempre a favore del secondo giocatore. In formule *6 + *4 + *2 = 0».

«Ah, quindi *6 + *4 = *2, e poi *6 + *2 = *4, e anche *4 + *2 = *6».

«Molto bene. Possiamo quindi riempire qualche altra casella della nostra tabella. Purtroppo notiamo che essa si ingrandisce, perché ora abbiamo introdotto anche il nimero 6».

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

«Vedo. Bisogna provare qualche altro gioco, per riempirla?».

«Bisognerà fare anche questo, sì. Ma per adesso possiamo fare un po' di aritmetica. Per esempio, siamo in grado di calcolare il valore di *3 + *5».

«E come facciamo?»
.
«Ci ricordiamo che *3 = *2 + *1, e così possiamo scrivere».

*3 + *5 = *2 + *1 + *5

«E questo a cosa ci serve?».

«Sappiamo che *1 + *5 = *4, e andiamo a sostituire:».

*2 + *1 + *5 = *2 + *4

«Ehi, *2 + *4 lo sappiamo calcolare, fa *6».

«Ed ecco quindi una nuova relazione: *3 + *5 = *6. Naturalmente ci saranno anche le altre relazioni gemelle: *3 + *6 = *5 e *5 + *6 = *3».

«Ho capito! Aggiorno la tabella, allora:».

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

«Come vedi, rimane ancora qualche casella vuota. Per riempirle dovremo studiare un altro gioco; prima di concludere, però, facciamo un riassunto dei giochi nulli trovati fino ad ora:».

(3,2,1)
(5,4,1)
(6,4,2)
(6,5,3)

«Per la prossima volta dobbiamo studiare (7,4,3)».

Nessun commento: