In memoria di Dennis Ritchie

Il mese di ottobre 2011 ha visto la scomparsa di due grandi geni dell'informatica. Del primo, Steve Jobs, hanno parlato diffusamente tutti i mezzi di comunicazione, e si sono versati fiumi di inchiostro (soprattutto digitale, ovviamente).
Del secondo, Dennis Ritchie, hanno invece parlato pochissimi. Pochissime persone, d'altra parte, saprebbero dire chi sia stato Dennis Richie, e che cosa abbia fatto di tanto memorabile.
Eppure, l'importanza delle sue ricerche e dei suoi risultati lo pongono tra i massimi geni della storia dell'informatica.
Bastano due parole molto brevi, per stabilire la statura di Ritchie nel pantheon degli informatici di ogni tempo. La prima è UNIX. La seconda è C.
Assieme ad un altro grande informatico come Ken Thompson, presso i Bell Laboratories che videro la nascita del transistor e del laser, Ritchie fu infatti uno dei principali artefici del sistema operativo UNIX. Per decenni UNIX ha rappresentato una risorsa fondamentale per aziende, università e appassionati. UNIX, nel corso della sua lunga storia, ha avuto due figli illustri: uno è Linux, il sistema open source e gratuito più diffuso al mondo, lanciato nei primi anni Novanta dallo studente finlandese Linus Torvalds, l'altro è Mac Os X, sistema adottato nei sistemi Apple Macintosh dal 2001 in poi.
Negli stessi anni in cui vedeva la luce UNIX, e cioè in quegli anni di grande creatività e vivacità culturale che segnarono il passaggio tra anni Sessanta e anni Settanta, Dennis Ritchie plasmò anche il linguaggio di programmazione C: un altro pilastro fondamentale dell'informatica dal cui grembo sono derivate decine di altre piattaforme, come C++, Java, Perl, PHP, Python e molti altri.
Per il suo contributo essenziale al mondo della computazione, Dennis Ritchie ottene nel 1983, insieme a Thompson, il prestigioso premio Turing.
Onore dunque non soltanto al pur geniale Jobs, ma anche al grande Ritchie.

Il teorema del pappagallo, ovvero la matematica in forma di giallo

Prendete un pappagallo. Non un pappagallo qualsiasi, s’intende, ma un pennuto parlante, un po’ pedante, irresistibilmente simpatico, di nome Nofutur, che “non ripete, ma racconta”. Aggiungete un anziano filosofo, il signor Pierre Ruche, generoso e combattivo, che gestisce una libreria del quartiere parigino di Montmartre. Non dimenticate Perrette, donna dall’enigmatico passato, i suoi figli, i gemelli Jonathan e Lea, concepiti in un tombino delle fogne dove lei era caduta per sbaglio, e soprattutto Max, ragazzino sordo ma dalla particolare sensibilità. Condite con Albert, taxista che ha conosciuto il mondo intero senza mai uscire da Parigi, e Habibi, proprietario di una drogheria araba. Completate il quadretto con una trama avvicente, da vero e proprio thriller, in cui gli insoliti testimoni si chiamano… Talete, Pitagora, Euclide, Archimede, Tartaglia, Goldbach, Eulero, Fermat!
Si potrebbe definire questo libro un giallo matematico. O si tratta forse un romanzo sulla matematica? Oppure un testo di storia della matematica camuffato da romanzo? O forse… Qualunque cosa sia, questo libro testimonia la grande passione dell’autore per numeri e teoremi: in questo libro, che da best-seller è divenuto ormai un classico, Denis Guedj, già noto per il romanzo storico-scientifico “Il meridiano”, vince la sua scommessa di trasformare l’arida e astratta matematica in qualcosa di vivo, animando numeri ed equazioni grazie alla concretezza delle vite dei suoi protagonisti.
A proposito di storie, non è la trama del romanzo in sé che conta. A dire il vero, si tratta di un plot forse un po’ debole: a tratti si ha la sensazione che gli stravaganti personaggi gravitanti attorno alla libreria parigina non rappresentino il vero centro dell’interesse di Guedj, ma che costituiscano soltanto una cornice, per quanto simpatica, escogitata per sostenere le storie dei veri protagonisti, i matematici dei secoli passati. Già, perché chi domina davvero la scena è la matematica stessa.

La trama merita comunque un accenno. Un giorno, l’anziano Ruche riceve una insolita lettera da un amico matematico che non vede da cinquant’anni, Elgar Grosrouvre. Nella lettera Grosrouvre annuncia che la sua immensa biblioteca di libri di matematica sta per essere trasportata a Parigi, presso la libreria di Ruche. Ma l’arrivo dei preziosissimi libri portano con sé la notizia della misteriosa morte di Grosrouvre in Amazzonia, sulla quale Ruche comincia ad indagare, aiutato dalla sua variegata “tribù” e dal variopinto pappagallo. Il filosofo Ruche, per decifrare l’enigma, si mette a studiare aritmetica, algebra, trigonometria e logica, materie che ha odiato fin dai tempi dell’università: a ottantaquattro anni (non è mai troppo tardi) scopre così la bellezza della matematica. Tra le pagine delle opere recapitate a Ruche, si nasconde la soluzione del giallo della morte di Grosrouvre: è stato forse ucciso a causa di alcune sue dimostrazioni che non ha voluto rivelare? O si è trattato di un incidente? Ruche e i suoi amici si ritrovano così scaraventati nell’affascinante mondo della matematica, viaggiano nei libri dall’Egitto ad Atene, da Crotone a Baghdad, facendo la conoscenza di illustri studiosi di ogni epoca: dai matematici dell’antica Grecia a quelli del mondo arabo, fino ad arrivare ai grandi matematici europei dei secoli più recenti. La svolta avviene quando prima Nofutur e poi anche Max vengono rapiti: per liberarli Ruche si ritrova in Sicilia, dove compare lo strano personaggio di Tavio, alias Don Ottavio. Il giallo comincia a dipanarsi, e per giungere alla soluzione finale la scena si sposterà addirittura a Manaus, in Amazzonia: e Nofutur, ovviamente, si rivelerà figura chiave.

Il merito più grande di Guedj è quello di aver saputo fare della matematica una storia appassionante e divertente, facendone risaltare la vera essenza: non formule complicate e astrusi teoremi, ma qualcosa di vivo, trascinante e affascinante.
Il pretesto narrativo in forma di giallo conduce per mano il lettore verso la riscoperta della storia della matematica, fatta di uomini in carne ed ossa alle prese con enigmi ben più intricati di quello della morte di Grosrouvre. Ogni lettore in più che il romanzo di Guedj ha affascinato e convinto della bellezza della matematica è una piccola grande vittoria della buona divulgazione. Anche un pappagallo può servire in questa impresa.

Carnevale della matematica #42: goto .mau.

"Quarantadue!" urlò Loonquawl. "Questo è tutto ciò che sai dire dopo un lavoro di sette milioni e mezzo di anni?"
"Ho controllato molto approfonditamente," disse il computer, "e questa è sicuramente la risposta. Ad essere sinceri, penso che il problema sia che voi non abbiate mai saputo veramente qual è la domanda."

Può darsi che il supercomputer Pensiero Profondo, tra i protagonisti della celeberrima "Guida Galattica per gli autostoppisti", avesse inteso rispondere alla epocale domanda "Quale fu il Carnevale della Matematica ospitato dal Post di .mau. nell'ottobre del 2011?"
Non siamo certi di questo, ma di sicuro questa edizione del Carnevale si presenta molto ricca di interessanti spunti.
Anche questo mese si è aggiunta ai blogger già noti una new entry: Leonardo Petrillo col suo bel blog "Scienza e musica".
Il tema, davvero accattivante, proposto dal buon .mau. era "Numeri e letteratura".
Mr. Palomar ha contribuito con soli due contributi, entrambi pertinenti con l'argomento: "La matematica invisibile di Calvino" e "Ineffabile, inafferrabile π"

Buona lettura e buon Carnevale a tutti!

Ineffabile, inafferrabile π

Che cos'hanno in comune la cantautrice inglese Kate Bush, salita alla ribalta internazionale nel 1978 con la hit "Wuthering Heights", e il grande scrittore tedesco Thomas Mann, premio Nobel per la letteratura nel 1929?
Apparentemente nulla. Eppure questi due artisti, pur nella profondissima diversità dei loro linguaggi espressivi, hanno dipinto due personaggi molto simili tra di loro, accomunati dalla loro passione per un numero: il misterioso e inafferrabile π.

Nella canzone "Pi", tratta dall'album "Aerial" del 2005, Kate Bush descrive la figura di un matematico ossessionato da quell'affascinante numero:

Sweet and gentle sensitive man
With an obsessive nature and deep fascination
For numbers
And a complete infatuation with the calculation
Of Pi

Oh he love, he love, he love
He does love his numbers
And they run, they run, they run him
In a great big circle
In a circle of infinity

3.1415926535 897932
3846 264 338 3279

Oh he love, he love, he love
He does love his numbers
And they run, they run, they run him
In a great big circle
In a circle of infinity
But he must, he must, he must
Put a number to it

Tradotto in italiano:

Uomo dolce, gentile e sensibile
Dalla natura ossessiva e profondamente affascinato
Dai numeri
E completamente infatuato del calcolo
Di π

Oh, lui ama, lui ama, lui ama
Lui ama davvero i suoi numeri
E lo portano, lo portano, lo portano
In un grande grande cerchio
In un cerchio di infinito.

3.1415926535 897932
3846 264 338 3279

Oh, lui ama, lui ama, lui ama
Lui ama davvero i suoi numeri
E lo portano, lo portano, lo portano
In un grande grande cerchio
In un cerchio di infinito.
Ma lui deve, lui deve, lui deve
Metterci sopra un numero.



E Thoman Mann? Uno dei personaggi minori del celebre romanzo "La montagna incantata", una delle opere fondamentali di Mann, è il procuratore Paravant, malato di tubercolosi e ricoverato nel sanatorio sulle Alpi svizzere in cui è ambientata la storia. Paravant non sembra molto diverso dal matematico "dolce, gentile e sensibile" e "completamente infatuato del calcolo di π", cantato da Kate Bush:

I suoi discorsi si aggiravano sempre e con tremenda monotonia intorno al rapporto pi greco, a questa disperata frazione che l’umile genio di un calcolatore mentale di nome Zacharias Dase calcolò fino a duecento decimali, ma per puro lusso, perché le possibilità di avvicinarsi all’irraggiungibile esattezza non si esaurirebbero neanche con duemila cifre, e anzi rimarrebbero tali e quali. Tutti scansavano il tormentato pensatore poiché chi gli capitava tra le grinfie era costretto a sorbirsi torrenti di parole infocate, miranti a destare la sua umana sensibilità per la vergogna che lo spirito umano sia contaminato dalla funesta irrazionalità di quel mistico rapporto. L’inutilità di moltiplicare in eterno il diametro per pi greco al fine di trovare la circonferenza, il quadrato del raggio per pi greco al fine di trovare la superficie del cerchio, procurava a Paravant attacchi del dubbio se dopo i giorni di Archimede l’umanità non si sia creata eccessive difficoltà e la soluzione del problema non sia invece puerile e semplicissima. Come? non si dovrebbe poter rettificare la circonferenza né pertanto piegare a cerchio qualunque retta? Certe volte il procuratore si credeva prossimo a una rivelazione. Spesso lo si vedeva, la sera tardi, nella sala da pranzo ormai deserta e scarsamente illuminata, ancora seduto alla sua tavola, sul cui piano sgombro disponeva accuratamente un pezzo di spago in forma di cerchio e poi, con gesto improvviso, lo stendeva formando una retta, e infine, con la testa fra le mani, si concentrava in amare riflessioni. Il consigliere gli dava talvolta una mano in quel malinconico trastullo e, in genere, incoraggiava il suo grillo. Anche a Castorp ricorse una volta il paziente col suo cruccio adorato, una e piú volte, perché aveva incontrato molta e amichevole comprensione nonché profonda simpatia per l’enigma del circolo. Illustrò al giovane la disperata situazione del pi greco presentandogli un disegno a tratti finissimi dove, con enorme fatica, era stato tracciato un cerchio tra due poligoni, l’uno inscritto e l’altro circoscritto, con innumerevoli piccolissimi lati, fino all ultima approssimazione umanamente possibile. Il resto invece, la curvatura che, su un piano etereo dello spirito, rifiuta di essere razionalizzata mediante la calcolabile circoscrizione, quella, disse il procuratore con la mandibola tremante, quella è il pi greco! Castorp, per quanto ben disposto, si rivelò meno sensibile al pi greco di quanto non fosse il suo interlocutore. Lo chiamò una burletta, consigliò il signor Paravant di non accalorarsi troppo nel giocare ad acchiapparlo e parlò dei punti senza dimensione, dei quali si compone il circolo dal non esistente principio alla fine non esistente, nonché della petulante malinconia insita nell’eternità in sé ricorrente senza direzione e durata: parlò con cosí pacati accenti religiosi da esercitare sul procuratore un transitorio influsso calmante.
(da "La montagna incantata" di Thomas Mann, traduzione di E. Pocar, Corbaccio, pagg. 593-594)

Il brano di Mann fa riferimento allo stretto legame esistente tra la determinazione esatta del valore di pi greco e l'antico problema della quadratura del cerchio: costruire, con riga e compasso, un quadrato che abbia la stessa area di un dato cerchio. Dato che un cerchio ha un'area di πr², il quadrato di pari superficie dovrebbe avere un lato di r moltiplicato per la radice quadrata di π. Il problema quindi si riduce alla determinazione di questa radice quadrata con il solo ausilio di riga e compasso.

Perfino Dante parla del problema della quadratura del cerchio, e lo fa nel momento finale e culmimante della sua Divina Commedia: verso la fine dell'ultimo Canto del Paradiso, quando il sommo poeta affronta una delle questioni teologiche più complesse, e cioè il mistero dell'incarnazione e della coesistenza tra natura divina e umana di Cristo.
Per far comprendere la difficoltà del problema, Dante lo paragona all'antico enigma della quadratura del cerchio, che a quell'epoca era ancora ben lontano da una risoluzione.

Qual'è 'l geomètra che tutto s'affige
per misurar lo cerchio, e non ritrova,
pensando, quel principio ond'elli indige,
tal era io a quella vista nova:
veder voleva come si convenne
l'imago al cerchio e come vi s'indova;
ma non eran da ciò le proprie penne:
se non che la mia mente fu percossa
da un fulgore in che sua voglia venne.
(Paradiso, XXXIII, 133-141)

Quasi sei secoli dopo Dante, precisamente nel 1882, il matematico tedesco Ferdinand von Lindemann scrisse la parola "fine" nella storia del quadratura del cerchio. Dimostrò infatti che π è un numero "trascendente", o, equivalentemente, non "algebrico", cioè non può essere determinato come soluzione di un'equazione del tipo P(x) = 0, dove P(x) è un polinomio di grado n con coefficienti interi.
Insomma, π è un numero strano, che salta fuori dappertutto (non solo in geometria, ma in tutti i rami della matematica), ma al tempo stesso non si lascia costruire ed afferrare in nessun modo.
Un altro celebre numero trascendente è la costante di Nepero e, base dei logaritmi naturali.
Poiché con riga e compasso è possibile costruire soltanto numeri "algebrici", la dimostrazione di Lindemann della trascendenza di π decretò anche l'impossibilità del problema della quadratura del cerchio.

Il cerchio, insomma, non si può "quadrare", e il procuratore Paravant, quindi, si affannava inutilmente su un problema impossibile. La scoperta di Lindemann, tuttavia, non ha interrotto i tentativi di determinare il valore di π con crescente precisioneche anzi continuano ancora oggi con grande fervore. L'unico limite, del quale i matematici sono ben consapevoli, è che non si potrà mai arrivare a determinare un valore esatto, e nemmeno una formula algebrica che fissi una volta per tutte quel numero sfuggente.

La grande poetessa polacca Wislawa Szymborska, premio Nobel per la letteratura nel 1996, ha dedicato una poesia all'inafferrabilità di π.

E' degno di ammirazione il pi greco
tre virgola uno quattro uno.
Anche tutte le sue cifre successive sono iniziali,
cinque nove due, poiché non finisce mai.
Non si lascia abbracciare sei cinque tre cinque dallo sguardo,
otto nove dal calcolo,
sette nove dall’immaginazione,
e nemmeno tre due tre otto dallo scherzo, ossia dal paragone
quattro sei con qualsiasi cosa
due sei quattro tre al mondo.
Il serpente più lungo della terra dopo vari metri s’interrompe.
Lo stesso, anche se dopo un po', fanno i serpenti delle fiabe.
Il corteo di cifre che compongono il pi greco
non si ferma sul bordo della pagina,
è capace di srotolarsi sul tavolo, nell’aria,
attraverso il muro, la foglia, il nido, nuvole, diritto fino al cielo,
per quanto è gonfio e senza fondo il cielo.
Quanto è corta la treccia della cometa, proprio un codino!
Com'è tenue il raggio della stella che s’incurva in ogni spazio!

E invece qui due tre quindici trecento diciannove
il mio numero di telefono il tuo numero di collo di camicia
l’anno mille novecento settanta tre sesto piano
il numero degli inquilini sessantacinque centesimi
la misura dei fianchi due dita una sciarada e una cifra,
in cui vola e canta, usignolo mio
e si prega di mantenere la calma,
e anche la terra e il cielo passeranno,
ma non il pi greco, oh no, niente da fare,
esso sta lì, col suo cinque ancora passabile,
un otto niente male,
un sette non ultimo,
incitando, eh sì, incitando l'indolente eternità
a durare.

da "Grandi numeri" (1976) di Wislawa Szymborska
(traduzione di Alessandra Czeczott)



Insomma, il "corteo di cifre" di π è "capace di srotolarsi... diritto fino al cielo"; questa ineffabile infinità, oltre a ossessionare matematici di ogni epoca, è stata sfruttata a proprio vantaggio nientemeno che dal capitano Kirk in un episodio della serie classica di Star Trek.



Nella puntata "Wolf in the Fold", infatti, una misteriosa entità aliena prende il controllo del computer principale dell'astronave Enterprise, e minaccia di uccidere tutti i componenti dell'equipaggio. Kirk ordina allora al computer di calcolare π fino all'ultima cifra: di fronte all'impossibilità del compito, l'entità, per evitare di impazzire, non può fare altro che abbandonare il computer, restituendo la tranquillità a Kirk e compagni.
Che dire? Lunga vita e prosperità... a π!

La matematica invisibile di Calvino

In un blog che si chiama "Mr. Palomar" è d'obbligo parlare, almeno ogni tanto, di Italo Calvino. Ma che c'entra Calvino con la matematica? C'entra, eccome.
Potrei ricordare che il grande narratore crebbe un una famiglia di scienziati (il padre era agronomo, la madre era laureata in matematica e in scienze naturali, quattro zii erano chimici); potrei riprendere una delle molte frasi di Calvino sulla scienza, già citata in un mio post: "l'atteggiamento scientifico e quello poetico coincidono: entrambi sono atteggiamenti insieme di ricerca e di progettazione, di scoperta e di invenzione"; e potrei sottolineare la svolta combinatoria e metanarrativa che Calvino imboccò a partire dalla fine degli anni Sessanta, con opere quali "Il castello dei destini incrociati", "Le città invisibili" e ovviamente "Palomar".

Sono forse le "Città invisibili", pubblicate nel 1972, il romanzo in cui si fanno più appariscenti i risultati della ricerca combinatoria dell'autore ligure.
Il romanzo è costituito dalle 55 descrizioni di città (tutte contraddistinte da classicheggianti nomi femminili) che Marco Polo riferisce a Kublai Khan. Le descrizioni sono raccolte in 9 capitoli, ciascuno dei quali viene aperto e chiuso da un dialogo tra il viaggiatore veneziano e l'imperatore mongolo. Fin qui nulla di particolare. Ma le 55 descrizioni, al di là del raggruppamento nei 9 capitoli, sono anche catalogate in 11 "serie" tematiche:



Le città e la memoria
Le città e il desiderio
Le città e i segni
Le città sottili
Le città e gli scambi
Le città e gli occhi
Le città e il nome
Le città e i morti
Le città e il cielo
Le città continue
Le città nascoste

Il modo in cui le 11 serie si alternano all'interno dei 9 capitoli costituisce una interessante questione strutturale e matematica, che nel corso degli anni è stata da molti analizzata e interpretata.
Certo, questa componente architettonica non esaurisce la complessità e la ricchezza degli spunti offerti dalle "Città invisibili": potrei citare la sottile distinzione tra realtà e invenzione, le difficoltà della comunicazione, il raffinato gioco a quattro tra gli autori-creatori di città, cioè Calvino e Marco Polo, e gli ascoltatori-fruitori, cioè Kublai Khan e il lettore del romanzo.
Per non parlare della fascinazione che abbiamo sperimentato nella lettura di queste descrizioni visionarie e surreali.

Ma perdonatemi: è mio dovere tornare all'aspetto combinatorio e strutturale. E vi assicuro che si tratta di un tema non meno affascinante dei temi ai quali ho accennato poco fa.
Lo stesso Calvino, nel corso di una conferenza che tenne in inglese, il 29 marzo 1983, agli studenti della Graduate Writing Division della Columbia University di New York (testo poi pubblicato dalla rivista americana "Columbia" e, nella traduzione italiana, utilizzato come presentazione dell'edizione delle "Città invisibili" negli Oscar Mondadori), spiegava:

"E' sulla base del materiale che avevo accumulato che ho studiato la struttura migliore, perché volevo che queste serie si alternassero, si intrecciassero, e nello stesso tempo il percorso del libro non si distaccasse troppo dall'ordine cronologico in cui i singoli pezzi erano stati scritti. Alla fine ho deciso di fissarmi su 11 serie di 5 pezzi ciascuna, raggruppati in capitoli formati da pezzi di serie diverse che avessero un certo clima in comune. Il sistema con cui le serie si alternano è il più semplice possibile, anche se c'è chi ci ha studiato molto per spiegarlo."

E' vero che molti hanno cercato di spiegare il meccanismo escogitato da Calvino ricorrendo ad artifici inutilmente complicati. Eppure si tratta di un gioco molto semplice, quasi banale: "il più semplice possibile", come disse lo stesso autore.
Riprendiamo i titoli delle 11 serie, nello stesso ordine di prima:
Ora costruiamo una specie di finestra scorrevole (la evidenziamo in arancione), con un'ampiezza tale da comprendere 5 titoli alla volta, e facciamola scivolare sulla nostra lista, contenendo all'inizio soltanto il primo titolo della lista e scendendo gradualmente verso il basso. La figura seguente illustra i primi tre passi del procedimento.



Nelle figure seguenti viene completato il giro completo dello scorrimento della finestra.








Tutto qui: aveva ragione Calvino a definire il sistema con cui le serie si alternano come "il più semplice possibile". L'ordine in cui le serie fanno la loro comparizione all'interno dei capitoli è regolato dal meccanismo che abbiamo appena illustrato, con l'unica particolarità che i primi 4 passi dello scorrimento della finestra mobile vanno a confluire tutti nel primo capitolo, e analogamente gli ultimi 4 passi del giro completo servono a definire la scaletta dell'ultimo capitolo: questo per dare sufficiente corpo ai primi e agli ultimi capitoli, cioè per evitare che venissero a crearsi capitoli costituiti soltanto da uno o due descrizioni.
Il primo capitolo delle "Città invisibili" risulta così costituito da "pezzi" appartenenti alle seguenti serie:

Le città e la memoria. 1.
Le città e la memoria. 2.
Le città e il desiderio. 1.
Le città e la memoria. 3.
Le città e il desiderio. 2.
Le città e i segni. 1.
Le città e la memoria. 4.
Le città e il desiderio. 3.
Le città e i segni. 2.
Le città sottili. 1.


Il secondo capitolo è definito dal quinto passo del giro di scorrimento, il primo "completo":

Le città e la memoria. 5.
Le città e il desiderio. 4.
Le città e i segni. 3.
Le città sottili. 2.
Le città e gli scambi. 1.


Dal terzo all'ottavo capitolo si procede analogamente, utilizzando i successivi passi dello scorrimento della finestra mobiile, mentre il nono e ultimo capitolo, come anticipato, corrisponde agli ultimi passi "incompleti" e risulta formato da "pezzi" appartenenti alle seguenti serie:

Le città e i morti. 5.
Le città e il cielo. 4.
Le città continue. 3.
Le città nascoste. 2.
Le città e il cielo. 5.
Le città continue. 4.
Le città nascoste. 3.
Le città continue. 5.
Le città nascoste. 4.
Le città nascoste. 5.


Ecco quindi il semplicissimo meccanismo escogitato da Calvino per inquadrare le sue 55 descrizioni di città in 11 serie e 9 capitoli: e a questo punto non posso impedirmi di ricordare come l'autore delle "Lezioni americane" considerasse la semplicità come un obiettivo che richiede un complesso lavoro per esser raggiunto: una qualità che non ha nulla a che spartire con la superficialità, ma che anzi è strettamente connessa alla leggerezza, una delle "sei proposte per il nuovo millennio". Più matematico di così!

Carnevale della matematica #41: goto Proooof

L'edizione numero 41 del Carnevale della Matematica è ospitata dal blog "Gli studenti di oggi" di Roberto Zanasi, alias Zar.
Accanto ai blogger ormai consolidati, questo mese hanno fatto il loro esordio un paio di new entry: "Hard Theorems" di Massimo Lauria, e Natura & Matematica di Cristofaro Sorrentino.
Anche questo mese Mr. Palomar non ha abbondato quanto a contributi: l'ultimo mese ha partorito soltanto il post sul cubo Soma e quello sul gioco musicale di Mozart, di cui ho parlato nell'ultima edizione di Moebius su Radio 24.
Buona lettura e buon Carnevale a tutti!

Mr. Palomar gioca a dadi sabato 10 a Moebius su Radio 24

Sono felice di annunciarvi che interverrò alla prossima puntata della nota trasmissione scientifica Moebius in onda sabato prossimo, 10 settembre, alle ore 20 (e in replica domenica alle ore 23), su Radio24.
Durante la trasmissione si parlerà di Mr. Palomar e soprattutto si giocherà a dadi, ricordando il gioco di Mozart di cui ho parlato nel post precedente.
Ringrazio lo staff di Moebius e in particolare i conduttori Federico Pedrocchi e Chiara Albicocco per la straordinaria opportunità che mi hanno offerto.
Buon ascolto a tutti!

Mozart gioca a dadi

Nel 1793 venne pubblicato, simultaneamente a Berlino e ad Amsterdam, un "Musikalisches Würfelspiel" ("Gioco di dadi musicale"), utilizzabile per comporre minuetti "senza la minima conoscenza della musica, tirando due dadi".
Il gioco ebbe subito un grandissimo successo: in pochi anni moltissime case editrici europee lo ristamparono, e vennero pubblicate versioni economiche e di lusso.

Il dettaglio più interessante è però rappresentato dall'autore di questo "divertimento": niente meno che Wolfgang Amadeus Mozart!
Tra la seconda metà del Settecento e l'inizio dell'Ottocento questo tipo di giochi musicali diventarono molto popolari in Europa, e oltre a Mozart anche altri compositori di grande rilevanza, come Carl Philip Emanuel Bach e Haydn ne furono attratti.

Il "Musikalisches Würfelspiel" mozartiano permetteva di comporre, in modo automatico, un minuetto strutturato secondo la forma tripartita in auge a quell'epoca: una prima parte, cioè il minuetto vero e proprio, una parte centrale detta "trio" perché originariamente era assegnata a tre strumenti solisti, e una terza parte che riproponeva il minuetto iniziale.
I minuetti e i trii dell'epoca erano costituiti tipicamente da 16 battute, e la loro struttura poteva basarsi su schemi abbastanza standard. Questa semplicità strutturale rappresentò per Mozart il requisito necessario per poter concepire l'idea di una composizione automatica.
Per comporre il minuetto, il gioco prevedeva l'utilizzo di una tabella con 11 righe e 16 colonne. In ognuna delle caselle risultanti era presente un numero da 1 a 176, che rimandava ad un libretto nel quale erano trascritte 176 battute composte da Mozart.
Le 16 colonne della tabella corrispondevano alle 16 battute del minuetto. Lanciando, per ciascuna delle 16 battute, due dadi e sottraendo 1 dal punteggio totale si otteneva un numero da 1 a 11. Consultando il libretto con il numero presente all'intersezione tra la colonna del numero di battuta e la riga determinata dal lancio dei dadi, si trovava la battuta mozartiana da utilizzare.
Seguendo questo procedimento il "giocatore" si ritrovava in mano un bel minuetto di 16 battute. E il trio da usare come parte centrale? Il procedimento era del tutto analogo, ma in questo caso la tabella da utilizzare aveva soltanto 6 righe, cosa che rendeva possibile utilizzare un solo dado.

Da notare che, lanciando due dadi, le 11 combinazioni possibili non hanno tutte la stessa probabilità: ad esempio il punteggio 7 è molto probabile, perché si ottiene con 6 diverse combinazioni, mentre il 2 o il 12 si ottengono con una sola combinazione. Alcuni minuetti, quindi, sono più probabili di altri, e non sappiamo se Mozart abbia tenuto conto di questo, ad esempio facendo corrispondere le battute "meglio riuscite" ai lanci di dadi più probabili.

La bravura di Mozart fu, in ogni caso, quella di scrivere battute che potessero adattarsi bene l'una con l'altra, cosa non banale anche in un contesto tonale come quello ovviamente scelto dal genio salisburghese.

Quanti possibili minuetti sono possibili con questo gioco? Per ognuna delle 16 battute del tema principale ci sono 11 battute possibili: quindi le combinazioni possibili sono in tutto 11¹⁶. Analogamente, il gioco consente la composizione di 6¹⁶ trii. Poiché il minuetto come forma musicale tripartita è dato dalla combinazione di un minuetto e di un trio, abbiamo in tutto 11¹⁶ x 6¹⁶ = 129.629.238.163.050.258.624.287.932.416 diverse composizioni possibili, cioè circa 129 miliardi di miliardi di miliardi!

Leggendo queste righe vi è venuta la voglia di giocare anche voi al "Musikalisches Würfelspiel" e comporre piacevolissimi minuetti mettendo insieme le battute del grande Amadeus? Andate all'indirizzo http://sunsite.univie.ac.at/Mozart/dice: e buon divertimento!

Meraviglie possibili e impossibili con il cubo Soma

Nei giorni scorsi ho passato qualche giorno a Torino, città che in questo periodo offre numerosi spunti culturali di altissimo livello, in gran parte legati alla celebrazione dei 150 anni dell'unità d'Italia: proposte che uniscono l'antico con il moderno, in una meravigliosa dimostrazione di eccellenza italiana.
Nel corso delle mie esplorazioni torinesi, ho visitato la magnifica reggia della Venaria Reale, nella quale trova posto una specie di tempio del gioco al quale è stato dato il nome di "Fantacasino". Qui ho trovato, con mia grande sorpresa, un paio di rompicapi matematici realizzati in legno e offerti al divertimento dei visitatori: le torri di Hanoi (delle quali ho parlato in un mio precedente post) e il celebre cubo Soma.
Il cubo Soma fu inventato da un genio dei rompicapi matematici: il danese Piet Hein.
La vita di Hein sembra uscita da un romanzo: nacque a Copenhagen nel 1905 da una famiglia che tra i suoi antenati vanta un altro Piet Hein, l'eroe nazionale olandese che si distinse all'inizio del Seicento come comandante navale nella guerra degli Ottant'Anni.
Nel 1940, quando la Danimarca fu invasa dai nazisti, il nostro Piet Hein si arruolò come partigiano, e combattè a capo di un gruppo antinazista fino alla fine della guerra.
Si sposò quattro volte, ed ebbe cinque figli.
Nel corso della sua lunga vita, Hein fu matematico, fisico, ingegnere, progettista e inventore, ma anche divulgatore scientifico, poeta e scrittore.
Durante la sua milizia nella resistenza danese, inventò un particolare tipo di poesia breve, chiamato "gruk" o "grook", e pubblicò i suoi primi componimenti antinazisti sul quotidiano danese "Politiken", con lo pseudonimo "Kumbel Kumbel".
Un esempio di gruk? Eccolo:

La via della saggezza

La via della saggezza?
E' evidente
e molto semplice:
sbaglia,
sbaglia
e sbaglia ancora,
ma sempre meno,
meno
e meno.

Come matematico, studiò a fondo una particolare curva, chiamata "superellisse": una sorta di via di mezzo tra un'ellisse e un rettangolo. La superellisse è divenuta un marchio di fabbrica dell'architettura scandinava moderna, ma è stata utilizzata anche in molti oggetti di design e nella progettazione dello stadio Olimpico di Città del Messico.

A noi Piet Hein interessa soprattutto come inventore di giochi e rompicapi matematici, tra i più belli che siano mai stati creati. Il gioco dell'Hex, profondamente studiato dalla "beautiful mind" di John Nash e descritto dal grande Martin Gardner, è suo. Sono suoi anche giochi noti come TacTix, Nimbi, Tangloids, Morra, Tower, Polytaire, Qrazy Qube, Pyramystery.

L'idea del cubo Soma, probabilmente il suo gioco più celebre, gli venne nel 1936, mentre seguiva una lezione di fisica quantistica di Werner Heisenberg. Il grande fisico stava descrivendo uno spazio suddiviso in celle cubiche, e il giovane Hein si trovò a riflettere su quali forme possano essere costruite combinando insieme cubetti uniti tra di loro per una faccia.
Hein concentrò il proprio interesse sulle forme "irregolari", cioè sulle combinazioni di cubetti che presentano delle concavità. Ad esempio, con un solo cubetto o con due cubetti, non è possibile creare forme irregolari; con tre cubetti è possibile creare una sola forma irregolare, illustrata nella figura seguente:



E con quattro cubetti? Hein osservò che potevano essere costruite sei figure irregolari:



Ora, il bello deve ancora venire. Hein provò a contare i cubetti utilizzati per costruire queste sette figure: 3 per l'unica figura da 3 cubetti, 4x6=24 per le 6 figure da 4 cubetti, in tutto 27 cubetti.
Ma... 27 è il cubo di 3! La domanda nacque spontanea nella mente di Hein: non è che combinando opportunamente queste sette figure si possa ottenere un bel cubo 3x3x3?

Hein si mise al lavoro e trovò subito la risposta: sì, è possibile!
La soluzione non è unica: nel 1961 i matematici J. H. Conway e M. J. T. Guy hanno dimostrato che escludendo simmetrie e rotazioni il problema ammette 240 diverse soluzioni.
Certo, trovare il modo giusto di combinare i sette pezzi del cubo Soma non è per tutti facile, e la sfida è un rompicapo appassionante.




Con i sette pezzi base, oltre al cubo 3x3x3 che rappresenta la prima sfida per chi voglia cimentarsi con il rompicapo, è possibile costruire innumerevoli altre forme curiose. Nella figura a lato è illustrata una ipotetica "stanza del matematico", nella quale il tavolo, le sedie e il divano sono tutte figure che si possono ottenere a partire dai sette pezzi base.

Naturalmente non tutte le figure costituite da 27 cubetti possono essere costruite con i sette pezzi base: un po' come accade con i bidimensionali polimini, anche le costruzioni Soma si prestano a interessanti dimostrazioni di impossibilità.



Martin Gardner, nel suo classico "Enigmi e giochi matematici", mostra come le due forme illustrate nella figura seguente non possano essere costruite con i pezzi del cubo Soma.

Della seconda forma, Gardner propone anche una interessante dimostrazione di impossibilità.

Il cubo Soma assomiglia un po' al tangram e un po' ai rompicapi con i polimini (dei quali ho già accennato in questo blog in questo e in questo articolo), ma ha in più il pregio di essere tridimensionale.
Perché Hein scelse questo nome? "Soma" è il nome dell'immaginaria droga descritta da Aldous Huxley nel suo romanzo "Brave New World" ("Il mondo nuovo").
Concludo con un passo da questo romanzo:

...non un momento di riposo... non un momento per sedersi e pensare - ché se per qualche sfortunato caso una tal fessura di tempo si apre nella solida sostanza delle loro distrazioni, c'è sempre il Soma, il delizioso Soma...

Carnevale della matematica #40: goto Popinga

Il Carnevale della Matematica di questo caldo agosto è stato ospitato dal magnifico e prezioso blog dell'amico Popinga ("Scienza e letteratura: terribilis est locus iste") .
La mia segnalazione arriva in ritardo, ma non poteva mancare data la ricchezza di contributi di questa edizione.
Il tema del mese, come sempre non vincolante, era particolarmente affascinante: "Quant'è bella geometria".
Quasi a voler compensare la prolificità del mese precedente, questa volta Mr. Palomar è stato particolarmente taccagno: solo due post, uno soltanto dei quali aveva un vero e proprio contenuto.
Per fortuna altri blogger hanno contribuito con articoli davvero interessanti, assolutamente da leggere: buon Carnevale a tutti!

Un "mostruoso" fiocco di neve

Lo so, in giorni come questi di torrido sole, afa e zanzare, parlare di fiocchi di neve può sembrare anacronistico. Ma tant'è: non si può essere sempre in linea con la stagione; e poi, volete mettere: nei giorni di canicola è più piacevole parlare di neve piuttosto di climi tropicali, o no?
Ebbene, nel 1904, il matematico Helge van Koch,che non a caso era svedese, inventò una curva, oggi nota come "fiocco di neve di Koch", o anche "merletto di Koch", che i colleghi dell'epoca definirono una mostruosità matematica.
Costruire il fiocco di neve di Koch è molto semplice, almeno in teoria. Per prima cosa prendete un triangolo equilatero: per ognuno dei tre lati, dividete il lato in tre segmenti uguali e sostituite il segmento centrale con due segmenti identici che assieme al segmento eliminato costituirebbero un triangolo equilatero. Avrete ottenuto una sorta di stella di David, con 6 punte e 12 lati. Ripetete l'intera operazione per ciascuno dei lati della stella, ottenendo una stella ancora più frastagliata. Nella figura seguente sono mostrati i primi quattro passi della creazione del "mostro" di Koch; nell'animazione successiva è mostrato un numero maggiore di passi della costruzione.

Questo procedimento, proseguito all'infinito, tende verso quello che viene definito "fiocco di neve di Koch".
Perché la creatura del matematico svedese fu definita mostruosa? Alcune sue caratteristiche sono, a ben vedere, molto strane, se non addirittura paradossali.
In ogni passo della sua costruzione, come abbiamo visto, ciascun lato viene suddiviso in tre segmenti, uno dei quali è sostituito da due segmenti uguali: ciò significa che ad ogni iterazione la lunghezza totale aumenta di un fattore 4/3, e quindi il fiocco limite di Koch non può che avere una lunghezza infinita.
Nonostante la linea sia infinita, essa racchiude un'area ovviamente finita, e ciò può apparire, intuitivamente, una contraddizione in termini.

Altre proprietà esotiche della curva sono legate a considerazioni di analisi matematica più avanzate e meno intuitive: la curva è continua, ma non è derivabile in alcun punto.

Il merletto di Koch gode inoltre della stranissima proprietà dell'autosimilarità: ogni parte contiene infatti il tutto, cioè ingrandendo progressivamente un dettaglio si ritrova ogni volta l’immagine di partenza.
Ricordate il mio vecchio post sulla matematica di Ummagumma? Nella copertina "ricorsiva" di quel disco dei Pink Floyd, la foto appesa al muro si ritrovava l'intera scena della copertina complessiva, e così via, per due livelli successivi di profondità.
Nel merletto di Koch accade qualcosa di molto simile: ricorsione e autosimilarità sono concetti molto vicini.

Un'altra caratteristica esotica della curva di Koch è la sua dimensione.
Che cos'è la dimensione di una curva? La questione, per la verità, è molto profonda e non può essere esaurita in poche righe; cercherò comunque di fornire sull'argomento qualche indicazione intuitiva, non necessariamente rigorosa.
Qual è la dimensione di un segmento? Bè, ovviamente 1. E quella di un quadrato? Certamente 2. E quella di un cubo? Non può che essere 3.
Va bene, ma perché? Come di definisce, in generale, la dimensione di un oggetto geometrico? E qual è la dimensione del fiocco di neve di Koch?
Intuitivamente, qual è il quadrato più piccolo che possiamo usare per racchiudere interamente (o, come direbbero i matematici, "ricoprire") un segmento lungo un metro? Ovviamente un quadrato con la diagonale di un metro. E se disponessimo soltanto di quadrati con diagonale di mezzo metro, cioè pari alla diagonale iniziale divisa per N=2? Avremmo bisogno di M=2 quadrati, perché mettendone uno a fianco dell'altro le due diagonali si sommerebbero a raggiungere il metro di lunghezza del segmento da ricoprire. Analogamente, se avessimo soltanto quadrati con diagonale pari a 25 cm (N in questo caso è uguale a 4), avremmo bisogno di M=4 quadrati.
Ebbene, la dimensione dell'oggetto (in questo caso il nostro segmento) è l'esponente al quale dobbiamo elevare N per ottenere M. In questo caso, al variare della grandezza dei quadrati, N ed M sono sempre uguali tra loro, e l'unico esponente che lascia invariato qualsiasi numero è 1. La dimensione di un segmento è quindi 1, come ci aspettavamo.

Se ripetessimo la stessa operazione con un quadrato, otteremmo una dimensione sempre uguale a 2, com'è in effetti la dimensione che ci aspettiamo di assegnare ad un oggetto bidimensionale. E per un cubo si otterrebbe una dimensione 3, risultato del tutto prevedibile e per nulla sorprendente.

E per il fiocco di neve di Koch? Qui la faccenda diventa più strana, se proprio non vogliamo scomodare l'aggettivo "mostruoso".
Inoltre, prenderò in esame non l'intero fiocco di Koch, ma solo un terzo dell'intera curva chiusa: questa porzione corrisponde alla curva che evolve a partire da uno dei tre lati del triangolo iniziale. Quando si parla genericamente di "curva di Koch", si intende proprio questa porzione aperta dell'intero "fiocco".
La dimensione della curva aperta di Koch, comunque, è identica a quella del fiocco di neve di Koch: non spiegherò perché, ma, se potete, credetemi sulla parola.
Se il lato di partenza è lungo 1 metro, possiamo ricoprire la curva finale di Koch con un quadrato la cui diagonale è lunga 1 metro. Se però disponiamo di quadrati con diametro pari a un terzo di metro, allora avremo bisogno di 4 quadrati, come indicato in figura.

Volendo utilizzare quadrati ricoprenti ancora più piccoli, secondo un fattore di rimpicciolimento 3, dovremo sostituire ogni quadrato grande con 4 quadrati più piccoli, e così via indefinitamente.
Per la curva di Koch, quindi, N ed M stanno tra loro come 3 sta a 4. Ora, l’esponente al quale dobbiamo elevare 3 per ottenere 4 è pari a log(4) / log(3), che è circa uguale a 1,2619.
Quindi, per quanto strano ciò possa essere, non possiamo che concludere che la dimensione del fiocco di neve è D = 1,2619.

Esistono quindi oggetti, e il merletto di Koch ne è un rappresentante emblematico, la cui dimensione non è intera. Per giunta questi oggetti godono di quella diabolica proprietà nota come autosimilarità: prendendone un pezzetto si ritrova l'oggetto completo di partenza. E inoltre, come abbiamo visto, si tratta di curve non derivabili.
Caratteristiche troppo bizzarre perché non fossero giudicate "mostruose" dai matematici di un secolo fa. Il matematico francese Charles Hermite affermò addirittura di "ritrarsi con spavento e orrore da questa piaga lamentevole delle funzioni che non hanno derivata".
Oggi oggetti di questo genere non fanno più paura, e vengono chiamati frattali: il fiocco di Koch è, in effetti, una delle prime curve frattali che siano state descritte.

Pitagora

Mosse tabù

Mr. Palomar e il suo amico Mr. Wilson si trovano a passeggiare sulle colline, in una zona molto vasta, caratterizzata da ondulazioni continue, irregolari e disuguali.
I due si inerpicano su ripidi sentieri attraverso i boschi, seguiti da discese erbose e da nuove salite.
- Dovevamo studiare meglio la cartina prima di partire. Qui è tutto un saliscendi! - esclama Mr. Palomar col fiatone.
- Te l'ho detto, la cartina l'ho dimenticata a casa. Ma suvvia, non è piacevole un po' di saliscendi? La verità è che non hai più il fisico.
- Sarà. Ma spero che manchi poco all'arrivo.
- Il punto dove dovremmo arrivare è il punto più basso dell'intera area collinare.
- Me lo hai già detto. Chissà se siamo sulla strada giusta - brontola Mr. Palomar.
- Tranquillo, prima o poi arriveremo!
- Già, prima o poi...
- Piuttosto, visto che il percorso è così ondulato, sarebbe stato interessante portare un altimetro.
- Un altimetro? Sarebbe stata più utile la tua cartina, dove sono indicate le linee altimetriche!
- Ma anche un altimetro potrebbe aiutare. Come ti dicevo, il punto dove dobbiamo arrivare è il punto alla quota più bassa di tutta questa zona.
- Va bene, ma l'altimetro ti dice la quota del punto in cui siamo, non di tutti i punti del territorio!
- Hai ragione, però conoscendo l'altitudine del punto in cui siamo e quella dei punti immediatamente vicini, si può avere un'idea di quale strada intraprendere!
- Mi stai dicendo che non sei più sicuro se stiamo seguendo il sentiero giusto?
- No, tranquillo, sono sicuro. O... quasi.
- Speriamo. Ma l'idea che ti può dare l'altimetro è sicuramente imperfetta. Supponiamo che qui la quota sia di 300 metri, e che sia invece di 350 metri se ci spostiamo di mezzo chilometro a nord, 300 metri se andiamo a ovest, 250 metri a sud e 290 a est. Tu ti incammineresti verso sud, immagino. Però chi ti dice che imboccando quella direzione, mezzo chilometro dopo non si cominci a salire tornando a 300 metri e più? Magari è meglio piegare verso nord, perché dopo l'altura può esserci una discesa verso il punto basso che vogliamo raggiungere! E poi, lasciamelo dire, il tuo altimetro è perfettamente inutile: possiamo vedere a occhio se nelle varie direzioni ci siano salite o discese! Il fatto è che questa informazione potrebbe essere ingannevole.
- Hai perfettamente ragione! Ti concedo che l'altimetro serva a poco. Ed è vero che quell'informazione la puoi ricavare anche semplicemente guardandoti attorno. Ma questa informazione rimane molto utile per trovare la strada giusta.
- Forse. Ma seguendo pedissequamente questo metodo rischi di prendere direzioni del tutte sbagliate.
- Sì, ma non ho finito di spiegarti il mio metodo.
- Sentiamo. Sono tutto orecchi.
- In pratica la regola fondamentale è spostarsi seguendo la direzione che comporta il maggiore abbassamento possibile della quota. Tuttavia, questo può portare ad un problema.
- Quale problema?
- Il problema che tu stesso hai intuito. Seguendo il tuo esempio, se io mi incammino verso sud per scendere ad una altitudine di 250 metri, potrei scoprire, una volta spostatomi nella nuova posizione, che tutte le direzioni attorno a me condurrebbero verso punti più in alto.
- Appunto, è proprio ciò che obiettavo.
- In pratica mi troverei in una specie di buca, dalla quale non posso spostarmi perché qualunque direzione mi farebbe "peggiorare" la situazione, cioè non mi consentirebbe di abbassare la quota corrente.
- Però, pensaci un attimo. Questo potrebbe essere un buon segno: potresti infatti essere arrivato nel punto di destinazione, quello più basso di tutti.
- Certo, ma potrebbe anche essere un falso punto di destinazione. In altre parole, anziché il punto in assoluto più basso della zona, potrebbe essere semplicemente un punto circondato da punti più alti, e tuttavia meno basso del punto che desideriamo raggiungere: insomma, come dicono i matematici, invece del minimo globale, un minimo locale.
- E come si fa allora?
- Rischiamo di rimanere intrappolati in questi "falsi" minimi. Occorre che il nostro metodo consenta di uscire da queste buche.
- Non possiamo farlo finché la regola prescrive di scegliere la direzione che porta verso il maggiore abbassamento della quota. Se siamo finiti in una buca, la quota la possiamo soltanto alzare, non abbassare. Però un aumento "temporaneo" sarebbe l'unico modo per uscire dalla buca: poi potremmo essere premiati trovando una nuova promettente discesa.
- Hai colto perfettamente il nocciolo della questione. Infatti il metodo di cui voglio parlarti ammette, soltanto quando non si può fare di meglio, anche "mosse peggioranti", cioè spostamenti verso quote maggiori, proprio per evitare di restare intrappolati nelle buche.
- Bene, è tutto qui?
- No. C'è un altro problema. Immagina di essere finito in una buca. Come abbiamo detto, potremmo essere già arrivati al nostro traguardo; ma potremmo anche essere finiti in un minimo locale dal quale dovremmo allontanarci per esplorare altre zone. Ammettendo gli spostamenti peggioranti, il nostro metodo ci consente di risalire per un po' uno dei versanti del burrone. Cosa succede subito dopo?
- Dato che il metodo prescrive comunque di seguire la direzione migliore, dovremmo girare sui tacchi e tornare indietro, finendo di nuovo nella voragine. Poi torneremmo a risalire il pendio, e quindi scenderemmo di nuovo, all'infinito.
- Brutta cosa. Il metodo non funziona.
- E' proprio qui che interviene la trovata geniale. Il metodo proibisce di ripetere la stessa "mossa" per un certo tempo. Quindi, quando abbiamo risalito il versante, non possiamo finire nella gola di nuovo perché così facendo ripercorreremmo uno spostamento già effettuato, cosa proibita dal nostro metodo. In questo modo, visto che la mossa rimane "tabù" per un certo numero di spostamenti, abbiamo tutto il tempo di risalire completamente il pendio e metterci "in salvo", allontanandoci dal pericoloso canyon.
- Interessante. Hai inventato tu questo procedimento?
- No. Il metodo che ti ho descritto è noto come "tabu search", o "ricerca tabu", ed è stato ideato dall'informatico americano Fred Glover, verso la fine degli anni Ottanta.
- Viene davvero utilizzato in qualche applicazione?
- Come no. E' una delle tecniche più note e più apprezzate per affrontare difficili problemi di ottimizzazione. Spesso i ricercatori hanno bisogno di risolvere problemi che corrispondono alla ricerca di minimi di funzioni complicate dall'andamento non ben conosciuto: qualcosa di simile al nostro problema di cercare il punto più basso di un territorio del quale non conosciamo l'altimetria.
- E utilizzando questa tecnica, si riesce sempre a trovare il minimo globale?
- Assolutamente no. Il più delle volte il "tabu search", così come altre tecniche simili, permette di avvicinarsi molto alla soluzione migliore; altre volte consente di individuarla con precisione; altre volte ancora non fornisce soluzioni di alta qualità, ma si tratta di casi meno frequenti. In ogni caso, le tecniche come il "tabu search" vengono chiamate "euristiche": la loro caratteristica principale è che utilizzando queste tecniche non è detto che venga trovata sempre la soluzione migliore di tutte.
- E allora, perché queste tecniche vengono utilizzate?
- Perché in molti casi non possiamo fare di meglio. Se abbiamo dimenticato a casa la cartina e non ricordiamo più il sentiero da seguire, l'unica possibilità è affidarsi a metodologie approssimate di questo tipo.
- E' anche il nostro caso? - chiede preoccupato Mr. Palomar
- Temo di sì - risponde Mr. Wilson - Non ricordo più il percorso giusto. Dovremo affidarci alla ricerca tabu per riuscire a tornare a casa!

Carnevale della matematica #39: goto .mau.

Il Carnevale della Matematica di luglio, che coincide con la Presa della Bastiglia, è ospitato dal Fondatore, Maurizio Codogno, alias .mau., in particolare dal suo ormai celebre blog delle "Notiziole"
Il tema del mese riguarda i "giochi matematici" (o "la matematica e i giochi", o "il gioco della matematica"...). Come sempre, il tema non è vincolante: e infatti alcuni blogger si sono attenuti e altri no.
Mr. Palomar ha contribuito con sei articoli (mese abbastanza prolifico...), quattro dei quali riguardano il tema proposto.
Ma la novità più rilevante è la presenza di una nuova partecipante agli eventi carnascialeschi: Cristina Sperlari, insegnante di scuola primaria, con il suo blog "Il piccolo Friedrich".
Buon Carnevale a tutti!

Il gioco della fine del mondo

Hanoi è la capitale dello stato di Vietnam dal 1976, anno della riunificazione tra Vietnam del Nord e Vietnam del Sud. Lo scorso 10 ottobre (un giorno matematicamente molto particolare secondo il calendario gregoriano: 10/10/10) gli abitanti di Hanoi e tutti i vietnamiti hanno festeggiato il millesimo anniversario della costruzione della città, voluta dall'imperatore Lý Thái Tổ che la chiamò Thăng Long, cioè "dragone che si alza in volo".
La città di Hanoi è ben nota, oltre che ai geografi, agli storici e ai viaggiatori, anche agli informatici. Perché mai? Semplicemente perché nel 1883 il matematico francese Edouard Lucas, per attribuire un tocco di esotismo ad un rompicapo di sua invenzione, si inventò una leggenda collegata all'antica città di Hanoi. Secondo la leggenda di Lucas, in un tempio di Hanoi alcuni monaci sono intenti, da tempo immemore, a poggiare dischi d'oro su colonne di diamante, consapevoli che nel momento in cui avranno terminato il loro compito il mondo avrà fine.
Più precisamente, ci sono 3 colonne e 64 dischi di dimensioni diverse. All'inizio dei tempi i dischi erano incolonnati sulla prima colonna in ordine di grandezza, cioè in modo tale che ogni disco poggiasse su un disco più grande (i dischi formavano quindi un cono). Da allora i monaci hanno cominciato a spostare dischi, uno alla volta, rispettando la regola fondamentale secondo la quale è vietato poggiare un disco su un disco più piccolo, e con l'obiettivo supremo di spostare tutti i dischi sulla terza colonna.
Come si risolve il rompicapo? La soluzione che si impara nei corsi di programmazione è un tipico esempio di algoritmo ricorsivo, e anche un eccellente esempio di ragionamento per induzione.
Supponiamo di essere in grado di risolvere il gioco per n dischi, e cimentiamoci nella versione con n+1 dischi. Sulla prima colonna avremo quindi n+1 dischi, che dobbiamo spostare sulla terza colonna. Sapendo risolvere il rompicapo con n dischi, non avremo difficoltà a spostare i primi n dischi dalla prima alla seconda colonna; potremo agevolmente spostare il disco (n+1)-esimo dalla prima alla terza colonna, e infine ripeteremo il procedimento degli n dischi spostando tutti i dischi dalla seconda alla terza colonna.
Siccome il gioco è banalmente risolvibile se n=1 (si tratta semplicemente di spostare un disco dalla prima alla terza colonna), per induzione possiamo concludere che è possibile risolvere il rompicapo per qualsiasi numero n.
Si può dimostrare che il numero minimo di mosse necessarie per risolvere il rompicapo con n dischi è pari a 2ⁿ-1. Se i dischi fossero soltanto 3, basterebbero quindi 2³ - 1 = 7 mosse; con 64 dischi, il numero diventa enorme: i monaci dovrebbero effettuare più di 18 miliardi di miliardi di spostamenti!
Possiamo quindi stare tranquilli: se immaginiamo che per spostare un disco i monaci impieghino un secondo, il mondo finirà tra circa 584 miliardi di anni, un tempo ben superiore a quello necessario a trasformare il Sole nella gigante rossa che inghiottirà anche il nostro pianeta.

Il numero di Dio

Immaginate di dover raggiungere un luogo della vostra città dove non siete mai stati, assolutamente entro una certa ora. Potete aiutarvi con il navigatore, o affidarvi alla vostra conoscenza della città, o ancora chiedere indicazioni a qualche passante. In ogni caso non vi basta semplicemente arrivare, ma avete bisogno di trovare un tragitto ottimale, possibilmente il più breve possibile.
Esistono infatti moltissimi, addirittura infiniti percorsi per arrivare in un certo luogo, e uno di essi è quello che permette di giungere a destinazione nel minor tempo possibile.
Se invece di raggiungere un luogo dovete cimentarvi con un rompicapo, ad esempio il celeberrimo cubo magico di Rubik, o il gioco del quindici, di cui ho parlato in un mio precedente post, la situazione non è molto diversa. Potreste accontentarvi di risolvere “semplicemente” il gioco, cioè portare il cubo, probabilmente disordinato, nella configurazione ordinata con tutte le facce colorate di un solo colore, oppure spostare le tessere del gioco del quindici in modo che i numeri siano tutti in sequenza. Ma se siete giocatori provetti, questo non vi basta: volete trovare la via più breve, che conduce sempre alla disposizione finale ordinata nel minor numero di mosse. Se la trovaste davvero, probabilmente sareste talmente orgogliosi di voi stessi da sentirvi “come un dio”: e ne avreste ben donde! Non a caso un algoritmo, cioè un procedimento ben definito, che consenta di risolvere un rompicapo come il cubo di Rubik o il gioco del quindici con il numero minimo possibile di mosse e riducendo al minimo la quantità di memoria utilizzata viene chiamato “algoritmo di Dio”.
Se il riferimento all’essere supremo può sembrarvi esagerato, sappiate che escogitare una procedura di questo tipo, in genere, non è compito facile. La clausola sull'utilizzo della memoria è a questo proposito importante: riferendoci per esempio al cubo di Rubik, sarebbe facile, in linea di principio, pensare ad una enorme tabella precompilata in cui ad ogni configurazione possibile del cubo viene fatta corrispondere la sequenza ottimale per risolvere il rompicapo. Ma si dà il caso che il giocattolo di Rubik può assumere 43 miliardi di miliardi di possibili configurazioni: produrre e utilizzare una simile tabellona sarebbe poco maneggevole perfino per i computer più potenti.
Albert Einstein disse "Quando la soluzione è semplice, Dio sta rispondendo". Potremmo anche immaginare Dio come un risparmiatore, che predilige le vie che consentono di sprecare meno risorse possibili: non solo il tempo, ma anche lo spazio, cioè la memoria.
Un degno algoritmo di Dio per il cubo di Rubik, quindi, dovrebbe essere sempre capace di determinare la sequenza di mosse più breve per riordinare il diabolico marchingegno, senza ricorrere a giganteschi indici. La ricerca di una procedura di questo tipo è strettamente collegata ad una domanda che molti di noi, giocherellando con il famoso rompicapo, ci siamo posti: quante mosse sono necessarie per risolvere questo puzzle? Equivalentemente: qual è il numero minimo di mosse con cui possiamo certamente risolvere il cubo partendo da una configurazione qualsiasi? Sono certo che avrete già immaginato come i matematici hanno chiamato questo numero. Proprio così: il numero di Dio.
Già nel 1981, quando il cubo magico era all'apice del suo successo in tutto il mondo, il matematico Morwen Thistlethwaite dimostrò che 52 mosse sono sempre sufficienti per risolvere il cubo, partendo da qualsiasi configurazione. Questo significava che il numero di Dio non poteva essere maggiore di 52: ma probabilmente era più basso. Dal 1981 in poi, molti altri matematici cercarono di abbassare quel numero, e ci riuscirono. Nel 1990 si era già arrivati a 42, nel 1992 si scese a 37, e nel 1995 si arrivò a quota 29.
In questo stesso anno Michael Reid si cimentò nel compito opposto: trovare un limite inferiore al numero di Dio, cioè un numero di mosse sotto il quale non si può andare per configurazioni particolarmente "rognose". Reid fissò questo limite a 20.
Il numero di Dio era quindi compreso tra 20 e 29. Il limite superiore non scese per dieci anni, ma nel 2005 scoprì che 28 mosse sono sempre sufficienti. Tra il 2006 e il 2008 il gioco si fece duro, e l'asticella si abbassò per cinque volte, toccando quota 22 nell'agosto 2008.
La ricerca del numero di Dio era ormai giunta alla sua fase decisiva. La risposta definitiva arrivò esattamente un anno fa, nel luglio 2010, quando Morley Davidson, Tomas Rokicki, Herbert Kociemba e John Dethridge dimostrarono che bastano sempre 20 mosse per riordinare i colori del cubo.
Il numero di Dio è quindi 20. Ma come hanno fatto questi matematici a determinarlo? Utilizzando calcolatori potentissimi e software molto sofisticati che hanno esplorato in modo intelligente l'enorme numero di possibili configurazioni. Gli studi di Davidson e colleghi hanno determinato che su un totale di 43 miliardi di miliardi di possibili configurazioni, circa 300 milioni necessitano di esattamente 20 mosse, mentre la stragrande maggioranza delle configurazioni possono essere risolte in un numero di mosse compreso tra 15 e 19.
Per chi volesse saperne di più:
http://www.cube20.org/
http://www.bbc.co.uk/news/technology-10929159