«Vai».
«Un insieme di nimeri G = {*a, *b, *c, …} (cioè un insieme di pile di Nim composte da a, b, c, … pedine) può essere considerato come un nimero *m (cioè un'unica pila Nim composta da m elementi), in cui m è il più piccolo numero naturale (incluso lo 0) che non è compreso tra i valori a, b, c, …».
«Uh, bella roba».
«È chiaro quello che afferma? Abbiamo fatto un sacco di esempi, no?».
«Sì, è il principio del Poker Nim generalizzato come piace tanto fare a voi Veri Matematici».
«Esattamente. I numeri più grandi di m sono inutili, perché quelle mosse sono annullabili quando e come si vuole. Ciò che conta è solo m».
«Ci sono».
«Questa viene detta Minimal Excluded Rule, per gli amici Mex».
«Ok».
«Si può anche definire una funzione Mex: per esempio possiamo scrivere che Mex({0,1,2,5,9}) = 3».
«Il più piccolo intero non negativo che non è compreso nell'insieme».
«Benissimo. E ora ti invito a riguardare, con occhi più consapevoli, la tabella che abbiamo scritto con tanta fatica:».
+---+---+---+---+---+---+---+---+ | 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 | +---+---+---+---+---+---+---+---+
«Mi sembra sempre quella, anche se manca una casella».
«Certo. Facciamo finta di non sapere ancora quale numero debba essere scritto in quella casella».
«Ah, va bene. Sarebbe il risultato di *5 + *1».
«Esatto. Stiamo quindi chiedendoci a cosa è equivalente un Nim composto da una pila da 5 pedine e un'altra pila da una sola pedina».
«Giusto».
«Ora, le possibile mosse che un giocatore può fare giocando a *5 + *1 sono queste:».
(4,1)
(3,1)
(2,1)
(1,1)
(1)
(5)
«Vero».
«Ma noi conosciamo i nimeri relativi a tutti quei giochi, perché possiamo leggerli dalla tabella».
«Anche questo è vero; aspetta che li scrivo tutti:».
(4,1) = *5
(3,1) = *2
(2,1) = *3
(1,1) = *0
(1) = *1
(5) = *5
«Ok, quindi?».
«Quindi ci basta applicare la regola Mex: G è uguale al nimero *m dove m è il più piccolo intero non negativo non compreso nell'elenco 0, 1, 2, 3, 5».
«E quindi è 4!».
«Ottimo. Con questo sistema si può compilare la tabella andando molto più in fretta, rispetto al tempo che abbiamo impiegato noi per farci tutti i calcoletti».
«In pratica mi basta guardare i numeri che si trovano a sinistra e sopra alla casella che voglio riempire: devo prendere il loro Mex».
«Proprio così: ecco una tabella più grande, questa volta calcolata (anzi, fatta calcolare dal computer) utilizzando questo nuovo metodo. Ho dovuto rimpicciolirla, altrimenti non ci sarebbe stata».
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 1| 0| 3| 2| 5| 4| 7| 6| 9| 8|11|10|13|12|15|14| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 2| 3| 0| 1| 6| 7| 4| 5|10|11| 8| 9|14|15|12|13| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 3| 2| 1| 0| 7| 6| 5| 4|11|10| 9| 8|15|14|13|12| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 4| 5| 6| 7| 0| 1| 2| 3|12|13|14|15| 8| 9|10|11| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 5| 4| 7| 6| 1| 0| 3| 2|13|12|15|14| 9| 8|11|10| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 6| 7| 4| 5| 2| 3| 0| 1|14|15|12|13|10|11| 8| 9| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 7| 6| 5| 4| 3| 2| 1| 0|15|14|13|12|11|10| 9| 8| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 8| 9|10|11|12|13|14|15| 0| 1| 2| 3| 4| 5| 6| 7| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 9| 8|11|10|13|12|15|14| 1| 0| 3| 2| 5| 4| 7| 6| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |10|11| 8| 9|14|15|12|13| 2| 3| 0| 1| 6| 7| 4| 5| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |11|10| 9| 8|15|14|13|12| 3| 2| 1| 0| 7| 6| 5| 4| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |12|13|14|15| 8| 9|10|11| 4| 5| 6| 7| 0| 1| 2| 3| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |13|12|15|14| 9| 8|11|10| 5| 4| 7| 6| 1| 0| 3| 2| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |14|15|12|13|10|11| 8| 9| 6| 7| 4| 5| 2| 3| 0| 1| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |15|14|13|12|11|10| 9| 8| 7| 6| 5| 4| 3| 2| 1| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
«Devi ancora spiegarmi la faccenda dei colori».
«Tra poco parliamo anche di quelli. Prima, però, il Teorema Fondamentale».
Nessun commento:
Posta un commento