lunedì 29 luglio 2013

Nim — 10. Mex

«Siamo pronti per enunciare la legge fondamentale».

«Vai».

«Un insieme di nimeri = {*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

«Molto bene. Quindi giocare in *5 + *1 significa giocare in G = {*0, *1, *2, *3, *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: