Quante scale musicali esistono? (parte prima)

Olivier Messiaen durante una lezione (1978)

Ricordate il mio post sulla matematica di Olivier Messiaen? Tra i numerosi punti di contatto con la matematica offerti dalla sua opera, citavo, in chiusura di post, i "modi a trasposizione limitata". Di che cosa si tratta? Per comprenderne il significato, occorre procedere un passo alla volta.
Ricorderete, dai miei antichi post sulla scala pitagorica, il concetto di "ottava": un intervallo tra due note in cui la nota più acuta ha una frequenza doppia rispetto alla nota più grave.
Dato che due note separate da un tale intervallo suonano come la stessa nota, anche se ad altezze diverse, si conviene di indicarle con lo stesso nome, per esempio "do": naturalmente si tratterà di due "do" diversi, uno all'ottava inferiore e l'altro all'ottava superiore.
Nel sistema musicale occidentale moderno, basato sul cosiddetto temperamento equabile, l'ottava viene suddivisa convenzionalmente in 12 intervalli uguali tra di loro, chiamati semitoni.

Ciascuna delle dodici "tacche" indicate nella figura corrispondono a note che possono essere utilizzate da un compositore, come colori sulla tavolozza del pittore. Se la nota di riferimento è un do, allora le note indicate dalle tacche sono, rispettivamente, il do diesis (per convenzione del sistema equabile coincidente al re bemolle), il re, il re diesis (uguale al mi bemolle), il mi, il fa, e così via.

Che cos'è una scala musicale? Semplicemente un insieme di note, scelte tra quelle offerte dal sistema equabile, cioè tra quelle corrispondenti alle dodici tacche, che un compositore decide di considerare come note "utilizzabili" in un certo brano musicale.
La selezione delle note appartenenti a una certa scala viene operata su un'ottava di riferimento (per esempio quella rappresentata nella figura precedente): implicitamente essa si riflette invariata su tutte le altre ottave.
Per esempio, se decidiamo di scrivere un pezzo in do maggiore, implicitamente scegliamo una tavolozza formata dalle sette note che compongono la scala di do maggiore. Sul diagramma precedente, le note utilizzabili (sette su dodici) sono quelle indicate in rosso:

Le note selezionate sono, in questo caso, il do, il re, il mi, il fa, il sol, il la, il si.
Nella figura è indicata (in blu) anche la nota posta all'ottava superiore: essa formalmente non fa parte dell'ottava di riferimento, ma, per quanto detto poco sopra, questa nota fa comunque parte delle note della scala, anche se ad un'ottava diversa.

Se invece preferiamo la scala minore (naturale), avremmo ancora sette note disponibili, ma sistemate in modo diverse sulle tacche dell'ottava:

In questo caso abbiamo selezionato il do, il re, il mi bemolle (cioè il re diesis), il fa, il sol, il la bemolle (cioè il sol diesis), il si bemolle (cioè il la diesis).

Siamo amanti della dodecafonia? Allora probabilmente adotterete la scala cromatica, cioè quella formata da tutte e dodici le note esistenti:

Queste sono soltanto tre delle numerose scale che possono essere costruite sulla base del sistema equabile. Ma quante sono, in tutto, le scale possibili?
Non è banale rispondere a questa domanda. Innanzitutto, dobbiamo renderci conto che esistono scale formate da un numero qualsiasi di note, ovviamente compreso tra 1 e 12. La scala maggiore e la scala minore naturale sono entrambe formate da sette note. La differenza tra le due sta nel diverso "pattern", cioè dalla diversa posizione che le sette note occupano sulla "retta" dell'ottava. La scala cromatica, invece, è formata da dodici note.

Come possiamo fare per costruire tutte le scale esistenti? Dato che le due note estreme dell'ottava di riferimento rappresentata sulla nostra retta graduata fanno convenzionalmente parte della scala (la prima a pieno titolo, la seconda all'ottava superiore), la costruzione di una scala consiste nella scelta di eventuali altre note comprese tra queste due note estreme.
Partiamo dalle scale formate da una sola nota (lo so, una scala formata da una sola nota è una scala ben strana; soprattutto immaginate quanto noiose possano essere le composizioni musicali fondate su tale scala! Eppure ci tocca considerare anche questo caso degenere, il quale, benché musicalmente poco interessante, è matematicamente degno al pari degli altri). Quante sono le scale di questo tipo? Una soltanto, visto che abbiamo già posizionato una nota all'inizio dell'ottava, e altre non ne possiamo mettere: non abbiamo alcuna possibilità di scelta.
Quante sono, invece, le scale formate da due note? Qui la faccenda si fa più complessa. Si tratta di decidere dove collocare una seconda nota, in modo da suddividere l'ottava in due intervalli. Le possibili scelte a nostra disposizione corrispondono, matematicamente parlando, alle partizioni di cardinalità 2 del numero intero 12, cioè ai modi possibili di scrivere 12 come somma di 2 interi positivi, senza tener conto dell'ordine degli addendi:

12 = 1 + 11

12 = 2 + 10

12 = 3 + 9

12 = 4 + 8

12 = 5 + 7

12 = 6 + 6

La prima partizione, 12 = 1 + 11, ci suggerisce di partizionare l'ottava in due intervalli, rispettivamente formati da 1 semitono e da 11 semitoni, ottendo la seguente scala:

Esistono quindi soltanto 6 scale formate da due note? Non esattamente. Ricordiamoci che le partizioni elencate non tengono conto dell'ordine degli addendi. In altre parole, la partizione 12 = 1 + 11 va intesa anche come 12 = 11 + 1. Una scala altrettanto importante si ottiene quindi collocando l'intervallo di 11 semitoni prima dell'intervallo di 1 semitono:

Analogamente, la partizione 12 = 2 + 10 produce due scale diverse, derivanti dalle partizioni dell'ottava in due intervalli di 2 e di 10 semitoni: nella prima scala troviamo per primo l'intervallo di 2 semitoni, nella seconda scala quello di 10 semitoni.
E così accade anche per le successive tre partizioni (12 = 3 + 9, 12 = 4 + 8, 12 = 5 + 7). L'ultima partizione, 12 = 6 + 6, invece, produce una sola scala, perchè i due intervalli nei quali viene suddivisa l'ottava sono uguali tra di loro, essendo entrambi formati da 6 semitoni.
In tutto, quindi, contiamo 11 scale formate da due note.

Passando alle scale formate da tre note, dobbiamo conteggiare le partizioni di cardinalità 3 di 12, cioè i modi possibili di scrivere 12 come somma di 3 interi positivi, sempre ignorando l'ordine degli addendi. Abbiamo in tutto 12 partizioni:

12 = 1 + 1 + 10
12 = 1 + 2 + 9
12 = 1 + 3 + 8
12 = 1 + 4 + 7
12 = 1 + 5 + 6
12 = 2 + 2 + 8
12 = 2 + 3 + 7
12 = 2 + 4 + 6
12 = 2 + 5 + 5
12 = 3 + 3 + 6
12 = 3 + 4 + 5
12 = 4 + 4 + 4

Anche in questo caso, per ciascuna partizione dobbiamo considerare le possibili permutazioni. Ad esempio, la partizione 12 = 1 + 1 + 10 dà origine a 3 permutazioni (12 = 1 + 1 + 10, 12 = 1 + 10 + 1 e 12 = 10 + 1 + 1).

In generale, dobbiamo tener conto che si tratta di permutazioni con ripetizione: nello scrivere la somma che restituisce 12 come risultato, infatti, possiamo avere degli addendi che si ripetono (come l'1 nella partizione precedente). La formula che dobbiamo utilizzare in generale, quindi, è il fattoriale della cardinalità della partizione (nel caso che stiamo analizzando, 3!) diviso per il prodotto dei fattoriali delle numerosità delle singole ripetizioni di addendi. Nell'esempio 12 = 1 + 1 + 10, il numero di permutazioni è allora dato da 3! / 2!, cioè appunto 3.
Per la cronaca, le scale di tre note risultano alla fine essere in tutto 55. In modo analogo, con un po' di pazienza si può calcolare quante sono le scale di N note, con N compreso tra 1 e 12:

Notate in particolare la piacevole ed evidente simmetria nei numeri presenti nella seconda colonna.
In tutto, quindi, le scale possibili risultano essere 2048 (gli appassionati di musica e dell'omonimo videogioco forse ne saranno felici).
Attenzione, però: ognuna di questa scala può essere trasposta da un'ottava di riferimento a un'altra, cambiando in questo passaggio le proprie caratteristiche (e anche il proprio nome). Ma questi aspetti meritano un approfondimento, che fornirò nella seconda e ultima parte di questo post.
E i modi a trasposizione limitata di Messiaen, che cosa c'entrano? Un po' di pazienza, cari lettori: anche questo diventerà chiaro nella prossima puntata.

Carnevale della Matematica #84 su MaddMaths!

"Passato il santo, passato il miracolo", si dice spesso, e non a torto. Ma se il santo è il Carnevale della Matematica, bè, anche se sono passati 5 giorni dall'uscita dell'edizione di aprile, il "miracolo" non può essere considerato passato. E quindi spero mi perdonerete se promuovo soltanto oggi il Carnevale di aprile, mirabilmente organizzato da quell'ottimo sito che risponde al nome di MaddMaths!.
Introdotto dal verso "canta canta il merlo melodioso", che secondo la Poesia Gaussiana del sommo Popinga è associato al numero 84, il Carnevale di MaddMaths! ci regala un interessante sguardo su un tema molto particolare: i mestieri dei matematici. Proprio questo è il tema del mese della Consapevolezza Matematica 2015, versione italiana dell'americano Mathematics Awareness Month.
Come sempre molto numerosi e degni di nota i contributi dei blogger (tra cui il mio Gli enigmi di Coelum: l'ossessione di Clarke, che corrisponde alla seconda "puntata" della serie di approfondimenti sugli enigmi da me pubblicati sulla rivista Coelum: stavolta ho parlato di polimini, argomento classico della matematica ricreativa).
Congratulazioni a MaddMaths! per l'ottimo allestimento e a tutti i partecipanti. E buon divertimento a chi, dopo tutti questi giorni, non ha ancora letto il Carnevale.
La prossima edizione (con verso gaussiano (“zampettando tra i cespugli”) sarà ospitata dal Fondatore, Maurizio Codogno, sulle sue Notiziole di .mau.

Gli enigmi di Coelum: l'ossessione di Clarke

Continua la serie degli approfondimenti sugli enigmi da me pubblicati sulla rivista Coelum Astronomia. Questa volta tocca ai polimini, argomento da me già trattato anni fa su questo blog nei post "Come giocare su una scacchiera con i pezzi del Tetris" e "Ancora sui polimini".
Alcune delle informazioni che troverete in questo approfondimento, quindi, non saranno del tutto nuove per i lettori di Mr. Palomar: ma non credo che sia male rinfrescarle...
Anche il Sommo Popinga aveva parlato di polimini in un bel post del lontano 2012.

Per cominciare, cosa sono questi polimini? Beh, sono figure geometriche piane ottenute congiungendo tra di loro quadrati uguali e facendo in modo che ogni quadrato confini, tramite un lato, con almeno un altro quadrato. Se i quadrati da mettere insieme sono tre, esistono soltanto due possibili configurazioni (quella con i tre quadratini in fila e quella a L), che possiamo chiamare trimini.

Con quattro quadratini, possiamo costruire invece i tetramini, che sono in tutto cinque (vedi figura a lato).
Ciascuno di questi pezzi viene considerato sempre lo stesso tetramino anche se viene ruotato o riflesso in qualsiasi direzione. Ciò non avviene nel Tetris, dove non è possibile riflettere (o, se preferite, capovolgere) i pezzi. Per questo motivo i tetramini cadenti del celebre videogioco erano sette e non cinque: i pezzi a L e a S venivano rappresentati nelle due forme speculari.

Se abbiamo cinque quadratini, ecco i pentamini, che sono ben dodici, e per comodità memonica vengono contrassegnati ciascuno con una lettera dell’alfabeto (vedi figura a lato).

Analogamente, si può parlare di esamini (polimini da sei), eptamini (da sette), ottomini (da otto), e così via. I polimini formati da due soli quadratini, invece, sono molto meno interessanti dal punto di vista della matematica ricreativa, anche perché esiste una sola possibilità di costruire una forma siffatta. Qualcuno sostiene che questi polimini “banali” devono essere chiamati domini, e che ciò spiegherebbe l’origine del nome del celebre gioco del domino.
In realtà il gioco del domino deve il suo nome al colore delle tessere con le quali si gioca, notoriamente bianche e nere: gli stessi colori caratterizzavano infatti un antico costume carnevalesco a cappuccio, simile alla bautta veneziana, chiamato appunto domino. Il nome dell’antico gioco delle tessere costituisce soltanto una curiosa coincidenza linguistica.

A inventare i polimini fu un ventiduenne studente americano ad Harvard, Solomon W. Golomb.

Nel 1953, durante una noiosa lezione, Golomb cominciò a tracciare su un foglio delle figure costituite da unioni di quadratini. Resosi conto del potenziale interesse matematico della sua scoperta, Golomb si mise a classificarle (in base al numero di quadratini), e tentò di stabilire quanti polimini esistono per ciascun tipo.
A dire il vero, le figure ideate da Golomb non erano del tutto nuove: già nel 1907 Henry Dudeney, nei suoi celebri Canterbury Puzzles, aveva proposto dei problemi di fatto basati su polimini, e altri enigmi simili vennero pubblicati tra gli anni Trenta e gli anni Cinquanta dal bimestrale enigmistico inglese Fairy Chess Review.
Golomb, comunque, fu il primo a studiare la questione da un punto di vista matematico rigoroso e sistematico. Il suo primo sforzo fu rivolto a trovare una formula semplice che permettesse di determinare il numero di polimini di una certa specie.
Ad oggi una simile formula non è nota. Quel che si sa è che questo numero cresce molto rapidamente all’aumentare del numero dei quadratini: gli esamini sono 35, gli eptamini 108, e già con 12 quadrati si arriva a ben 63600 combinazioni possibili.

Qualche tempo dopo il giovane Golomb presentò la sua idea al Club di Matematica di Harvard, e il gioco dei polimini divenne rapidamente popolarissimo tra gli studenti. Fu Martin Gardner, il più famoso dei “giocologi” matematici, a diffonderlo in tutto il mondo grazie ai suoi articoli sul Scientific American.

I polimini rappresentano senza dubbio uno dei temi prediletti dalla matematica ricreativa. Esistono numerosi giochi e rompicapi costruiti attorno a queste figure geometriche. La maggior parte di questi problemi consiste nel tentativo di tassellare figure assegnate utilizzando polimini di un certo tipo.

Tra i problemi più classici vi è la tassellatura di rettangoli di area 60 (ad esempio 6×10, 5×12, 4×15 o 3×20) utilizzando i dodici pentamini esistenti. Esistono 2339 soluzioni per il rettangolo 6×10, 1010 per il rettangolo 5×12, e 368 per il rettangolo 4×15.

Come ricordavo nell’articolo su Coelum, il problema del rettangolo 3×20, che ossessionò Arthur Clarke, è invece molto più arduo, e le soluzioni sono soltanto due, come illustrato in figura.


Un altro problema famoso, affrontato da Dudeney e da Gardner, consiste nel coprire una scacchiera 8×8 con i 12 pentamini esistenti, lasciando vuote quattro caselle. Una possibile soluzione è illustrata nella figura a fianco.

Golomb escogitò un gioco competitivo basato su questo problema, oggi in commercio con il nome Quintillions: a turno, i due giocatori devono disporre sulla scacchiera un pentamino, finché uno dei due non ha più posto per collocare un pezzo. Golomb calcolò che una partita può durare dalle 5 alle 12 mosse.
Nella variante nota come Blokus, oltre ai pentamini si possono usare anche altri tipi di polimini.
Un altro problema molto citato, ideato dal matematico americano Raphael Robinson, è quello della triplicazione: mettendo insieme nove pentamini, si deve costruire una figura con la stessa forma di uno dei pentamini, ma tre volte più grande.

Nella figura a lato sono illustrati alcuni esempi, uno per ogni tipo di pentamino.

E i tetramini? Il fatto è che questi tipi di polimini sono meno interessanti dal punto di vista dei giochi matematici. Ad esempio, è stato provato che non esiste alcun modo di sistemare i 5 tetramini in un rettangolo di area 20.
Si deve quindi ricorrere a tassellature alternative: una di queste consiste nel sistemare i 5 pezzi in un rettangolo 3×7, con un quadratino escluso. Oppure, è possibile coprire un rettangolo di 5×8 celle con due set completi di tetramini.

La sfida di ottobre 2013 consisteva in un problema di tassellazione con tetramini, di mia invenzione. Si trattava di estendere il normale set di 5 tetramini, duplicandone uno, e di sistemare i sei pezzi così ottenuti in un rettangolo di dimensioni 4×6.

Riuscite a trovare qualche soluzione?
Attenzione che tra poco rivelerò quelle che conosco io (quindi, se desiderate cimentarvi nell'impresa, non leggete oltre!)

Le tre soluzioni a me note del problema, a meno di rotazioni e riflessioni, sono illustrate qui sotto:

Pare che non esistano altre soluzioni oltre a queste tre: è curioso notare che tutte e tre sono basate sulla duplicazione del pezzo a forma di T.
Buon divertimento a tutti con i polimini!

Carnevale della Matematica #83 su DropSea

È stato festeggiato ieri mattina, con grande (e meritata) eco mediatica, il più speciale dei Pi Day del secolo, quello che ci ha permesso di associare le prime nove cifre decimali di π alla data e all'ora.
Alle 9:26 e 53 secondi di ieri mi trovavo in un'aula di una scuola primaria in provincia di Belluno, a intrattenere una classe quarta con uno dei miei laboratori di matematica.

Avevo preparato per tempo i bambini, spiegando loro la particolarità della ricorrenza: al momento giusto hanno ricambiato con commovente entusiasmo, accogliendo lo scoccare dell'ora fatidica con un count down degno di una festa di capodanno o del lancio di un razzo destinato all'allunaggio.

Com'è tradizione, il Carnevale marzolino coincidente con il Pi Day è organizzato da Gianluigi Filippelli sul blog DropSea. E come sempre accade in quest'occasione, il bravo Gianluigi ha allestito una rassegna di grande qualità, punteggiando i numerosi contributi con le ormai celebri "Notizie pi greche": sorprende ogni volta il fatto che vi sia così tanto da raccontare su questo numero, e che non si esauriscano mai le sorprese e le curiosità matematiche.

In definitiva, un'edizione corposa e piena di cose interessanti da leggere: se volete saperne di più sul nobile rapporto tra circonferenza e diametro, non potete certo ignorare il fillippellesco post.

Mr. Palomar ha partecipato al Carnevale con il post (fuori tema) intitolato Gli enigmi di Coelum: alberi nel cielo. 

Ah, dimenticavo: ringrazio di cuore Gianluigi per avermi simpaticamente definito "rock star del gruppo" (evidentemente devo questo apprezzato quanto immeritato appellativo al fatto di aver scritto un librino sui Pink Floyd e la matematica).

Appuntamento alla prossima edizione del Carnevale, che sarà ospitata da quel signor sito che risponde al nome di MaddMaths. Complimenti a Gianluigi e a tutti i partecipanti al Carnevale. E lunga vita a π!

Gli enigmi di Coelum: alberi nel cielo

Come qualcuno ricorda, da ormai quasi due anni curo sulla prestigiosa rivista Coelum Astronomia una rubrica di matematica ricreativa, significativamente intitolata Moebius.

Questa mia attività è per me qualcosa di entusiasmante: immeritatamente posso dire di fare qualcosa di vagamente simile a quello che hanno fatto o fanno alcuni giganti della divulgazione matematica, come Martin Gardner, Douglas Hofstadter, e, per citare alcuni maestri di casa nostra, i Rudi Mathematici.

Insomma, lo ammetto: per me Moebius è un gran divertimento. Gli ingredienti principali di ogni articolo sono tre: un po' di matematica raccontata con semplicità, una sfida lanciata al lettore e un pizzico di astronomia per condire il tutto.

Se volete divertirvi anche voi con la matematica giocosa di Moebius, e mettervi alla prova ogni mese con un avvincente enigma, non dovete fare altro che abbonarvi a Coelum: vi basterà poi risolvere per primi il problema del mese per vincere sei mesi gratuiti!

Per gentile concessione della redazione, ho la facoltà di riproporre su questo blog, con qualche mese di ritardo, gli approfondimenti, a suo tempo usciti sul sito di Coelum, riguardanti i temi trattati negli articoli pubblicati sulla rivista cartacea: sono argomenti che in alcuni casi ho già in parte trattato su Mr. Palomar. Ma vedrete, non mancheranno le novità interessanti.

Comincerò con le note relative all'articolo uscito a settembre 2013, nel quale avevo suggerito una possibile parentela tra le costellazioni e le reti in matematica: in entrambi i casi ci troviamo di fronte a un insieme di nodi (le stelle) congiunte da archi (le linee che danno una "forma" alle costellazioni, così come vengono convenzionalmente raffigurate negli atlanti stellari).

I matematici hanno cominciato a parlare di reti, o di grafi, come talvolta si preferisce dire, in tempi relativamente recenti. Ad introdurre per primo questo concetto fu, intorno al 1736, lo svizzero Leonhard Euler (spesso italianizzato in Eulero), uno dei più grandi geni matematici di ogni epoca.

A offrire a Eulero l’assist per fondare la teoria dei grafi fu un curioso enigma che si ispirava alla particolare conformazione della città prussiana di Königsberg.

Questa città, che oggi si chiama Kaliningrad e si trova in territorio russo, è famosa per avere dato i natali al filosofo Immanuel Kant e al matematico David Hilbert. Il fiume che attraversa l’area cittadina, il Pregel, forma due vaste isole, che nel Settecento erano collegate tra di loro e con le due aree principali della città tramite sette ponti. Il problema consisteva nel tracciare un percorso che attraversasse ognuno dei sette ponti una e una sola volta, tornando infine al punto di partenza.
Oggi i matematici chiamano “euleriano” un percorso di questo tipo. Cosa fece Eulero per meritare un simile onore? Semplicemente dimostrò che a Königsberg non esiste un circuito euleriano.

Come vi riuscì? La mossa vincente fu formulare il problema in termini di “rete”. Eulero rappresentò infatti ciascuna delle aree urbane come un “nodo” e ciascuno dei ponti come un “arco”. Analizzando la rete che si era originata, si accorse che da ogni nodo usciva un numero dispari di archi; nel contempo riuscì a dimostrare che in una rete esiste un percorso euleriano se e soltanto se non vi sono nodi toccati da un numero dispari di archi. Ecco allora che la passeggiata euleriana sui ponti di Königsberg è impossibile.

Il bello è che Eulero fu il primo in assoluto a risolvere un problema ricorrendo a strumenti di questo tipo: mentre disegnava il grafo della città di Königsberg, di fatto Eulero stava fondando un nuovo importante ramo della matematica.
I colleghi di Eulero lo snobbarono per questa sua trovata: secondo loro soltanto argomenti come l’analisi infinitesimale, la teoria dei numeri e la geometria erano degni delle attenzioni di un matematico, e tutto il resto era solo perdita di tempo.
Ma proprio il tempo diede ragione a Eulero. Oggi la teoria dei grafi è considerata un’area fondamentale della matematica, insostituibile in molti rami della fisica, dell’ingegneria, dell’informatica.
Senza rendercene conto, tutti i giorni abbiamo a che fare con le reti: cosa sono, secondo voi, gli alberi genealogici, gli organigrammi aziendali, i diagrammi di flusso, gli schemi elettrici? E che dire del reticolo di strade della nostra città, della rete dei telefoni cellulari, di internet, del web, dei social network?
Perché, allora, non trattare anche le costellazioni come reti? Un tempo gli atlanti si limitavano a mostrare le posizioni delle stelle presenti in ogni costellazione, decorando il tutto con eleganti disegni ispirati a personaggi mitologici; ma in tempi più recenti sono comparse le familiari linee che congiungono le stelle tra di loro. Questi intrecci sono reti a tutti gli effetti, e per di più planari, in quanto le linee non si intersecano mai, se non nelle stelle stesse.

Già nel 1930 furono stabiliti i confini convenzionali delle costellazioni, ma il modo in cui le stelle di ogni costellazioni vengono collegate tra di loro non fu mai oggetto di standardizzazione. A seconda che il disegno di una costellazione contenga o meno circuiti chiusi, ci possiamo trovare di fronte a una rete qualsiasi o ad una rete speciale, chiamata “albero”.

Sono chiamati alberi, quindi, i grafi in cui, presi a caso due nodi, esiste esattamente un percorso che li congiunga. Ovviamente, il carattere “arboreo” o meno di una costellazione è legato alla libera scelta di come unire le stelle l’una all’altra. Cassiopea, ad esempio, viene tipicamente disegnata come una grande W, ma nessuno ci impedisce, per una volta, di trasgredire e tratteggiarla in modo diverso.
Il problema di settembre 2013 richiedeva appunto di ridisegnare Cassiopea in modo che le stelle Segin, Ruchbah e Tsih siano collegate ciascuna a una sola stella, mentre Caph è collegata a tre stelle. Veniva anche richiesto di dimostrare l’unicità della soluzione trovata.

Siete in grado di risolvere l'enigma? Se volete provarci da soli, aspettate a leggere il seguito di questo post! (ovviamente, per chi indovinerà la risposta non ci sarà nessun premio, se non la soddisfazione di essere riusciti nell'intento)

Un possibile approccio per risolvere il rompicapo è il seguente.

 

Dato che le stelle prese in considerazione sono cinque (Segin, Ruchbah, Tsih, Shedir e Caph), si tratta di disegnare un albero formato da cinque nodi. Ora, dal punto di vista della topologia della rete, un simile albero può essere di tre tipi soltanto (vedi figura).

Che esistano soltanto queste tre topologie lo si può vedere molto facilmente. Provate a costruire un albero di cinque nodi passo dopo passo, cioè partendo da un nodo soltanto e aggiungendo via via gli altri: vi accorgerete che le opzioni possibili vi porteranno comunque verso queste tre conformazioni, e nessun’altra è raggiungibile.
Dato che nella nuova Cassiopea che vogliamo costruire c’è una stella (Caph) collegata a tre stelle, possiamo senz’altro escludere il primo tipo di albero (in cui nessun nodo ha tre adiacenti) e anche il secondo (nel quale il nodo centrale ha quattro adiacenti, e gli altri quattro ne hanno soltanto uno, appunto quello centrale).
Siamo quindi nel terzo prototipo di grafo, nel quale vi è un nodo C (nel nostro caso Caph) legata a tre suoi vicini (B, D, E). Dato che Segin, Ruchbah e Tsih devono avere una sola vicina, il nodo B è sicuramente Shedir, adiacente a Caph e collegato a due nodi.
Per trovare la soluzione, non ci resta che abbinare i nodi A, D ed E alle stelle Segin, Ruchbah e Tsih. Due di questi (D ed E) devono legarsi a Caph, e un altro (A) a Shedir. Da una rapida analisi della disposizione delle stelle di Cassiopea, appare evidente che soltanto scegliendo Ruchbah come nodo A (e quindi abbinando Segin e Tsih ai nodi D ed E) si evitano sovrapposizioni di linee, preservando la planarità del grafo.
Quindi l’unica soluzione compatibile con gli indizi dati è quella illustrata nella figura seguente (dove gli archi dell’albero individuato sono mostrati in rosso, sovrapposti alla tradizionale W di Cassiopea):

Carnevale della Matematica #82 su Rudi Matematici, ovvero "Mr. Palomar è diverso"

Per la prima volta in più di 4 anni, Mr. Palomar non ha partecipato questo mese al Carnevale della Matematica. Perché? Si è forse stufato di far parte di questo nobile cenacolo? No, assolutamente no, decisamente no! Semplicemente, come i miei sparuti lettori avranno già notato, impegni e concomitanze varie hanno fatto sì che le ultime settimane siano state poco generose in termini di post, cosicché nessun contributo poteva essere offerto all'evento carnevalizio di febbraio. Ma sicuramente, già dal prossimo mese, Mr. Palomar tornerà.
La mia diserzione di questo mese, devo dire, mi ha addolorato in modo particolare, per almeno tre buoni motivi:
1) perché il Carnevale della Matematica è sempre il Carnevale della Matematica (altro che il Festival di Sanremo);
2) perché quello di febbraio è il Carnevale più autenticamente carnevalesco dell'anno;
3) perché quello di febbraio è tradizionalmente il Carnevale della Matematica ospitato dagli ineffabili Rudi Mathematici, e potete tutti capire che un Carnevale ospitato dai Rudi è sempre, inevitabilmente, qualcosa di superlativo.
Insomma, quando ho scritto agli amici Rudi comunicando la mia assenza, l'ho fatto con un certo dispiacere.
Quando poi il Carnevale è uscito, sabato scorso, ho cominciato a leggerlo, trovandovi mille conferme alle alte aspettative che i valenti Rudi ogni volta generano. Il tema, di per sè geniale, era la diversità, ovvero: "famolo strano". Il nome in codice gaussiano lo lascio raccontare ai Rudi stessi:

Negli anni (perché sì, è indubbio: 82 diviso 12 fa un numero plurale di anni) si sono consolidate delle tradizioni. Una, ad esempio, è quella che ha aperto questo post, proprio sotto il titolo: trattasi di un verso poetico, per la precisione dell'ottantaduesimo verso della Poesia Gaussiana (o dell'unicità della fattorizzazione) del sommo Popinga. Ha il sublime e duplice fascino d'essere infinita e al tempo stesso prevedibile (almeno nella struttura), come solo le consapevolezze scientifiche e le debolezze umane sanno essere. E con questo, all'Ignaro Pellegrino dovremmo aver sciolto il primo dubbio, dacché "canta innamorato" potrebbe perfino apparir incongruo, in un posto (e in un post) dove ci si aspetta matematica. O forse no... in fondo, ce lo ricordiamo benissimo, che oggi è la festa degli innamorati; e poi, come se non bastasse, siamo pure in piena settimana canterina. E se pensate che si stia scherzando, o beh... alla fin fine è anche la settimana cruciale del Carnevale (quello tout-court).

Oltre ai numerosi contributi, magnificamente presentati dai padroni di casa, il Carnevale propone anche un divertente "quiz fotografico": i Rudi hanno infatti raccolto una serie di immagini di famosi scienziati ritratti in atteggiamenti insoliti (per esempio in moto o nel bel mezzo di una corsa, o intenti a giocare con strani trastulli, o a suonare il violino o i bonghi, e così via). Quale miglior modo di celebrare la diversità, ovvero, in questo caso, il genio?

Ma, continuando a leggere il Carnevale dei Rudi, a un certo punto mi sono accorto che, nonostante la mia dichiarata assenza, veniva comunque menzionato il mio nome. Com'è possibile? Bè, il mitico trio ha individuato, proprio nella mia (inevitabile) decisione di non figurare tra i contributori, un segno di diversità, al punto da decidere di proclamarmi "vincitore del Carnevale":

Tempo di far calare il sipario, mentre ancora volano coriandoli per l'aere. Non prima di aver stabilito il vincitore del Carnevale, però ("Vincitore? Che vincitore? Non c'è mai stato un vincitore, in tutta la storia dei carnevali matematici..."). Ebbene, il vincitore è - lo stabiliamo or ora - colui che si è mostrato più aderente al tema: e in questa edizione il vincitore è, senza ombra di dubbio, Paolo Alessandrini, fedele e abituale Carnevalista, che ci ha scritto scusandosi di non poter dare, stavolta, contributo veruno. C'è qualcuno che può obiettare, in questo Carnevale della Diversità? Più diverso di così...

Confesso che non avevo minimamente pensato alla mia defezione come un segnale di diversità. Ma, a ben vedere, i Rudi hanno perfettamente ragione. Sono stato diverso da tutti gli altri partecipanti, ma soprattutto diverso da me stesso, avendo sempre partecipato dal lontano gennaio del 2011.
Leggendo quanto ho riportato sopra, lo ammetto, ho riso di gusto per diversi minuti. Grazie di cuore, Rudi! Grazie a voi posso ancora dire di essere stato presente a tutte le edizioni del Carnevale!
Il prossimo mese il Carnevale sarà celebrato nel giorno del Pi-Day, cioè il 14 marzo: come è consuetudine a ospitarlo sarà il blog DropSea, di Gianluigi Filippelli.
Evviva il Carnevale, evviva i Rudi!

Un anno di matematica e Pink Floyd

Ieri il mio librino La matematica dei Pink Floyd ha compiuto un anno, dato che è uscito ufficialmente il 24 gennaio 2014.
Sono stati dodici mesi entusiasmanti: ho avuto l'onore di presentare l'e-book al Salone Internazionale del Libro di Torino ma anche in altre occasioni non meno divertenti, presso biblioteche e scuole e all'interno di trasmissioni radiofoniche.
Il destino ha anche voluto far sì che l'anno del mio librino coincidesse con l'anno del ritorno dei Pink Floyd, con il nuovo album The endless river.
Anche il 2015 mi vedrà impegnato a parlare del mio e-book.
Il prossimo martedì 24 febbraio sarò alla Biblioteca Comunale di Maserada sul Piave, in provincia di Treviso, dove sarà riproposta una serata simile a quella di Breda di Piave dello scorso novembre: non un classico incontro con l'autore, ma una carrellata di suggestioni musicali e matematiche, un assaggio dei temi trattati nel libro, e poi immagini, video, letture.

Interverranno Stefano Zamuner, che con la sua chitarra regalerà alcune preziose atmosfere floydiane, e Christian Stradiotto, che leggerà alcuni passi del libro.
La serata, ovviamente a ingresso libero, avrà inizio alle ore 20.30. 

Ringrazio la Biblioteca e l'Amministrazione di Maserada per la stimolante opportunità che mi hanno offerto. E mi raccomando (almeno chi si trova dalle parti di Treviso): non mancate all'appuntamento!

Carnevale della Matematica #81 su Scienza e Musica

Come spesso accade, giungo in ritardo a recensire il Carnevale della Matematica. Che poi, a ben vedere, il Carnevale è già di per sè un insieme (e che bell'insieme!) di recensioni di post, e almeno uno dei post recensiti è sempre di Mr. Palomar: se allora quest'ultimo a sua volta recensisce il Carnevale in un post che potrebbe anche finire sul successivo Carnevale, ecco chiudersi un anello che quasi quasi il buon Hofstadter definirebbe "strano".
Ma non divaghiamo: il Carnevale di inizio 2005 è stato ospitato da Leonardo Petrillo nel suo blog Scienza e musica, con l'interessante tema "Storia, Personaggi e Applicazioni dell'Analisi Matematica".
Se non l'avete ancora letto, fate attenzione: è un Carnevale ricchissimo, ma che dico ricchissimo, monumentale, ma che dico monumentale, enorme. Il bravo Petrillo ci regala una magnifica e memorabile introduzione storica sull'analisi matematica, che non parte, come solitamente si fa, da Newton e Leibniz, ma da molto prima, come spiega lo stesso Leonardo:

Sì, è vero, vengono considerati giustamente "padri" di tale disciplina le grandi menti di Isaac Newton e Gottfried Wilhelm von Leibniz (tra l'altro in accesa disputa fra loro), eminenti personalità scientifiche del XVII secolo, tuttavia la nostra introduzione partirà, come giusto che sia, da tempi molto più remoti.
Anzi, ci focalizzeremo proprio sulle origini antiche di questa branca della matematica, in quanto in tal contesto non sarebbe possibile affrontare tutti i numerosissimi e straordinari sviluppi che ci furono dopo i lavori di Newton e Leibniz (ci dovremmo dilungare davvero troppo e inoltre si rischierebbe di non poter fare a meno di un certo livello di tecnicismo, inadeguato per un'introduzione di un carnevale).

Il Carnevale, poi, propone la sua generosa carrellata di contributi, alcuni a tema e altri no: e in questa seconda categoria rientra anche il post offerto da Mr. Palomar, sul premio Turing Donald Knuth.
Dimenticavo una cosa molto importante, anzi due: il nome gaussian-popinghiano in codice di questa edizione è "il merlo, il merlo: il merlo? il merlo!", e la sua cellula melodica è... bè, andate a vedere da voi, no?
E non dimenticate che la prossima edizione del Carnevale sarà ospitata, come tradizionalmente accade a febbraio, da quei simpaticoni dei Rudi Mathematici, con il tema (davvero azzeccatissimo) della diversità. Buon Carnevale a tutti!

I premi Turing: Donald Knuth

Ricordo che ai tempi dell'università mi imbattevo di continuo in articoli o libri di informatica che, nella bibliografia, immancabilmente citavano uno dei testi sacri di questa disciplina: The Art of Computer Programming (in italiano L'arte della programmazione), dell'informatico americano Donald Knuth.
Probabilmente contagiato da questa usanza, anch'io alla fine decisi di inserire il sacro titolo nella bibliografia della mia tesi, come potete vedere nella figura qui a fianco.
Donald Knuth ha festeggiato proprio l'altro ieri, 10 gennaio, il suo settantasettesimo compleanno. Quando a Padova trovavo il suo libro citato ovunque, l'insigne ricercatore era appena più che cinquantenne: e io che me lo figuravo come un accademico decrepito, se non addirittura già defunto!
The Art of Computer Programming (spesso citata come TAOCP) è una monografia in più volumi, riguardante la teoria degli algoritmi e la loro analisi. Nei piani iniziali di Knuth, cioè attorno al 1962, doveva diventare un libro singolo in dodici capitoli. Negli anni successivi, però, il progetto si ampliò moltissimo, al punto che l'autore decise di strutturare la monografia in ben sette volumi. I primi tre uscirono rispettivamente nel 1968, nel 1969 e nel 1973. Si dovette attendere il 2005 per vedere una prima edizione del quarto volume (che venne completato nel 2011). L'opera è quindi tuttora largamente incompleta, e nuovi volumi sono attesi per i prossimi anni.

Seguendo le orme del padre, organista dilettante, anche il giovane Donald studiò musica, e da ragazzo suonava l'organo in chiesa alla domenica. Una sua passione giovanile era inventare cruciverba, che poi pubblicava nel giornalino della scuola. A quattordici anni vinse un concorso sponsorizzato da una ditta di dolciumi. La sfida era formare il maggior numero possibile di parole con le lettere di "Ziegler's Giant Bar": Donald ne trovò ben 4500, mentre i giudici stessi ne avevano soltanto 2500 nella loro lista di riferimento.
Oltre che dalla musica e dall'enigmistica, Donald era fortemente attratto dalla fisica e dalla matematica, e per molto tempo fu incerto su quale sarebbe stata la sua strada. Un bel giorno decise che sarebbe diventato un fisico, ma nemmeno questa si rivelò essere la scelta definitiva: alla fine cambiò facoltà e si iscrisse a matematica (la musica è tuttavia rimasta un suo grande amore: oggi trascorre molto tempo suonando un organo a canne che è stato installato nella propria abitazione).

Knuth ottenne il dottorato in matematica nel 1963, al California Institute of Technology, dove subito dopo fu assunto come professore associato. In quegli anni ricevette la proposta di scrivere un libro sui compilatori, e fu questo l'assist che lo portò a redigere il suo celebre e monumentale trattato.
Lavorò poi per la NSA (National Security Agency), e nel 1968 divenne professore alla Stanford University.
Gli anni successivi lo videro destinatario di una lunga serie di importanti premi: oltre al premio Turing, vinto nel 1974, Knuth fu insignito del Grace Murray Hopper Award, della National Medal of Science, del John von Neumann Medal e del prestigioso Premio Kyōto.
Nel 1992 Knuth si ritirò dall'insegnamento: di tanto in tanto tiene ancora lezioni informali, che lui ama chiamare "computer musings" (meditazioni informatiche"). Citando la sua celebre opera, la Stanford University lo ha insignito del titolo di "Professor Emeritus of The Art of Computer Programming".

Il contributo principale di Knuth, riversato in TAOCP e motivo dell'assegnazione del premio Turing, riguarda soprattutto la teoria degli algoritmi e la loro analisi. Cosa significa analizzare un algoritmo? Essenzialmente determinare la quantità di risorse (tempo e spazio di memoria) necessarie per eseguire l'algoritmo stesso su un computer. Naturalmente, la quantità di risorse necessarie dipende dalla mole di dati che vengono dati in ingresso all'algoritmo: tuttavia, è di solito possibile stabilire una funzione che lega queste due grandezze, cosicché si scopre che esistono algoritmi la cui funzione cresce molto rapidamente e algoritmi per i quali la funzione si mantiene invece su livelli bassi anche per grandi quantità di dati in ingresso. Si dice che gli algoritmi del primo tipo hanno un'alta complessità, mentre quelli del secondo tipo, caratterizzati da una complessità più bassa, si rivelano quelli preferibili per la risoluzione di problemi.
Nel suo trattato Knuth considera in dettaglio molti problemi computazionale, fornendo indicazioni sugli algoritmi utilizzabili per risolverli e sistematizzando le tecniche matematiche rigorose per l'analisi della complessità.

Oltre che per queste fondamentali ricerche, Knuth è noto anche per avere creato il sistema tipografico TeX, adatto alla composizione di testi matematici e scientifici. Da questo sistema, Leslie Lamport,  vincitore del premio Turing nel 2013, derivò il popolare linguaggio di markup LaTeX.
Restando sempre nell'ambito tipografico, Knuth inventò anche METAFONT, un linguaggio di programmazione usato per definire font vettoriali.
Un altro merito di Knuth è legato alla cosiddetta "literate programming", un approccio alla programmazione in cui il programma viene descritto utilizzando una lingua naturale come l'italiano, inframezzando qua e là porzioni di codice: il contrario di quello che fanno solitamente i programmatori, che producono lunghi file di codice con qualche commento in linguaggio naturale ogni tanto.
Knuth, inoltre, è sempre stato un fiero oppositore del concetto di brevetto nel capo del software.

Ma al si là dei suoi risultati nell'ambito della ricerca informatica, Donald Knuth è celebre per la sua poliedricità, per il suo umorismo e per certe scelte per così dire bizzarre.
Per cominciare, non usa più la posta elettronica dal 1990: lui stesso afferma di averla utilizzata solo per 15 anni, a partire dal 1975. In questa pagina spiega le ragioni della sua scelta.

Per ogni errore scovato nei suoi libri, Knuth riconosce un premio di 256 penny, cioè, come dice lui, un "dollaro esadecimale".
I numeri di versione del sistema TeX tendono asintoticamente al valore di π. Dopo la versione 3, sono stati assegnati via via i valori 3.1, 3.14, 3.141 e così via.
Per il sistema METAFONT il meccanismo è lo stesso, ma la versione limite è il numero e. Knuth ha affermato che gli eventuali bug ancora presenti al momento della sua morte saranno promossi a funzionalità, e le versioni saranno fissate ai valori π ed e.
Infine, Knuth è anche uno studioso della Bibbia, e autore di un bizzarro libro in cui analizza il testo sacro prendendo in esame soltanto il sedicesimo versetto del terzo capitolo di ciascun libro. Se volete ascoltare Knuth parlare della Bibbia, recatevi il prossimo 8 marzo nella prima chiesa luterana di Palo Alto: sentirete il padre dell'arte della programmazione raccontare il suo progetto di scrivere una complessa opera per organo basata sull'Apocalisse di San Giovanni.