+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 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| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
«Oh, finalmente».
«Ho aspettato tanto perché così nel frattempo siamo diventati pratici nel calcolare somme di nimeri e Mex».
«Bene, ti ascolto».
«Allora, partiamo dal semplice: se avessimo a disposizione solo il nimero *0, cioè il gioco nullo, la tabella sarebbe molto facile da fare».
«Già, avrebbe una casellina sola, quella rossa».
«Infatti. Ora complichiamo un pochino, aggiungiamo *1. Ora abbiamo due nimeri, *0 e *1, che possiamo combinare in tre modi diversi: *0 + *0, *0 + *1 e *1 + *1. Di questa somma sappiamo già tutto, la regola del Mex ci dice che non usciamo dall'insieme {*0, *1}, e tutte le possibili somme si esauriscono qui».
«Abbiamo fatto la cornice blu».
«Sì. Ora le cose si complicano: se aggiungiamo un nuovo nimero, e cioè *2, ci accorgiamo che possono capitare casi in cui si deve calcolare il Mex di {*0, *1, *2}».
«Giusto, per esempio se dobbiamo calcolare *1 + *2».
«Ottimo. Vale la pena perdere un po' di tempo sui calcoli, per capire cosa c'è sotto: quando calcoliamo il risultato di *1 + *2, stiamo analizzando tutto quello che potrebbe succedere quando un giocatore muove o nel primo gioco o nel secondo».
«Vero».
«Quindi, dato che *1 = {*0} e *2 = {*0, *1}, le possibili mosse sono queste:».
*0 + *2 (muovo nel primo gioco, togliendo l'unica pedina)
*1 + *1 (muovo nel secondo gioco, togliendo una pedina)
*1 + *0 (muovo nel secondo gioco, togliendo due pedine)
«Sì, i possibili risultati sono stati calcolati in precedenza, sono *2, *0 e *1».
«E quindi il Mex vale *3».
«E infatti abbiamo detto che se aggiungiamo *2, abbiamo bisogno anche di *3 per completare la tabella, che sarebbe la nuova cornice colorata di giallo».
«Sì. Ora la domanda: perché dobbiamo aggiungere un nuovo nimero?».
«Ma l'abbiamo appena detto!».
«Aspetta: perché proprio uno solo, e non due o tre o chissà quanti?».
«Ah… uhm».
«Ragioniamo: la regola del Mex è tale per cui ogni riga e ogni colonna sono composte tutte da nimeri diversi».
«Eh, sì, questo lo capisco: il Mex è il più piccolo intero non negativo non presente a sinistra e sopra la casella che vogliamo riempire, quindi non ne posso mai scrivere due uguali».
«Benissimo. Ora osserva la griglia che contiene solo *0 e *1».
«Quella blu».
«Quella: è composta da due righe e due colonne; se voglio allargarla succederà prima o poi che i due nimeri che la compongono, *0 e *1, si devono trovare al di fuori della zona blu».
«Senza dubbio: *0 e *1 sono i due nimeri più piccoli, nella regola del Mex saltano fuori in fretta».
«E allora quando mi capiterà di avere *0 e *1 fuori dalla zona blu, nella zona blu dovranno esserci altri due nuovi nimeri».
«Ah! Ecco perché devo aumentare di due caselle! E dopo avrò a disposizione quattro nimeri, e se vorrò allargare la zona gialla ce ne vorranno altri quattro, poi otto, sedici, trentadue…».
«Perfetto, hai capito. Non ti spaventerà dunque questa regola:».
1. Se a e b sono minori di 2k, allora lo sarà anche *a + *b.
«Non mi spaventa, è quello che abbiamo detto finora. La regola dei colori, insomma».
«Benissimo. Un'ultima considerazione: osserva la prima riga (o la prima colonna) di ogni nuova cornice».
«Cioè quando cambiano colore?».
«Sì, esatto».
«Boh, la prima riga blu è *1, *0».
«Poi?».
«La prima riga gialla è *2, *3, *0, *1».
«Poi la prima riga viola è *4, *5 , *6, *7, *0, *1, *2, *3».
«E la prima riga fucsia è *8, *9, *10, *11, *12, *13, *14, *15, *0, *1, *2, *3, *4, *5, *6, *7, quindi?».
«Quindi succedono varie cose. Prima di tutto, ogni riga di un colore nuovo parte da una potenza di 2».
«Ok, un altro modo di dire quello che abbiamo visto prima».
«Già. Poi, grazie alla regola del Mex, le righe di un nuovo colore proseguono in ordine crescente fino a metà lunghezza».
«Vero anche questo, prima ci sono i nuovi nimeri, poi quelli vecchi».
«Quindi, riassumendo, se prendiamo come esempio la prima riga viola, quella che comincia con *4, *5, *6, *7, e ci ricordiamo che quei nimeri sono il risultato di una somma, possiamo dire questo:».
*4 + *0 = *4
*4 + *1 = *5
*4 + *2 = *6
*4 + *3 = *7
«E poi ci fermiamo, perché *4 + *4 non fa *8 ma *0».
«Bene. Generalizzando, cosa possiamo dire?».
«Uhm, forse possiamo dire che se prendiamo una potenza di 2 e sommiamo dei nimeri, è come se facessimo una somma normale?».
«Quasi. La regola vale solo fino a metà riga, nel nostro esempio fino a *4 + *4 escluso».
«Ok, allora ho capito, provo a formulare la regola: se sommo una potenza di 2 con un nimero minore di essa, è come se stessi facendo una somma tra normali numeri».
«Bene, in formule è così:».
2. Se a < 2k, allora *a + *2k = *(a + 2k).
«Capito».
«Da cui deduciamo subito queste regole pratiche:».
3. La somma-nim di due diverse potenze di 2 è uguale alla loro somma ordinaria, e la somma-nim di due numeri uguali è 0.
«Perché dici somma-nim?».
«Per non mettere tutti gli asterischi, e per non dover specificare ogni volta che le potenze di 2 che consideriamo sono dei nimeri».
«Ah, ok. E come mai le hai chiamate regole pratiche?».
«Perché ci permettono di fare molto in fretta i calcoli. Ti faccio qualche esempio: vogliamo calcolare il risultato di questa operazione:».
5 ⊕ 3
«Cos'è quello strano simbolo?».
«Significa che stiamo addizionando nimeri, è come se avessi scritto *5 + *3. Dato che dobbiamo fare un po' di calcoli, mi pare che sia più comodo. Tieni presente che quando scrivo ⊕ intendo l'addizione tra nimeri, mentre quando scrivo + intendo la normale addizione tra numeri».
«Ah, va bene. Allora, dobbiamo calcolare 5 ⊕ 3».
«Sì, utilizzando solo la regola pratica, cioè quella che abbiamo indicato col numero 3».
«Ma è una regola che parla di potenze di 2, o di numeri uguali».
«Vorrà dire che dobbiamo trasformare quei numeri in potenze di 2».
«Come se stessimo facendo un cambiamento di base?».
«Esattamente, ottimo! 5 in base 2 è uguale a 101, cioè 4 + 1».
«Mentre 3 è uguale a 11, cioè 2 + 1».
«E quindi il nostro calcolo diventa questo:».
5 ⊕ 3 = (4 + 1) ⊕ (2 + 1)
«E adesso come facciamo? Abbiamo due diversi simboli di somma».
«La somma-nim di due diverse potenze di 2 è uguale alla loro somma ordinaria, quindi scrivere 4 + 1 è come scrivere 4 ⊕ 1».
«Ah, allora possiamo togliere le parentesi e usare solo il simbolo della somma-nim:».
5 ⊕ 3 = 4 ⊕ 1 ⊕ 2 ⊕ 1
«Ora ricordati che la somma-nim di due numeri uguali è uguale a 0».
«E quindi posso scrivere questo:».
5 ⊕ 3 = 4 ⊕ 1 ⊕ 2 ⊕ 1 = 4 ⊕ 2
«Ora hai due potenze di 2 da sommare, quindi…».
Quindi posso calcolare il risultato: 4 ⊕ 2 = 4 + 2 = 6
«Benissimo. Se vogliamo utilizzare la notazione a cui siamo abituati, abbiamo calcolato che *5 + *3 = *6».
«Concorda con la tabella».
«Col vantaggio che non abbiamo avuto bisogno di consultarla per poter calcolare il Mex».
«Bello, si dovrebbe riuscire a fare i calcoli più in fretta».
«È così. Prova per esempio a calcolare questo:».
11 ⊕ 22 ⊕ 33
«Uh, questi sono numeri fuori dalla tabella. Allora, prima scompongo in potenze di 2 i vari numeri».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
33 = 32 + 1
«E fin qua ci siamo».
«Poi addiziono tutto».
«Sì, ma ti conviene già scartare le coppie di numeri uguali».
«Ah, giusto: si annullano. Allora mi rimane questo:».
8 ⊕ 16 ⊕ 4 ⊕ 32 = 60
«Molto bene. Ora che hai capito, puoi anche abbreviare i calcoli e, se vuoi, usare l'altra notazione. Per esempio:».
*9 + *25 + *49 = (*8 + *1) + (*16 + *8 + *1) + (*32 + *16 + *1) = *32 + *1 = *33
«Ah, hai colorato le potenze che si semplificano».
«Sì, come vedi è molto comodo. Ora, una domanda: se noi facessimo la somma normale, otterremmo un numero certamente più grande o più piccolo di quello che otterremmo facendo la somma-nim?».
«Mh, a volte viene uguale, mentre altre volte più grande, dato che nella somma-nim ci sono delle possibili semplificazioni».
«Molto bene, quindi potremmo dire che a ⊕ b ≤ a + b».
«Direi proprio di sì».
«Un'ultima domanda: quando le due somme sono diverse, per cosa differiscono?».
«Per le potenze di 2 che ho semplificato».
«Bene, e posso dire che ogni volta che faccio una semplificazione tolgo due copie dello stesso numero?».
«Certo».
«E quindi tolgo un numero pari ogni volta».
«Ho capito: le due somme differiscono per un numero pari (o per 0, quando non ci sono semplificazioni, ma tanto anche 0 è pari)».
«Perfetto. Ecco l'ultima regola di oggi:».
4. La somma-nim è minore o uguale della somma usuale, ed esse differiscono per un numero pari.
«E quindi?».
«E quindi ora possiamo parlare di una strategia vincente per il Nim».
5 commenti:
la prima riga gialla è *2, *3, *0, *1, non *2, *3, *1, *0 (ma tanto chi legge ad agosto?)
ah, se non hai corretto nel precedente c'è un "numeno"
Grazie, correggo.
(non trovo "numeno", però)
perché era "inteno" al posto di "intero". Ora ci si può chiedere quali siano i miei percorsi mentali che mi fanno ricordare "c'era una n al posto di una r" ma non la parola in questione - anzi peggio, ricordare un sinonimo.
Ma forse è meglio di no :-)
Benissimo :-)
Corretto pure quello, rigrazie.
Posta un commento