Il "Computus" di Spencer Jones

Domani è Pasqua, e volendo inserire un post di sapore pasquale in un blog di matematica, non potevo che parlare del problema del calcolo della data della Pasqua.
Nei secoli passati si utilizzava la parola latina "computus", senza altre specificazioni, per indicare appunto questo particolare calcolo: prova dell'importanza che veniva attribuita a questo tipo di procedura.
Com'è noto, la Pasqua cristiana cade nella prima domenica successiva al primo plenilunio successivo all'equinozio di primavera. Ad esempio, la prima luna piena della primavera di quest'anno si è verificata lunedì scorso, 16 aprile: quindi per festeggiare la Pasqua dobbiamo aspettare domani. Il plenilunio precedente è stato il 19 marzo, troppo presto per considerarlo un plenilunio di primavera.
Questa curiosa regola per fissare la data in cui celebrare la resurrezione di Cristo fu stabilita al Concilio di Nicea del 325; in base ad essa, la Pasqua non può verificarsi prima del 22 marzo o dopo il 25 aprile. Quest'anno siamo quasi al limite massimo. Un giorno più in là e avremmo celebrato la più importante ricorrenza cristiana insieme alla Liberazione: l'ultima volta che accadde fu nel 1943, quando la seconda guerra mondiale era ancora in corso e il 25 aprile 1945 era di là da venire. La prossima volta sarà nel 2038.
Tre anni fa la Pasqua cadde, al contrario, molto "bassa": il 23 marzo, un solo giorno dopo il limite inferiore. Per vedere una Pasqua festeggiata il 22 marzo si deve risalire addirittura al 1761, e la prossima volta sarà nel 2285!
Come è ragionevole supporre, non tutte le date comprese tra il 22 marzo e il 25 aprile sono ugualmente probabili come date pasquali: ad esempio le Pasque basse sono, come abbiamo visto, piuttosto rare.
La figura seguente illustra la distribuzione statistica: come vedete le date comprese tra il 28 marzo e il 20 aprile sono più o meno equiprobabili, con un curioso picco positivo in corrispondenza del 19 aprile, mentre le date "basse" e "alte" sono progressivamente più rare mano a mano che ci si avvicina ai limiti consentiti.

Come si esegue il "Computus"?
L'algoritmo più famoso è sicuramente quello scoperto dall'onnipresente matematico Carl Friedrich Gauss, ma questa procedura ha il difetto di utilizzare un parametro che varia a seconda dell'intervallo di due secoli che si considera.

Un algoritmo che non presenta questa aspetto "poco elegante" (sono certo che Gauss da lassù mi perdonerà per questa impertinenza) è riportato sul prezioso libro "Astronomical Algorithms" di Jean Meeus (edito da Willmann-Bell), ma venne descritto da Spencer Jones (nella foto accanto) nel suo volume "General Astronomy" del 1922.
Jones fu un illustre astronomo inglese, noto anche per essersi occupato, intorno al 1940, dell'affascinante problema dell'esistenza della vita su altri pianeti.
Il metodo di Jones, valido per il calendario gregoriano e per qualsiasi secolo, richiede, come unico dato di partenza, l'anno X del quale si desidera calcolare la data della Pasqua, e consiste nell'eseguire, in dieci passi, alcune divisioni, per ognuna delle quali occorre annotare quoziente e resto.
La tabella seguente dovrebbe fornire la descrizione completa dell'algoritmo.

       Dividere                 per   quoziente   resto

1)     l'anno X                 19                  a
2)     l'anno X                100        b         c
3)     b                         4        d         e
4)     b + 8                    25        f        
5)     b - f + 1                 3        g        
6)     19a +b -d - g + 15       30                  h
7)     c                         4        i         k
8)     32 + 2e + 2i - h - k      7                  l
9)     a + 11h + 22l           451        m        
10)    h + l -7m + 114          31        n         p

Una volta arrivati in fondo, n indica il mese in cui cade la Pasqua nell'anno X: 3 sta per marzo, 4 per aprile; e p+1 indica il giorno della Pasqua.
Ad esempio, prendiamo X = 2011. Dividendo 2011 per 19 otteniamo il resto a=16 (passo 1), e dividendolo per 100 otteniamo il quoziente b=20 e il resto c=11 (passo 2).
Se dividiamo b=20 per 4 (passo 3), il quoziente è d=5 e il resto è e=0; nel passo 4, b+8=28 va diviso per 25, fornendo il quoziente f=1.
Il passo 5 ci chiede di dividere b - f + 1 = 20 per 3, e otteniamo il quoziente g=6.
Nel passo 6, dividiamo 19a +b -d - g + 15 = 328 per 30, annotandoci il resto h=28.
Dividendo poi c=11 per 4 (passo 7), otteniamo il quoziente i=2 e il resto k=3.
Al passo 8, calcoliamo 32 + 2e + 2i - h - k = 5 diviso 7, e il resto è l=5.
Dividendo a + 11h + 22l = 434 per 451 (passo 9), otteniamo il quoziente m=0, e infine (passo 10), dividiamo h + l -7m + 114 = 147 per 31, ricavando il quoziente n=4 e il resto p=23.
Il valore n=4 ci dice che la Pasqua cadrà in aprile, e p+1=24 ci fornisce il giorno esatto, domani appunto.
Buona Pasqua a tutti i lettori di Mr. Palomar!

Strani sonetti

Sicuramente molti lettori hanno già sentito parlare dell'OuLiPo, e sanno cos'è: un gruppo di scrittori di lingua francese, fondato nel 1960, che inventò interessanti tecniche di scrittura "vincolata", spesso legate a criteri matematici.
Due celebri membri dell'OuLiPo furono Raymond Queneau, autore de "I fiori blu", di "Zazie nel metro" e degli "Esercizi di stile", e Georges Perec, che, come già raccontato in questo blog, utilizzò un quadrato greco-latino per dare una struttura al suo romanzo "La vita, istruzioni per l'uso".
Sulle tecniche di scrittura oulipiane si potrebbero riempire centinaia di post di interesse matematico: ma vorrei limitarmi ad un esempio piccolo piccolo, che vi propongo in forma di enigma domenicale.
Uno dei componenti dell'OuLiPo, certo meno noto di Perec e Queneau, fu Jacques Bens (1931-2001), il quale inventò una forma alternativa di sonetto, e riempì addirittura un intero libro con 41 esempi di questa nuova struttura.
Il sonetto classico è formato da quattordici versi, di solito endecasillabi, raggruppati in strofe composte rispettivamente da 4, 4, 3 e 3 versi (in totale appunto 14).
Per illustrare la struttura classica del sonetto propongo il seguente celebre esempio dantesco:

Tanto gentile e tanto onesta pare

Tanto gentile e tanto onesta pare
la donna mia quand'ella altrui saluta,
ch'ogne lingua deven tremando muta,
e li occhi non l'ardiscan di guardare.

Ella si va, sentendosi laudare,
benignamente d'umiltà vestuta;
e par che sia una cosa venuta
da cielo in terra a miracol mostrare.

Mostrasi sì piacente a chi la mira,
che dà per li occhi una dolcezza al core,
che 'ntender no la può chi non la prova:

e par che de la sua labbia si mova
uno spirito soave pien d'amore,
che va dicendo a l'anima: Sospira.

Il sonetto di Bens utilizza invece una struttura di strofe costituite rispettivamente da 3, 1, 4, 1 e 5 versi. Eccone un esempio:

Mélancolique

Je vais donc retrouver mes anciens horizons,
Cette odeur pas perdue des vents et des maisons.
J’ai l’air d’abandonner, mais n’ayez nulle crainte:

Si je quitte Paris, c’est pour le mieux aimer.

On incline à brusquer une banale étreinte.
Mais que vaut cet orgueil qui n’est plus de saison?
Allez donc réunir le cœur et les raisons.
La ville, en souriant, laisse sa rude empreinte:

Si je quitte Paris, c’est pour vous mieux aimer.

Vous mieux aimer, je ne pouvais y croire, mais
Je vois bien qu’aujourd’hui le présent nous emporte.
Il me faut, pour vous voir, m’éloigner quelque peu.
J’enferme mes regrets, puisque cela se peut,
Après avoir glissé ma clé sous votre porte.

Lascio ai lettori due compiti: il primo è tradurre il sonetto dal francese, il secondo, più interessante dal punto di vista della matematica giocosa, è capire il motivo di questa particolare struttura.
Non è affatto difficile, sono sicuro che l'avete tutti capito: il primo che inserirà un commento con la soluzione esatta meriterà un pubblico elogio su un prossimo blog.

Il nodo dei Led Zeppelin

Pochi giorni fa vi ho parlato delle meraviglie matematiche celate nel disco "Ummagumma" dei Pink Floyd. Quell'album uscì nel 1969. Un paio di anni dopo, i Led Zeppelin, altra grande band del rock britannico, realizzarono il quarto album della propria discografia, che essendo privo di un titolo ufficiale passò alla storia come "Led Zeppelin IV".

Il disco ebbe un successo enorme in tutto il mondo, e si stima che furono vendute circa 32 milioni di copie. Una delle canzoni contenute nell'album, "Stairway to Heaven", diventò uno dei brani più celebri della storia del rock.
In "Ummagumma" gli aspetti matematici non si nascondevano nelle canzoni, ma nella copertina: una cosa simile avviene anche in questo disco dei Led Zeppelin, curatissimo negli aspetti grafici e simbolici.

Sul recto della copertina (cioè sul davanti) appare l'immagine di una parete, con la carta da parati sbrindellata: appesa al muro, una vecchia cornice racchiude una fotografia di un contadino con una grossa fascina di legname sulle spalle.

Nell'interno della copertina, si ammira un disegno ispirato alla figura dell'Eremita dei tarocchi, mentre nella quarta di copertina, sopra i titoli delle canzoni, osserviamo quattro simboli misteriosi.
I quattro Led Zeppelin decisero infatti di firmare il loro disco ciascuno con un simbolo scelto personalmente.
Il primo simbolo, quello scelto da Jimmy Page, fu disegnato personalmente dal chitarrista: si trattava di uno strano segno, vagamente rassomigliante alla parola "ZoSo", ma del quale Page non rivelò mai il significato e l'origine.

Anche il quarto dei simboli raffigurati, associato al cantante Robert Plant, era originale, e pare ispirato ad una simbologia legata al mitico continente Mu.
Il secondo e il terzo simbolo, rispettivamente scelti dal bassista John Paul Jones e dal batterista John Bonham, furono trovati sul famoso "Book of Signs" di Rudolf Koch.
Il simbolo di Bonham raffigurava tre anelli intrecciati, associati alla triade di madre, padre e figlio; ma è quello di Jones che merita qualche parola in più in un blog come questo, dato il suo interesse geometrico.

Il nome tecnico della figura scelta dal bassista è "triquetra". Si tratta di una strana forma che si può costruire utilizzando esclusivamente dei cerchi. In che modo? Prendete due cerchi uguali, e intersecateli tra loro come mostrato nella figura a fianco, facendo in modo che il centro di ognuno si trovi sulla circonferenza dell’altro. L’intersezione tra i due cerchi è la figura centrale bianca, detta “vesica piscis”, cioè vescica di pesce, o anche “mandorla”. Questa semplice figura geometrica cela in sé una interessante particolarità matematica. Se calcoliamo il rapporto tra la sua altezza e la sua larghezza, otteniamo esattamente il valore della radice di 3. Gli antichi greci si erano accorti di questa proprietà, che d’altra parte può essere dimostrata per via geometrica abbastanza facilmente.
Per le sue proprietà geometriche e matematiche, la “vesica piscis” è sempre stata un simbolo religioso e mistico, non solo in India, nella Mesopotamia antica e in varie civiltà asiatiche e africane, ma anche nel Cristianesimo. La mandorla venne associata alla figura di Cristo in quanto legata al concetto di seme e quindi simbolo di vita; inoltre, essendo l’intersezione tra due cerchi, apparve come simbolo perfetto di Cristo in quanto ponte tra il mondo materiale e quello spirituale, tra l’uomo e Dio.

Bene, ora che conosciamo e abbiamo imparato a costruire una “vesica piscis”, la possiamo usare per costruire la triquetra: è importante sapere che per raggiungere il nostro obiettivo non ci basterà una “vesica piscis”, e nemmeno due, ma ce ne serviranno ben tre, che dobbiamo sovrapporre tra loro come indicato nella figura qui sotto.


I lettori più smaliziati si saranno però accorti che la triquetra mostrata nella figura non è soltanto una sovrapposizione di tre figure a forma di mandorla: o meglio, può essere vista anche così, ma può anche essere costituita come una linea, intrecciata mirabilmente a se stessa, che disegna il contorno delle tre “vesicae piscis”. Costruita così, la nostra triquetra è a tutti gli effetti un nodo, e in particolare il cosiddetto “nodo a trifoglio”. Gli esperti di araldica riconosceranno in questo tipo di nodo un simbolo molto utilizzato negli stemmi, che riecheggia nel proprio nome la celebre leggenda del nodo di Gordio legata ad Alessandro Magno: il “nodo gordiano”.
Il profilo del nodo a trifoglio e del nodo gordiano differisce da quello della triquetra per il fatto di avere le estremità arrotondate, laddove la triquetra mostra invece le punte che le derivano dalle tre “vesicae piscis”.

Lo studio delle strutture topologiche riconducibili a nodi, cioè a curve chiuse intrecciate nello spazio, occupa nella matematica un posto non trascurabile. La teoria dei nodi ha importanti applicazioni alla fisica, alla chimica e alla biologia. Uno dei primi matematici che studiarono i nodi, già nel Settecento, fu Alexandre-Théophile Vandermonde, che molti studenti o ex studenti associano inevitabilmente al concetto matematico del determinante. In seguito a studiare i nodi furono, oltre che i matematici, anche molti fisici. Lord Kelvin nel 1867 propose la teoria degli “atomi vortice”, secondo la quale gli atomi non sono altro che mulinelli che si muovono nell’etere, annodati tra di loro; per verificare la solidità della teoria Kelvin, aiutato da altri ricercatori, si imbarcò nell’enorme impresa di compilare una tavola di tutti i nodi topologicamente distinti. La teoria degli atomi vortice non resse a lungo, e crollò quando i fisici compresero che l’etere non esisteva; ma le ricerche sui nodi compiute da Kelvin e dagli altri matematici rimasero preziose e vennero continuate. Oggi lo studio matematico dei nodi e dei cosiddetti “link” (cioè collezioni di nodi) rappresenta una delle più complicate, interessanti e attive branche della matematica. Uno dei punti di contatto con la fisica è oggi rappresentato dalla teoria delle stringhe, tra le candidate a fornire una modalità di conciliazione tra la relatività generale e la fisica quantistica.
La triquetra, in particolare, rappresenta, nella teoria dei nodi, l’esempio più semplice di nodo non banale. Se la “vesica piscis” era stata usata come simbolo di Cristo, la triquetra venne spesso associata alla Trinità, e tale associazione appare abbastanza ovvia se consideriamo la natura “triplice” di questa figura.
Il simbolo della triquetra appare spesso nell’arte e nella cultura germanica e in quella celtica.

Insomma, quando John Paul Jones scelse questo simbolo per firmare, assieme agli altri tre Led Zeppelin, il loro capolavoro del 1971, scelse una figura semplice, figlia soltanto di umili cerchi, ma sorprendentemente densa di matematica, di storia, di cultura.

Ancora su scienza e poesia

Scriveva Italo Calvino nel saggio "La sfida al labirinto" del 1962 (nella raccolta "Una pietra sopra"):

L'atteggiamento scientifico e quello poetico coincidono: entrambi sono atteggiamenti insieme di ricerca e di progettazione, di scoperta e di invenzione.

La matematica di Ummagumma (Parte 2)

Quale altra meraviglia matematica emerge dalla copertina di "Ummagumma" dei Pink Floyd?
Osserviamo ancora una volta l'immagine del disco (basta scendere un attimo alla prima parte di questo "multi-post"): al primo "livello" di ricorsività, cioè nella prima delle matrioske, troviamo in primo piano, seduto, il chitarrista David Gilmour; dietro di lui riconosciamo il bassista Roger Waters, seduto appena fuori della soglia di casa; il batterista Nick Mason è in piedi nel prato; e sullo sfondo, nella posizione della candela, scorgiamo il tastierista Rick Wright.
Per spostare la nostra attenzione al secondo dei livelli di ricorsività dobbiamo osservare la fotografia appesa al muro; balza subito all'occhio che qui le posizioni occupate dai musicisti e le pose da loro assunte sono le stesse del primo livello: anche qui uno dei membri della band è seduto sulla sedia in primo piano, un altro è seduto per terra fuori della porta, un terzo membro è in piedi nel prato, e l'ultimo sta a testa in giù sullo sfondo.
Ma si nota altrettanto subito che gli stessi posti non sono occupati dalle stesse persone: la successione Gilmour-Waters-Mason-Wright del primo livello è infatti diventata ora Waters-Mason-Wright-Gilmour.
Detto diversamente, il chitarrista, che nella prima scena appariva in primo piano, ora si trova laggiù in fondo a fare yoga, mentre gli altri tre sono avanzati ciascuno di un posto: in particolare il paroliere-bassista si trova ora davanti a tutti.
Spingendoci nei livelli più profondi del ciclo ricorsivo, cosa che ci richiede uno sforzo visivo non indifferente per scavare nell'immagine, la permutazione si ripete altre due volte con la stessa logica. Al terzo livello la successione diventa, ormai prevedibilmente, Mason-Wright-Gilmour-Waters, mentre all'ultimo livello è Wright-Gilmour-Waters-Mason: è a questo punto che la copertina di "A saucerful of secrets" appesa al muro interrompe il loop.


La tabella precedente illustra la situazione che emerge dalla copertina.
I livelli della ricorsione sono associati alle righe della tabella, e le posizioni (o pose) corrispondono alle sue colonne; nelle caselle intermedie viene indicato quale musicista occupa una certa posizione ad un certo livello.
Non è difficile notare che su ogni riga e su ogni colonna della tabella i quattro componenti del gruppo appaiono ciascuno esattamente una volta.
Ciò equivale a dire che ad ogni livello sono presenti i quattro musicisti, ciascuno dei quali associato ad una delle posizioni standard, e ognuno degli accoppiamenti musicista-posizione è unico, cioè non compare mai in più di un livello.
Una struttura matematica di questo tipo, in cui un certo numero di oggetti (in questo caso i quattro musicisti) sono associati ad altrettanti oggetti (le posizioni) in altrettanti modi tra loro completamente diversi (i livelli) viene chiamata "quadrato latino".


Chiaramente, se a realizzare "Ummagumma" fossero stati, anziché i Pink Floyd, gli Emerson Lake & Palmer, che erano in tre, il gioco si sarebbe dovuto sviluppare su tre livelli e tre posizioni, e non su quattro; analogamente, i Genesis della formazione classica avrebbero dovuto spaziare su cinque livelli e cinque posizioni.
In altre parole, questi gruppi avrebbero creato quadrati latini con lati di tre o cinque caselle, e non di quattro.

A scanso di equivoci, un quadrato latino non ha necessariamente a che fare con la ricorsività: accidentalmente nella copertina di "Ummagumma" intervengono entrambi questi concetti, intrecciati tra di loro (e questa straordinaria coincidenza mi ha ispirato questo doppio post), ma solitamente i quadrati latini non c'entrano nulla con strutture ricorsive.

Un semplice quadrato latino estraneo a questioni di ricorsività lo possiamo realizzare in casa con un mazzo di carte da gioco. Immaginiamo di estrarre i quattro re, le quattro regine, i quattro fanti e i quattro assi, e di voler disporre queste 16 carte in un quadrato 4x4, in modo che su ogni riga e su ogni colonna si trovino tutti i quattro diversi tipi di carte, senza ripetizioni. Vogliamo insomma che sulla prima riga ci siano un re, una regina, un fante e un asso, non importa in che ordine, e lo stesso deve accadere su ciascuna delle altre righe e su ciascuna delle colonne.
Una configurazione che soddisfi questi vincoli (come quella illustrata nella figura a lato) è ovviamente un quadrato latino: in questo caso, infatti, al posto dei quattro Pink Floyd abbiamo le quattro figure (re, regina, fante, asso), mentre le quattro colonne del quadrato giocano il ruolo delle quattro pose della copertina di "Ummagumma".

Il modo più semplice e comune di compilare un quadrato latino di lato N è quello di disporre nella griglia NxN i numeri da 1 a N, facendo attenzione che in ogni riga e in ogni colonna non si abbiano ripetizioni.
Chi si diletta a giocare a sudoku si sarà già reso conto che quel rompicapo altro non è che la ricerca di un quadrato latino 9x9: l'unica complicazione consiste nel fatto che, oltre alle righe e alle colonne, occorre considerare anche le sottogriglie interne 3x3.

Naturalmente nessuno ci impedisce di usare, al posto dei numeri, altri simboli: ad esempio colori (come nel quadrato latino qui a lato), lettere o quello che volete voi.

Ma torniamo al nostro quadrato di carte di gioco, complicando un po' le cose.
Ora non vogliamo soltanto che su ogni riga e su ogni colonna si trovino tutti i quattro tipi di carte, senza ripetizioni, ma anche che su ogni riga e su ogni colonna si trovino tutti i quattro semi, anche loro senza ripetizioni.
Quello che otterremo sarà una specie di sovrapposizione tra due quadrati latini: i matematici la chiamano "quadrato greco-latino".
Come comporre una simile struttura di carte da gioco? Semplice, anzi ce l'abbiamo già! Se andate a controllare, infatti, il quadrato latino che abbiamo creato poco fa con le figure delle carte da gioco, è anche un quadrato greco-latino, se in esso teniamo in considerazione anche i semi delle carte.

Perché queste strutture matematiche vengono chiamate "quadrati latini" e "quadrati greco-latini"? Leonhard Euler, il grande matematico svizzero del Settecento, noto in Italia come Eulero, fu il primo a usare questi reticoli, e introdusse la convenzione di usare, per i primi, lettere dell'alfabeto latino (nello stesso ruolo delle figure del nostro mazzo di carte), e, per i secondi, coppie formate da lettere latine e lettere greche (nel ruolo delle figure e dei semi).
In un post futuro parlerò delle applicazioni dei quadrati latini e greco-latini, soprattutto nella progettazione di esperimenti in biologia, medicina e sociologia, e di come i matematici e gli informatici si siano cimentati a lungo nel problema di ricercare quadrati latini e greco-latini di dimensioni sempre più grandi.

Se la copertina di "Ummagumma", uscita nel 1969, incasellava i quattro Pink Floyd in un sorprendente quadrato latino 4x4, nove anni dopo lo scrittore francese Georges Perec (nella foto sotto) scrisse addirittura un intero romanzo, il celebre "La vita, istruzioni per l'uso", basandosi su un quadrato greco-latino 10x10 (Eulero aveva ipotizzato che non esistessero quadrati greco-latini di tale dimensione, ma si era sbagliato: nel 1959 i matematici Bose, Parker e Shrikhande ne scoprirono uno).
Il blog Popinga ha parlato di questo argomento in un suo post di circa due anni fa (mi scuso quindi se ripeterò qui alcune delle cose scritte in quel post).

Il libro di Perec descrive un condominio parigino costituito da 99 stanze disposte su dieci piani. Ogni capitolo è ambientato in una stanza, ragione per cui il romanzo è composto da 99 capitoli.
Cosa c'entra il quadrato greco-latino 10x10 scoperto nel 1959? E' presto detto.
Perec compilò 42 elenchi (esercizio assai di moda ultimamente), ciascuno formato da dieci elementi che potevano essere utilizzati come "vincoli narrativi". Ad esempio, compose un elenco di citazioni letterarie, uno di località geografiche, uno di animali, e così via.
Divise quindi gli elenchi in 21 coppie, e utilizzò 21 volte il quadrato greco-latino 10x10, riempendone ogni volta le caselle con coppie di elementi presi dai due elenchi, esattamente come noi avevamo disposto, poco fa, coppie di figure e semi in un quadrato greco-latino 4x4.
Ovviamente ogni casella del quadrato 10x10 corrispondeva ad una delle stanze, e quindi a uno dei capitoli del romanzo. Il quadrato greco-latino ebbe quindi l'effetto di far corrispondere ad ogni stanza 21 coppie di elementi presi dai 42 elenchi. Questi elementi furono utilizati da Perec come "vincoli narrativi": ad esempio, una delle coppie associate ad una stanza poteva prescrivere di menzionare, nella narrazione del capitolo corrispondente, una certa citazione letteraria e una particolare località geografica.

La matematica di Ummagumma (Parte 1)

Nel fatidico anno 1969, i Pink Floyd, dopo i primi due album "The piper at the gates of dawn" e "A saucerful of secrets", nei quali era evidente la matrice psichedelica ed era stato fondamentale il contributo di Syd Barrett, realizzarono un disco molto diverso, più orientato verso i canoni del rock progressivo, al quale venne dato un titolo bizzarro: "Ummagumma".
Chi prendesse per la prima volta in mano quest’album, nella sua pregiata versione in vinile, o anche nella meno romantica edizione in CD, sicuramente sarebbe attratto dalla strana immagine di copertina. Alle spalle di David Gilmour seduto in primo piano, si nota una fotografia incorniciata e appesa al muro, e gli altri componenti del gruppo, in posizioni diverse fuori dalla porta di casa.
Fin qui nulla di strano. Ma se osserviamo bene la fotografia sul muro, vi notiamo una scena del tutto simile a quella dell’intera immagine di copertina: questa volta però è Roger Waters a essere seduto in primo piano, gli altri tre musicisti si trovano fuori dalla porta e sul muro, un’altra fotografia analoga alla precedente.

Com’è possibile? Stiamo impazzendo? No, semplicemente ci troviamo di fronte ad un sistema di matrioske, o di scatole cinesi. O, se volete, stiamo osservando un esempio interessante di ricorsività, o ricorsione, come amano dire gli informatici. La ricorsività si viene a creare ogniqualvolta un oggetto contiene una copia di se stesso, o fa in qualche modo riferimento a se stesso. Qualcosa di molto simile all’autoreferenzialità.
E’ chiaro che il gioco ricorsivo della copertina di "Ummagumma" potrebbe concettualmente proseguire all’infinito: ogni fotografia contiene una copia di se stessa, e solo interrompendo la successione in qualche modo si può uscire da questo folle circolo vizioso.
Se guardiamo la copertina ancora più in profondità, in effetti, ci accorgiamo che al quarto livello della ricorsione la fotografia appesa al muro non raffigura più la scena complessiva ma, con un colpo di teatro che ha del geniale, contiene la copertina del precedente album dei Pink Floyd: "A saucerful of secrets"!

Ecco quindi un brillante esempio di ciclo di ricorsione che, dopo un certo numero di ripetizioni, si arresta. E’ come avere un certo numero di matrioske, ciascuna delle quali ne contiene un’altra: prima o poi, inevitabilmente, troveremo una matrioska vuota, o, se volete, una matrioska contenente un oggetto che non è una matrioska.

Gli informatici conoscono bene il concetto di ricorsione, perché per risolvere alcuni problemi o per effettuare certi tipi di calcoli, è comodo servirsi di procedure che, ad un certo punto dell’esecuzione, invocano loro stesse, generando così una sequenza di chiamate che ha termine soltanto quando si verifica una situazione particolare: un po’ come la matrioska vuota o come l’improvvisa comparsa della copertina di "A saucerful of secrets" nella cornice appesa al muro!
Ad esempio, esiste in matematica una funzione particolare, chiamata "fattoriale", molto usata dagli statistici. Com'è noto, il fattoriale di un numero si calcola moltiplicando tra loro tutti i numeri interi da 1 fino a quel numero. Ad esempio il fattoriale di 3 è uguale a 1 x 2 x 3, cioè 6. Quanto è invece il fattoriale di 4? Bè, è uguale a 1 x 2 x 3 x 4, cioè a 24. Ma allora, direte voi, il fattoriale di 4 si può calcolare anche come il fattoriale di 3 (che è 6) moltiplicato per 4!
Immaginate di essere dei programmatori, e di dover scrivere una procedura informatica per calcolare il fattoriale di un numero qualsiasi. Potreste scrivere un programma ricorsivo, che prende il numero di partenza e lo moltiplica per il fattoriale del numero intero immediatamente precedente: ad esempio, come abbiamo visto, per calcolare il fattoriale di 4 usiamo il fattoriale di 3, per calcolare il fattoriale di 3 usiamo quello di 2, e così via.
Attenzione però: una volta arrivati al fattoriale di 0, non potreste ricorrere al fattoriale di -1, perché in questo modo fareste un bel buco per terra e comincereste a scavare nei numeri negativi, all’infinito, creando disastri! Da bravi programmatori dovrete ricordarvi di "A saucerful of secrets" o della matrioska vuota, che in questo caso è il fattoriale di 0: quando si arriva a 0, qui dovete fermarvi, e tener conto che il fattoriale di 0 è semplicemente 1!

Il concetto di ricorsività non appartiene soltanto alla matematica o all'informatica, ma anche, solo per fare alcuni esempi, alle arti figurative, alla letteratura, al cinema. Negli anni settanta, sulla scatola di uno dei prodotti di Droste, una marca olandese di cacao, era disegnata un’infermiera che reggeva in mano un vassoio con una tazza e una scatola della stessa marca. Il giornalista olandese Nico Scheepmaker coniò il termine "effetto Droste", per indicare immagini contenenti versioni ridotte di se stesse.
Un’espressione che è quasi un sinonimo di "effetto Droste" è "mise en abyme", in francese "messo nell’abisso". L’origine del termine va cercata nell’araldica, dove indica uno stemma che contiene un piccolo scudo all’interno di uno scudo più grande. Oggi, si parla di "mise en abyme" soprattutto nella critica letteraria, artistica e cinematografica, per indicare storie ricorsive strutturate a matrioska.


Questa notte ho fatto un sogno strutturato a matrioska:
io sognavo di sognare che un abate un po' cruento
dopo avermi esaminato mi ordinava di svegliarmi.
Io ubbidiente gli ubbidivo, cioè sognavo di svegliarmi
e me lo ritrovavo accanto con quel fare suo cruento,
lui che mi riesaminava, io che gli chiedevo affranto:
"Dimmi, abate, perché insisti nell'esaminarmi attento?
Ho commesso forse un atto che fu inviso all'abbazia?"
Egli, colto alla sprovvista, non sapendo fare meglio,
mi ordinò seduta stante di procedere a un risveglio.
(da "Abate cruento", di Elio e le Storie Tese)

Stefano Belisari, in arte Elio, è laureato in ingegneria elettronica, e certamente la ricorsione come concetto informatico ha un ruolo chiave in questo testo surreale, in cui la procedura "sogno" viene invocata (per usare un termine informatico) due volte: la prima volta, se così posso dire, dal programma principale, e la seconda volta dalla procedura stessa, appunto in modo ricorsivo. In entrambi i casi l'esecuzione della procedura termina a causa del comando dell'abate cruento, il quale ordina di "procedere a un risveglio". Dopo la prima uscita ci ritroviamo all'interno della procedura stessa, al primo livello di ricorsione, e dopo la seconda uscita ritorniamo al livello di partenza, quello del programma principale.

Un celebre esempio è offerto dall’Amleto di Shakespeare, nel quale a un certo punto i personaggi mettono in scena una tragedia che è molto simile all’Amleto stesso: l’Amleto, quindi, contiene dentro di sè un altro Amleto, il quale ne contiene un altro, e così via all’infinito.
Esempi più moderni di "teatro nel teatro" ce li propone Pirandello: nei suoi "Sei personaggi in cerca d’autore", lo spazio rappresentato sul palco del teatro è a sua volta il palco di un teatro, e i personaggi recitano la parte di attori che stanno provando un'altra opera teatrale di Pirandello, "Il gioco delle parti".
La letteratura moderna, d’altra parte, è piena di strutture ricorsive e giochi autoreferenziali, da "Aspettando Godot" di Samuel Beckett, a "Se una notte d’inverno un viaggiatore" di Italo Calvino, a molti racconti di Borges.
Anche il cinema ha fatto spesso uso di vertiginosi giochi di "mise en abyme": si pensi ad esempio al film "eXistenZ" di David Cronenberg, o ad "Inception" dell’anno scorso.


L’arte figurativa, soprattutto quella moderna, non è da meno. In alcuni famosi dipinti raffiguranti pipe, René Magritte compie una riflessione sulla differenza tra realtà e rappresentazione, giocando in modo molto profondo con i paradossi dell’autoreferenza. Ma l’artista che più di ogni altro ha affrontato le sottigliezze della ricorsione è il grafico olandese Maurits Cornelis Escher, famoso per i suoi disegni di costruzioni impossibili, distorsioni geometriche e tassellature del piano: potremmo citare la ricorsività intrecciata in "Mani che disegnano", dove una mano che impugna una matita sta disegnando su un foglio un'altra mano, la quale, a sua volta – ed ecco il paradosso - disegna la prima mano…

Tornando a "Ummagumma", il disco che ha offerto lo spunto per parlare di ricorsività, non posso evitare di notare che questa copertina ci regala anche un altro magnifico pretesto matematico: ma di questo parlerò nel prossimo post.

Audrey Hepburn, la Bocca della Verità e il filosofo ostinato

Mr. Palomar e il suo amico Mr. Wilson sono appassionati di cinema, e amano soprattutto i vecchi film americani degli anni Cinquanta.
Una delle ultime sere si sono trovati per rivedere insieme "Vacanze romane", celebre film del 1953 con Audrey Hepburn e Gregory Peck. In una delle scene della pellicola, ovviamente girata nella Città Eterna, Peck accompagna la Hepburn alla Bocca della Verità, e la invita a provare l'esperienza che ogni turista in visita a Roma ha sperimentato: introdurre la mano per qualche secondo nel temibile buco, sperando di poterla tirar fuori sana e salva. Audrey supera indenne la prova, e pretende poi che anche il suo amico si sottoponga allo stesso esame.
Alla fine del film, Mr. Palomar e Mr. Wilson discutono sulla scena della Bocca della Verità. A un certo punto, Mr. Wilson ipotizza una bizzarra variante alla scena.


- Immagina che Audrey Hepburn, nell'atto di introdurre la mano nella Bocca, avesse detto "Non riuscirò mai a tirar fuori la mia mano!"
- Perché mai dovrei immaginare questo? - ribatte Mr. Palomar.
- Bè, tu immaginalo.
- Va bene, lo immagino. E allora?
- Sai bene che, secondo la leggenda, l'antico mascherone punisce i bugiardi e gli adulteri, mordendo loro la mano.
- Sì, lo so. E con questo? Dove vuoi arrivare?
- Se dobbiamo credere alla leggenda, cosa possiamo dedurre dalla scena modificata?
Mr. Palomar riflette per qualche minuto. E' ormai abituato agli enigmi di logica inventati seduta stante dal suo amico, e tutto sommato non gli dispiace stare al gioco.
- Se Audrey dice che non riuscirà a tirar fuori la mano, significa che è una bugiarda! - risponde alla fine della sua riflessione.
- Esatto. Ma se è bugiarda, anche quello che ha appena detto è una bugia - puntualizza Mr. Wilson.
- Già. Quindi non è vero che non riuscirà a tirar fuori la mano!
- E allora, come la mettiamo?
- Se non è vero che non riuscirà a tirar fuori la mano, vuol dire che la tirerà fuori - deduce Mr. Palomar.
- Di conseguenza, non è più bugiarda! - conclude Mr. Wilson.
- Com'è possibile? - replica Mr. Palomar, sconcertato - é bugiarda o no?
- Siamo caduti in un circolo vizioso. Se non è più bugiarda, ciò che aveva affermato all'inizio è vero, e quindi è vero che non riuscirà a tirar fuori la mano, e quindi è di nuovo bugiarda, e allora...
- Ho capito - lo interrompe Mr. Palomar - Non è possubile uscire da questo cerchio infinito. Gli informatici direbbero che siamo finiti in un loop.
- Non è altro che un paradosso. E anche famoso. Già gli antichi greci lo conoscevano, e lo chiamavano il paradosso del mentitore. Pare che sull'epitaffio di un filosofo greco, un certo Fileta di Cos, ci fosse scritto "Fu il Mentitore a farmi morire, con le cattive notti che mi procurò". Insomma sembra che questo Fileta, nello sforzo ostinato di risolvere questo paradosso, si fosse così spremuto le meningi da rimanerci secco!
- Fatica sprecata, direi. Abbiamo capito facilmente che non c'è via d'uscita.
- Già, ma evidentemente per lui era diventata una questione di orgoglio.
- Oppure semplicemente non aveva avuto la possibilità di vedere il film che abbiamo visto noi. Per cui non aveva capito bene il paradosso.
- Già, e non aveva mai visto Audrey Hepburn. Cosa si sono persi, questi antichi greci.

Come ti decifro i Coldplay

Quando nel giugno del 2005 gli scaffali dei negozi di dischi si riempirono con le copie del nuovo album dei Coldplay, gli appassionati rimasero sorpresi e forse sconcertati da due caratteristiche del disco: il titolo e la copertina.
"X&Y" era sicuramente un titolo enigmatico, ma lo era ancora di più l'immagine di copertina, costituita da misteriosi rettangoli colorati disposti in una configurazione apparentemente insensata.
In realtà, l'immagine non conteneva misteriosi messaggi né clamorose rivelazioni in codice. Semplicemente, le due caratteristiche sconcertanti del disco contenevano la stessa informazione: detto altrimenti, i rettangoli colorati della copertina, decifrate secondo un codice in uso parecchi decenni fa, corrispondevano, in teoria, al titolo "X&Y".
Ho detto "in teoria", perché qualcosa dev'essere andato storto.
Ma andiamo con ordine.
Guardiamo bene la copertina del disco: lasciamo perdere i colori, che non sono essenziali per decifrare il messaggio, e cerchiamo di ridisegnare il reticolo raffigurando in grigio le caselle "piene". Otteniamo una specie di matrice con quattro colonne e cinque righe.


Il codice al quale accennavo poco fa è il cosiddetto "codice Baudot": sviluppato nel 1874, fu utilizzato nelle telescriventi per molti decenni, per essere poi soppiantato dai sistemi EBCDIC e ASCII.
Il codice Baudot venne inventato molti anni dopo il codice Morse. Mentre questo utilizzava cinque diversi simboli base, e cioè il punto, la linea, l'intervallo breve (tra ogni lettera), l'intervallo medio (tra parole) e l'intervallo lungo (tra frasi), il codice Baudot introduceva una semplificazione importante: i simboli utilizzati erano soltanto due, cosa che rendeva binario il sistema di codifica.
Ogni carattere veniva codificato nel codice Baudot con una sequenza di 5 bit, cosa che consentiva all'operatore di utilizzare una tastiera con cinque tasti come quella illustrata nella figura.


Utilizzando soltanto 5 bit per codificare un carattere, sarebbe stato possibile rappresentare soltanto 2 alla 5, cioè 32 caratteri in totale. Un po' pochi, non vi sembra? Le lettere sono già 26, e se aggiungiamo le 10 cifre da 0 a 9 siamo già a quota 36. E non abbiamo nemmeno preso in considerazione i simboli di interpunzione o altri simboli speciali. Per questo Baudot, senza dover aumentare i bit per ogni carattere, ebbe l'idea di suddividere i caratteri rappresentati in due insiemi diversi di caratteri: le lettere e le figure. Le 26 lettere da A a Z appartenevano ovviamente al primo insieme, mentre nel secondo ricadevano tutti gli altri caratteri, tra cui le cifre. Normalmente i caratteri venivano interpretati come lettere, e per indicare che il successivo carattere doveva essere invece interpretato come figura, veniva premesso il carattere speciale "11011" (indicando con "1" il simbolo "pieno" e con "0" il simbolo "vuoto").
Ogni combinazione di 5 bit, ad eccezione dei due caratteri speciali di "passaggio", poteva essere interpretata sia come lettera sia come figura, per cui i caratteri rappresentabili erano in tutto 60.


Alla luce di queste istruzioni, come si decifra il messaggio nella copertina del disco dei Coldplay? Se utilizzate bene la tabella di decodifica, otterrete come risultato "X9Y".
Ohibò, com'è possibile? Ci aspettavamo, ovviamente, "X&Y", cioè il titolo del disco!
Bè, ve l'avevo detto che qualcosa dev'essere andato storto.
Il carattere "&" è codificato, nel sistema Baudot, dalla sequenza "01011", mentre nel reticolo della copertina troviamo la sequenza "00011", che corrisponde a "9" (dato che il secondo carattere del messaggio è "11011", che precede un carattere interpretato come figura). Forse è stato commesso un banale errore di un bit nella preparazione dell'immagine di copertina; o chissà, forse l'errore è stato voluto, per introdurre un motivo in più di discussione tra i fan più "matematici".

All you need is Fourier

Tutti gli appassionati dei Beatles (io compreso) sanno che una delle canzoni più famose del gruppo, "A Hard Day's Night", si apre con uno strano accordo, dissonante e molto attraente. Come fecero i Beatles a ottenerlo? In altre parole, quali note suonarono per creare quella bizzarra armonia?
Pare infatti che, per quanto ci si provi, non sia affatto facile riprodurre alla perfezione l'effetto armonico che scaturì all'inizio di quel brano del 1964. Gli spartiti propongono almeno quattro varianti ufficiali, ma nessuna sembra essere soddisfacente quanto l'originale.
Certo, ai più sembrerà assurdo che qualcuno abbia dedicato tempo ed energie a questo quesito, diciamolo pure, piuttosto ozioso. Eppure si tratta di uno dei grandi "misteri" del rock 'n' roll, sul quale sono stati versati fiumi di inchiostro.
Va bene, sarà pure così, ma la matematica cosa c'entra?
C'entra eccome, al punto che un professore di matematica della Dalhousie University in Canada, tale Jason I. Brown, ha addirittura scritto, qualche anno fa, un articolo molto tecnico per dirimere l'annosa questione.


L'approccio scelto da Brown fa uso di una trasformata di Fourier: l'onda sonora corrispondente al frammento musicale viene analizzata e scomposta in una somma di infiniti termini, ciascuno dei quali rappresenta un'onda perfettamente sinusoidale (un suono puro come quello del diapason), con una sua frequenza propria e una propria ampiezza (o intensità). Ognuno di questi termini corrisponde a quello che i musicisti chiamano "armonica": quello caratterizzato dalla frequenza più bassa è l'armonica fondamentale, mentre gli altri rappresentano le armoniche secondarie, a frequenze multiple della fondamentale, sempre più trascurabili mano a mano che la frequenza cresce, in quanto l'ampiezza diminuisce progressivamente fino a spegnersi.


Se questa faccenda della trasformata di Fourier può apparirci arida e freddamente matematica, non dimentichiamo mai che è alla base di tutta l'armonia: la magia degli accordi e tutta l'arte del contrappunto, della fuga e della polifonia si reggono su questi concetti matematici.
Ha ragione il professor Brown quando afferma che "La musica è essenzialmente matematica". Così come aveva ragione George Gershwin quando disse che la musica è una scienza emozionale.
Ma sto divagando. Brown ha utilizzato, più precisamente, una trasformata discreta di Fourier (DFT, Discrete Fourier Transform): ha infatti campionato il segnale beatlesiano originario, ottenendo una successione di valori numerici, decine di migliaia al secondo, e poi ha applicato la trasformazione per convertire questa successione in un insieme di funzioni semplici, ognuna corrispondente ad una singola frequenza, cioè ad una nota musicale ben precisa.
La DFT è molto popolare anche tra gli informatici (a proposito di collegamenti tra musica e informatica...) perché uno degli algoritmi più celebri e importanti del Novecento è quello proposto nel 1965 da James Cooley e John Tukey per calcolare appunto la DFT (pare che l'algoritmo di Cooley e Tukey, in realtà, non fosse del tutto originale perché basato su una vecchia idea di Carl Friedrich Gauss: già, sempre lui).

Insomma, a quale conclusione ha portato lo studio del professor Brown?
Sulle prime, la ricerca sembrava essersi arenata su un binario morto. Dall'analisi di Fourier effettuata, sembravano uscire infatti troppe note.
Sappiamo che alla registrazione del brano erano presenti George Harrison, con la sua chitarra a 12 corde, John Lennon e la sua chitarra a 6 corde, e Paul McCartney al basso: ma questi strumenti non bastavano a rendere conto di tutte le frequenze rilevate dalla ricerca del professor Brown.
Certo, alcune delle note uscite dall'analisi potevano essere rumore di fondo, ma quali esattamente? Alcuni fatti erano assodati: ad esempio, le note più basse provenivano senz'altro dal basso di McCartney; ogni corda pizzicata da Harrison sulla sua chitarra a 12 corde doveva essere accompagnata dalla corrispondente armonica all'ottava superiore; e così via.


Dopo settimane di tentativi, il professor Brown non era ancora riuscito a spiegare tutte le frequenze: in particolare, restavano alcune armoniche associate ad una nota di Fa, che non poteva essere uscita da nessuno degli strumenti sopra menzionati.
E allora? Chi suonò quel famigerato Fa?
Un giorno Brown ebbe l'idea risolutiva: la nota fantasma deve essere uscita da un pianoforte suonato da George Martin, il cosiddetto "quinto Beatles", produttore del celebre gruppo e autore di indimenticabili arrangiamenti ed orchestrazioni (come in "Yesterday", "Eleanor Rigby" e "Penny Lane").

Mi chiedo però: visto che l'articolo del professor Brown è uscito ormai da diversi anni, nessuno ha ancora pensato di chiedere a George Martin se quel giorno lui si trovasse davvero alla tastiera del pianoforte a registrare con i Beatles, o se invece era in tutt'altre faccende affaccendato?
Ma chi se ne importa, l'importante era parlare un po' di Beatles e di trasformate di Fourier... O no?

San Paolo, i cretesi e Benigni

Nella Lettera a Tito (1,10-16), San Paolo scrive:

Uno dei loro, proprio un loro profeta, già aveva detto: "I Cretesi son sempre bugiardi, bestie malvagie, oziosi ghiottoni”. Questa testimonianza è vera. Perciò correggili con fermezza, perché rimangano nella sana dottrina e non diano più retta a favole giudaiche e a precetti di uomini che rifiutano la verità.

A cosa si riferiva il mio illustre omonimo, folgorato sulla via di Damasco?
Ovvio: al celebre paradosso del mentitore, il classico paradosso logico tradizionalmente attribuito alla figura semi-mitica del filosofo cretese Epimenide, il quale un giorno avrebbe affermato:

Tutti i cretesi sono bugiardi.

Se un cretese ci dicesse che tutti i cretesi sono bugiardi, oltre a sospettare della sanità mentale dell'isolano, per seguirlo saremmo costretti a infilarci in un vicolo logico senza uscita: infatti se fosse vero quel che dice, lo status di mentitore dovrebbe applicarsi anche a lui, e quindi non dovremmo credergli, il che ci porterebbe a ritenere che i cretesi sono tutti bugiardi, e di conseguenza... Aiuto, è proprio un circolo vizioso infinito!

Sul paradosso del mentitore sono stati versati fiumi di inchiostro: oltre ad essere un pallino dei logici (anche per il suo collegamento con il teorema di incompletezza di Gödel), è un cavallo di battaglia dei matematici ricreativi, tra i quali il sempre (giustamente) citato Martin Gardner.

Esistono molte versioni alternative di questo paradosso. Una delle forme classiche è la seguente:

Questa frase è falsa.

Il filosofo francese Jean Buridan, italianizzato in Giovanni Buridano o latinizzato in Iohannes Buridanus, vissuto intorno al 1300, famoso per avere precorso alcuni risultati della fisica moderna, come ad esempio il principio d’inerzia, riformulò il paradosso spezzando la frase in due:

Socrate dice "Platone dice il falso"

Platone dice "Socrate dice il vero"

Prendendo le due frasi separatamente, non troviamo alcun paradosso, ma considerate insieme esse provocano il solito disastro. Se ipotizziamo che Socrate sia sincero, allora Platone mente; ma allora Socrate non dice il vero, e ciò confuta la nostra ipotesi iniziale: Socrate è bugiardo, e quindi Platone è sincero. Ma allora Socrate dice il vero, e così via, in una nuova slavina di contraddizioni. Se partiamo con un’assunzione opposta, cioè che Socrate sia bugiardo, ricadiamo nella stessa catena di antinomie e non possiamo stabilire chi tra Socrate e Platone dice il vero e chi dice il falso.

Un’altra versione famosa del paradosso è quella che lo storico Diogene Laerzio attribuisce al filosofo Eubulide di Mileto, vissuto nel IV secolo a.C. L’affermazione paradossale di Eubulide è sintetizzata in una frase di una sola parola (greca):

ψευδόμενος

cioè "io sto mentendo".
La formulazione di Eubulide è più interessante di quella di Epimenide, sia perché egli focalizza la sua affermazione su di sé, cioè enuncia una frase autoreferenziale, sia perché con l'espressione "sto mentendo" anziché "sono bugiardo", Eubulide non lascia spazio all’eventualità che la frase stessa possa essere vera.
Già, perché quando diciamo che una persona è bugiarda, non intendiamo dire che costui dica sempre bugie appena apre bocca. Ogni tanto, anche un uomo bollato come mentitore una piccola verità la dirà pure, o no?.
Come ha detto una volta Roberto Benigni: "Anche Adolf Hitler o Stalin, un ponte, una strada l'avranno fatta. Anche il Mostro di Firenze l'avrà detto 'buongiorno' a qualcuno qualche volta!"
Concedendo allora che di tanto in tanto anche un bugiardo possa asserire il vero, dovremmo ammettere che l’affermazione del cretese Epimenide può essere veritiera: e in questo caso non si genererebbe alcun paradosso.

Comunque, allineiamoci pure all'interpretazione "severa", in base alla quale un bugiardo è un individuo che non dice mai cose vere, e quindi l'affermazione di Epimenide è inevitabilmente paradossale.
In questa prospettiva, non sappiamo se San Paolo, nel riprendere l'affermazione paradossale di Epimenide, fosse consapevole o meno di riprodurne l'assurdità.
Sarebbe infatti assurdo citare proprio un cretese per dare valore alla propria tesi della inaffidabilità dei cretesi.
Voglio invece credere, anche per una questione di simpatia derivante dall'omonimia, che San Paolo avesse compreso perfettamente il paradosso e che il suo intento fosse in realtà ironico.

Paradossi elettorali

Oddio, diranno i miei lettori, adesso anche lui si mette a parlare di politica.
No, niente affatto: lungi da me l'idea di snaturare il blog con spericolate deviazioni di argomento.
Tuttavia, per rendere più vivo e chiaro il paradosso elettorale che voglio esporvi, mi riferirò a nomi reali, utilizzandoli comunque senza riferimento alla realtà.
Supponiamo che in un recente sondaggio sia stato chiesto agli italiani di esprimere le proprie preferenze elettorali in uno scenario probabile che vede la presenza di tre blocchi politici, rispettivamente guidati da Berlusconi, Bersani, Casini.
Ad ogni intervistato viene chiesto di mettere in ordine di preferenza i tre candidati alla guida del governo.
Emerge che il 66,66% degli elettori italiani preferisce Berlusconi a Bersani; risulta inoltre che il 66,66% degli italiani preferisce Bersani a Casini.
Sembrerebbe ovvio, a questo punto, concludere che le chance di Casini siano pressoché nulle, e che Berlusconi sia preferito a Casini dalla maggioranza degli italiani.
E' così? Anche se può apparire strano, non è detto.
Supponiamo infatti che un terzo degli intervistati abbia risposto con il seguente ordine di preferenza:
1. Berlusconi;
2. Bersani;
3. Casini.
Un altro terzo ha invece espresso il seguente ordine:
1. Bersani;
2. Casini;
3. Berlusconi.
Il rimanente 33,33% ha fornito le seguenti preferenze:
1. Casini;
2. Berlusconi;
3. Bersani.
Ora, vediamo che, se queste sono state le risposte degli intervistati, effettivamente due terzi (precisamente il primo e il terzo gruppo) preferiscono Berlusconi a Bersani, e altri due terzi (il primo e il secondo gruppo) preferiscono Bersani a Casini.
Tuttavia, vediamo che sempre due terzi degli italiani (rappresentati dal secondo e dal terzo gruppo) preferiscono Casini a Berlusconi, contrariamente alle aspettative dettate dalle prime due indicazioni di preferenza.
Questo paradosso del voto era conosciuto già alla fine del Settecento, e viene di solito associato al nome di Jean-Antoine-Nicolas de Caritat, noto come marchese di Condorcet.
Condorcet si occupò di politica negli anni della Rivoluzione Francese, ma anche di economia e di matematica.
Il suo paradosso evidenziò la difficoltà di progettare un sistema elettorale ideale: in particolare mostrava che i voti di preferenza, quando esistono almeno tre scelte, possono assumere una configurazione "ciclica", in quanto le preferenze collettive non sono necessariamente transitive. Da ciò consegue che i desideri della maggioranza possono essere contraddittori, cioè in conflitto gli uni con gli altri.
Chissà se i nostri politici conoscono questo curioso e antico paradosso elettorale...

Il gioco del quindici

Non è sorprendente che molti esperti di scacchi siano passati alla storia non tanto per aver lasciato importanti contributi sul gioco dei pezzi bianchi e neri, ma per avere inventato enigmi matematici o proposto tecniche algoritmiche per risolvere difficili problemi.
Abbiamo già incontrato, qualche post fa, il caso di Johann Berger, scacchista austriaco con l'hobby degli algoritmi per stilare i calendari dei tornei.
Un altro celebre scacchista fu Samuel Loyd, americano, anche lui vissuto a cavallo tra Ottocento e Novecento.


Il nome di Loyd è ben noto agli appassionati di scacchi come compositore di problemi, ma i suoi meriti vanno ben oltre le frontiere di quel gioco. Molti, tra i quali Martin Gardner, lo hanno considerato "il più grande enigmista d'America": pare che abbia inventato migliaia di giochi ed enigmi, alcuni dei quali molto sofisticati dal punto di vista matematico. Una delle sue intuizioni più geniali è un rompicapo nel quale tutti noi ci siamo prima o poi cimentati: il cosiddetto "gioco del quindici".
Lo scopo del gioco è ben noto: in una specie di scatola quadrata di plastica dobbiamo mettere in ordine quindici tesserine quadrate, numerate da 1 a 15; le tesserine possono scorrere solo in orizzontale e in verticale, ma nello spostarle dobbiamo fare i conti con il fatto che esiste un solo spazio vuoto!
Si parte solitamente da una situazione casuale, più o meno caotica, e si deve arrivare nella configurazione illustrata nella figura in alto.

Sam Loyd propose il suo gioco nel 1878. Si racconta che il successo del rompicapo fu così travolgente, che i francesi arrivarono a descriverlo come un flagello peggiore dell'alcool e del tabacco, in Germania diventò molto popolare tra i deputati del Reichstag, mentre in America venne proibito il suo utilizzo negli uffici durante le ore di lavoro!

Su disposizione di Loyd, la confezione del gioco che venne messa in commercio non aveva le tessere disposte in una configurazione caotica: semplicemente, rispetto alla situazione finale ordinata, aveva le due caselle del 14 e del 15 scambiate, come illustrato nella figura qui accanto.
Loyd offrì un premio di ben 1000 dollari al primo che avesse trovato una soluzione.
Visto che si trattava soltanto di due caselle scambiate tra loro, sulle prime si pensò che l'enigma fosse di facile risoluzione: tuttavia, i mesi e gli anni passarono senza che nessuno si facesse avanti a reclamare il premio.


Ovviamente, Loyd aveva fatto bene i suoi conti: il problema era impossibile!
Perché?
Per capire l'arcano, almeno a grandi linee, occorre considerare, in ogni configurazione del gioco dalla quale si parte per cercare di arrivare all'ordinamento totale, il numero di coppie di caselle che non si trovano nella situazione "naturale". Ad esempio, la disposizione iniziale proposta da Loyd presenta una sola coppia di caselle non ordinate tra di loro: quella del 14 e quella del 15, che sono appunto invertite l'una rispetto all'altra.


Anche la configurazione illustrata nella figura qui accanto presenta un numero di inversioni pari a 1: infatti soltanto la casella del 2 e quella dell'1 sono scambiate tra di loro.




Nella successiva figura, le inversioni sono in tutto 4: per verificarlo, osservate una per una tutte le caselle, e per ognuna controllate con quali altre caselle si verifica un "cattivo" ordinamento reciproco.


Non è difficile dimostrare (e infatti i matematici lo hanno fatto) che se il numero di inversioni di una certa disposizione iniziale è pari, allora si può risolvere il rompicapo, portando tutte le caselle nella loro situazione completamente ordinata, ma se è dispari ciò non è possibile.
Ecco perché Loyd sapeva di non correre alcun rischio, e mise in palio una somma che nessuno poté mai riscuotere!

L'informatica leggera

Poi, l'informatica. E' vero che il software non potrebbe esercitare i poteri della sua leggerezza se non mediante la pesantezza del hardware; ma è il software che comanda, che agisce sul mondo esterno e sulle macchine, le quali esistono solo in funzione dei software, si evolvono in modo d'elaborare programmi sempre più complessi. La seconda rivoluzione industriale non si presenta come la prima con immagini schiaccianti quali presse di laminatoi o colate d'acciaio, ma come i bits d'un flusso d'informazione che corre sui circuiti sotto forma d'impulsi elettronici. Le macchine di ferro ci sono sempre, ma obbediscono ai bits senza peso.

(Italo Calvino, da "Lezioni americane. Sei proposte per il prossimo millennio", scritte nel 1985 e pubblicate postume nel 1988).

Capire Gödel

Verso la fine dell'anno scorso ho letto un libro che un giovane logico veneziano, Francesco Berto, ha scritto su uno degli argomenti più citati e tuttavia meno capiti di tutta la logica: il teorema di incompletezza di Gödel.
Capire (veramente) Gödel non è cosa facile.
Ma questo eccellente saggio può aiutare a farlo, a condizione che ci sia davvero la voglia e la pazienza per penetrare nell'argomento.
Berto è stato davvero bravo: ha confezionato un'ottima ed esaustiva esposizione del celebre teorema, affrontandone i diversi aspetti in modo estremamente rigoroso, ma senza allontanrsi troppo da un taglio divulgativo.
Diciamo che il libro si pone a metà strada tra un testo universitario, specialistico, e un saggio divulgativo per tutti.
Grazie a questo libro ho finalmente chiarito le mie idee su alcuni aspetti gödeliani che altri testi non spiegavano bene, o peggio, sui quali vengono spesso diffuse interpretazioni errate.
Il buon Berto non si ferma a spiegare, bene, il teorema dal punto di vista prettamente "logico", ma delinea, in modo molto appassionante e completo, il quadro storico che portò a quel risultato, e soprattutto approfondisce molto le conseguenze che esso ebbe nel dibattito filosofico degli ultimi ottant'anni.
Consiglio questo libro a chiunque sia curioso e desideroso di capire Gödel. Costerà un po' di fatica, ma ne vale la pena.

Ancora sui polimini

La storiella di Mr. Palomar e Mr. Wilson che giocano con i pezzi del Tetris su una scacchiera generalmente riservata ad altri giochi, come gli scacchi, merita certo alcuni approfondimenti.
Innanzitutto, i polimini di Golomb: uno dei primi tentativi del matematico americano deve essere stato certamente quello di trovare una formula che permettesse di calcolare quanti polimini possono essere costruiti con un certo numero di quadrati.
Non mi risulta che sia nota una simile formula: la funzione, come si può vedere nella figura seguente, cresce molto rapidamente (già con 12 quadrati esistono ben 63600 polimini possibili).


Il problema di coprire una scacchiera 8x8 con i 12 pentamini esistenti, lasciando vuote quattro caselle, è molto vecchio: Martin Gardner, nei suoi "Enigmi e giochi matematici" raccolti dallo "Scientific American", ci racconta che una soluzione a questo rompicapo fu pubblicata nel 1907 da Henry Dudeney nel suo libro "The Canterbury puzzles", che proponeva enigmi e giochi ispirati ai personaggi dei "Canterbury Tales" di Geoffrey Chaucer.
Molte altre soluzioni vennero proposte successivamente. E' stato dimostrato che se le quattro caselle sparse vengono poste vicine, a formare un tetramino quadrato, esistono soluzioni per qualsiasi collocazione di questo tetramino. Ad esempio, se il tetramino viene posto al centro della scacchiera, come nella soluzione proposta da Mr. Wilson, esistono 65 soluzioni diverse, che vennero trovate nel 1958 dall'informatico Dana Scott, premio Turing nel 1976. Se invece si accetta che le quattro caselle sparse possano stare ovunque, le soluzioni possibili del rompicapo di Dudeney diventano molte migliaia.
Il gioco competitivo nel quale ognuno dei due giocatori dispone polimini sulla scacchiera, cercando di far sì che l'avversario si trovi a un certo punto senza spazio per porre propri pezzi, fu inventato da Golomb nel 1954. Golomb calcolò che, giocando con i pentamini, una partita può durare da 5 a 12 mosse: in altri termini, 5 è il numero minimo di pentamini diversi che devono essere sistemati sulla scacchiera in modo che non ci sia più spazio per disporre altri pentamini diversi; d'altra parte, dopo aver collocato 12 pentamini in qualsiasi maniera, sicuramente resterebbero soltanto le quattro famose caselle in sovrappiù, e non ci sarebbe spazio per un altro pentamino (e comunque non esisterebbe un tredicesimo tipo di pentamino).
Golomb suggerì anche un paio di principi strategici utili per aumentare le probabilità di vittoria:
1. "cercate di fare mosse che lascino spazio per un numero pari di pezzi";
2. "se non riuscite ad analizzare bene la situazione, fate qualcosa per complicarla ancora di più, in modo che l'avversario faccia ancora più fatica a fare la sua analisi".
Giocando con i tetramini, invece, non ho idea di come potrebbe cambiare la natura del gioco: sarebbe interessante provare!
Il gioco nel quale i due giocatori collocano tetramini sulla scacchiera rispettando la regola delle carte geografiche politiche, nelle quali regioni confinanti devono avere colori diversi, è di mia invenzione. In questo caso, ovviamente si deve disporre di più pezzi per ogni tipo di tetramino: altrimenti non si potrebbero mettere sulla scacchiera pezzi con lo stesso colore. D'altra parte, utilizzando la convenzione dei matematici e non quella del Tetris, con cinque tetramini si coprono soltanto 20 caselle: appare quindi evidente che il gioco necessita di più pezzi per ogni tipo (o colore). Con l'accorgimento di Mr. Wilson, peraltro, due dei cinque tipi di tetramini hanno una doppia colorazione, a seconda della faccia che viene scelta per la collocazione sulla scacchiera.
Anche per questo gioco, non ho prove sperimentali della giocabilità: potrebbe anche rivelarsi un gioco poco divertente o addirittura non giocabile. Anche qui non c'è che da provare a giocare: se qualche lettore volesse galileianamente sperimentare la cosa, sarei curiosissimo di conoscere i risultati.

Un'ultima nota: il nostro Golomb, oltre a fondare la matematica dei polimini, inventò anche un'altra diavoleria matematica: il "regolo" che porta il suo nome. Immaginate di avere un regolo, sul quale sono indicate le posizioni corrispondenti ai numeri interi: 1, 2, 3, e così via. Ora vogliamo tracciare alcune tacche su di esso, in corrispondenza di alcune delle posizioni intere indicate, ma in modo che non ci sia alcuna coppia di tacche poste alla stessa distanza. Trovare regoli di Golomb è semplice, ma trovare quello con il numero di tacche più grande possibile compatibilmente con la sua lunghezza è un problema computazionalmente molto difficile.

Come giocare su una scacchiera con i pezzi del Tetris

Una ventina d'anni fa Mr. Palomar passava molto tempo davanti al pc giocando a Tetris, il gioco delle forme colorate che cadono in una sorta di pozzo e che devono essere spostate e ruotate in modo da completare il numero maggiore possibile di righe orizzontali ininterrotte: quando una siffatta riga viene creata, come per incanto sparisce, dando respiro al giocatore.
Mr. Palomar ricorda bene i sette tipi di pezzi del Tetris:


Il gioco del Tetris venne ideato nel 1985 da un geniale programmatore russo, Aleksej Leonidovič Pažitnov, che allora lavorava in un centro di ricerca dell'Accademia delle Scienze Sovietica. Quando il gioco cominciò a spopolare in tutto il mondo, verso la fine degli anni Ottanta, al buon Pažitnov, in quanto dipendente statale, non vennero riconosciuti i diritti d'autore: cosicché nel 1991 fece le valigie ed emigrò negli Stati Uniti, dove poté meglio raccogliere i frutti del proprio ingegno.
Passato il periodo di "innamoramento" per l'allucinogeno videogame, Mr. Palomar esaurì ben presto l'interesse verso il Tetris, dedicandosi ad altro e dimenticando quella passione giovanile.
Spesso, però, le cose del passato tendono imprevedibilmente a tornare. Poco tempo fa Mr. Palomar fu invitato a casa di un suo amico, Mr. Wilson, esperto di matematica e di giochi matematici. Mentre i due parlavano del più e del meno, Mr. Palomar notò alcuni pezzi di cartone colorato su un tavolo e domandò all'amico di cosa si trattasse.
- I tetramini! Non ti ricordi più il Tetris?
- Ah, è vero!
A Mr. Palomar sembrò che un remoto ricordo fosse riemerso da uno sperduto anfratto della sua memoria.
- Ricordi perché si chiamano così, vero? Ogni pezzo colorato che nel Tetris deve essere sistemato sul fondo del pozzo è formato da quattro quadratini, e quindi...
- Sì, lo ricordo, non c'è bisogno che me lo spieghi.
- Aspetta, porto la scacchiera!
- La scacchiera? Stavamo parlando del Tetris, mica degli scacchi!
- Aspetta. Aspetta e vedrai - rispose Mr. Wilson, infilandosi frettolosamente nel suo studio.
Tornò con una pesante scacchiera di legno sotto braccio. La posò sul tavolo. Mr. Palomar prese in mano uno dei tetramini di cartone e si accorse che i quattro quadrati che lo costituivano coincidevano perfettamente con la dimensione dei quadrati della scacchiera. In altre parole, ogni forma colorata di Mr. Wilson poteva essere posata sulla scacchiera in modo da coprire le caselle con precisione.
- Un momento! - disse improvvisamente Mr. Palomar - Qui ci sono solo cinque tetramini di cartone, mentre nel Tetris i pezzi erano di sette tipi. Ne hai persi due?
- No - rispose Mr. Wilson - Guarda qui! - e capovolse due delle cinque sagome: quella rossa e quella blu. Il tetramino rosso era colorato di verde sull'altro lato, mentre quello blu aveva l'altra faccia arancione.
- Ahhh, forse ho capito! - esclamò Mr. Palomar - Nel Tetris due tetramini sono considerati di tipo diverso se differiscono per una riflessione o per una rotazione nello spazio tridimensionale. Quindi il tetramino blu, simile ad una J, è diverso dal tetramino arancione, simile ad una L, e così quello rosso, dalla forma di una Z va distinto da quello verde, fatto a S.
- Esatto. I matematici, invece, preferiscono considerare uguali due tetramini che differiscono per una riflessione o per una rotazione, ed io ho seguito questa convenzione nel ritagliare queste sagome. Però, in onore del glorioso Tetris, ho mantenuto, sulle due facce dei tetramini "bivalenti", le due diverse colorazioni. Guarda queste altre forme adesso.
Mr. Wilson aprì una busta, dalla quale fuoriuscirono altre 12 sagome di cartone colorato.


- Queste però non sono tetramini, o sbaglio?
- Non sbagli. Conta i quadrati in ogni forma.
- Uno, due, tre, quattro... cinque. Sono... pentamini?
- Indovinato. Tetramini e pentamini non sono che casi particolari di polimini, cioè figure piane composte da un numero finito di quadrati connessi tra di loro lungo i lati. In inglese si chiamano polyominoes.
- Quindi se usiamo soltanto tre quadratini per ogni forma, abbiamo dei... trimini?
- Certo. E con due quadratini abbiamo...
- Aspetta! Lasciami indovinare: domini?
- Già. Non ti dice niente questa parola? Non ti ricorda un famoso gioco?
- Il domino! Certo! In effetti i pezzi del domino non sono altro che coppie di quadrati connessi.
- Proprio così. E con numeri di quadrati superiori a cinque, abbiamo invece gli esamini (che non sono esami facili!), gli ettamini, e così via.
Mr. Palomar rimase qualche secondo in silenzio, osservando le sagome colorate sul tavolo. Poi disse:
- Stavo pensando ai domini, polimini con due quadrati: esiste un solo modo di connettere due quadrati tra di loro per i lati, cioè esiste un solo tipo di domino. Giusto?
- Giusto. Così come esistono due tipi di trimino.
- E i pentamini? Quanti sono?
- Sono 12, seguendo la convenzione in auge presso i matematici. Gli esamini invece sono 35, gli ettamini 108, gli ottamini 369, e così via. Fu un certo Solomon W. Golomb, studente di Harvard negli anni Cinquanta, che, annoiato dalle lezioni, cominciò a disegnare polimini sul suo quaderno a quadretti, per poi classificarli e analizzarli.


Mr. Wilson tacque per qualche secondo, poi aggiunse, quasi tra sè e sè:
- Forse mentre faceva questo non immaginava che stava fondando uno dei capitoli più affascinanti della matematica ricreativa. Qualche anno dopo, però, Golomb divenne professore alla University of Southern California e approfondì molti settori dell'ingegneria, della teoria dei numeri e della teoria delle comunicazioni elettriche. Dopo la sua invenzione dei polimini, molti matematici e divulgatori, primo fra tutti il grande Martin Gardner, hanno esplorato a fondo quel mondo di quadratini, anche molto prima che il Tetris lo portasse alla ribalta del grande pubblico.
- Ma la scacchiera? Cosa vuoi farci?
- Cosa vuoi fare con una scacchiera? Giocare, no?
- Con i tetramini e i pentamini?
- Certo. Ci sono un sacco di giochi che si possono fare su una scacchiera usando polimini come questi. Ad esempio, prova a coprire la scacchiera usando i 12 pentamini.
Mr. Palomar rifletté:
- Dodici pentamini coprono 12x5=60 caselle, mentre la scacchiera comprende 8x8=64 caselle. Cosa ne facciamo delle 4 caselle rimanenti?
- Molto perspicace, complimenti! Le lasciamo vuote, semplicemente.
Per qualche secondo Mr. Palomar guardò l'amico con sguardo ebete, poi provò a sistemare sulle caselle della scacchiera le sagome di cartone, cercando di ricoprire esattamente tutta la scacchiera.
Dopo qualche minuto di tentativi infruttuosi, esclamò:
- Mica facile, però!
- No, non lo è. Su internet ci sono molti programmini che mostrano come si può ottenere un simile ricoprimento. Ad esempio una soluzione è questa.
Mr. Wilson spostò alcuni pezzi sulla scacchiera e ottenne la seguente configurazione:


- Eh, troppo comodo! La fai facile tu che conosci già la soluzione.
- Hai ragione. Ma pensa, anche imponendo il vincolo di collocare le quattro caselle eccedenti al centro della scacchiera, esistono ben 65 soluzioni diverse.
- Va bene, proverò ad esercitarmi a casa.
- Adesso ti faccio vedere un gioco che ho inventato io, con i cinque tipi di tetramini. Si gioca in due, io contro di te. Soltanto che devo tirare fuori altri pezzi di cartone che ho preparato. Infatti serve avere un certo numero di pezzi per ciascun tipo di tetramini: ad esempio un po' di pezzi del tipo lungo (quello celeste), un po' del tipo quadrato (quello giallo), e così via. Il gioco prende ispirazione dalle carte geografiche politiche.
- Le carte geografiche?
- Sì, in queste carte due stati confinanti non possono essere colorati con lo stesso colore. Analogamente, il gioco consiste nel posare a turno sulla scacchiera un pezzo, con la regola che non si può mettere un pezzo vicino ad altro dallo stesso colore.
- Interessante, proviamo.
I due giocarono per un po'. Il gioco era abbastanza divertente, ma a un certo punto Mr. Palomar, desideroso di provare nuovi rompicapi, domandò:
- Conosci altri giochi?
- Certo. Ce n'è uno ancora più semplice, ma molto divertente. Anche questo si può giocare in due, con i tetramini oppure con i pentamini. Io scelgo un pezzo e lo metto dove voglio sulla scacchiera. Poi tocca a te, e fai altrettanto. Perde chi che non riesce più a collocare un pezzo senza che vada a sovrapporsi agli altri.
- Caspita! Questo mi sembra un bel gioco!
- L'ha inventato il buon Golomb in persona.
- Proprio un tipo interessante, questo Golomb. Mi piacerebbe conoscerlo.
- Potremmo andare a trovarlo in California.
- Perché no?
I due cominciarono a giocare, e non smisero se non dopo parecchie ore.