Gramellini, la matematica e la memoria

Nella rubrica del Corriere della Sera intitolata "Il caffè", Massimo Gramellini ci dispensa ogni giorno una pillola di saggezza delle sue. Spesso le riflessioni gramelliniane sono argute e azzeccate, ma talvolta stonano un poco.
Nella tazzina di oggi, intitolata "Maturità alla memoria", il noto giornalista affronta il tema della verifica scritta di matematica prevista come seconda prova dell'esame di stato del liceo scientifico. La notizia da cui Gramellini prende le mosse è descritta in un altro articolo del Corriere: un gruppo di studenti lancia una petizione sul sito Change.org, per chiedere al Ministero dell'Istruzione l'abolizione del divieto di utilizzare formulari durante la prova di matematica, in analogia con quanto avviene durante i compiti di italiano, in cui è consentito l'uso di dizionari.

Ecco un passaggio della petizione:
"Ci sembra più che anacronistica l’assenza di un formulario scientifico nell’elenco degli strumenti utilizzabili. A nostro parere una prova di maturità dovrebbe valutare le capacità e le competenze che lo studente ha sviluppato nel corso dei suoi studi senza che la 'forza bruta' della memoria filtri l’effettiva validità di tali capacità, le quali dovrebbero risiedere nell’abilità di analisi, riconoscimento e di risoluzione di determinati problemi specifici, e non nella difficoltà di ricordare a memoria formule e procedure sistematiche non inerenti alle competenze, ma al puro immagazzinamento di pratici mezzi di risoluzione".
Il Ministero, nella persona del sottosegretario Vito De Filippo, ha respinto la richiesta (che nel frattempo aveva trovato un sostegno politico in un esponente del Movimento 5 Stelle), fornendo motivazioni a mio parere abbastanza ragionevoli e condivisibili.

Nel suo Caffè, Gramellini plaude alla decisione ministeriale, ribadendo l'importanza della memoria nella crescita dei nostri ragazzi e profetizzando che il governo "perderà in blocco il voto dei diciottenni, perché nel Paese dei balocchi e degli 'aiutini' chi promette scorciatoie risulta ovviamente più simpatico dei cultori della fatica".
E fin qui nulla di strano, o di criticabile. Il fatto è che Gramellini si perde poi in un elogio compiaciuto, e a suo stesso dire "conservatore", della memoria, quasi che imparare la matematica si riducesse, in un ultima analisi, nella memorizzazione di una lunga lista di "regole" e di formule, da applicare acriticamente per risolvere i problemi. Lasciamo perdere il passaggio in cui l'editorialista se la prende con i computer e quello in cui impreca contro il Sessantotto: il punto fondamentale sul quale, secondo me, vale la pena di riflettere è l'immagine falsata che molte persone, Gramellini compreso, hanno della matematica.

Il mio professore di Analisi 1 e di Analisi 2 all'università, del quale ho già raccontato qualche aneddoto, spiegava che lui le "formule" mica le sapeva tutte a memoria. "Però me le so ricavare", diceva.
Il fatto è che saper ricavare una formula, o, detto in maniera più appropriata, dimostrare un teorema, richiede di aver capito quel teorema. Ecco il punto. È giusto proibire l'uso dei formulari durante la prova della maturità perché l'essenza della matematica non può essere condensata in un bignami di formule pronte all'uso. Ed è giusto far capire ai ragazzi (per lo meno agli studenti del quinto anno del liceo scientifico) che ciò che conta non è mandare a memoria la regoletta, ma comprendere, il più profondamente possibile, il "mondo" che sta attorno a quella regoletta: in questo modo, dovesse la regoletta scomparire dalla memoria, è agevole ricavarla nuovamente proprio perché è stato compreso il ragionamento associato.

Se uno studente impara a memoria, senza alcuno sforzo di capirne il senso ultimo, la formula del quadrato del binomio:

corre ovviamente il forte rischio di dimenticarla nel momento della necessità. Ma se lo studente si spinge appena al di là della scatola nera della formula, e si ricorda (ecco una forma più "nobile" di memoria) che elevare un oggetto al quadrato significa moltiplicare quell'oggetto per se stesso, sarà immediato arrivare a scrivere:

e quindi

Ecco che la formula viene ricavata anche se lì per lì era stata dimenticata. Di fatto lo studente ha dimostrato un teorema. E cos'è la matematica se non dimostrare teoremi?

L'uso della memoria che Gramellini sembra caldeggiare per imparare la matematica è un utilizzo acritico e nozionistico, l'esatto contrario di quello che serve davvero. Un po' come imparare a memoria poesie senza capire cosa vogliono dire. Può essere utile, certo, per allenare la memoria, ma allora tanto varrebbe esercitarsi con l'elenco telefonico. Se si tratta di imparare davvero la matematica, forse è il caso di provare a capirla, e non solo di memorizzare "regole", anche perché alla lunga questo esercizio sterile finirebbe per fare odiare questa disciplina, e nasconderebbe gli aspetti più gratificanti.

Certo, non si può pretendere che tutti capiscano (tutta) la matematica. Per qualcuno (molti, forse) può essere saggio non andare troppo oltre la memorizzazione di formule pronte all'uso: addentrarsi troppo nel senso profondo e nelle dimostrazioni potrebbe rappresentare una inutile forzatura. Così come quasi tutti possono riuscire a imparare a memoria l'"Infinito" di Leopardi, ma non per tutti è facile capirne il significato profondo.
Tuttavia, il ragionamento può essere per fortuna applicato a vari livelli. E comunque la petizione si riferiva agli studenti di quinta liceo scientifico. Quei ragazzi dovrebbero uscire dalla scuola sapendo che la matematica non è un insieme di formule, ma è piuttosto un universo di ragionamenti creativi, di intuizioni, di deduzioni: queste cose possono portare, è vero, anche a formule utilizzabili per risolvere problemi ed esercizi, ma la matematica, per fortuna, non è solo questo.

Gli enigmi di Coelum: Il primo della classe

Ritratto di Carl Friedrich Gauss pubblicato sull'”Astronomische 

Nachrichten” nel 1828.

Tornano gli enigmi di Coelum: il protagonista di questa puntata è uno dei più grandi matematici della storia: Carl Friedrich Gauss (1777-1855). Nato da una famiglia di umile estrazione sociale, dimostrò fin dalla più tenera età la sua straordinaria propensione per la matematica e per le scienze in genere. A scuola, raccontano le cronache, si annoiava perché sapeva già tutto, avendo imparato da solo formule e regole matematiche, e non di rado arrivava a correggere il maestro.
È famoso l’aneddoto secondo il quale, all’età di nove anni, riuscì a risolvere in pochi secondi un problema che il maestro aveva assegnato alla classe allo scopo di tenere occupati i ragazzi per buona parte dell’ora di lezione. L’esercizio consisteva nel sommare tutti i numeri interi da 1 a 100. Probabilmente la maggior parte delle persone, di fronte a questo compito, non troverebbe niente di meglio da fare che eseguire pazientemente tutte le 99 addizioni, una dopo l’altra, arrivando infine al risultato richiesto.
Ma fare matematica, come dico sempre, non è fare conti, ma trovare regolarità e strutture. Il giovanissimo Gauss trovò nel problema una regolarità comodissima per arrivare alla soluzione senza impazzire con i calcoli: si accorse che la somma del primo numero, 1, e dell’ultimo numero, 100, era uguale alla somma del secondo numero, 2, e del penultimo, 99, e anche a tutte le altre somme costruibili in modo analogo spostandosi verso la somma centrale (50+51) arrivando contemporaneamente da sinistra e da destra. La somma complessiva, comprese Gauss, si ottiene quindi sommando 50 volte la somma parziale 101, ed è quindi pari a 5050.
L’insegnante di Gauss, resosi conto del genio precoce del ragazzo, lo segnalò al duca di Brunswick, il quale finanziò i suoi studi al Collegium Carolinum tra il 1792 e il 1795. Successivamente Gauss frequentò l’università di Gottinga, dove ottenne una serie di importanti risultati, tra i quali spiccano quelli inerenti alla geometria e all’invenzione dell’arimetica modulare.

Nel 1796 formulò, senza dimostrarla, la congettura nota come teorema dei numeri primi, sulla quale tornerò più avanti. Tre anni dopo, nella sua tesi di dottorato, dimostrò il teorema fondamentale dell’algebra, secondo il quale un qualsiasi polinomio di grado maggiore o uguale a 1, con coefficienti reali o complessi, ammette almeno una radice reale o complessa. Quest’ultimo risultato, anche se Gauss lo dovette precisare e perfezionare negli anni successivi, fu particolarmente rilevante, anche perché molti brillanti matematici del passato, tra cui il grande Eulero, avevano tentato di dimostrare il teorema senza mai riuscirci.
Nel 1801 pubblicò il famoso trattato Disquisitiones Arithmeticae, che raccoglieva molte delle fondamentali innovazioni ottenute negli anni precedenti nel campo della teoria dei numeri (cioè dell’aritmetica): una di queste fu l’introduzione dei numeri immaginari e complessi, che qualche lettore ricorderà di avere studiato a scuola o all’università.
Il geniale matematico tedesco soffriva di una strana malattia: il perfezionismo. Quando trovava una dimostrazione, non la pubblicava se non arrivava ad essere assolutamente certo della sua perfezione. Inoltre era ossessionato dalla possibilità che altri potessero rubargli le scoperte, e per questo appuntava le sue idee in modo criptico, così che nessuno potesse comprenderne il reale significato.

Giuseppe Piazzi

La scoperta di Cerere
Cerere, l'asteroide più grande della fascia principale del Sistema solare, oggi considerato pianeta nano, fu scoperto casualmente il 1° gennaio 1801 (il primo giorno del XIX secolo) dall’astronomo italiano Giuseppe Piazzi, presso l’Osservatorio Nazionale del Regno delle Due Sicilie a Palermo.
Piazzi non riuscì a seguire a lungo il moto di Cerere, perché l’11 febbraio l’asteroide entrò in congiuzione diventando invisibile dalla Terra. L’astro andò così perduto, e lo stesso Piazzi, non del tutto convinto di avere scoperto un nuovo pianeta, minimizzò annunciando di avere trovato semplicemente una cometa. Le osservazioni di Piazzi furono comunque pubblicate nel settembre 1801, e il ventiquattrenne Gauss entrò subito in possesso di questi dati.
Il matematico tedesco sviluppò un nuovo metodo, basato sui minimi quadrati, per determinare la traiettoria completa di un astro utilizzando tre sole osservazioni. Applicando questa tecnica al caso dell’asteroide perduto, Gauss riuscì a predire l’orbita di Cerere e i suoi calcoli condussero alla riscoperta dell’astro il 31 dicembre 1801, ad opera di Franz Xaver von Zach e Heinrich Olbers.
L’anno che si era aperto con la scoperta casuale di Piazzi si concludeva con il felice ritrovamento dell’asteroide, grazie al genio di Gauss.

Ritratto di Carl Friedrich Gauss, ad opera di
Christian Albrecht Jensen.

Numeri primi
Che cos’è un numero primo? Semplicemente un numero naturale che non può essere diviso per nessun altro numero naturale se non per 1 e per se stesso. Per esempio, 5 è un numero primo, perché non ammette divisori che non siano 1 o 5, mentre 6 non lo è, perché può essere diviso per 2 e per 3, oltre che per 1 e 6.
Il grande matematico greco Euclide dimostrò che i numeri primi sono infiniti, cioè scelto un certo numero naturale N si può sempre trovare un numero primo più grande di N.
I numeri primi sembrano collocati in modo disordinato lungo la linea dei numeri naturali. Non è per nulla facile individuare una regolarità, una legge semplice che governi la loro distribuzione.

Il teorema dei numeri primi, congetturato per la prima volta da Gauss nel 1796, descrive in modo approssimato come i numeri primi siano distribuiti tra i numeri naturali. In particolare, afferma che, scelto un numero reale positivo x, la quantità di numeri primi minori o uguali a x può essere stimata approssimativamente come x diviso il logaritmo naturale di x.
Man mano che ci spinge verso valori di x più grandi, l’approssimazione fornita dal teorema risulta sempre più accurata.
Gauss intuì che il teorema era veritiero, ma non trovò il modo di dimostrarlo rigorosamente, cosa che invece riuscì cent’anni dopo la prima formulazione, grazie ai due matematici Hadamard e de la Vallée Poussin.

La copertina delle “Disquisitiones Arithmeticae”

Il teorema fondamentale dell'aritmetica
Nelle “Disquisitiones Arithmeticae” del 1798, Gauss dimostrò per la prima volta il teorema fondamentale dell’aritmetica, secondo il quale:
Ogni numero naturale maggiore di 1 o è un numero primo o si può esprimere come prodotto di numeri primi. Tale rappresentazione è unica, se si prescinde dall’ordine in cui compaiono i fattori.
Che cosa significa questa affermazione? Prendiamo un numero come 5. Si tratta di un numero primo, e quindi ci troviamo nel primo caso. Prendiamo invece 6. Dato che questo non è un numero primo, il teorema ci assicura che possiamo esprimerlo come prodotto di numeri primi. In effetti possiamo scrivere 6 = 2 × 3, e i numeri 2 e 3 sono primi. Ma il teorema ci dice un’altra cosa ancora più importante: che non possiamo trovare un’altra fattorizzazione di 6 in numeri primi, prescindendo dall’ordine dei fattori. In altre parole, è vero che possiamo anche scrivere 6 = 3 × 2, ma questa non è una diversa fattorizzazione: è un modo diverso di scrivere quella di prima, con i fattori riportati in ordine diverso.
Il solito Euclide, negli “Elementi”, aveva dimostrato che ogni numero è primo oppure fattorizzabile in numero primi, ma non era arrivato rigorosamente a provare l’unicità della fattorizzazione. Vi si era avvicinato molto, ma fu Gauss a dimostrare per primo questa verità fondamentale della matematica.
Per evitare il “fastidio” derivante dai diversi ordini in cui i fattori primi possono essere elencati, i matematici hanno stabilito una convenzione, semplice quanto ovvia: i fattori devono essere scritti in ordine crescente, dal più piccolo al più grande, eventualmente ripetendo quelli che compaiono più volte.
I seguenti sono quindi esempi di fattorizzazioni scritte bene: 6 = 2 × 3, 60 = 2 × 2 × 3 × 5, 100 = 2 × 2 × 5 × 5.
Si pone a questo punto una vecchia e spinosa questione: anche 1 è un numero primo?
Teoricamente, se dovessimo attenerci unicamente alla definizione che ho dato sopra, dovremmo dire di sì. Ma considerare 1 come primo comporterebbe un grosso guaio: ogni fattorizzazione non sarebbe più unica, perché potremmo sempre aggiungere una quantità indefinita di uni all’inizio della fattorizzazione stessa. Avremmo cioè 60 = 2 × 2 × 3 × 5, ma anche 60 = 1 × 2 × 2 × 3 × 5, 60 = 1 × 1 × 2 × 2 × 3 × 5, 60 = 1 × 1 × 1 × 2 × 2 × 3 × 5, e così via all’infinito.
Per evitare questo fastidio, e per restituire validità al teorema fondamentale dell’aritmetica, i matematici hanno stabilito per convenzione che 1 non è primo.

Il problema prooposto e la soluzione
L’enigma di Coelum 185 proponeva di sfruttare il teorema fondamentale dell’aritmetica per costruire una specie di codice segreto utile per cifrare un messaggio. Se ciascun numero intero può essere fattorizzato in uno e in un solo modo, perché non usare questa “firma” unica per trasformare un numero in un messaggio cifrato? Per esempio, il numero 42042 viene fattorizzato come 2 × 3 × 7 × 7 × 11 × 13, e quindi la sua firma è costituita dai fattori 2, 3, 7, 7, 11, 13.
Se, a questo punto, ci inventiamo liberamente una tabella di corrispondenza che associ ogni numero primo a una lettera dell’alfabeto, la fattorizzazione si tramuta in una successione di lettere.
Immaginiamo che i numeri primi siano associati alle lettere secondo l’ordine alfabetico: il 2 corrisponderà alla lettera A, il 3 alla B, il 5 alla C, il 7 alla D, l’11 alla E, e così via.
Secondo questa chiave, il nostro numero 42042 viene codificato come ABDDEF.
Naturalmente non è necessario che scorrendo la tabella di corrispondenza in modo che i numeri primi crescano, le lettere vengano assegnate in ordine alfabetico. In altre parole, andrebbe benissimo anche una tabella in cui al 2 corrisponda la lettera M, al 3 la lettera F, al 5 la lettera Q, eccetera, così come qualunque altra tabella di corrispondenza che ci venga in mente.
L’unico (grave) inconveniente di questo metodo di crittazione è che le lettere sono soltanto 26 (considerando l’alfabeto inglese), e quindi possiamo arrivare al massimo al numero primo 101. Un numero come 2884, che si fattorizza come 2 × 2 × 7 × 103, non potrebbe essere codificato perché ci mancherebbe la lettera corrispondente al fattore 103.
L’enigma proposto, comunque, non incorreva in questo problema.
Vediamo i termini del problema. Una certa tabella di corrispondenza è stata stabilita, ma noi non la conosciamo a priori. Sappiamo solo che:
il numero 575795 viene codificato come “TERRA”
il numero 18 viene codificato come “ISS”
il numero 147407 viene codificato come “LUNA”.
Quale numero viene codificato con la parola “STELLA”?

Per risolvere il quesito, basta trovare le fattorizzazioni dei tre numeri proposti.
Il numero 575795 è sicuramente divisibile per 5 (lo riconosciamo dalla sua ultima cifra, 5): dividendolo per 5 otteniamo 115159. Come procedere ora? Abbiamo in mano un numero dispari, quindi il 2 non è tra i divisori. Nemmeno 3, 5 o 7 vanno bene, e lo possiamo verificare provando le rispettive divisioni, e osservando che escono risultati non interi. Il numero 11, invece, va bene: dividendo 115159 per 11 otteniamo il numero intero 10469. Continuando così, scopriamo che i successivi fattori primi sono 19, ancora 19, e infine 29. La fattorizzazione completa di 575795 è quindi 5 × 11 × 19 × 19 × 29.
Guardiamo la parola corrispondente: “TERRA”. La lettera T è dunque associata al numero 5, la lettera E all’11, la lettera R al 19, e la lettera A al 29.
Fattorizzare 18 è molto più facile: si trova subito che è uguale a 2 × 3 × 3: dato che la codifica letterale è “ISS”, ecco che la lettera I è associata al 2, e la lettera S al 3.
Ci rimane il numero 147407: utilizzando ancora il solito algoritmo di fattorizzazione, scopriamo che esso equivale a 13 × 17 × 23 × 29. La parola corrispondente è “LUNA”: ritroviamo correttamente la A associata al numero primo 29, e inoltre arricchiamo la nostra tabella con le corrispondenze L = 13, U = 17, N = 23.
Abbiamo ora tutti gli ingredienti necessari per risolvere il problema, cioè per decodificare la parola “STELLA”. Conosciamo già i numeri correlati alle lettere di queste parola: la S corrisponde al 3, la T al 5, la E all’11, la L al 13, e la A al 29.
Il prodotto 3 × 5 × 11 × 13 × 13 × 29 dà come risultato 808665, che quindi è il numero cercato.

I sistemi di Lindenmayer e la successione di Thue-Morse

Aristid Lindenmayer

Per definire una sequenza numerica molto spesso si specificano i primi elementi della sequenza e si fornisce una regola per generare gli infiniti elementi successivi. Per esempio, la celeberrima successione di Fibonacci si costruisce partendo dagli elementi 0 e 1, e rispettando la regola secondo la quale ogni termine successivo è la somma dei due che lo precedono.
Ora, proviamo a costruire una sequenza diversa, formata esclusivamente da zeri e uni. Il suo primo elemento è uno zero. La regola da rispettare è la seguente: ogni elemento genera il suo successore attraverso le sostituzioni 0 → 01 e 1 → 10. Il secondo termine della sequenza è quindi 01. Il terzo è 0110. Il quarto 01101001. E così via.

Il sistema di costruzione della sequenza rientra nella famiglia dei cosiddetti "L-systems", o sistemi di Lindenmayer. Questa famiglia di sistemi, a sua volta, fa parte del più ampio mondo dei "sistemi di riscrittura", nei quali, genericamente, vengono fissate alcune regole di sostituzione che possono essere applicate agli oggetti di un insieme.
Un sistema di riscrittura è un sistema di Lindenmayer se esistono:
1. una famiglia di simboli ammessi;
2. un elemento iniziale formato da una concatenazione di simboli ammess;
3. un insieme di regole di sostituzione per la generazione degli elementi successivi.

Disegni di piante generati mediante sistemi di Lindenmayer

Non deve stupire che questi sistemi prendano il loro nome non da un matematico o da un informatico, ma da un biologo. L'ungherese Aristid Lindenmayer, infatti, vissuto tra il 1925 e il 1989, ideò questo giochino di riscrittura per descrivere formalmente il comportamento delle cellule vegetali e la crescita di alcuni semplici organismi multicellulari, ad esempio particolari tipi di alghe. Successivamente i sistemi di Lindenmayer vennero applicati con successo anche a specie vegetali più complesse. Sono stati impiegati anche per generare frattali, mediante un processo di autosimilarità (un frattale costituito da più copie di se stesso, come il celebre triangolo di Sierpinski).

Torniamo all'esempio iniziale. In questo caso, i simboli ammessi sono 0 e 1, l'elemento iniziale è 0, e le regole di sostituzione sono quelle citate sopra: 0 → 01 e 1 → 10.
Diamo ancora un'occhiata ai primi termini della sequenza: 0, 01, 0110, 01101001, ... Balza all'occhio una prima proprietà: ogni elemento della successione è formato da un numero di cifre doppio rispetto al suo predecessore.
Un'altra caratteristica è la seguente: ogni elemento è costituito dal suo predecessore concatenato con il suo complemento. Detto altrimenti, ogni termine include il precedente come sua prima metà. Per esempio, abbiamo visto che il terzo termine è 0110. Per costruire il suo complemento basta invertire ogni cifra binaria, cioè trasformare gli zeri in uni e viceversa. Otteniamo quindi 1001. Il nostro quarto elemento è 0110 concatenato a 1001, cioè 01101001.

Ecco, abbiamo trovato un modo alternativo per definire in modo costruttivo la nostra sequenza, che viene illustrato nella figura a fianco.

In virtù della seconda proprietà del sistema, potremmo considerare un'altra sequenza: anziché la successione delle stringhe binarie che raddoppiano di lunghezza ad ogni passo, potremmo considerare un'unica stringa, quella di lunghezza infinita alla quale converge la sequenza che abbiamo preso in esame in precedenza: anche questa stringa può essere studiata come una successione, perché è formata da cifre binarie che ne costituiscono gli elementi.
I primi 16 termini della successione sono quindi: 0110100110010110.

Una volta formalizzata la successione in questo modo, saltano fuori alcune proprietà davvero sorprendenti. Ma andiamo in ordine.
Per cominciare, la successione viene chiamata di Thue-Morse, dai nomi dei due matematici che l'hanno studiata: il danese Axel Thue e l'americano Marston Morse.

Vediamo una prima proprietà: l'n-esimo termine della successione è uguale a:

• 0, se il numero n-1 espresso in forma binaria contiene un numero pari di uni;
• 1, se il numero n-1 espresso in forma binaria contiene un numero dispari di uni.

Attenzione: l'elemento che compare per primo nella sequenza è in realtà associato all'indice 0, non all'1. In binario, 0 si scrive ancora 0, che non contiene uni al suo interno. Zero può essere considerato un numero pari, quindi il primo elemento è 0. Vediamo ora, ad esempio, l'elemento associato a n=5: in binario 5 si scrive 101, che contiene due uni. Due è pari, quindi il sesto elemento è 0. Il nono elemento: 8 in binario è 1000, in cui compare un solo uno. Essendo uno dispari, il nono elemento è un 1. E così via.

Quel genio matematico che risponde al nome di John Conway e di cui ho parlato più volte (ad esempio qui), ha avuto un'ideona: ha chiamato "odiosi" i numeri interi n tali per cui l'n-esimo termine della sequenza di Thue-Morse è 1, e "malvagi" quelli per cui l'n-esimo termine è 0. Perché tutto questo odio e questa malvagità"? Soltanto un gioco di parole: in inglese "pari" si dice "even", che suona simile a "evil" ("malvagio"), e "dispari" si dice "odd", che assomiglia a "odious" ("odioso").

Un'altra curiosa proprietà è la seguente: fissato a 0 il termine associato a n=0, il termine associato a 2n (con n naturale qualsiasi) è uguale a quello associato a n, e il termine associato a 2n+1 è uguale al "complemento" del termine associato a n ("complemento" nel senso che 1 è il complemento di 0 e viceversa). Provare per credere.

Non è nemmeno difficile convincersi del fatto che, preso un qualsiasi n naturale, la porzione di successione formata dai primi 2n termini è palindroma, cioè si legge allo stesso modo da sinistra a destra e da destra a sinistra.

Ma il bello deve ancora venire. Intanto beccatevi le proprietà qui a fianco. Che la successione di Thue-Morse sia legata a quantità come la radice quadrata di 2 può sembra abbastanza normale, ma che anche qui venga fuori pi greco, beh, è già molto più stupefacente.
Ricordate il linguaggio Logo, quello che poteva essere usato, tra le altre cose, per guidare una tartaruga su un piano cartesiano?
Ebbene, immaginiamo che i termini successivi della sequenza di Thue-Morse rappresentino ordini impartiti alla tartaruga. Più precisamente, un 1 deve essere interpretato come "vai avanti di una posizione", e uno 0 come "girati in senso antiorario di 60°".
Secondo voi che disegno traccerà la tartaruga seguendo le cifre binarie della nostra sequenza? Proviamo a vedere.

Non si capisce molto, vero? Già, perché servono molti termini della sequenza, cioè molte istruzioni per  il simpatico rettile, perché il risultato cominci a prendere forma. Vediamo cosa succede dopo 2⁸ = 256, 2¹⁰ = 1024, 2¹² = 4096 e 2¹⁴ = 16384 istruzioni.

Vi ricorda qualcosa? Se scegliamo, per la cifra 1, una rotazione antioraria di 120° anziché 60°, si ottiene un disegno ancora più pulito:

Ebbene sì: è il fiocco di neve di Koch, uno dei frattali più famosi. Modificando ancora le regole della tartaruga, ma utilizzando sempre la successione di Thue-Morse, si ottengono risultati interessanti, come questi:

Per questi e altri divertimenti vi rimando al blog Three-Cornered Things di Zachary Abel.

Max Euwe

Una proprietà interessante della successione di Thue-Morse è l'assenza in essa di stringhe della forma XXX, dove X è una qualsiasi sequenza di cifre binarie. Un grande campione di scacchi come Machgielis "Max" Euwe (1901 – 1981), che oltre ad essere stato il quinto campione del mondo di scacchi tra il 1935 e il 1937, fu anche una brillante mente matematica, contestò una delle regole "tedesche" che vigevano nel gioco degli scacchi intorno al 1929: una partita poteva essere dichiarata patta se la stessa sequenza di mosse viene ripetuta per tre volte di seguito.
Sfruttando la successione di Thue-Morse, Euwe dimostrò che la regola non escludeva di per sè partite di lunghezza infinita.
Grazie a questa scoperta, venne accettata universalmente la regola in base alla quale una partita può essere dichiarata patta se una posizione si presenta per tre volte, indipendentemente da quali mosse l'abbiano determinata.

E qui mi fermo. La sequenza di Thue-Morse ha anche affascinanti connessioni con il gioco del Nim, con la risoluzione di problemi di distribuzione di risorse tra due contendenti, con la teoria dei numeri, con la combinatoria delle parole, e con un sacco di altre cose. Buon divertimento.

Buon 2017!

Con il post precedente questo blog ha festeggiato i suoi primi 250 post pubblicati.
Era il primo gennaio del 2011 quando iniziai, praticamente per gioco, a scrivere cose su queste pagine. Sono passati sei anni, e di acqua sotto i ponti ne è passata molta. 2011, cioè il primo anno di Mr. Palomar, era un numero primo, cioè divisibile soltanto per se stesso e per 1.
Dopo sei anni si ripropone questo fatto, perché anche 2017 è un numero primo.
Per la precisione, si tratta di un numero primo di Friedlander-Iwaniec, cioè della forma

Non ci credete? Prendete a = 44 e b = 3. Il precedente numero primo con questa proprietà è 1777 (a = 39, b = 4), che è l'anno della nascita di Gauss.
2017 fa anche parte di una terna pitagorica, essendo l'ipotenusa di un triangolo rettangolo i cui cateti sono 792 e 1855.
Sicuramente ci saranno altre proprietà del 2017, ma mi fermo qui, non prima di aver augurato un felice nuovo anno a tutti gli amici di Mr. Palomar.
Buon 2017 a tutti!

Gli enigmi di Coelum: La Coppa dei Mondi

La nuova puntata degli enigmi di Coelum verte su un tema che ho già trattato non soltanto nel mio libro "La matematica nel pallone", ma anche in un trittico di post pubblicato agli albori di questo blog. Ecco i link a quei tre antichi articoli:
Parte 1
Parte 2
Parte 3

Ogni anno, intorno al mese di luglio, viene stabilito il calendario del campionato di calcio di Serie A.
Forse molti di voi si saranno a volte chiesti come si svolge tale procedura. Si tratta di una normale estrazione, come quando vengono sorteggiati i numeri del lotto, o di un complicato calcolo effettuato da un supercomputer? Sicuramente definirlo sorteggio sarebbe riduttivo e semplicistico. Come spiegato nell’articolo di giugno, stabilire il calendario di un girone all’italiana, cioè di un torneo in cui ogni squadra disputa un incontro con ciascuna delle altre partecipanti, non è un’operazione banale, a meno che il numero delle formazioni non sia molto esiguo.
Johann Berger, maestro di scacchi austriaco vissuto tra il 1845 e il 1933, inventò l’algoritmo più famoso tra quelli proposti per risolvere il problema. Nel mio articolo pubblicato sulla rivista Coelum, si immaginava di dover stilare il calendario della Coppa dei Mondi 2514, le cui otto partecipanti sono Terra, Luna, Marte, Cerere, Ganimede, Europa, Callisto e Titano. La prima giornata è determinata semplicemente formando i quattro accoppiamenti che derivano dall’ordine in cui abbiamo elencato le squadre:

E la seconda giornata? Immaginiamo di mantenere la Terra fissa al suo posto in alto a sinistra, e facciamo ruotare in senso orario le altre squadre. Marte si ritroverà nella prima riga, a fianco della Terra. La Luna scenderà nella seconda riga, Cerere nella terza, ed Europa nella quarta. Titano passerà nella prima colonna, restando comunque nella quarta riga. Callisto salirà nella terza riga, spingendo Ganimede nella seconda. Il risultato sarà il seguente:

Proseguendo in questo modo si compileranno tutte le altre giornate del torneo, con la certezza che, alla fine, ogni squadra incontrerà ciascuna delle altre esattamente una volta.
Ma quante saranno le giornate? Se ogni squadra deve incontrare sette avversarie, è evidente che la Coppa si articolerà in sette giornate, in ognuna delle quali saranno disputate quattro partite. Il numero totale degli incontri sarà quindi 7 × 4 = 28. In generale, se le squadre che partecipano a un girone all’italiana sono N (con N pari), le giornate saranno N-1, e, dato che ogni giornata comprenderà N/2 partite, saranno giocati in tutto N(N-1)/2 incontri. Tutto questo considerando il solo turno di andata: se è previsto anche il girone di ritorno le giornate saranno 2(N-1) e le partite N(N-1).
Nella Serie A del nostro campionato di calcio, che comprende N=20 squadre, vengono disputate 2(N-1) = 38 giornate, per un totale di N(N-1) = 380 partite.
E se le squadre fossero in numero dispari? In questo caso, a turno ognuna delle formazioni dovrebbe riposare, e il numero delle giornate uguaglierebbe così il numero delle partecipanti. In termini più formali, se le squadre sono N (con N dispari), le giornate saranno N. Visto che a ogni giornata si giocherebbero (N-1)/2 incontri, le partite complessive, prescindendo dal girone di ritorno, saranno N(N-1)/2: esattamente lo stesso risultato che avevamo ottenuto nel caso di N pari. Per esempio, 19 squadre darebbero vita a un torneo di N = 19 giornate, per un totale di N(N-1)/2 = 171 gare. Abbiamo così risposto al primo quesito proposto nel numero di giugno (peraltro abbastanza banale rispetto al secondo).

Il metodo di Berger è l’unico possibile per risolvere il problema del campionato? No di certo. Esistono molti altri algoritmi adatti allo scopo. Sinceramente non so se nel sorteggio dei calendari dei campionati di calcio venga utilizzata una variante dell’algoritmo di Berger o un approccio computazionale completamente diverso. Sicuramente il metodo “puro” di Berger non è utilizzabile in queste occasioni, perché nella determinazione delle giornate devono essere considerati molti vincoli supplementari. Per esempio si fa in modo che le partite tra le squadre più forti non vengano programmate nelle giornate iniziali del campionato, si evita che in una medesima giornata debbano giocare in casa squadre della stessa città, come Verona o Chievo, e così via.
È quindi ipotizzabile che il computer adibito alla determinazione dei calendari sia programmato con un algoritmo simile a quello proposto da Berger, ma modificato e perfezionato in modo da tener conto di una serie di constraint aggiuntivi. Il problema del calendario del campionato mi ha affascinato fin da quando ero ragazzino. Quando avevo una dozzina d’anni, mi cimentavo, con un amichetto compagno di innumerevoli partite a pallone nei cortili di casa, nella compilazione dei calendari dei nostri campionati immaginari. Ma gli algoritmi che adoperavamo erano molto rozzi e poco efficaci. Erano basati su un faticoso approccio per tentativi: si tentava di programmare giornata per giornata, e se a un certo punto incontravamo un ostacolo insormontabile (cioè scoprivamo che le ultime due squadre non ancora abbinate in una giornata si erano già incontrate in una giornata precedente), eravamo costretti a ricominciare tutto da capo.
Diversi anni dopo, non conoscendo ancora il metodo di Berger, escogitai un metodo molto più elegante per risolvere il problema in modo diretto. Supponiamo di avere N squadre. Costruiamo una tabella con N righe e N colonne: ogni riga e ogni colonna corrisponde a una delle squadre. Il nostro obiettivo è riempire ogni casella interna con un numero, che rappresenta la giornata in cui le due squadre in questione si incontreranno tra di loro. Naturalmente, dobbiamo escludere le caselle della diagonale principale, corrispondenti alle improbabili partite in cui una squadra gioca contro se stessa. Per semplicità, possiamo anche trascurare metà tabella, per esempio quella sotto la diagonale principale, perché le caselle di questa zona rappresentano le stesse partite descritte nell’altra metà: potrebbero essere utilizzate per il girone di ritorno, ma una volta che è programmato il turno di andata, basta ripetere la sequenza delle partite, a campi invertiti, e anche il ritorno è determinato.
Considerando le N=8 partecipanti alla Coppa dei Mondi, la tabella di partenza sarebbe la seguente:

In generale, condizione necessaria e sufficiente affinché la compilazione di una simile tabella rappresenti un calendario valido per un campionato è che su ogni riga e su ogni colonna siano presenti tutti i numeri da 1 a N-1, senza ripetizioni. Infatti, la ripetizione di un numero su una medesima riga o colonna starebbe a indicare che una squadra deve giocare due partite nella stessa giornata, e che, corrispondentemente, un’altra squadra non giocherebbe alcuna partita. Situazione questa ovviamente non accettabile.
Forse il vincolo della non ripetizione dei numeri su righe e colonne vi avrà fatto venire in mente il sudoku: in effetti una parentela c’è, ed esistono interessanti connessioni anche con altri concetti matematici come i quadrati latini e i problemi di colorazione dei grafi. Per i lettori interessati ai dettagli, rimando agli articoli del mio blog citati nella bibliografia.
Vediamo come si articola l’algoritmo. Si parte con la matrice compilata con degli zeri.

A questo punto ha inizio il ciclo principale. Si considera, una dopo l’altra, le squadre partecipanti, e per ciascuna vengono individuate la riga e la colonna corrispondenti. Immaginiamo di scendere dall’alto verso il basso lungo la colonna, “rimbalzare” sulla diagonale principale, e percorrere la riga verso destra. Lungo questo cammino, ogni volta che troviamo una casella ancora a zero, la riempiamo con un numero. Quale numero? Per ogni cammino, cercheremo la prima casella che possiamo riempire, e tenteremo di riempirla con il numero successivo a quello presente nella casella immediatamente precedente. Se si tratta della prima casella del cammino, tenteremo di piazzare un 1. Ad ogni nuovo tentativo di riempimento, cresceremo di 1.
Ogni volta che tentiamo di collocare un numero, comunque, controlleremo se il numero candidato non sia stato precedentemente collocato su un’altra casella dello stesso cammino, o della stessa riga, o della stessa colonna: in questo caso ritenteremo il riempimento con il numero aumentato di 1. Se, a un certo punto, a cammino non ancora completato, scopriremo di essere già arrivati a N-1 (nel nostro esempio 7), il successivo incremento ci farà ripartire da 1.
Percorrendo in questo modo il cammino relativo alla Terra, si ottiene:

Dopo aver “sistemato” anche la Luna, ci ritroveremo con questa tabella:

Alla fine dell’intero ciclo di “cammini”, la tabella si riempirà in questo modo:

A questo punto è facile “leggere” il calendario ottenuto. Per esempio, la prima giornata sarà composta dalle partite corrispondenti alle caselle riempite con un 1: Terra-Luna, Marte-Callisto, Europa-Cerere e Titano-Ganimede. Come potete vedere, il risultato è diverso, già nella prima giornata, da quello prodotto dall’algoritmo di Berger. Questo non deve sorprendere, anzi. Con un numero di squadre appena un po’ grande, come 8, sarebbe infatti molto strano che due diversi approcci generassero calendari identici.

Il problema da me proposto sulle pagine di Coelum consisteva nel pianificare il girone all’italiana della Coppa dei Mondi 2514 con le otto squadre già menzionate (Terra, Luna, Marte, Cerere, Ganimede, Europa, Callisto e Titano), facendo però in modo di rispettare lo strano vincolo imposto dagli immaginari organizzatori: a ogni giornata due partite sono in programma al pomeriggio e due alla sera, e prese due squadre qualsiasi tra le partecipanti, esse giocheranno alla stessa ora soltanto tre volte (compresa la giornata in cui si troveranno a gareggiare l’una contro l’altra), mentre nelle altre occasioni scenderanno in campo in fasce orarie diverse.

La figura sotto illustra una soluzione del problema. Se prendiamo, per esempio, Terra e Luna, è facile notare che queste due squadre giocheranno alla stessa ora alla prima giornata (quando giocheranno l’una contro l’altra), alla seconda (quando entrambe scenderanno in campo di pomeriggio), e alla terza (quando giocheranno entrambe in notturna), mentre in tutte le altre giornate si troveranno a disputare i loro incontri in orari differenti.