lunedì 15 luglio 2013

Nim — 4. Nimeri

«Abbiamo detto che il Nim (3,2,1) è un gioco uguale a zero».

«E cioè vince il secondo giocatore, mi ricordo».

«Bene, adesso convertiamo tutto in termini numerici».

«In che senso?».

«Vedrai. Partiamo dall'inizio, il Nim più facile di tutti, questo: (0). Comincia tu».

«Ma dai, cosa vuol dire? Non ci sono pedine, cosa tolgo?».

«Niente, perciò hai perso».

«Ah, certo, grazie».

«In un gioco nullo vince il secondo, no? Il gioco nullo più semplice è (0), che è nullo in tutti i sensi. Dunque (0) = 0».

«Argh».

«Ora analizziamo questo: (1). Questa volta comincio io, tolgo la pedina, e ti passo (0)».

«Ma basta!».

«Nel gioco (1) vince il primo giocatore, e quindi è un gioco fuzzy. Abbiamo detto che si scrive (1)║0».

«Uhm, avrei detto 1>0».

«Effettivamente 1 è maggiore di 0, ma qui non stiamo parlando del numero 1, ma del Nim con una pedina, cioè di (1). Ti ricorderai che il Nim, essendo un gioco imparziale, non potrà mai essere né positivo né negativo. Se non è zero, è fuzzy».

«Ma i numeri sono tutti o positivi, o negativi, o nulli, questa faccenda del fuzzy non mi torna».

«Infatti il gioco (1) non lo rappresenteremo con un numero, ma con un simbolo che si comporta come un numero che però deve soddisfare a determinate regole. Vedilo come generalizzazione dei numeri».

«Andiamo bene… E che simbolo si usa?».

«Questo: (1) = *».

«Un asterisco?».

«Sì, si chiama star, e viene anche indicato come *1».

«Vabbé».

«Ora, ricordi la nostra regola numero 1?».

«Sì, quella che dice che una pila è fuzzy».

«Esatto. Daremo a una pila composta da n elementi il valore *n. Per esempio, (2) = *2, (3) = *3, e così via».

«Ah. E perché?».

«Perché così siamo in grado di fare dei conti. Ad esempio, l'ultima volta abbiamo visto che (3,2,1) = 0».

«Sì, mi ricordo».

«E allora scriviamo questa operazione: *3 + *2 + *1 = 0».

«E ha senso?».

«Non secondo le usuali regole dell'aritmetica, perché quei simboli non sono numeri. Ma esistono altre regole, ben precise e definite, con le quali si può fare un'aritmetica dei nimeri».

«Dei nimeri?».

«Sì, questi nuovi numeri (che non sono numeri) vengono detti nimeri, proprio per il fatto che derivano dal Nim».

«…».

«Ehm. Ora facciamo un passo avanti: pensiamo al Nim (3,2,1) come se fosse la composizione di due giochi Nim, e cioè (3,2) e (1)».

«In che senso?».

«Nel senso che tu puoi decidere, ogni volta che sta a te, se giocare sul primo Nim oppure sul secondo».

«Ma non cambia niente, no? Tanto io tolgo pedine da una singola pila, cosa mi importa sapere se sto giocando a (3,2,1) oppure alla composizione di (3,2) con (1)?».

«Nulla, è proprio questo il punto: ogni Nim complesso può essere pensato come la somma di giochi Nim più semplici».

«Ah, ecco. Ma allora la somma *3 + *2 + *1 potrebbe essere interpretata come la somma di tre semplici Nim, cioè (3), (2) e (1), no?».

«Proprio così. E il fatto che (3,2,1) = 0 significa che quella composizione, come anche la composizione di (3,2) con  (1), è uguale a 0».

«Va bene».

«Per evitare di dire sempre che stiamo componendo due Nim, utilizziamo una notazione più comoda e certamente efficace: (3,2) + (1) = 0».

«Uh, una somma di giochi?».

«Proprio così: una somma di giochi è un gioco nel quale tu puoi scegliere dove fare la mossa: nel primo o nel secondo dei due giochi componenti. Ora pensa alla regola 2: quando succede che la somma di due pile è uguale a zero?».

«Quando le due pile sono uguali».

«Perfetto. Allora noi diciamo che i due giochi (3,2) e (1) sono uguali, nel senso che il secondo giocatore ha una strategia vincente».

«Aspetta, mi sono perso».

«Se due giochi sono uguali la loro somma è zero, se la somma è zero il gioco è vinto dal secondo giocatore».

«Ho capito».

«Ok, quindi (3,2) + (1) = 0. Nel linguaggio dei nimeri, possiamo dire che *3 + *2 = *1».

«Abbiamo applicato la regola 2, vero?».

«Sì, è come se avessimo a che fare con due pile uguali. Naturalmente la suddivisione di (3,2,1) in (3,2) + (1) è arbitraria, avremmo potuto dire che (3,2,1) è la somma di (3,1) e (2)».

«E quindi anche *3 + *1 = *2?».

«Esattamente. O anche *2 + *1 = *3».

«Direi di aver capito».

«Perfetto. La prossima volta facciamo una tabella e vediamo qualche gioco più complicato».

Nessun commento: