mercoledì 24 luglio 2013

Nim — 8. Tabella completa

«Ormai abbiamo capito il meccanismo, quindi direi di andare un po' più spediti del solito nello studio del Nim (7,4,3)».

«Va bene, spero di riuscire a seguire».

«Omettiamo l'analisi delle posizioni ovvie, cioè quelle in cui viene cancellata una pila, o si creano due pile uguali. Abbiamo già detto che sono mosse da non fare, se il primo giocatore vuole avere speranza di vincere».

«Giusto».

«Non rimangono allora molte mosse. Se il primo giocatore porta una delle due pile più grandi a 2 oppure a 1, il secondo può portare a 1 oppure a 2, rispettivamente, l'altra pila più grande».

«Vediamo… Le mosse che potrebbe fare il primo giocatore sono queste, se non sbaglio:».

(2,4,3)
(1,4,3)
(7,2,3)
(7,1,3)

«Giusto. In ognuno di questi quattro casi il secondo può ricondurre il gioco a (3,2,1)».

«Che è una delle posizioni buone, quindi in questo caso vince il secondo».

«Sì. Il primo giocatore potrebbe però muovere diversamente. Per esempio, potrebbe muovere in (6,4,3) oppure (7,4,2)».

«Mh, allora il secondo non potrebbe giocare (3,2,1), però può utilizzare un'altra delle posizioni buone. Può muovere in (6,4,2), e vincere».

«Bene. Rimangono gli ultimi due casi: (5,4,3) e (7,4,1)».

«In questo caso il secondo giocatore se la cava con (5,4,1)».

«Perfetto, quindi anche questo Nim è a favore del secondo, cioè è nullo. Ecco un riassuntino:».




«Quindi possiamo aggiungere qualcosa alla tabella della somma dei nimeri».

«Certo: ora sappiamo che *7 + *4 + *3 = 0, e quindi la somma di due qualunque di quei nimeri è uguale al terzo».

«Uhm, però mi sa che ancora non basta».

«Perché?».

«Non riesco a riempire tutte le caselle. Per esempio, non so quanto fa *2 + *5».

«Bé, calcolalo!».

«Ah, posso provarci. Vediamo un po', *2 + *5 = *3 + *1 + *5. Ho usato il fatto che *2 = *3 + *1».

«Bene. Sai anche quanto fa *1 + *5, no?».

«Fa *4, quindi ho trovato che *2 + *5 = *3 + *4, e quest'ultima somma fa *7. Bene, quindi *2 + *5 = *7».

«E tutte le relazioni gemelle, naturalmente. Ti manca solo un calcolo, poi la tabella è completa».

«Quale?».

«*1 + *6».

«Provo subito: *1 + *6 = *1 + *2 + *4 = *3 + *4 = *7. Facile!».

«Ottimo! Ora puoi riempire la tabella».

«Eccola:».

+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| 1 | 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 |
+---+---+---+---+---+---+---+---+


«Con un po' di fatica, ce l'abbiamo fatta».

«Mi chiedo se ci sia una regola».

«Naturalmente».

«Capirai».

Nessun commento: