venerdì 19 luglio 2013

Nim — 6. Lente progressioni

«Allora, hai scoperto qualcosa sul Nim (5,4,1)?».

«Mah, mi sono fatto uno schemino, e ho visto che in alcuni casi si riesce a ricondurre il gioco a (3,2,1), che abbiamo già studiato».

«Bene, bene, fammi vedere questo schemino».

«Eccolo».



«Molto bene! Questo significa che se il primo giocatore fa una delle mosse che hai scritto, il secondo giocatore riesce a riportare la situazione a (3,2,1), che è un gioco nullo e quindi gli assicura la vittoria».

«Sì, però non ho analizzato tutti i casi, mi sembrano tanti».

«Vediamo… Per adesso hai stabilito che se uno dei due giocatori riduce una delle due pile maggiori a 3 oppure a 2, allora l'altro giocatore riduce l'altra delle due pile maggiori a 2 oppure a 3, ottenendo (3,2,1). Ora proviamo a procedere sistematicamente per cercare di capire qualcosa degli altri casi. Che succede, per esempio, se il primo giocatore ottiene (5,1,1)?».

«Uhm, se applico la proprietà che dice che due pile uguali sono cancellabili, quel gioco dovrebbe essere uguale a (5)».

«Esatto, e quindi vince il secondo giocatore».

«Eh, sì. Questo succede anche se il primo giocatore passa da (5,4,1) a (4,1,1)».

«Certo, stessa cosa. Quindi non solo al primo giocatore non conviene ridurre una delle due pile maggiori a 3 oppure a 2, ma non gli conviene nemmeno ridurla a 1».

«Eh, no».

«Cosa gli rimane da fare?».

«Potrebbe ridurre una delle pile a 0».

«In questo caso potrebbe ottenere (5,1), oppure (4,1), oppure (5,4). Cosa sappiamo dei Nim con due pile diverse?».

«Che sono giochi fuzzy, per la regola 3».

«E quindi anche in questo caso vince il secondo giocatore».

«Eh, sì».

«Direi che abbiamo analizzato tutto, no?».

«Già: qualunque mossa faccia il primo giocatore, il secondo vince».

«Quindi il gioco (5,4,1) è nullo. Come scriveresti l'operazione con i nimeri?».

«Scriverei *5 + *4 + *1 = 0».

«Bene. Esistono poi altri tre modi equivalenti, no?».

«Ah, sì: *5 + *4 = *1, oppure *5 + *1 = *4, oppure ancora *4 + *1 = *5».

«Benissimo: possiamo allargare la tabella, allora. Eccola qua».

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

«E nelle caselle vuote cosa ci mettiamo?».

«Lo scopriamo tra un po'».

Nessun commento: