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.

Sulla poesia della matematica

Afferma la grande poetessa polacca Wislawa Szymborska, premio Nobel per la letteratura nel 1996, nel libro "Letture facoltative" del 1992:

Non ho difficoltà a immaginare un’antologia dei più bei frammenti della poesia mondiale in cui trovasse posto anche il teorema di Pitagora. Perché no? Lì c’è quella folgorazione che è connaturata alla grande poesia, e una forma sapientemente ridotta al termini più indispensabili, e una grazia che a non tutti i poeti è stata concessa.

Mr. Palomar e Doctor Subtilis

Mr. Palomar conosce un tizio che scrive poesie. A dire il vero, sarebbe più giusto dire che questo tale scribacchia delle mostruosità che nemmeno l'uomo più generoso del mondo potrebbe definire lontanamente poesie: ma si dà il caso che questo poetastro si ritiene all'altezza di Dante, Leopardi e Montale.
Mr. Palomar ha capito ben presto che si tratta di megalomania patologica, e ultimamente cerca di stare alla larga da questo conoscente, o perlomeno di evitare in sua presenza l'argomento poesia, per non dovere dirgli in faccia cosa pensa delle sue manie di grandezza. Si sa, coi matti è meglio andare cauti.
Un giorno, però, gliel'ha detto chiaro e tondo: "Se lei è Dante, allora io sono Napoleone!"
Quando ci vuole, ci vuole. Mr. Palomar è un uomo dal cuore tenero: si fa sempre mille problemi a tirar fuori le unghie, e quelle poche volte che lo fa, poi rimugina a lungo sull'avvenuto. Così quel giorno, ripensando alla frase pronunciata, Mr. Palomar ragionava così tra sè e sè:
"Che senso ha veramente dire che se lui è Dante, allora io sono Napoleone?
E' strana la lingua italiana! Certo, capisco bene che si tratta di una iperbole: come a dire che se è vera un'assurdità come quella che mi ha detto il poetastro, allora siamo autorizzati a dire tutte le assurdità che vogliamo. Ma da un punto di vista logico, è vero che c'è proprio questa relazione di causa-effetto?"

Mr. Palomar ha pensato a lungo, ha tirato fuori alcuni libri dalla sua libreria, e si è ricordato di un filosofo scozzese vissuto intorno al 1300, Giovanni Duns Scoto, che a causa delle sue sofisticate argomentazioni logiche (per alcuni cavillose) venne soprannominato "Doctor Subtilis".
A Scoto, ha scoperto Mr. Palomar, viene tradizionalmente attribuita la scoperta di un principio fondamentale della logica, detto anche "principio di esplosione" o "Ex falso sequitur quodlibet" (cioè: "dal falso discende qualsiasi cosa"): ma in realtà questo teorema fu scoperto da qualche altro logico sconosciuto. Cosa dice questo principio?
Che se per assurdo consideriamo vera una contraddizione logica, allora possiamo dedurre come vera qualsiasi affermazione ci venga in mente. Quindi, ha pensato Mr. Palomar con un briciolo di emozione, se è vero che il poetastro è proprio Dante, allora posso davvero concludere che io sono Napoleone.

Come si spiega la legge dello (pseudo)Scoto?
Noi sappiamo che il conoscente di Mr. Palomar non è Dante, eppure vogliamo ammettere che sia vero ciò che lui sostiene, e cioè che lui è Dante. La contraddizione è quindi data dal fatto che ammettiamo come vere entrambe le affermazioni:
1. il tizio è Dante
2. il tizio non è Dante
Allora Mr. Palomar può legittimamente dire:
"il tizio è Dante oppure io sono Napoleone"
Infatti, dato che abbiamo ammesso come vera la prima parte della frase, anche la complessiva frase disgiuntiva deve essere vera.
Mr. Palomar osserva che se una frase disgiuntiva è vera, significa che è vera almeno una delle sue due parti. Ciò equivale a dire che le due parti non possono essere contemporaneamente false, cioè che l'affermazione "il tizio non è Dante e io non sono Napoleone" deve essere falsa (quest'ultima deduzione è nota come "legge di De Morgan").
Però abbiamo ammesso all'inizio che il tizio non è Dante: quindi deve essere l'affermazione "io non sono Napoleone" ad essere falsa.
Perciò il nostro Mr. Palomar, senza più timore di sbagliare, trae dalla contraddizione iniziale la sorprendente e iperbolica conclusione: "io sono Napoleone".

Il problema del campionato - Parte 3 (con un algoritmo originale dell'autore)

Lasciamo quindi da parte tutte le complicate questioni sulla colorazione dei grafi, anche perché non sono poi così utili per affrontare praticamente la questione del calendario di un girone all'italiana. Vediamo invece alcune tecniche che possiamo davvero utilizzare.
Avevo accennato ad un algoritmo che avevo ideato nel 1996, e che sembra in grado di trovare sempre un calendario valido, con l'unica condizione che il numero di squadre sia pari.
L'idea mi venne, dopo una serie di infruttuosi tentativi, pasticciando sulla matrice di cui abbiamo ampiamente parlato nei post precedenti. Ricordo che la matrice viene riempita con numeri che corrispondono al numero della giornata in cui è programmata la partita tra le due squadre corrispondenti alla riga e alla colonna.
Pensai subito, tuttavia, di semplificare la questione trascurando una delle due sezioni triangolari, cioè considerando soltanto la sezione in alto a destra della diagonale principale: i gironi di andata e di ritorno, infatti, sono una la ripetizione dell'altro, per cui è sufficiente programmarne uno per avere automaticamente anche l'altro.
L'algoritmo parte quindi con la matrice vuota, o meglio con degli zeri nelle caselle che dovremo riempire (supponiamo sempre N=4).


A questo punto ha inizio il ciclo principale dell'algoritmo.
Prenderemo, una dopo l'altra, alcune "coppie" formate da una riga e da una colonna della matrice, dove la riga e la colonna corrispondono alla stessa squadra. Per ciascuna di queste coppie, possiamo immaginare di scendere dall'alto verso il basso lunga la colonna, "rimbalzare" sulla diagonale principale, e dirigerci verso destra lungo la riga gemella.
A cosa serve questo "cammino" lungo colonne e righe? Ovvio: a riempire le caselle che troviamo ancora a zero lungo il nostro cammino.
E come eseguire questo riempimento? Per ogni coppia, la prima volta che troviamo una casella da riempire, proviamo a metterci un 1, se lungo il cammino sulla "coppia" non abbiamo trovato che zeri, altrimenti proviamo con il numero successivo all'ultimo trovato prima della casella da riempire: se il numero può starci, nel senso che su nessuna riga o colonna della matrice si creano ripetizioni, e inoltre il numero inserito non era già stato scritto sulla stessa "coppia", allora passiamo alla prossima casella da riempire, altrimenti tentiamo con il numero successivo, e così via. Ovviamente quando arriviamo a N-1, il numero successivo da provare sarà di nuovo 1.
Eseguendo questo procedimento sulla coppia formata dalla prima colonna e dalla prima riga, si ottiene la matrice seguente:



Proseguendo con altre due passate, si ottiene il risultato finale:


Gli incontri della prima giornata saranno quindi A-B e C-D, quelli della seconda A-C e B-D, mentre nella terza e ultima giornata si disputerranno le partite A-D e B-C.



Un altro algoritmo, sicuramente più famoso del mio, in grado di risolvere il problema, è quello cui accennavo nella prima parte di questo ormai estenuante post (pazientate, siamo ormai alla fine!). A inventarlo fu un maestro di scacchi austro-ungarico, Johann Nepomuk Berger.
Prendiamo le nostre N=4 squadre: A, B, C e D, e scriviamole in una tabellina così strutturata:


La prima giornata sarà allora costituita dagli incontri A-B e C-D.
Ora manteniamo fissa la squadra in alto a sinistra, mentre nella colonna "CASA" facciamo scorrere le squadre verso l'alto e nella colonna "TRASFERTA" facciamo scorrere le squadre verso il basso. Le squadre che fuoriescono da una colonna passeranno nell'altra colonna. Otteniamo la tabella seguente, corrispondente alla seconda giornata:


Ripetendo per un'ultima volta lo stesso procedimento di rotazione in senso orario, si ottiene la terza giornata:



Guarda caso, abbiamo ottenuto la stessa programmazione generata dal mio algoritmo.
Provate con un numero maggiore di squadre, ad esempio 6, oppure 8, o anche di più: con ogni probabilità otterrete con i due algoritmi calendari diversi.
Buon divertimento!

Il problema del campionato - Parte 2

Una delle meraviglie (meravigliosa per me, s'intende) presenti nel mitico almanacco del calcio (vedi Parte 1 di questo multi-post) era che venivano riportati i risultati di tutte le partite di tutti i campionati italiani di serie A, dalle lontane ottocentesche origini fino alla stagione in corso; ma la vera meraviglia per i miei occhi era che queste informazioni erano pubblicate in un modo estremamente compatto: una paginetta per ogni campionato, cioè per ogni anno.
Com'è possibile? Venivano usati caratteri microscopici, da leggere con la lente d'ingrandimento? No, semplicemente avevano escogitato un semplice ma ingegnoso metodo per risparmiare molto spazio, che a me piacque molto.

Solitamente i risultati delle partite di un torneo vengono riportati in una forma come la seguente (tratta da Wikipedia):


Nell'almanacco, invece, per ogni stagione veniva presentata una matrice quadrata con un numero di righe (e di colonne) pari al numero di squadre partecipanti, e nelle caselle interne venivano riportati i risultati delle partite che avevano visto in campo le due squadre corrispondenti alla riga e alla colonna di riferimento.
Per convenzione, in ogni incontro la squadra di casa era quella corrispondente alla riga, e quella ospite era quella corrispondente alla colonna. In questo modo, la diagonale principale della matrice restava vuota per l'ovvio motivo che una squadra non può giocare contro se stessa.
Presa una qualsiasi casella (quindi una partita) in una o nell'altra delle sezioni triangolari divise dalla diagonale principale, la casella speculare rispetto alla diagonale stessa risulta corrispondere alla ripetizione della stessa partita nell'altro girone della stagione (se la prima partita appartiene al girone di andata, la seconda appartiene al girone di ritorno, e viceversa).
Se N è il numero di squadre del torneo (si ipotizza che N sia sempre pari), la matrice quadrata avrà lato N per costruzione; le partite complessivamente presenti sono quindi N² - N (occorre infatti togliere la diagonale principale vuota), quindi N(N-1).
In effetti le giornate del campionato sono N-1, perché ogni squadra deve giocare contro tutte le squadre tranne se stessa (d'altra parte, N-1 è il numero di caselle compilate in ogni riga e in ogni colonna); e in ogni giornata vengono disputate N/2 partite. Quindi le partite complessive in un girone di andata sono 1/2 N(N-1), numero che va raddoppiato per tener conto del girone di ritorno: viene così confermato il risultato N(N-1) ottenuto sopra.
(Nelle figure seguenti, per semplificare un po', ho posto N=4).


Il trucco della matrice per risparmiare spazio è piuttosto banale e ovvio, direte voi. Certo, ma all'undicenne che ero allora ingenuamente sembrò geniale.
Quando, anni dopo, mi cimentai nel problema della generazione del calendario, tema centrale di questi post, mi tornarono subito alla mente le magiche matrici dell'almanacco del calcio.
Immaginai che all'interno delle caselle, anziché i risultati degli incontri, fossero scritti i numeri delle giornate in cui tali incontri sono programmati (o già disputati).
Ad esempio, la partita tra la Squadra A e la Squadra B è programmata per la giornata n. 1, la partita tra la Squadra B e la Squadra C è programmata per la giornata n. 3, e così via.


Ora apportiamo una nuova leggera variazione alla matrice: trascuriamo la differenza tra andata e ritorno, e di conseguenza nelle due caselle corrispondenti all'andata e al ritorno di un certo incontro tra due squadre (due caselle speculari nel senso spiegato prima), mettiamo lo stesso numero, relativo, per convenzione, alla giornata del girone di andata in cui si disputa la prima delle due gare.
Otteniamo una matrice come quella seguente:


Osservando la matrice ottenuta, notiamo che essa gode di due interessanti proprietà:
1) è simmetrica rispetto alla diagonale principale;
2) tralasciando le caselle vuote sulla diagonale, su ogni riga e su ogni colonna sono presenti tutti i numeri da 1 a N-1, senza ripetizioni.
Per la verità, queste due condizioni sono necessarie e sufficienti affinché la matrice rappresenti un calendario valido per un campionato. Infatti, se su una stessa riga o colonna ci fossero due caselle con lo stesso numero, vorrebbe dire che una squadra dovrebbe giocare due partite nella stessa giornata (e, corrispondentemente, un'altra squadra non giocherebbe alcuna partita): situazione questa ovviamente non ammessa.

Vi viene in mente qualche famoso rompicapo in cui accade qualcosa di simile?
Risposta esatta: il sudoku!


Anche il sudoku si gioca su una matrice quadrata, precisamente con N=9.
Su ogni riga e colonna devono essere posti tutti i numeri da 1 a 9, senza ripetizioni: lo stesso termine "sudoku", in giapponese, significa proprio qualcosa come "i numeri devono comparire una sola volta".
Le uniche due differenze, rispetto alla matrice del campionato, sono le seguenti:
1. anche le caselle sulla diagonale vanno riempite regolarmente, come le altre;
2. esiste un ulteriore vincolo, relativo ai 9 sotto-quadrati 3x3 evidenziati all'interno dello schema complessivo: anche in ciascuno di essi, tutti i numeri da 1 a 9 devono essere presenti senza ripetizioni.

Sia per giocare a sudoku sia per stilare il calendario del campionato, quindi, si tratta di risolvere un problema vincolato in cui occorre assegnare dei numeri ad alcune caselle.
Prendiamo in esame la matrice del campionato, di lato N, e trasformiamo ogni casella in un nodo di un grafo, mettendo in ogni casella l'indicazione della partita corrispondente.
Poi colleghiamo tra loro, mediante archi, gli N nodi che appartengono alla stessa riga, e poi facciamo lo stesso con i nodi che appartengono alla stessa colonna.
Usiamo però l'accortezza di accorpare tra loro i nodi che contengono una partita tra le stesse due squadre: andata e ritorno per noi, ora, sono la stessa cosa.
Il grafo che si ottiene alla fine di questo procedimento è il seguente:


Il nostro problema iniziale consisteva nell'assegnare un numero (da 1 a N) a ciascuna delle caselle della matrice. Il corrispondente problema sul grafo è assegnare un numero (da 1 a N) ad ogni nodo del grafo ottenuto.
In questo grafo, infatti, ogni nodo corrisponde a due caselle della matrice originaria. Sappiamo che queste due caselle conterranno lo stesso numero, corrispondente alla giornata in cui si disputerà la gara di andata tra le squadre in questione: per determinare la giornata della gara di ritorno basterà aggiungere N-1.

Se ci viene dato un grafo come quello della figura precedente, come possiamo procedere per assegnare un numero da 1 a N a ciascun nodo?
L'unico vincolo che dobbiamo rispettare è che a due nodi collegati tra loro non può essere assegnato lo stesso numero.
Spesso, per rendere il problema più... vivace, anziché assegnare un numero da 1 a N a ciascun nodo del grafo, si assegna un colore, preso da una gamma di N colori.
Il vincolo diventa allora che due nodi contigui non possono condividere lo stesso colore (a volte si descrive questo vincolo dicendo che "non possono esistere archi monocromatici").
E' chiaro che usando colori invece che numeri, il problema non muta minimamente la sua struttura matematica.
I matematici chiamano questo problema graph coloring, cioè colorazione dei grafi.
Si tratta di un problema molto noto nell'ambito della ricerca operativa, cioè di quella parte della matematica e dell'informatica che si occupa di formalizzare problemi complessi di ottimizzazione attraverso modelli matematici, allo scopo di trovare soluzioni ottime, se possibile, o approssimate.
Tornerò sull'argomento in altri post; qui mi limito a sottolineare che colorare i grafi (ovviamente rispettando la condizione degli archi monocromatici) non è per niente affare da poco, anzi il più delle volte rappresenta un problema molto difficile.
Nella prossima parte, quindi, vedremo come il problema del campionato convenga che sia risolto utilizzando altri metodi, molto più semplici.
Valeva la pena, però, fare questa deviazione: anche se non fruttuosa sul piano della ricerca di tecniche risolutive, per lo meno interessante e, spero, divertente.