sabato 14 settembre 2013

Carnevale della Matematica #65, o 5512, o 1018, o 10014, o 10000012, o LXV, o 5×13, o 12+82, o 42+72, o O5, o anche 15+24+33+42+51.

Benvenuti al Carnevale della Matematica numero 65 (in base 10), dedicato al tema della navigazione.

Una notizia curiosa che riporta Wikipedia in inglese sul numero 65 è la seguente:

The traditional age for retirement in the United Kingdom, Germany, the United States, Canada, and several other countries.

Ok, era una battuta. Parlando invece di cose serie, 65 è il numero identificativo della prima portaerei statunitense nucleare, dismessa il 1 dicembre 2012; il suo nome è USS Enterprise. La prossima nave che porterà il glorioso nome sarà la CVN-80, pronta probabilmente intorno al 2025 — ci riaggiorniamo al Carnevale della Matematica #80, perché, come dice il Capitano, Let's make sure history never forgets the name Enterprise.



Veniamo ai contributi di questo mese, elencati in rigoroso ordine di arrivo, senza tenere conto dell'attinenza al tema del Carnevale (che, si sa, è solo un pretesto per poter scrivere cose strane nell'introduzione).

Martino, dal suo blog Termueske, parla del Google Pagerank: come fa Google a indovinare quasi sempre dove volete andare quando navigate su internet?



Spartaco Mencaroni, da Il coniglio mannaro, ci propone un racconto dal titolo Prima dell'autunno che parla di navigazione e, più o meno metaforicamente, di come la scienza può essere una via per superare i limiti che si crederebbero assoluti.



Marco Fulvio Barozzi, su Popinga, ha scritto tre contributi:
  • La successione di Vauban (altro che porcheria!). Il marchese di Vauban, generale, stratega, ingegnere militare, è stato una delle figure più importanti del lungo regno del Re Sole. Si occupò di calcoli per motivi di servizio, pur non essendo un matematico di professione. In tarda età cominciò a scrivere una serie di saggi contenenti memorie e congetture, tra cui la curiosa “Porcheria, o calcolo stimato per conoscere fino a dove può giungere la produzione di una scrofa in un periodo di dieci anni”, nella quale propose l’allevamento generalizzato del maiale, concludendo che in sole dodici generazioni «vi sarebbero così tanti [maiali] da nutrire l’Europa». I calcoli del marchese danno origine a una successione numerica che oggi fa parte del repertorio OEIS.
  • Nunes, tra ortodromie e lossodromie. Il problema della rotta più breve tra due punti sulla sfera terrestre cominciò a porsi in termini stringenti quando le navi incominciarono ad attraversare gli oceani, nei decenni successivi al viaggio di Colombo. Della questione si occupò il matematico portoghese Pedro Nunes, il quale pubblicò nel 1537 due trattati sui problemi di navigazione, in cui sosteneva che gli archi di circoli massimi (le ortodromie), che costituiscono i percorsi più brevi tra due punti, non sono, tranne che nel caso dell’'equatore e dei meridiani, rotte costanti: se si vuole seguire un’ortodromia è necessario cambiare continuamente rotta (cioè l’angolo con il meridiano). Il cammino seguito con angolo costante rispetto ai meridiani è invece costituito da una curva che egli descrive per primo, la lossodromia.
  • Matematica applicata e filosofia. Un originale contributo alla secolare discussione sulla natura della matematica è fornito da un articolo di Paul Wilson, un matematico applicato neozelandese, il quale si chiede “Che cosa ci dice l’applicabilità della matematica riguardo ai suoi fondamenti?” Nel porre questa domanda egli dà per acquisito che non esiste alcun serio disaccordo sul fatto che la matematica sia applicabile. Nessuna delle spiegazioni fornite finora sembra soddisfacente, perciò Wilson propone la costruzione di un nuovo paradigma basato sull’applicabilità, che potrebbe portare a una migliore comprensione della natura della matematica e dell’universo fisico.



Paolo Alessandrini pubblica, su Mr. Palomar, un post dal titolo Parole informatiche: navigare (che non è uguale a surfare, eh).



Annarita Ruberto, da Matem@ticaMente, ci propone



Leonardo Petrillo pubblica, nel blog Al Tamburo Riparato, un post sulle spirali logaritmiche e la lossodromia, curva utilizzata come riferimento nella navigazione terrestre.



Jean M.M. ha scritto tre post sul blog Con le mele | e con le pere:
  • La cosa più meravigliosa del mondo, che è un approssimatore universale di funzioni. Nientemeno. Ed una delle sue capacità più sorprendenti è la memoria. E così, scivolando sulla curva dell'oblio, si arriva ad un problemino di matematica discreta.
  • Ferrara 2013 – Divertissement 18-20. Tre problemini di geometria che prendono spunto dai particolari di fotografie scattate durante una gita a Ferrara. Per arrivarci si può saltare a piè pari un lunghetto (s)prologo che parla di meta-vanitas.
  • Che convoluzione, un tetraedro! Una semplice immagine rappresenta graficamente una formula alternativa per il calcolo dei numeri tetraedrici. Nel testo, una spiegazione della stessa insieme a una comparazione con la formula standard che ci porta, a sorpresa, ad imbatterci in altri numeri figurati, quelli piramidali.



Giungiamo ora ai Rudi Mathematici, che sul loro blog hanno pubblicato tanto:



Ora passiamo a Roberto Natalini, che su MaddMaths! ha scritto:
  • A che serve la matematica? La domanda dalle cento risposte. Se si è professore di matematica, matematico, studente di matematica o semplicemente genitore di uno studente, inevitabilmente ci si dovrà confrontare con LA grande domanda: a che cosa serve la matematica? Che si presenti sotto la forma di “A che cosa serve la trigonometria / il calcolo degli integrali / sapere che apiùbialquadratougualeadaduepiùdueabipiùbidue?” o nella variante affermativa “Ad ogni modo, la matematica non serve a niente”, il senso è sempre lo stesso. A che diavolo può servire la matematica? Traduzione, con pregevoli licenze, dell’articolo A quoi ça sert, les maths? - a cura di Kees Popinga.
  • Vita da Matematico: Silvia Poles. Silvia Poles si è laureata in matematica all'Università di Padova nel 1996. Dal 2000 lavora alla EnginSoft alla identificazione dei “problemi industriali e delle possibili soluzioni matematiche in termini di metodi, impegno e tempi”. Da quest'anno fa parte del Consiglio Direttivo della SIMAI.
  • Alfabeto matematico: G come Gradiente, di Corrado Mascia. Carlo ne è sicuro: ogni fenomeno in natura avviene a causa della presenza di un gradiente. Un gradiente topografico genera un fiume ed un gradiente di energia elastica, accumulata poco a poco all'interno della crosta terrestre, è responsabile di un terremoto. Carlo ne è convinto ed io, a modo mio, gli vado dietro. Entro al supermercato, reparto frutta e verdura, e mi congelo: tutta colpa di un gradiente di temperatura. Ne esco, e mi pare di morire dal caldo. Nuova imprecazione contro il gradiente, unico responsabile di questa sgradevole variazione termica.
  • Facebook e la teoria dei grafi. Presentiamo un nuovo progetto realizzato dagli alunni del triennio corso programmatori P/A e P/C dell'Istituto Tecnico Economico G. Calò di Francavilla Fontana (Br).
  • Radio3 Scienza: Il matematico e i manga. Abiti da dandy, una grande spilla a forma di ragno e una passione sfrenata per i fumetti giapponesi. Oltre a una medaglia Fields, il premio Nobel dei matematici, vinta nel 2010. A Radio3 Scienza Cédric Villani, direttore dell’Institut Henri Poincaré di Parigi e autore di Il teorema vivente (Rizzoli, 2013), ha raccontato le sue passioni e il suo lavoro matematico. Roberto Natalini e Fabio Pagan ne parlano nella puntata del 16 agosto 2013.
  • La gioia dei Numeri di Steven Strogatz. Roberto Natalini recensisce il nuovo libro di Steven Strogatz, una guida per tutti al piacere della matematica.
  • L'equazione del Millennio e la matematica come divertimento. L'Equation du Millénaire (L'equazione del millennio), una graphic novel prodotta dalla Fondation Science Mathématiques de Paris e recensita da Roberto Natalini.




Chris Sorrentino ha parlato, su Natura Mat3matica, della geometria del taxi (o di Manhattan, o di Torino, vedete voi). Come cambia la geometria se cambia il concetto di distanza?



.mau. dice che ha scritto poco, vediamo. Sul Post ha pubblicato:
Sulle Notiziole ha recensito due libri:
E ha pubblicato quattro giochini:

Bene, il Carnevale finisce qui. Il prossimo sarà ospitato da .mau. stesso sul Post e avrà come tema Parole e Numeri. Cominciate a pensarci.

mercoledì 7 agosto 2013

Nim — 14. La strategia vincente

«Alcuni libri, tra cui anche quello di Martin Gardner, suggeriscono di fare i conti con i nimeri in modo diverso rispetto a quello che abbiamo usato noi».

«E perché?».

«Mah, non saprei dirlo esattamente. Forse perché danno il metodo bello e pronto, senza spiegare niente, o forse perché in origine lo studio del Nim è stato fatto proprio in questo modo».

«Uh, un articolo del 1901».

«Sì, la teoria di Sprague-Grundy è venuta dopo».

«Ah, ecco. E come faceva l'autore…».

«Charles L. Bouton».

«Come faceva Bouton a vincere al Nim?».

«La regola base per le operazioni era questa: scrivi i numeri in binario e fai la somma senza riporto».

«Cosacosa?».

«Ti faccio vedere con i calcoli che abbiamo fatto l'altra volta. Abbiamo visto, per esempio, che *5 + *3 = *6. Bouton diceva di trasformare 5 e 3 in binario…».

«Cioè 510 = 1012 e 310 = 112».

«Sì. Poi metti in colonna e fai la somma senza tener conto del riporto. In pratica usi queste regole: 0 + 0 = 0, 1 + 0 = 1 e 1 + 1 = 0».

«Vediamo, ecco qua:».

1 0 1
  1 1
-----
1 1 0

«Molto bene. Quanto fa 1102?».

«Fa 4 + 2 = 6, giusto!».

«Prova anche con *11 + *22 + *33».

«Pronti:».

11 =     1 0 1 1
22 =   1 0 1 1 0
33 = 1 0 0 0 0 1
----------------
     1 1 1 1 0 0

«E 1111002 = 6010».

«Giusto anche questo. Come mai funziona?».

«Bé, sono le regole che abbiamo scoperto l'altra volta: due numeri uguali si cancellano quando vengono sommati, no?».

«Sì».

«E questo significa che quando sommi trascuri il riporto: 1 + 1 = 0 è una cancellazione, in pratica».

«Ah, già. E l'altra regola diceva che le potenze di 2 si sommano normalmente, come se usassimo la somma usuale».

«E infatti quando passiamo da forma binaria a forma decimale sommiamo potenze di 2, tutto qua».

«Bella roba. Ma questo cosa ha a che fare con la strategia vincente?».

«Ci arriviamo subito: ricorderai la nostra partita a Nim (3,2,1)».

«Certo, ho cominciato io, ma dato che *3 + *2 + *1 = 0 hai vinto tu».

«Ottimo riassunto: se tu giochi a un gioco nullo, hai perso. Io, per vincere, devo fare in modo che tu abbia sempre a che fare con un gioco nullo».

«E come fai?».

«Ti faccio vedere con un esempio: inventati un Nim con quante pile vuoi».

«Boh, per esempio (3,14,15,9)».

«Bene, per prima cosa scomponiamo in potenze di 2 tutti i numeri:».

3 = 2+1
14 = 8+4+2
15 = 8+4+2+1
9 = 8+1

«Va bene, poi?».

«Ora faccio i conti, quanto vale la somma-nim di quei quattro numeri?».

«Devo fare la somma in colonna, dopo aver trasformato in binario?».

«Non c'è bisogno: con la scomposizione in somme di potenze di 2 puoi fare a mente, guarda prima cosa si cancella».

«Se non sbaglio, cancellando le cifre a 2 a 2 uguali, mi rimane 8+2+1».

«Che fa 11. Siccome 11 è diverso da 0, comincio io».

«Fai pure, immagino che mi passerai un gioco nullo».

«Naturalmente. Il problema è: come faccio a farlo diventare nullo?».

«Come fai?».

«Visto che dopo le semplificazioni avanzano i numeri 8, 2 e 1, li cancello: sottraggo 11 dalla terza pila».

3 = 2+1
14 = 8+4+2
4 = 4
9 = 8+1

«Ah, adesso il gioco fa zero. Ora tocca a me?».

«Sì. Qualunque mossa tu farai, il gioco non potrà valere ancora zero».

«Perché?».

«Perché puoi togliere pedine solo da una pila, quindi sbilancerai certamente le coppie che prima si cancellavano».

«Ah, già. Bé, allora cancello tutta la pila da 14».

3 = 2+1
4 = 4
9 = 8+1

«Siamo a 8 + 4 + 2 = 14».

«Ora come fai a tornare a zero? Non puoi cancellare l'otto, il quattro e il due, sono in pile diverse!».

«Sottraggo due pedine dalla terza pila».

«Perché?».

«Pensa all'8 che vedi nella terza pila: se sottrai due pedine diventa 6, cioè 4 + 2, che è quello che mi serve per bilanciare tutto:».

3 = 2+1
4 = 4
7 = 4+2+1

«Ah, ecco! Ancora una volta è 0. Se ora togliessi 5 pedine dalla terza pila?».

3 = 2+1
4 = 4
2 = 2

«Dimmi tu cosa dovrei fare».

«Hai 2+1 sopra, hai 2 sotto, ti basta trasformare il 4 in 1».

3 = 2+1
1 = 1
2 = 2

«Già. E siamo arrivati al nostro vecchio conoscente: (3,2,1). Direi che possiamo concludere la partita, no?».

«Eh, sì. Ma ci si riesce sempre a far diventare nullo un gioco non nullo?».

«Sì, pensa a come fai i calcoli: se il gioco non è nullo significa che nelle semplificazioni c'è qualche potenza di 2 sbilanciata. Se queste potenze sbilanciate si trovano su una pila sola, le cancelli tutte».

«E se si trovano su pile diverse?».

«Cerchi la più grande, e la diminuisci fino a farla diventare uguale alla somma delle altre».

«Uh, possiamo vedere un altro esempio?».

«Eccolo qua: (11,22,33)».

«Chi comincia?».

«Vai, per questa volta comincia tu. Devi vincere, visto che abbiamo già calcolato la somma-nim di questo gioco e sappiamo che vale 60».

«Allora, mi scrivo i numeri come somme di potenze di 2:».

11 = 8 + 2 + 1
22 = 16 + 4 + 2
33 = 32 + 1

«Bene, ho visto che hai messo anche i termini che si semplificano. Adesso?».

«Scelgo la potenza più alta, che è 32, e devo trasformarla in 16+8+4, che fa 28. Tolgo 4 pedine dalla terza pila:».

11 = 8 + 2 + 1
22 = 16 + 4 + 2
29 = 16 + 8 + 4  + 1

«Molto bene, ora tutto è bilanciato e tocca a me: siamo sicuri che io non possa passare a un'altra configurazione nulla?».

«Uh, ma cadrebbe tutta la teoria che abbiamo sviluppato!».

«Ottima risposta, ma riesci a darmene una più pratica? Perché non posso diminuire una qualche pila fino a bilanciare di nuovo tutto?».

«Mh, non saprei dirlo».

«Diciamo che scelgo la pila più grande, quella da 29. Se tolgo il 16, rimane un 16 sbilanciato».

«Ma non sei obbligato a togliere proprio 16, no?».

«No, ma se comunque tolgo almeno una pedina da quella pila, succede che almeno una delle potenze di 2 che la compongono deve diminuire».

«Già».

«E allora la sua gemella, che necessariamente si trova in un'altra pila, sarà sbilanciata».

«Ah, certo, non posso avere due potenze di 2 uguali nella stessa pila!».

«Potenza della notazione posizionale, se mi concedi la battuta».

«Battuta?».

«Ehm, ok, non faceva ridere. Comunque, andiamo avanti, tolgo 5 pedine dalla pila da 29:».

11 = 8 + 2 + 1
22 = 16 + 4 + 2
24 = 16 + 8

«Avanzano un 4 e un 1. Qui ho molte scelte, posso prendere uno dei due 16 e diminuirlo fino a farlo diventare 4+1».

«No, no, 16 è già bilanciato! Devi prendere la potenza più alta tra quelle non bilanciate».

«Ah, ecco. Allora devo trasformare il 4 della seconda fila in 1: sottraggo 3 dalla seconda pila:».

11 = 8 + 2 + 1
19 = 16 + 2 + 1
24 = 16 + 8

«Ormai hai capito, no? Ogni volta che io sbilancio, tu ribilanci.».

«Direi proprio di aver capito tutto».

«Perfetto, a questo punto allora direi che possiamo fermarci».

«Fine degli studi sul Nim?».

«Fine, ora si tratta di giocare».

lunedì 5 agosto 2013

Nim — 13. Variazioni sulla regola della somma

«Ora vediamo di capire come mai ci sono colori diversi nella tabella della somma di nimeri».

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 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».

venerdì 2 agosto 2013

Nim — 12. Il Cavaliere Distratto

«Ora studiamo un nuovo gioco, così capiamo la potenza della teoria di Sprague-Grundy. Il gioco si chiama Il Cavaliere Distratto».

«Bel nome».

«Abbiamo un cavaliere (cioè un cavallo degli scacchi) che si può muovere su una scacchiera, che possiamo immaginare infinita andando a destra e verso il basso».

«Ok, e perché è distratto?».

«Perché perde le cose. Al momento ha perso sei scatole, che abbiamo messo da parte. Scopo del gioco è quello di fare arrivare il cavaliere in una delle quattro caselle d'angolo in alto a sinistra e raccogliere tutte le scatole. Le caselle in questione sono queste:».

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

«Lo zero all'interno cosa significa?».

«Ho già messo il nimero corrispondente a quella posizione: lì il gioco relativo alle mosse del cavaliere è finito».

«Ma si possono ancora raccogliere scatole?».

«Sì, in pratica abbiamo due giochi: una pila di 6 scatole, e il cavaliere sulla scacchiera. Ogni giocatore può muovere in uno dei due giochi, o prende delle scatole o muove il cavaliere».

«Ok».

«E, naturalmente, del gioco riguardante la presa delle scatole sappiamo tutto, è un Nim composto da una pila di sei elementi, quindi vale *6».

«Bene».

«Il problema è capire quali nimeri associare alle posizioni del cavallo sulla scacchiera, ma con la teoria di Sprague-Grundy non abbiamo problemi a fare i calcoli. Rispetto agli scacchi, però, c'è una restrizione: il cavallo non può muovere dove vuole, ma solo nelle due caselle sopra di lui e nelle due alla sua sinistra. Questo per fare in modo che il gioco prima o poi termini».

«Insomma, se il cavallo si trova nella casella blu, può solo andare sulle caselle rosse, giusto?».

+---+---+---+---+---+
|   |   | 2 |   | 4 |
+---+---+---+---+---+
|   |   | 3 | 2 | 5 |
+---+---+---+---+---+
| 2 | 3 | X | 1 | 6 |
+---+---+---+---+---+
|   | 2 | 1 | 0 | 7 |
+---+---+---+---+---+
| 4 | 5 | 6 | 7 | 0 |
+---+---+---+---+---+

«Giusto. Ora proviamo a calcolare il nimero corrispondente alla casella rossa».

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

«E come facciamo?».

«Facciamo un elenco delle caselle in cui il cavallo può muoversi».

«Ce n'è una sola, quella arancione in seconda riga, prima colonna».

«Bene, quindi il cavallo nella casella rossa corrisponde a un gioco fatto così: G = {*0}».

«Uhm».

«Ricorda che un gioco è definito dalle sue mosse, se il cavallo si trova nella casella rossa c'è una sola mossa possibile, il cui valore è 0».

«Ah, già».

«Ora, applicando la regola del Mex, possiamo calcolare il valore della casella: quanto vale Mex({*0})?».

«È il minimo intero non negativo non compreso nell'elenco delle mosse del gioco, quindi direi 1».

«Più precisamente, *1. Ma nella tabella mettiamo solo 1. Per simmetria mettiamo 1 anche nella casella alla terza riga, prima colonna».

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

«Sì, giusto, i calcoli sono gli stessi. Ora calcoliamo il valore della nuova casella rossa?».

«Sì, vai».

«Vediamo: ci sono due caselle verso le quali il cavallo può muoversi: quella nell'angolo in alto a sinistra, di valore 0, e quella in terza riga, prima colonna, di valore 1».

«Vuoi dire *1».

«Ah, già. Quindi se il cavallo si trova nella casella rossa siamo di fronte a un gioco G = {*0, *1}. Quindi il Mex dovrebbe essere 2».

«Dici bene: mettiamo il valore nella tabella. Già che ci sono te la riempio un po' io, e ti faccio fare un altro calcolo. Cosa mettiamo ora nella casella rossa?».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 7 | 4 | 5 |
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 |   | 7 | 6 | 5 | 4 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 7 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 7 | 6 | 1 | 0 | 3 | 2 |
+---+---+---+---+---+---+---+---+
| 1 | 1 | 4 | 5 | 2 | 3 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 1 | 5 | 4 | 3 | 2 | 1 | 0 |
+---+---+---+---+---+---+---+---+


«Ah, ora sono possibili tutte e quattro le mosse del cavallo. Stiamo giocando a un gioco G = {*0, *2, *2, *0}; ho scritto i nimeri due volte perché anche se a due a due sono uguali, le caselle su cui posso muovere sono diverse».

«Va bene, non c'è problema. Ora il Mex: quanto vale?».

«Mex(G) =  *1, quindi in quella casella ci va un 1, vero?».

«Molto bene! Ecco la tabella completa:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 2 | 2 |...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 1 | 4 | 3 | 2 |...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 4 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 |...|...|...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 |...|...|...|...|...|...|
+---+---+---+---+---+---+---+---+

«Non è proprio completa, eh».

«Eh, no, per sapere cosa mettere nelle caselle coi puntini dovrei prolungare un po' le prime righe e le prime colonne».

«E perché hai colorato quelle quattro caselle con un colore diverso?».

«Perché, anche se ancora non si vede tanto, la tabella ricomincia uguale a sé stessa a partire da quelle quattro caselle».

«Ah, Ma ora giochiamo anche?».

«Sì, ti lascio scegliere dove posizionare il cavallo, e io farò la prima mossa.».

«Vabbé, tanto so già che perderò».

«Ehm».

«Diciamo che metto il cavallo qua:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 2 | 2 |...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 1 | 4 | 3 | 2 |...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 4 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 |...|...|...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 |...|...|...|...|...|...|
+---+---+---+---+---+---+---+---+

«Allora io tolgo 3 elementi dalla pila delle scatole: ora ne rimangono 3».

«Uhm, allora tolgo un elemento anche io dalla pila delle scatole».

«Ok, allora rimangono due elementi, e io muovo qua:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 2 | 2 |...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 1 | 4 | 3 | 2 |...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 4 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 |...|...|...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 |...|...|...|...|...|...|
+---+---+---+---+---+---+---+---+

«Allora io muovo in questa casella:».

+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 2 | 3 | 2 | 2 |...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 1 | 4 | 3 | 2 |...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 3 | 4 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 0 | 0 |...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 |...|...|...|...|
+---+---+---+---+---+---+---+---+
| 1 | 1 |...|...|...|...|...|...|
+---+---+---+---+---+---+---+---+

«E io tolgo una scatola, ora ne rimane una».

«E io ho perso: se prendo la scatola, tu muovi il cavallo in una delle quattro caselle di valore zero, se invece faccio io quella mossa, tu prendi la scatola. Come hai fatto?».

«Ho usato la teoria di Sprague-Grundy. Quando tu hai scelto la posizione del cavallo, in pratica mi hai lasciato un gioco G1 = {*0, *1, *2, *2}».

«Corrispondente alle quattro possibili mosse che poteva fare il cavallo, giusto».

«E poi mi hai lasciato anche le sei scatole, cioè un gioco G2 = *6».

«Una pila Nim da 6 elementi, giusto».

«Per la teoria di Sprague-Grundy, anche G1 è equivalente a una pila Nim, no?».

«Vero anche questo, si usa il Mex: G1 = *3, il valore scritto nella casella».

«Perfetto. In pratica stavamo giocando a un Nim con due pile: (3,6)».

«Ah! Sappiamo che vince il primo giocatore».

«Certo, per questo ho cominciato. E la strategia è stata quella di passarti sempre due pile uguali. Se riguardi le mosse, ho fatto in modo che G1 e G2 avessero sempre lo stesso valore».

«E siccome un Nim con due pile uguali è nullo, ho perso…».

«Infatti».

«Bella roba. Ma qual è la strategia vincente per un Nim un po' più complicato?».

«Bella domanda».