Buon 2017!

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

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

Gli enigmi di Coelum: La Coppa dei Mondi

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

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

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

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

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

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

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

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

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

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

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

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

I Premi Turing: Michael Rabin e Dana Scott

Michael Rabin

La serie dedicata agli informatici che hanno vinto il Premio Turing prosegue con una lentezza geologica: perdonatemi. Ma, come sa bene chi li studia, i fenomeni geologici procedono con inesorabile costanza: si va adagio, ma non ci si ferma.

Nel 1959, Michael Rabin e Dana Scott scrissero un articolo intitolato “Finite Automata and Their Decision Problem”, con il quale nasceva un nuovo settore dell’informatica teorica: lo studio degli automi non deterministici.

Un automa non deterministico è una variante, o meglio una generalizzazione, del classico concetto di automa a stati finiti (deterministico). Un automa a stati finiti (deterministico) è un’astrazione con la quale è possibile descrivere il comportamento di molti sistemi reali. Più nello specifico, esso è costituito da:
- un insieme finito I dei possibili input (o ingressi) del sistema;
- un insieme finito O dei possibili output (o uscite) del sistema;
- un insieme finito S dei possibili stati del sistema;
- una "funzione di transizione" f, che stabilisce univocamente quale dei possibili stati del sistema sarà il prossimo, noti lo stato attuale e l'input attuale;
- una "funzione degli output" g, che stabilisce qual è l'output del sistema, noti lo stato attuale e l'input attuale.

Visto che siamo in periodo di feste di fine anno, consideriamo un kit di luci per un albero di Natale: immaginiamo che vi sia un interruttore che, premuto una prima volta, accende le luci in una modalità fissa, e, premuto una seconda volta, attivi la modalità intermittente. Se premiamo l’interruttore una terza volta, le luci si spengono, e il ciclo può essere riavviato.
Il sistema preso ad esempio è molto semplice: ha un solo input possibile (la pressione dell'interruttore), due output (le luci fisse e le luci intermittenti) e tre stati, che possiamo denominare rispettivamente “S” (spento), “F” (fisso), “I” (intermittente). L’automa a stati finiti (deterministico) che descrive il nostro luccicante sistema può essere quindi disegnato come segue:

Nel grafo sono rappresentate, in modo abbastanza autoesplicativo, le funzioni di transizione e delle uscite.

Ora vi chiedo un ulteriore sforzo di immaginazione (coraggio, abbiamo quasi finito, poi resta la parte più semplice e biografica del post): supponiamo che la funzione di transizione, anziché "produrre" come valore uno dei possibili stati del sistema, "produca" una collezione di stati futuri, cioè un sottoinsieme di S. Il risultato sarà un automa a stati finiti non deterministico.
Calma, ragazzi: com'è possibile che la funzione di transizione determini più stati futuri, anziché uno solo? Proprio così: il sistema si può trovare, nello stesso istante, in diversi stati contemporanei, un po' come il gatto di Schrödinger che è vivo e morto nello stesso tempo. Questa è la differenza, o meglio la generalizzazione, rispetto al caso tradizionale deterministico.

Dana Scott

Naturalmente la versione non deterministica è più astratta e meno intuitiva da digerire rispetto alla sua omologa deterministica. Tuttavia, credetemi, questo modello matematico si presta a modellare molte situazioni reali per le quali la versione deterministica sarebbe troppo poco espressiva.

I due ideatori della nozione di automa a stati finiti non deterministico, ovvero Rabin e Scott, provenivano da contesti diversi. Rabin era nato nel 1931 a Breslavia, città allora appartenente alla Germania, oggi alla Polonia, ed era figlio di un rabbino ebreo. All'età di quattro anni si trasferì con la famiglia nel Mandato britannico della Palestina, dove ebbe l'opportunità di coltivare il suo talento per la matematica studiando nella migliore scuola superiore di Haifa e poi, dal 1949, presso l'Università Ebraica di Gerusalemme. Si laureò nel 1953 e conseguì il dottorato nel 1956.
Scott, invece, era nato a Berkeley, in California, nel 1932. Frequentò la prestigiosa Università della sua città studiando logica e filosofia e ottenendo la laurea nel 1954. Trasferitosi a Princeton, ricevette il PhD nel 1958, sotto la supervisione del celebre matematico Alonzo Church. Subito dopo ottenne un incarico di insegnamento presso l'Università di Chicago.

Nel 1959 la IBM organizzò, nei pressi di New York, un workshop estivo al quale invitò un gruppo ristretto di giovani e promettenti ricercatori. Tra i cervelli selezionati c'erano sia Rabin che Scott: fu così che i destini dei due studiosi si incrociarono.
Probabilmente i due non avrebbero mai pensato che, grazie all'articolo scritto in quell'estate newyorkese, avrebbero fondato una nuova branca dell’informatica teorica e avrebbero vinto, diciassette anni dopo, il premio più prestigioso dedicato alla computer science.
L'importanza del loro concetto di automa non deterministico non venne riconosciuta subito. Tuttavia, dopo il fatidico 1959, la carriera dei due scienziati fu piuttosto rapida. Rabin tornò all'Università di Gerusalemme, dove a soli 29 anni divenne professore associato e capo dell'Istituto di Matematica. Quattro anni dopo era professore ordinario. Scott ottenne un posto a Berkeley, si spostò qualche anno dopo a Stanford e poi a Princeton.

Negli anni successivi Rabin e Scott si occuparono non soltanto di automi non deterministici ma anche di altri temi dell'informatica teorica. Scott divenne un guru nel campo della logica matematica, specialmente per quanto riguarda le logiche non classiche e la semantica denotazionale. Rabin, invece, contribuì in modo determinante allo studio degli automi probabilistici, agli algoritmi di confronto tra stringhe (pattern matching), alla crittografia e alla sicurezza informatica. Trasferitosi nel 1975 al MIT come visiting professor, ideò assieme a Gary Miller un fondamentale procedimento, basato sull'ipotesi di Riemann generalizzata, per determinare velocemente se un numero è primo o no.

Carnevale della Matematica #104

 Canta allegro, canta, canta

 (dalla Poesia Gaussiana del Sommo Popinga)

Benvenuti all'edizione n. 104 del Carnevale della Matematica, la quinta ospitata da Mr. Palomar.
Anche nel 2015 era capitato a queste pagine ospitare l'illustre rassegna di contributi a sfondo matematico durante il mese di dicembre. Visto  che la curiosa evenienza si è verificata anche quest'anno, ho ritenuto opportuno proporre un tema di atmosfera natalizia: senza molto fantasia, la scelta è caduta su "stelle, nastri, palle, alberi, code e altre suggestioni matematico-natalizie".
Forse giustamente, pochi dei partecipanti si sono lasciati vincolare da questa traccia, ma noi veterani del Carnevale sappiamo bene che non succede mica niente se si va fuori tema: anzi, non ditelo a nessuno, ma quasi quasi è meglio.
Il Carnevale della Matematica, idea sempre luminosa del mai abbastanza lodato .mau., ha ormai ampiamente superato quota cento, ma non dimostra certo la vetustà di un ultracentenario: come un giovane e vispo virgulto, canta allegro ("canta, canta"), e lo fa sulle vivaci note della cellula melodica dell'amico Flavio "Dioniso" Ubaldini:

Prima di iniziare a scorrere i contributi, vediamo, com'è nella tradizione del Carnevale, alcune proprietà matematiche del numero 104.
Naturalmente, si tratta di un numero pari (quindi, a maggior ragione, non primo ma composto, ragion per cui il motto gaussiano di cui sopra è composto da più parole): i suoi divisori sono 1, 2, 4, 8, 13, 26, 52 e lo stesso 104. Poiché i divisori sono 8, e 8 è uno di loro, si dice che 104 è un numero rifattorizzabile o un numero tau. Essendo pari alla somma di alcuni dei suoi divisori (104 = 1 + 4 + 8 + 13 + 26 + 52), è anche un numero semiperfetto. Perfetto non è, perché sommandoli tutti si va oltre 104 (per questo è detto anche numero abbondante).
Assieme al suo consecutivo 105, forma una coppia di Ruth-Aaron, in quanto la somma dei loro fattori primi senza considerare l'esponente è in entrambi i casi 15.
Compare nelle terne pitagoriche (40, 96, 104), (78, 104, 130), (104, 153, 185), (104, 195, 221), (104, 330, 346), (104, 672, 680), (104, 1350, 1354) e (104, 2703, 2705).
Può essere scritto come somma di quadrati, dato che 104 = 10² + 2².
Infine, è il più piccolo numero di segmenti lineari unitari che possono esistere in un piano, dove quattro di loro si toccano ad ogni vertice.

Uscendo per un attimo dal seminato matematico, dal 2008 è attivo a Parigi un importante centro culturale ed espositivo di 39000 m². Esso è situato in un edificio industriale ottocentesco, un tempo servizio comunale di pompe funebri: trovandosi al numero 104 di Rue d’Aubervilliers, ha preso il nome di "Cent Quatre".

104 è anche il numero di sinfonie di Joseph Haydn (o per lo meno il numero ufficialmente riconosciuto, dato che sicuramente il grande compositore ne scrisse di più).
La più famosa di queste sinfonie è la Sinfonia n. 45 in Fa diesis minore, scritta nel 1772 per il principe Nikolaus Esterházy. Quando la composizione venne eseguita la prima volta, a Eszterhaza, la residenza estiva del principe, nell'adagio finale i musicisti a turno smisero di suonare, spensero la candela del loro leggio e lasciarono la sala: il pezzo fu terminato soltanto da due violini con sordina, uno dei quali era suonato dallo stesso Haydn. Pare che con questo gesto il compositore volesse far capire al principe che il soggiorno a Eszterhazasi era prolungato a dismisura, e tutti i musicisti desideravano tornarsene al più presto presso le loro famiglie. Per questo motivo la sinfonia è universalmente nota come "Sinfonia degli addii".

E veniamo finalmente ai contributi.
Annalisa Santi, dal suo blog Matetango, mi segnala una Intervista Impossibile a Babbo Natale. Come mi scrive la stessa autrice, l'intervista nasce dalla constatazione che ogni bambino prova una grande delusione nel momento in cui scopre che Babbo Natale non è reale: ebbene, l'antidoto a tale dispiacere potrebbe essere un ragionamento fisico-matematico. Come suggerisce la stessa Annalisa, l'intervista potrebbe stimolare anche i più grandicelli a curiosare sui temi della fisica quantistica.

Flavio Ubaldini, noto anche come Dioniso Dionisi, recentemente divenuto anche apprezzato autore teatrale, nonché autore del blog Pitagora e dintorni, non si limita a fornire generosamente la sopra menzionata cellula melodica, ma contribuisce con alcuni suoi lavori.
In particolare, mi segnala Gli n-ternologi su Mathematics in Europe, in cui sottolinea che mentre qualcuno ne esce, il suo blog entra in Europa. Il sito Mathematics in Europe, infatti, ha pubblicato The concept of n-triplewatch, versione inglese del suo post Orologi con terne di singole cifre (n-ternologi) (che era stato seguito da N-ternologi: il 2-ternologio completato).
Flavio propone anche N-ternologi: il 2-ternologio semplificato
in cui racconta come, in seguito alla pubblicazione dell'articolo su Mathematics in Europe, Lorenzo Folcarelli, un giovane studente del Politecnico, abbia proposto una nuova 2-ternoformula per il numero 7.

Roberto Zanasi, dal glorioso blog Gli studenti di oggi
(quello che, per inciso, sarà eternamente ricordato per avere ospitato la prima edizione del Carnevale della Matematica, ormai più di 8 anni fa) offre La Formula del piccolo Gauss senza parole, con un bell'albero di Natale illuminato.

E veniamo ad Alice Riddle (al secolo Francesca Ortenzio), Rudy d'Alembert (all'anagrafe Rodolfo Clerico) e Piotr Rezierovic Silverbrahms (pseudonimo di Piero Fabbri), ovvero gli inimitabili Rudi Matematici. Mi scrivono chiedendo perdono per la fretta con cui mi inviano i loro contributi, ma al tempo stesso mi (ci, vi) regalano una serie di post che come al solito brillano per fantasia e intelligenza.
Il tradizionale Compleanno è dedicato a Norbert Wiener, ed è un pezzo che spazia in modo geniale e gustosissimo tra barzellette sui fisici e sugli ingegneri, circuiti elettrici, sciacquoni e cibernetica. Come sottolineano i tre Rudi, è anche ricchissimo di esempi di retroazione o feedback.
Per la serie dei Giochi del Capo, ecco una nuova puntata, Rien ne va plus 4 - Ogni tanto, va bene a tutti e due, in cui si parla di giochi finiti dove tuttavia si possono incontrare situazioni di loop potenzialmente infinito.
Si prosegue con MacBeth, un articolo che descrive un gioco molto simile all’Othello, al punto che il suo autore ha deciso di battezzarlo con un altro titolo di tragedia shakespeariana.
Infine, Il problema di novembre (579) - Vampiri lineari e quadratici, ovvero il classico post con la soluzione dell'ultimo problema proposto su Le Scienze.
I Rudi fanno poi sapere che il prossimo numero di RM, la rivista fondata nell'altro millennio, è in ritardo ma arriverà presto!

Tocca ora a Math is in the Air, blog divulgativo sulla matematica applicata, sempre molto ricco di spunti interessanti.
Davide Passaro mi comunica che lui e gli altri autori hanno deciso di contribuire con post "belli corposi, in modo che tutti abbiano qualcosa da leggere sotto l'albero mentre mangiano fritti, panettoni e dolci vari!"
Il primo articolo di Davide Passaro ha come titolo I colloqui con i genitori di un insegnante di matematica: la stupidità non è ereditaria. In questo articolo si parla del ruolo della matematica nella società e dell'unica esperienza più temibile di una riunione di condominio o di una fila alla posta: i colloqui fra genitori e professori.

Simulazione con Python: un esempio del profilo di temperatura nel tempo (Parte 2), di Rosario Portoghese, prosegue una serie dedicata alle equazioni differenziali e alla loro discretizzazione usando il linguaggio Python. Il tema è la simulazione dell'equazione di diffusione del calore.
La storia di Pi Greco: intervista recensione a Pietro Greco [Parte 1] è un'intervista al giornalista e divulgatore scientifico Pietro Greco, che parla del suo libro "Storia di Pi Greco" e riflette sulla sua esperienza di giornalista, sull'editoria e sul percorso di divulgatore scientifico.
Teoria dei giochi: il problema delle coppie è un articolo di Giulia Bernardi che prosegue la serie sulla teoria dei giochi. In questo caso si parla del problema delle coppie e di come la matematica può aiutare a trovare il giusto partner.

Completa l'elenco delle segnalazioni di "Math is in the air" il post Kaggle: The Home of Data Science, nel quale Andrea Capozio spiega cosa è Kaggle, una piattaforma online dedicata alle competizioni tra modelli predittivi e analitici.

Non sarebbe un normale Carnevale della Matematica se MaddMaths! non contribuisse con la sua consueta lunghissima serie di articoli di elevata qualità.
Si parte con Sono usciti i risultati dell'indagine OCSE-PISA 2015: nei giorni scorsi, sul sito https://www.oecd.org/pisa, sono stati resi noti i risultati dell’indagine OCSE-PISA 2015. PISA è l’acronimo di Programme for International Student Assessment, ed è un’indagine internazionale triennale volta a valutare le competenze dei quindicenni in scienze, matematica e lettura. L’indagine ha assunto una rilevanza planetaria sia dal punto di vista quantitativo che qualitativo: molto spesso infatti i risultati e le comparazioni tra Paesi sono motivo di dibattito sulla qualità dell’educazione, e talvolta influenzano le scelte di politica educativa.
In La marcia dei piccoli pinguini di Phillip Island si racconta di come alcuni ricercatori italiani di matematica abbiano osservato i piccoli pinguini di Phillip Island in Australia e abbiano trovato un modello matematico per descrivere il modo con cui tornano a casa (spoiler: ogni tanto qualche pinguino entra in crisi).
L'articolo La CIIM dice la sua sulla seconda prova dell'Esame di Stato relaziona sui lavori della Commissione Italiana per l’Insegnamento della Matematica dell'Unione Matematica Italiana (CIIM), che ha proposto un documento sulla questione dell'esame di Stato. Molti ritengono che quest'anno l'esame potrebbe vertere (per la prima volta nella storia del Liceo scientifico di ordinamento) sulla fisica invece che sulla matematica. Questo ha scatenato svariate reazioni nelle comunità vicine al mondo della scuola. MaddMaths! ha inteso dare spazio alla vicenda, alle varie opinioni in merito e agli sviluppi, partendo dal documento della CIIM.
Per quanto riguarda l'Angolo Arguto, MaddMaths! mi segnala Alla mostra di Escher al Palazzo Reale di Milano: Giuseppe Rosolini è andato a Milano a vedere la mostra del celebre artista olandese, e gli è piaciuta (ci ha incontrato anche Fabio Fazio, mi riferisce Roberto Natalini, ma questo Rosolini non lo scrive).


In Ripetizioni - Puntata 8: "Pane" di Davide Palmigiani, si parla di pane, frazioni, antico Egitto e ... Festival della scienza di Genova.
L'articolo Scuola Astre #3 - La teoria dei giochi e l’attività della Pubblica Amministrazione presenta il terzo elaborato della Scuola Astre, proposto da Andrea Renzi, del corso di laurea in Giurisprudenza.
Ricordo di Jean-Christophe Yoccoz, scritto da Stefano Marmi, giunge in seguito alla prematura scomparsa, avvenuta il 3 settembre scorso, di un grande scienziato e di un grande uomo.
In Il Club Segreto dei Triangoli Diversi e il problema dell’area, Fabrizio Calimera, Alessia Cristofanilli e Giulio Codogni descrivono una loro esperienza di teatro e matematica, e in dettaglio raccontano di come, in questo contesto, abbiano provato ad affrontare il problema dell'area.
Infine, se siete dei "buoni boccali" inglesi e volete assaggiare tutte, ma proprio tutte, le birre offerte dai pub del Regno Unito, ora la matematica vi viene in soccorso. Scopritelo in Ecco il "birra tour" perfetto tra i pub inglesi.

Se un Carnevale non può privarsi di MaddMaths!, ancora più imprescindibile è l'apporto del Fondatore, ovvero Maurizio .mau. Codogno, autore non di un solo blog ma almeno di due: quello sul Post, che porta semplicemente il nome del suo autore, e le Notiziole di .mau.
La produzione codogniana dell'ultimo mese è, come sempre, abbondante (anche se Maurizio mi scrive "poca roba stavolta").
Sul Post abbiamo la pillola Pubblicare da morti, con l'ultimo articolo scritto da Ron Graham e Steve Butler insieme a... Paul Erdős, morto vent'anni fa; e il post Più errori nel previsto (negli USA) dove .mau. racconta degli errori nei sondaggi americani.
Sulle Notiziole, al solito ci sono tanti quizzini della domenica: Lancette quasi sovrapposte, Bilancia taroccata, Frase autodefinita e Lavaggio auto. Codogno mi invia anche due recensioni: La magia della matematica (un approccio un po' diverso alle nozioni di matematica nelle scuole superiori) e Reflections: The Magic, Music and Mathematics of Raymond Smullyan (teoricamente un'autobiografia di Smullyan, praticamente, a parere di .mau., una delusione). Per finire, ecco anche Chi ha votato per Trump?, dove vengono spiegati alcuni possibili errori statistici che in genere passano inosservati.

Il blog Al Tamburo Riparato
mi propone Rivoltare una sfera: un contributo sul problema topologico dell'eversione di una sfera. Nell'articolo si parla anche di Stephen Smale: il matematico che, nel 1958, dimostrò che è possibile rivoltare una sfera senza praticare buchi o tagli. Il post si conclude con un valzer di Josef Strauss denominato, non a caso, "musica delle sfere".

Gianluigi Filippelli, autore di DropSea, tiene a precisare che nell'ultimo mese non ha scritto molto: l'unico suo dono al Carnevale di dicembre è Mondo matematico: la crittografia, una recensione/approfondimento particolarmente interessante sul libro "Matematici, spie e pirati informatici" della collana "Mondo Matematico".

Chiudo ricordando (autoreferenzialmente) i due post usciti negli ultimi giorni su queste pagine.
Gli enigmi di Coelum: Natale su Ganimede è l'ennesima puntata della serie sui miei problemi astro-matematici pubblicati negli anni scorsi sulla rivista Coelum. Questa volta è di scena un problema di ambientazione natalizia, con un Babbo Natale intento a svolazzare per il sistema solare a portare regali ai bambini buoni. Moebius di Natale, invece, riesuma un mio vecchio post sui nastri di Moebius, parlando anche dei miei laboratori matematici per bambini.

Ringrazio di cuore tutti gli amici che hanno contribuito al Carnevale con l'abituale bravura e generosità. Appuntamento all'anno nuovo per la prossima edizione. Evviva il Carnevale!

Moebius di Natale

In un mio vecchio post di 5 anni fa parlavo di nastri di Moebius e di alberi di Natale.
Un lustro dopo, ho il piacere di presentarvi un video nel quale illustro le meraviglie della celebre striscia.
Il video è stato realizzato per promuovere il mio laboratorio "Matemagica", che negli ultimi anni ho proposto numerose volte presso scuole e biblioteche. Con un manipolo di amici, abbiamo raccolto in un catalogo questa e altre proposte (laboratori didattici e spettacoli, non solo di matematica e informatica ma anche di geologia, educazione ambientale, chimica, cultura dell'informazione, musica e letteratura), e abbiamo denominato il progetto "Pitecum".
Un nome che sta a indicare una simpatica e curiosa scimmietta (un "piteco"), ma che trasmette pure un messaggio un po' folle che a noi piace molto: qualcosa come "il pi greco sia con te". 

Se vi interessano i nostri laboratori e i nostri spettacoli, contattateci al nostro indirizzo di posta elettronica, o mandateci un messaggio alla nostra pagina Facebook.
Il video sulla striscia di Moebius, e altri filmati analoghi, relativi ad altri laboratori inclusi nel catalogo del Progetto Pitecum, sono stati realizzati da Adriano Bianchi, in collaborazione con il GDS Dolomiti "E. Fermi". Questi video saranno presto pubblicati anche sul sito Redooc.com, assieme a nostri testi e lezioni illustrative.
Buon divertimento con i laboratori di Pitecum!

Gli enigmi di Coelum: Natale su Ganimede

Proseguendo la serie dedicata ai miei enigmi pubblicati in passato sulla rivista "Coelum", ho pensato di non rispettare, per la prima volta, l'ordine di pubblicazione degli articoli: questo allo scopo di offrirvi ora, in dicembre, il pezzo più "natalizio" che abbia mai pubblicato sulla suddetta rivista, evitandone così una inopportuna uscita intorno a Ferragosto.

Prendete un foglio di carta. Disegnate a caso alcuni punti, e colorate di rosso uno di loro. Immaginate ora che il punto rosso rappresenti il punto di partenza e di arrivo di un tragitto che deve necessariamente toccare anche tutti gli altri punti, ciascuno una e una sola volta.
Ora, se esaminate il vostro foglio, vi accorgerete che, molto probabilmente, esistono numerosi tragitti che soddisfano i requisiti: tutti partono dal punto rosso, passano attraverso tutti gli altri (ciascuno esattamente una volta), e finiscono di nuovo sul punto rosso. Il bello è che i percorsi possono avere lunghezze diverse. Il vostro compito è trovare il tragitto più breve tra tutti quelli ammissibili.
Ogni percorso possibile è formato da una sequenza di segmenti consecutivi, ciascuno dei quali congiunge tra di loro due punti. Per stabilire qual è il percorso più breve, dovete armarvi di righello (e di pazienza), prendere in esame tutte le soluzioni possibili e di ciascuna misurare la lunghezza totale (equivalente alla somma delle lunghezze dei singoli segmenti che congiungono i punti): in questo modo il problema si riduce alla fine a un confronto tra tutte le soluzioni trovate.
Una formulazione più rigorosamente matematica richiede che vengano specificate in partenza le distanze esistenti tra tutte le possibili coppie di punti. Ciò è necessario perché le coppie di punti connesse da segmenti in una certa soluzione sono in generale diverse dalle coppie congiunte in un’altra soluzione. I matematici chiamano grafo completo una rete di punti corredata di queste informazioni sulle distanze tra punti.
Il problema che ho descritto è noto come “problema del commesso viaggiatore”. È uno dei problemi classici della teoria dei grafi, e trae il suo nome dall’interpretazione tipica che viene data: un commesso viaggiatore deve visitare una serie di città (ciascuna esattamente una volta) partendo da una di esse e terminando il suo giro nella stessa città di partenza, scegliendo però il viaggio più breve possibile.
Ad esempio, consideriamo il grafo completo della figura qui sotto. Supponiamo che ognuno dei 4 nodi corrisponda a una città, e che gli archi che congiungono i nodi tra di loro rappresentino le strade che collegano una città all’altra.
Su ogni strada viene indicata la sua lunghezza (ad esempio in km). Consideriamo la città 1 come punto di partenza e di arrivo dei tragitti.

Un possibile percorso è quello che attraversa, nell’ordine, le città 1 – 4 – 2 – 3 -1. Se fate la somma dei numeri indicati sugli archi interessati, scoprite che la lunghezza complessiva di questo percorso è 95 km. Un altro percorso possibile è 1 – 3 – 4 – 2 – 1, la cui lunghezza è 80 km. Il secondo percorso, quindi, è migliore del primo.
Quanti sono i possibili percorsi che dobbiamo considerare? Il loro numero equivale al numero di possibili permutazioni dei nodi del grafo completo privato del nodo di partenza e di arrivo (che sicuramente deve trovarsi all’inizio e alla fine della sequenza), cioè al numero di modi di mettere in fila questi 3 nodi. Ebbene, non è difficile dimostrare che il numero di permutazioni di un insieme di N elementi è dato dal fattoriale di N, che si indica con il simbolo N! e che corrisponde al prodotto di tutti i numeri interi compresi tra 1 e N. Nel nostro esempio di grafo con 4 città, i nodi in questione sono N = 3, e quindi le possibili soluzioni sono pari a N! = 3! = 3 × 2 × 1 = 6.

Per risolvere il problema, dovremmo misurare la lunghezza di ciascuno dei possibili 6 percorsi, e alla fine potremmo stabilire qual è il più breve in assoluto.
Finché i nodi del grafo (cioè le città) sono soltanto 4, o comunque molto poche, il numero di soluzioni possibili è abbastanza limitato, ed è quindi possibile esaminarle tutte, magari conl’ausilio di un programma informatico. Purtroppo, però, il fattoriale è una funzione che cresce molto rapidamente (vedi tabella): già con 8 città le alternative sarebbero 40.320, con 10 città salirebbero a 3.628.800, e con 20 città si arriverebbe a più di 2 miliardi di miliardi!
Anche impiegando computer potentissimi, il problema diventa ben presto intrattabile, e sono necessarie tecniche di approssimazione (o euristiche) per la ricerca delle soluzioni.

Qualche lettore affezionato ricorderà che nel primo articolo della rubrica Moebius, uscito nel numero di luglio-agosto 2013, avevo parlato di due celebri rompicapi matematici: le torri di Hanoi e il gioco icosiano. L’inventore di quest’ultimo fu Sir William Rowan Hamilton, che nel 1857 descrisse il gioco durante una riunione della British Association for the Advancement of Science.
Il rompicapo consisteva nel trovare un cammino che toccasse tutti i vertici di un dodecaedro (uno dei solidi platonici, da me trattati nel numero di settembre 2014), percorrendo ciascuno degli spigoli esattamente una volta. Nelle due figure sono mostrati la confezione originale del gioco e una soluzione.

Il gioco icosiano è, evidentemente, una particolare variante del problema del commesso viaggiatore, in cui il grafo di partenza non è completo, cioè è possibile utilizzare solo alcuni archi (quelli che corrispondono a spigoli del dodecaedro) e non altri.
Il problema generale del commesso viaggiatore, invece, fu analizzato negli anni Trenta del XX secolo dopo dal matematico austriaco Karl Menger, famoso soprattutto per aver descritto un particolare frattale tridimensionale noto come “spugna di Menger”.
L’ormai popolare riferimento alla figura del “commesso viaggiatore” nel nome classico del problema fu un’intuizione del matematico americano Hassler Whitney.

Per cercare di risolvere il problema del commesso viaggiatore (o “travelling salesman problem”, TSP, all’inglese), fino agli anni ‘50 del secolo scorso si utilizzò sempre il cosiddetto metodo di “forza bruta”, cioè l’enumerazione esaustiva di tutti i percorsi possibili e la comparazione delle rispettive lunghezze: ciò rendeva del tutto impensabile la risoluzione del problema con un numero di nodi appena superiore a una decina.
Nel 1954 i matematici americani George Dantzig, Ray Fulkerson e Selmer Johnson proposero un metodo alternativo, basato sulla tecnica dei piani di taglio, per risolvere il problema in modo più efficiente: così facendo riuscirono a trovare un percorso ottimale attraverso le 48 capitali degli Stati Uniti (Alaska e Hawaii non erano ancora diventati Stati a tutti gli effetti) più Washington, capitale federale.
La soluzione migliore, come scoprirono i tre matematici, era quella illustrata in figura.

Nel 1962, la Procter & Gamble lanciò un concorso tra i suoi clienti: per aggiudicarsi il premio in palio, si doveva risolvere il problema del commesso viaggiatore su una rete con 33 città.
Ulteriori progressi vennero ottenuti nei decenni successivi, sfruttando la crescente potenza dei computer ma soprattutto le tecniche via via più raffinate che i ricercatori riuscirono a sviluppare. Si cominciò così a risolvere il problema anche con molte migliaia di nodi.

Nel numero 187 di Coelum, la rubrica Moebius ha rivestito il classico problema del commesso viaggiatore di un’ambientazione al tempo stesso interplanetaria e natalizia: la sfida consisteva nell’aiutare Babbo Natale a trovare un percorso ottimale per portare regali a tutti i bambini buoni del Sistema Solare.
Più precisamente, il contesto fantascientifico da me ipotizzato prevedeva cinque mondi abitati: la Terra, la Luna, Marte, Cerere e Ganimede. I mondi sono tra di loro connessi da speciali collegamenti, e ogni rotta che congiunge due mondi può essere percorsa dall’astroslitta di Babbo Natale in un certo numero di ore, il medesimo nelle due direzioni. In questo particolare problema del commesso viaggiatore (o meglio, del Babbo Natale interplanetario), al posto delle città abbiamo quindi i cinque pianeti, e ogni arco del grafo è etichettato non da una lunghezza in chilometri, ma da un tempo di percorrenza in ore.
Cito dall’articolo:

Precisamente, Marte dista due ore e mezza dalla Terra, ma la stessa distanza lo separa anche dalla Luna e da Ganimede. Tra la Terra e la Luna c’è un’ora di volo, mentre il nostro satellite dista tre ore e mezza da Ganimede. Terra e Cerere sono lontani quattro ore, e due ore separano il pianeta nano da Ganimede e anche da Marte.

Il compito del lettore consisteva pertanto nel trovare il tragitto più veloce, non il più breve. Ma non solo. Il percorso ottimale doveva soddisfare anche un ulteriore, fondamentale vincolo: ogni bambino del Sistema Solare doveva ricevere un regalo. Si ipotizza infatti che ciascuno dei pianeti abitati ospiti un certo numero di bambini e un magazzino con una data quantità di giocattoli. All’arrivo su ogni pianeta, Babbo Natale può caricare sul suo fantastico veicolo volante i giocattoli presenti nel magazzino. Nella tabella seguente sono indicati il numero di bimbi e di giochi presenti su ogni mondo.

Pianeta	Numero bambini	Numero giocattoli
Terra	1 miliardo	1,1 miliardi
Luna	100 milioni	100 milioni
Marte	400 milioni	200 milioni
Ganimede	200 milioni	400 milioni
Cerere	100 milioni	0

In conclusione, il percorso ottimale deve permettere a Babbo Natale di partire dalla Terra, visitare ognuno degli altri quattro pianeti, ciascuno esattamente una volta, e ritornare al punto di partenza, utilizzando i collegamenti indicati e riuscendo a portare un regalo a ogni bambino. Semplice, no?

Qualche lettore appassionato di fantascienza si sarà forse ricordato che il titolo dell’articolo di dicembre, “Natale su Ganimede”, è lo stesso di un racconto dell’amatissimo (sicuramente da me, ma non solo) scrittore e divulgatore scientifico Isaac Asimov.
Il racconto fu pubblicato nel 1942 sulla rivista Startling Stories. In una sua autobiografia, Asimov rivelò che si era sforzato di scrivere una storia soprattutto divertente, cosa che, a suo parere, è una delle più difficili in assoluto per uno scrittore. Curiosamente, anche il racconto di Asimov tira in ballo Babbo Natale. La storia, com’è facile immaginare, è ambientata sul satellite gioviano Ganimede, per l’occasione popolato da strane creature simili a struzzi, chiamati ossies e utilizzate dalla Ganymedan Products Corporation come forza lavoro. Un giorno qualcuno racconta agli ossies di Babbo Natale, e loro decidono di scioperare finché il barbuto portatore di doni non si recherà in visita su Ganimede. L’azienda entra in una grave crisi, e ciò costringe gli abitanti umani di Ganimede a inscenare una finta visita di Babbo Natale. Tutto sembra risolto, quando gli ossies richiedono che Babbo Natale vada a trovarli ogni anno. Peccato che l’anno ganimediano, cioè il periodo di rivoluzione di Ganimede attorno a Giove, dura soltanto sette giorni terrestri…

La risoluzione del problema richiedeva un po’ di attenzione. Partendo dalla Terra, Babbo Natale può caricare sulla sua astroslitta 1,1 miliardi di regali, ma dovrà consegnarne 1 miliardo prima di lasciare il pianeta. Decollerà quindi con un carico di “soli” 100 milioni di giocattoli, cosa che gli impedirà di atterrare su Marte, visto che sul pianeta rosso ci sono 400 milioni di bambini ma soltanto 200 milioni di giocattoli. La sua seconda tappa potrà quindi essere Cerere oppure la Luna.
Nel primo caso, dopo il pianeta nano sarà sicuramente la volta di Ganimede, perché Marte risulta ancora off limits per motivi di eccedenza di bambini rispetto ai doni disponibili. Dopo Ganimede Babbo Natale deve raggiungere la Luna e Marte, in uno dei due ordini possibili, per poi fare ritorno sulla Terra.
Anche nel secondo caso, la successiva tappa dopo la Luna deve essere per forza di cose Ganimede, seguito da Marte e Cerere, in entrambe le sequenze possibili, e infine la Terra.
I quattro percorsi ammessi sono di conseguenza:

Terra Cerere Ganimede Luna Marte Terra

Terra Cerere Ganimede Marte Luna Terra

Terra Luna Ganimede Marte Cerere Terra

Terra Luna Ganimede Cerere Marte Terra

I tempi di percorrenza dei quattro tragitti sono, rispettivamente: 14,5 ore, 12 ore, 13 ore, 11 ore.
Il percorso ottimale, quindi, risulta il seguente:

Terra Luna Ganimede Cerere Marte Terra