venerdì 28 gennaio 2011

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!

martedì 25 gennaio 2011

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.

domenica 23 gennaio 2011

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.

martedì 18 gennaio 2011

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.

domenica 16 gennaio 2011

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.

mercoledì 12 gennaio 2011

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".

domenica 9 gennaio 2011

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!

venerdì 7 gennaio 2011

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 N2 - 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.

mercoledì 5 gennaio 2011

Il problema del campionato - Parte 1

Ricordo, come fosse ieri, una mattina negli ultimi mesi del 1982: avevo 11 anni ed ero a casa da scuola con l'influenza. Suonò il campanello: era il postino, con un pacco da consegnare. Scese la mamma a prenderlo, e poi me lo portò. Era il mitico "Almanacco illustrato del calcio", che mi ero conquistato grazie ai "buoni" raccolti con le ancor più mitiche figurine Panini.
Se il concetto di felicità può essere associato ad alcuni particolari giorni della vita, quel giorno fu uno di questi. Ricordo la gioia con cui sfogliai avidamente le pagine, navigando tra campionati d'anteguerra, statistiche, schede dei calciatori, e l'esaltante copertina in cui campeggiava il compianto Enzo Bearzot che alzava al cielo la coppa del mondo appena vinta.
Ora del calcio non mi interessa più nulla, ma allora lo seguivo con entusiasmo (in particolare il Verona, che tre anni dopo avrebbe vinto lo scudetto), e certo uno degli aspetti che mi divertivano maggiormente era il lato statistico, combinatorio dei campionati: insomma mi incuriosiva scoprire come, all'interno di un campionato (ad esempio una stagione di campionato italiano di serie A), si succedessero le giornate, ciascuna costituita da un insieme di partite che, ovviamente, non potevano ripetersi nello stesso torneo, salve le ripetizioni nel girone di ritorno.
Mi sovviene ora un altro ricordo: con un amichetto vicino di casa, compagno di innumerevoli partite a pallone nei cortili di casa, ci eravamo ad un certo punto cimentati nello stilare il calendario di un nostro immaginario campionato. Le partite programmate, poi, le disputavamo noi due e altri amici, non virtualmente ma davvero, nel cortile, con le felpe ammonticchiate a fare da pali per le porte.
Precursori del fantacalcio? Può darsi, ma certamente potete immaginare le difficoltà che due ragazzini di 11 anni potevano trovare nel risolvere a mano, senza computer (era il 1982) e senza sofisticate cognizioni algoritmiche (avevamo 11 anni) un problema complicato come quello della creazione del calendario di un campionato con un numero di squadre non banale.

Naturalmente avevamo inconsapevolmente adottato un approccio che potrei definire di "backtracking": provavamo cioè a stilare, una dopo l'altra, le giornate di campionato, finché incontravamo un ostacolo insormontabile, vale a dire finché ci accorgevamo che le ultime due squadre non ancora accoppiate in una certa giornata si erano già incontrate in una giornata precedente. Allora dovevamo tornare indietro ("backtrack", appunto), ovviamente non si sa bene quanto indietro, e cambiare qualcosa nella speranza di non incontrare più ostacoli del genere.
Non ricordo, francamente, se fossimo a un certo punto riusciti ad arrivare in fondo nella titanica impresa di stilare un calendario completo: mi pare di no (con un numero di squadre realistico, diciamo 16, e con un approccio naif come quello descritto sarebbe stato, credo, quasi impossibile).
Ma mi pare di ricordare di aver escogitato, stremato dai tentativi infruttuosi, un volgare barbatrucco per aggirare l'ostacolo. Avevo preso un calendario reale, ad esempio quello del campionato di serie A in corso, che immaginavo generato da chissà quali fumanti elucubrazioni di fantascientifici cervelloni elettronici; tanto per confondere un po' le acque, l'avevo sottoposto ad una permutazione casuale delle giornate, e infine avevo fatto corrispondere ciascuna squadra del campionato reale con una squadra del nostro campionato immaginario. In questo modo avevo ottenuto un calendario, per le nostre partite in cortile, apparentemente nuovo, ma che in realtà celava la stessa struttura combinatoria di quello reale preso come modello. Furbizie da undicenni.

Il problema del calendario del campionato mi rimase sempre caro, a maggior ragione negli anni successivi quando cominciai a conoscere il mondo dell'informatica e degli algoritmi.
Nei primi anni Novanta scrissi vari programmi in Pascal che affrontavano il problema per via euristica o di backtracking (insomma, per tentativi).
Nel 1996 trovai un algoritmo esatto, cioè che trovava sempre una soluzione ammissibile non per tentativi, ma seguendo una propria logica diretta e andando dritto al risultato. Conservo il codice Pascal di quell'idea, e tornerò sull'argomento.

Per la verità, pare che esista un algoritmo molto vecchio in grado di risolvere il problema (io appresi di ciò piuttosto tardi), e che venne escogitato da uno scacchista austriaco, Johann Berger, vissuto tra il 1845 e il 1933.
Nelle prossime parti di questo "multi-post" toccherò anche questo argomento.
Vi lascio con un'anticipazione della seconda parte: il problema può essere modellato matematicamente anche ricorrendo alla teoria dei grafi, e il rompicapo che ne deriva assomiglia molto al gioco del sudoku.

lunedì 3 gennaio 2011

2011 è primo!

Già, proprio così!
Ecco tutti gli anni primi del XX e del XXI secolo:
1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999.
2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099.
Forse l'umanità si divide in due parti: quelli che a questa notizia restano del tutto indifferenti (pensando nel contempo che chi gliel'ha comunicata deve essere malato) e quelli che invece si entusiasmano (oppure vanno a verificare che sia davvero così).
Voi da che parte state?

Pensieri sopra GEB


Riporto qui alcune mie considerazioni su una lettura che mi ha impegnato durante l'anno da poco finito. Avevo inserito queste mie note in Anobii (a proposito, sono presente anche là come Mr. Palomar, o più precisamente come Palomar71...), e le riporto qui, testualmente.
Di sicuro tornerò anche su questo libro, ricchissimo di spunti di ogni genere, in gran parte di tipo logico e matematico.

Che si può dire, dopo molti mesi trascorsi nella lettura di questa monumentale e profondissima opera?
Di sicuro questo è e resterà uno dei libri della mia vita, un libro che, pur nei suoi limiti (che ci sono), credo meriti la celebrità che ha guadagnato fin dalla sua pubblicazione.

Di cosa parla GEB? Una domanda che molti mi hanno rivolto durante questi mesi, e alla quale, sembra strano, non è per niente immediato rispondere.
Uno degli obiettivi dichiarati di Hofstadter era quello di investigare il problema della mente e cercare una spiegazione dei meccanismi per cui fenomeni come la coscienza e il libero arbitrio emergono da un substrato come l'intreccio neuronico del cervello; altro obiettivo era quello di studiare le possibilità dell'intelligenza artificiale.
Obiettivi molto ambiziosi, come si vede.

La critica più ricorrente a GEB è che il libro si dilunga per centinaia di pagine su argomenti apparentemente periferici rispetto al tema centrale, come il teorema di Gödel, l'autoreferenza, le opere di Escher, la musica di Bach, la genetica, i sistemi formali, la logica proposizionale, la programmazione, lo zen, per non parlare dei dialoghi alla Lewis Carroll continuamente inframezzati ai capitoli del libro.
Questa critica ha senza dubbio un suo fondamento, anche perché le tesi centrali del libro vengono affrontate ed esposte solo alla fine, quasi frettolosamente, e forse, va ammesso, un po' superficialmente.
Ma tutto il resto è periferico fino a un certo punto: l'enorme quantità di argomenti che vengono affrontati nelle ottocento pagine è propedeutica per arrivare al nucleo delle idee di Hofstadter, e ogni questione che viene discussa prima o poi ritorna, magari intrecciata ad altro, ma averla capita a suo tempo serve per poter procedere.
Forse ancora più importante è il fatto che il libro ha una struttura e un taglio che vanno ben al di là del classico saggio di divulgazione: Hofstadter utilizza un'impostazione che molto si avvicina alla narrativa, con tutte le sue tecniche.
Per questo motivo, succede continuamente che un argomento venga avviato, e poi interrotto prima di arrivare a percepire un senso di completamento o di chiarimento, per passare ad un altro tema apparentemente slegato, e così via.
Questa tecnica deve avere frustrato e innervosito molti lettori (anche il sottoscritto).
E' molto probabile che il libro sarebbe stato migliore se avesse avuto una scaletta più chiara e lineare e meno caotica e vorticosa; così come sarebbe stato desiderabile un numero minore di pagine "preparatorie" e una più approfondita esposizione della tesi finale.
Ma questo, evidentemente, è lo stile di Hofstadter: prendere o lasciare. E non si può negare che questa impostazione abbia il suo fascino e la sua efficacia, come la tecnica del rimando nei romanzi.

Non c'è dubbio che al lettore sia richiesto un impegno non comune per portare a termine la lettura di questo volume ponderoso. La sua complessità è notevole, i livelli di lettura sono molteplici, intricata è la struttura, e di continuo Hofstadter gioca con le parole, con gli intrecci, con sottili riferimenti.
Certo, a volte emerge un autocompiacimento che non rende simpatico l'autore. Ma gli va dato atto di avere progettato un edificio davvero notevole: forse più per la struttura che per il reale contenuto.

Ho particolarmente apprezzato la spiegazione del celebre teorema di incompletezza, che peraltro avevo studiato su altri testi più tecnici: Hofstadter ne espone una dimostrazione molto brillante e giocosa.
Più in generale, ho trovato il libro molto interessante proprio per questa capacità di raccontare temi molto tecnici attraverso trovate pseudo-narrative e brillanti: per uno come me che si interessa alle tecniche della divulgazione scientifica e alle sue relazioni con la narrativa, certamente GEB rappresenta un esempio molto importante e originale.

domenica 2 gennaio 2011

Giochi sotto l'albero

Le feste natalizie si avviano al termine: ancora pochi giorni e l'Epifania se le porterà via...
E si sa, questo è un periodo adatto per cimentarsi in giochi divertenti e appassionanti che coinvolgano tutta la famiglia, tra l'albero, il presepe, una fetta di pandoro e lo spumante. Se poi i giochi sono intelligenti e magari di tipo matematico, ancora meglio!

Segnalo allora il sito FlashGames.it, ricchissimo di giochi online di ogni tipo, e in particolare la sezione dei giochi di logica, in cui si trovano molti rompicapi e giochi davvero ingegnosi e ben costruiti.

Tornerò senz'altro su alcuni di questi giochi, adatti non solo al periodo di fine anno ma a tutto l'anno!

sabato 1 gennaio 2011

Iniziano oggi gli "anni dieci"?

Lo so, lo so, è una questione pedante, oziosa, del tutto inutile; ma anche giocherellare con la matematica può sembrare ozioso, eppure ci piace...
Nel lontano gennaio 2000, nella mia precedente vita da astrofilo, avevo scritto sull'argomento un articolo, per il bollettino del Circolo Astrofili Veronesi del quale facevo parte.
Un altro buon contributo sull'argomento si trova in questo articolo di Paolo Bonavoglia.

Ebbene, l'annosa (è proprio il caso di usare questo termine) questione è la seguente: quando è iniziato il terzo millennio? Il primo gennaio del 2000 o un anno dopo? E di conseguenza, quando sono iniziati gli "anni dieci" del XXI secolo? Il primo gennaio del 2010 oppure stamattina?
Prima di tutto diciamo che si tratta, sempre e comunque, di pure convenzioni, e quindi non esiste una risposta "esatta" in senso assoluto.
Poco sopra ho scritto "di conseguenza", dando per scontato che la scelta dell'inizio del secolo (o del millennio) determini a sua volta, senza possibilità di sgarrare, la collocazione dei decenni che chiamiamo "anni dieci", "anni venti", e così via; ma anche questa è una convenzione, e nulla vieta di svincolare le due cose.
Ma andiamo per ordine.

Molto spesso si parla di "anno zero", intendendo l'anno iniziale dell'era cristiana, cioè l'anno nel quale nacque Gesù Cristo. Ebbene, l'anno zero non è mai esistito (almeno secondo la convenzione ufficiale in uso).
Nel 532, il calendario in uso nell'Europa cristiana si basava ancora sulla data della fondazione di Roma. In quell'anno Dionigi il Piccolo, un monaco erudito che era diventato, per così dire, il consulente matematico del Papa, si cimentò nel calcolo della data della nascita di Cristo, e stabilì che il Salvatore era venuto al mondo nell'anno 753 ab urbe condita.
In quell'epoca, però, non era stato ancora "inventato" lo zero, visto che gli Arabi e le loro innovazioni matematiche erano ancora di là da venire, per cui il buon Dionigi non aveva altra scelta che collocare, in prossimità della data individuata per la nascita di Cristo, l'anno 1 dopo Cristo: l'anno precedente si sarebbe chiamato per forza di cose anno 1 avanti Cristo.
Insomma, niente anno zero, perché lo zero non lo conosceva nessuno.
E quindi, secondo una lettura rigorosa (e rigida), dato che il primo secolo ebbe inizio con l'anno 1, lo stesso deve essere terminato, dopo i suoi bravi cent'anni, alla fine dell'anno 100. Tutto il resto viene di conseguenza: il ventesimo secolo è terminato il 31 dicembre 2000 per lasciare spazio al nostro secolo, iniziato il primo gennaio 2001 insieme al terzo millennio.

Fin qui la rigida deduzione a partire dalla scelta convenzionale di Dionigi e degli storici.
Ma il peccato originale, come dicevo, sta nell'avere fatto a meno dello zero.
Questa "colpa" può essere certo perdonata a Dionigi e ai suoi contemporanei, così come non si può rimproverare agli antichi, ad esempio, di non avere scritto dell'America; ma non per questo possiamo permetterci anche noi di continuare a ignorare l'invenzione araba dello zero, oggi fondamentale in tutti i sistemi di numerazione.
Non è un caso, osserva giustamente Bonavoglia, se il famigerato "millennium bug" si è verificato allo scoccare della mezzanotte del primo gennaio 2000, e non certo un anno dopo.
D'altra parte, come sottolineavo nel mio vecchio articolo, anche dal punto di vista emotivo è stato ben più significativo il passaggio dall'anno con i 3 nove a quello con i 3 zeri, piuttosto che l'aggiunta di una misera unità al Duemila.
Inoltre, sarebbe contraddittorio dire che l'anno 1900 non fa parte del Novecento, o che il 2010 non fa parte degli "anni dieci"!
D'altra parte, per noi uomini del terzo millennio, abituati al sistema decimale di tipo posizionale, viene naturale considerare lo zero come il primo numero, e quindi considerare il 2000 come il primo anno del nuovo secolo: e secondo questa impostazione, gli "anni dieci" del XXI secolo non sono iniziati stamattina, ma un anno fa.

Eppure se consultiamo su una buona enciclopedia la voce "Ventesimo secolo", troveremo, molto probabilmente, che viene ancora seguita la convenzione degli storici iniziata con Dionigi. E allora, come la mettiamo?
L'ho detto all'inizio, è solo questione di convenzioni; ma spesso mettersi d'accordo sulle convenzioni da seguire risulta fondamentale.

C'è chi ha suggerito soluzioni salomoniche, per salvare capra e cavoli: ad esempio lasciare pure vacante l'anno zero, ma far terminare il primo secolo con l'anno 99, in modo da mettere a posto tutto già a partire dal secondo secolo; oppure, addirittura postulare bizantine distinzioni tra il Novecento (iniziato nel 1900) e il XX secolo (iniziato nel 1901), e così via.
Probabilmente la soluzione più semplice è quella che già da molto tempo costituisce la convenzione ufficiale adottata dagli astronomi: l'anno 1 avanti Cristo di Dionigi viene ribattezzato anno zero, e quindi, evviva! reintroducendo l'anno zero tutto risulta più semplice, e la convenzione "naturale", in accordo col sistema decimale viene ristabilita.
Ad essere pignoli, però, in questo modo la polvere non viene eliminata ma nascosta sotto il tappeto, cioè negli anni prima di Cristo, che si trovano ad essere sfasati rispetto all'ormai consolidato calendario degli storici.
Insomma, dovremmo riscrivere i libri di storia. La data dell'inizio dell'impero romano, ad esempio, andrebbe corretta: non sarebbe più il 27 a.C. ma il 26 a.C.
Chissà, potrebbe essere una buona occasione di business per gli editori...

Anno nuovo...

... blog nuovo. Un blog di matematica? Sì, ma di matematica divertente, ricreativa, giocosa. E un po' anche di informatica, ma sempre con lo scopo di scoprire lati interessanti e divertenti. E chi diavolo è questo Mr. Palomar? Non c'è una sola risposta. Chi conosce Calvino potrebbe avere qualche sospetto: "Palomar" è uno dei suoi ultimi libri, una raccolta di racconti imperniati sul personaggio del titolo, un uomo curioso, analitico, osservatore della natura e di se stesso. "Mr. Palomar", tra l'altro, è il titolo delle traduzioni inglesi del libro. Ma che c'entra con la matematica? Bè, la struttura stessa del libro cela alcune pensate matematiche, con i 27 capitoli disposti ordinatamente in 3 parti composte ciascuna di 3 gruppi di 3. Ma soprattutto l'indole osservatrice del signor Palomar è molto simile all'atteggiamento di chi si occupa di matematica o informatica. Già, perché secondo me l'osservazione e la curiosità non sono esclusive di chi si occupa di scienze naturali, e deve quindi osservare galileianamente la natura; anche nella matematica e nell'informatica servono questi ingredienti, assieme alla creatività, perché forse Platone non aveva tutti i torti, e creare strutture è quasi sempre trovare e osservare queste strutture, come se già esistessero da qualche parte... Al nostro signor Palomar, quindi, certamente piace la matematica, soprattutto quella combinatoria, e in particolare quella giocosa e pregna di interconnessioni e contaminazioni. Insomma, la matematica che troverà spazio in questo blog. In particolare, la matematica che piace a me è quella che permette di esplorare legami inaspettati con altre discipline, non solo con le altri scienze ma anche con le altre arti, con la musica, con la letteratura. E non è un caso che uno dei racconti di "Palomar" è quel "Luna di pomeriggio" che ha dato il nome ad un'associazione culturale fondata da me e altri amici per coniugare scienza e arte... Calvino stesso scriveva: ”Rileggendo il tutto, m’accorgo che la storia di ‘Palomar’ si può riassumere in due frasi: ‘Un uomo si mette in marcia per raggiungere, passo a passo, la saggezza. Non è ancora arrivato.‘“ Un blog è poca cosa per raggiungere la saggezza. Ma chissà, forse vale almeno la pena di mettersi in marcia.

La top ten dei miei video su YouTube (1° posto)

Rullo di tamburi! Eccoci finalmente in vetta! E, devo dire, la vetta della classifica dei miei video su YouTube appare per il momento davver...