Innanzitutto un rapido ripasso su cosa significa scrivere un numero in base b. Se abbiamo il numero cdefg_b, noi dobbiamo leggerlo come c·b⁴ + d·b³ + e·b² + f·b + g; insomma se procediamo da destra a sinistra iniziando a contare da zero dobbiamo moltiplicare la i-esima cifra per la i-esima potenza della base. Detto così sembra inutilmente complicato, lo so: ma ci servirà in seguito. La seconda cosa che serve è la tavola pitagorica: abbiamo due tabelle di dimensione b×b, una per la somma e una per la moltiplicazione.

I primissimi computer, quelli ancora elettromeccanici, lavoravano in base 10 per abitudine e perché comunque era necessario interfacciarsi con i “calcolatori”, nel senso di “persone che fanno i calcoli”. Quando si è passati ai primi calcolatori elettronici le cose sono mutate: per un computer infatti la base più naturale era la base 2, perché la si può mettere in campo con un circuito on/off che ha appunto due valori. Ci penserà poi il computer stesso a convertire tra base 2 e base 10: è un compito stupido, ma proprio per questo il computer è adattissimo a farlo. Le tavole pitagoriche per la base 2 sono banali, e le vediamo qui sotto.

Quello che non è probabilmente noto è che all’inizio della storia dei computer erano state proposte anche altre basi, proprio come erano state proposte altre dimensioni per il byte: oggi lavoriamo in esadecimale (un byte è un ottetto, formato da due gruppi di quattro bit) ma quando ero un giovane universitario ho usato un PDP 11/34 che lavorava in ottale, con l’unità di base chiamata nibble che era un nonetto formato da tre gruppi di tre bit.

Non credo che ci fosse una correlazione, ma all’inizio dello sviluppo dei computer, oltre che la base 10 e la poi vincente base 2, era stata proposta e usata anche la base 3. La scelta era dettata da considerazioni fisiche, perché si può immaginare che un circuito di memorizzazione possa avere una tensione positiva, negativa oppure nulla. C’era però una particolarità che se non conoscete non potreste mai indovinare: quei computer non usavano una base 3 standard, ma una sua variante, la base 3 bilanciata che usa come cifre 0, 1 e -1 (che scriverò M per usare un solo carattere). A ben pensarci, è anche logico: se abbiamo tensioni +,−,0 perché dobbiamo rimapparle in 0, 1, 2?

L’aritmetica con la base 3 bilanciata presenta alcune peculiarità a cui bisogna abituarsi. Il numero successivo a 1 è il numero a due cifre 1M_3b; se prendete la definizione data sopra per computare un numero in base b, potete subito verificare che in effetti 1M_3b = 3+(-1) = 2. Ecco la lista dei numeri da 0 a 10 in base 3 bilanciata, con tra parentesi il numero corrispondente in base 10, seguita dalle tavole pitagoriche: per comodità non userò più l’indice 3b.

    0 (0),
    1 (1),
    1M (2),
    10 (3),
    11 (4),
    1MM (5),
    1M0 (6),
    1M1 (7),
    10M (8),
    100 (9),
    101 (10)

Da un punto di vista teorico la base 3, bilanciata o no che sia, sarebbe quella ottimale, perché è il miglior compromesso tra numero di simboli richiesto e lunghezza dei numeri tipicamente usati (anche se… ma magari ne parliamo un’altra volta). La versione bilanciata della base semplifica anche le tavole pitagoriche, soprattutto quella della moltiplicazione che è sempre la peggiore da implementare; come avete visto, anch’esse sono simmetriche. Purtroppo però la tecnologia negli anni 1950 non riusciva a creare circuiti flip-flop-flap abbastanza affidabili, e oggi ricominciare da capo e creare nuovi componenti di questo tipo è troppo costoso per essere pratico. Restano comunque gli usi teorici della base: scrivere un numero in base tre bilanciata permette di risolvere immediatamente il problema dei pesi di Bachet.

Abbiamo una bilancia a due piatti, e dobbiamo pesare un oggetto: qual è l’insieme di pesi ottimale per essere in grado di pesare oggetti da 1 a un dato numero n? La risposta è “si usa l’insieme di pesi di 1, 3, 9, 27… grammi”. Un oggetto pesante 17 grammi, infatti, può essere pesato mettendolo su un piatto insieme ai pesi da uno e nove grammi e ponendo sull’altro piatto il peso da 27 grammi. Ma 17 in base 3 bilanciata – il nome significherà pure qualcosa, no? – si scrive 1M0M: quindi il nostro oggetto sta insieme ai pesi corrispondenti alla cifra M nella rappresentazione, mentre quelli corrispondenti alla cifra 1 stanno dall’altra parte e quelli con lo 0 si lasciano da parte. Visto? teoria e pratica si complementano!

1. E luce fu

Aziono due interruttori, aspetto qualche minuto e ne spengo uno. Poi salgo. La lampadina accesa corrisponde all’interruttore rimasto azionato, la lampadina spenta ma tiepida all’interruttore che ho acceso e spento, la lampadina spenta e fredda all’interruttore che non ho toccato. Non per nulla ho specificato il tipo di lampadine!

2. Pacchetti postali

Ho preparato un pacchetto cubico in cui ogni lato è lungo 30 centimetri, e messo la barretta nella diagonale maggiore del cubo, che è è √3 volte il lato, cioè quasi 52 centimetri; resta un po’ di spazio anche per lo spessore della barretta che non è nullo come invece capita sempre nei problemi matematici…

3. Permutazioni

Una possibile soluzione è mostrata qui sotto.

4. Somme
4. Ricordate la prova del nove? Se la somma delle cifre di un numero è 2012, la sua radice numerica è 5. Sommando due numeri la cui radice numerica è 5, si ottiene un numero la cui radice numerica è 1. Ma si può fare di più, e ottenere un numero la somma delle cui cifre è 1! Detto in altro modo, il numero è 1000…000. Per ottenerlo basta sommare

5000...000999...9999+
4999...999000...0001

dove i 9 sono quelli necessari per arrivare alla somma delle cifre 2007, cioè ce ne sono 223.
Nel secondo caso, notate che sommando un numero a sé stesso non si può mai avere un riporto indotto. Basta allora considerare cosa succede con le cifre da 1 a 9: si vede subito che il miglior risultato si ha con il 5, che toglie 4 alla somma delle cifre della somma. La soluzione è perciò data da 2555….5555, dove i 5 sono 402. (Per amor di precisione il 2 può essere in una qualunque posizione, e si può sostituire un 1 e un 6 al 2 e a uno dei 5) La somma delle cifre sarà pertanto 406.

5. Codice
Il codice si completa con D1. Le lettere corrispondono infatti alle iniziali dei nomi dei mesi, e i numeri al numero di mesi con quella iniziale. Quindi A2 perché ci sono aprile e agosto, F1 perché c’è febbraio, e così via. Manca dicembre, che è l’unico mese che inizia con la d.

1. E luce fu

Nella soffitta della casa di mia nonna ci sono tre lampadine a incandescenza, ancora perfettamente funzionanti. Al piano terreno ci sono tre interruttori: mia nonna mi ha spiegato che a ciascun interruttore corrisponde una lampadina, ma non si ricorda a quale lampadina è associato ciascun interruttore. In questo momento sono a pian terreno, e so che tutte le lampadine sono spente. Come posso associare le lampadine agli interruttori facendo solo una visita alla soffitta?

2. Pacchetti postali

Ieri mattina sono andato alla posta per spedire una barretta di titanio lunga 50 centimetri. L’impiegato mi ha guardato e mi ha detto “Niente da fare: i regolamenti permettono di spedire solo pacchi di dimensione massima 30 centimetri”. Al mio ribattere “Ma è così stretta, praticamente un segmento!” la risposta è stata “I regolamenti sono regolamenti. Se vuole, la pieghi a metà”. Come se fosse possibile…
Stamattina sono tornato all’ufficio postale con la mia barretta impacchettata, ho sfoderato il mio miglior sorriso e ho consegnato un pacchetto con la mia barretta all’impiegato, commentando soavemente “Ha proprio ragione, i regolamenti sono regolamenti. Mi spedisca questo pacco, grazie.” Come ho fatto?

3. Permutazioni

Ci sono 24 modi per disporre i numeri da 1 a 4: 1234, 1243, 1342 e così via. Riempite i tre quadrati in modo che le 12 righe e le 12 colonne contengano tutte e 24 le disposizioni.

4. Somme
Ci sono due numeri M e N; per ciascuno di essi la somma delle cifre che li compongono è pari a 2012. Qual è al minimo la somma delle cifre che compongono il numero M+N? E se invece di due numeri se ne ha uno solo N, qual è la somma delle cifre di 2N?

5. Codice
Completate questo insieme con una lettera e un numero (e una spiegazione di perché avete scelto quella lettera e quel numero sufficientemente logica da essere accettata da me).

A2 – F1 – G2 – L1 – M2 – N1 – O1 – S1

Cosa si intenda per dio, probabilmente lo immaginate; la caratteristica di Eulero – o più precisamente di Eulero-Poincaré – è un invariante topologico che fu inizialmente definito dall’immenso matematico svizzero per studiare i poliedri. Ricordate dai tempi della scuola la formula “facce più vertici uguale spigoli più due”, o la sua versione mnemonica “fatti vedere sabato alle due”? Bene, il numero F+V-S (per un poliedro pari a 2, per quello che si legge sopra) è la caratteristica di Eulero di un poliedro, o più generalmente della superficie di una sfera.

La caratteristica di Eulero è sempre un numero intero, quindi i semidei sono esclusi: può anche essere negativa, come per esempio per la superficie di un pretzel che ha caratteristica −2: in questo caso al posto di déi si parla di demoni. La cosa interessante è che se il nostro universo è uno spazio tridimensionale infinito allora la sua caratteristica di Eulero è uno, mentre se fosse la superficie tridimensionale di una sfera quadridimensionale allora sarebbe zero. Come potete intuire, potremmo finalmente avere una prova cosmologica dell’esistenza (o della non-esistenza) di Dio, stroncando tutte le diatribe sulla correttezza delle prove ontologiche esplicitate dalle grandi menti, a partire da Anselmo d’Aosta fino a giungere a Kurt Gödel.

Chiaramente, anche se si dimostrasse l’esistenza di un dio non si potrebbe dire molto di più sulle Sue caratteristiche: da questo punto di vista sarebbe forse preferibile ottenere un risultato negativo che perlomeno taglierebbe la testa al toro. Sembra però che l’articolo abbia già suscitato numerosi interventi, nonostante sia stato pubblicato di domenica: il professor Riba della Kamchatka State Technical University ha già annunciato di voler studiare come la topologia dell’inferno dantesco possa adeguarsi a questa nuova teoria. Purtroppo noi italiani non riusciamo mai a sfruttare le nostre conoscenze… Dobbiamo davvero darci all’ittica!

Endre Szemerédi, da Wikipedia

Il premio Abel 2012 è stato assegnato al matematico ungherese Endre Szemerédi, “per i suoi contributi fondamentali nella matematica discreta e informatica teorica, e il loro profondo e duraturo impatto nella teoria dei numeri additiva e nella teoria ergodica.” Il primo problema è riuscire a capire come si pronuncia il cognome: Wikipedia dice “sèmereidi”, e io sono costretto a fidarmi. La teoria ergodica è quella che studia il comportamento nel lungo periodo di un sistema dinamico: per esempio, se si mette una palla sull’angolo un biliardo di formato A0 e la si lancia in direzione della bisettrice tra le due sponde, si può dimostrare che in teoria dovrebbe toccare tutti i punti del biliardo. La teoria dei numeri additiva invece, come dicono le parole stesse, studia (gli insiemi di) numeri interi e come si comportano rispetto all’”addizione”, cioè a cosa succede quando si crea un nuovo insieme avente come elementi la somma di elementi degli insiemi dati. La congettura di Goldbach, quella che afferma che ogni numero pari è esprimibile come somma di due numeri primi, è un esempio: abbiamo la somma di due copie dell’insieme dei primi. Come spesso capita nella teoria dei numeri, gli enunciati sono facili da spiegare, visto che coi numeri interi ci abbiamo tutti a che fare: lo sono un po’ meno da dimostrare…

Szemerédi dev’essere un tipo simpatico: lo si capisce non solo dalla faccia, ma anche dal testo di questa intervista. Il nostro spiega che per due anni ha fatto il dottorato con il matematico sbagliato, Gelfand invece che Gelfond: quando fece la domanda, confuse le due lettere cirilliche. Peccato che lui sia sempre stato interessato alla matematica discreta, e quindi non capisse un tubo del suo relatore ufficiale: e peccato che quando alla fine riuscì a contattare Gelfond con la O e a strappargli la promessa di farlo diventare suo studente di dottorato, quello dopo due mesi ebbe un infarto e morì. Parlavamo di sfiga dei matematici? Szemerédi spiega anche che ha cominciato a fare matematica tardi, a 22 anni, perché suo padre voleva facesse il medico; solo che sentiva una responsabilità troppo grande, e ci volle un po’ prima che decidesse di passare alla matematica, seguendo come maestri Paul Turan e Paul Erdős. Racconta anche che se ne è andato negli USA lasciando la Cortina di Ferro… perché di là avrebbe guadagnato di più: in compenso, anche se è un esperto “di internet” ed è membro del dipartimento di informatica della Rutgers University, non sa usare un computer. Lui legge le email, e sua moglie scrive le risposte :-)

Ci sono svariati risultati in matematica che portano il nome di Szemerédi, e sono tutti nel mare magnum tra la combinatoria, la teoria dei numeri additiva, e la teoria dei grafi. In effetti i contributi informatici evidenziati nell’assegnazione del premio Abel vertono appunto sulla struttura di Internet, con le connessioni tra i vari server che formano un enorme grafo. Il teorema di Szemerédi vero e proprio è però probabilmente il risultato più interessante: come dicevo sopra, dimostrarlo è al di là delle mie conoscenze, ma almeno posso spiegare di che tratta, con l’aiuto di Plus Magazine.

Cosa sia una progressione aritmetica, dovreste ricordarvelo dalle elementari: un insieme ordinato crescente o decrescente di numeri tale che la differenza tra due elementi consecutivi sia sempre la stessa. Chessò: 15, 24, 33, 42, 51 è una progressione aritmetica di cinque elementi e di ragione (la famigerata differenza…) 9. Prendiamo ora un insieme infinito di numeri interi, e chiediamoci qual è la progressione aritmetica più lunga che vi si possa trovare. Per esempio, con i numeri pari possiamo trovare progressioni infinite: invece con l’insieme {1, 10, 100, 1000, 10000, 100000, …} vi potete convincere in fretta che non ci sono progressioni molto lunghe. Ce ne sono di lunghezza 1 (un singolo numero qualsiasi…); ce ne sono di lunghezza 2 (due numeri qualsiasi…) ma probabilmente ci fermiamo lì. I matematici naturalmente si sono subito chiesti come fare a capire quando si possono trovare progressioni più o meno lunghe, e hanno tirato fuori il concetto di densità di un insieme sugli interi: in pratica il limite del rapporto tra il numero di interi nell’insieme minori o uguali a un valore dato N, quando N tende a infinito. Può darsi che questo limite non esista: in questo caso si usa il concetto un po’ più complicato di limite superiore (se non vi piace la definizione di Wikipedia, pensate al limite superiore in questo modo: se invece che tutta una successione ne prendete solo una parte in modo da averne una che ha un limite, il limite superiore è sempre maggiore o uguale ad esso, e non si può abbassarlo ulteriormente).

Ordunque: una congettura di Turan e Erdős (i due di cui sopra) affermava che se questa densità è strettamente maggiore di zero allora è possibile trovare all’interno di un insieme infinito di interi una progressione aritmetica di lunghezza grande a piacere (ma non necessariamente infinita, attenzione!) Nel 1953 Klaus Roth dimostrò che c’era almeno una progressione di lunghezza tre. Nel 1969 Szemerédi portò la lunghezza a quattro. Come avrete capito, il lavoro sembrava improbo, specialmente perché non si riusciva a trovare un modo generale per affrontare il problema: beh, nel 1975 Szemerédi di colpo dimostrò la congettura complessiva: per ogni k si può trovare una successione aritmetica di lunghezza k.

Come ormai avrete intuito, un conto è dimostrare un teorema: altra cosa ben più importante è inventarsi procedure per la dimostrazione che servano a dimostrare altre cose. La matematica va avanti in questo modo. Beh: a partire dalle tecniche di Szemerédi nel 2004 Ben Green e Terence Tao hanno dimostrato che lo stesso risultato (per ogni k si può trovare una successione aritmetica di lunghezza k) vale anche per la successione dei numeri primi, che di per sé ha densità nulla ma a quanto pare ha comunque abbastanza numeri. Naturalmente il risultato è puramente di esistenza: la più lunga successione nota al momento è di 26 numeri, trovata con il progetto distribuito PrimeGrid, ed è formata dai numeri 43.142.746.595.714.191 + 23.681.770 · 223.092.870 · n, con n che va da 0 a 25. Sono certo che vi starete chiedendo perché non è stato scritto il prodotto esplicito: banalmente perché 223.092.870 è il prodotto dei primi da 2 a 23, e probabilmente chi ha calcolato il tutto ha preferito fare così.

Come al solito, tutto questo non serve a nulla: ma un matematico non si preoccupa mica…

L’email era notoriamente ritenuta un servizio del tipo “quando arriva, arriva”. Oggidì noi controllatori compulsivi della posta ci aspettiamo che il messaggio arrivi al massimo un minuto dopo essere stato spedito, ma di per sé il protocollo SMTP è di tipo “store and forward”: il messaggio è salvato da qualche parte nel server di partenza, che poi cerca di spedirlo… sperando che il server di arrivo sia raggiungibile, accetti il messaggio e non lo metta nella cartella spam. Nella maggior parte dei casi non ci saranno problemi, ma l’eccezione può sempre capitare: pensate a come si sentono i maturandi che “sono” l’eccezione, e capirete come non sia esattamente il caso di spedire le prove d’esame la mattina stessa. Molto meglio inviarle alcuni giorni prima protette da password, e inviare la password in broadcast: se il servizio televisivo pubblico può permettersi nelle ore di punta di trasmettere la diretta delle estrazioni del lotto, perché non si può fare un minishow mattutino col ministro che con voce stentorea declama i caratteri della password di decodifica?

Qualcuno potrebbe obiettare che gli astuti studenti potrebbero sfruttare quei giorni per ottenere in qualche modo i testi e riuscire a craccare la password: vediamo ora come il problema non sussista, con una semplice stima spannometrica. Immaginiamo di usare una password di dieci lettere generate casualmente. Se le lettere usate fossero 25, il numero di possibilità sarebbe 25¹⁰. È facile stimare questo numero a mente: esso è 10^{10 log 25}, cioè poco meno di 10¹⁴, o se preferite centomila miliardi. Vi assicuro che i conti li ho fatti davvero a mente. Infatti so a memoria che logaritmo di 2 è 0,30103, cioè poco più di 0,3; pertanto il logaritmo di 5 = 10/2 è poco meno di 1−0,3=0,7 e il logaritmo di 25 = 5² è il doppio di quello di 5, dunque quasi 1,4.

Supponiamo ora di avere un progetto distribuito che testi un milione di password al secondo (e sono tante). Per testarle tutte ci vogliono 10⁸ secondi, cioè più di tre anni; la probabilità che si trovi quella giusta in tre giorni – e già questo significa che il testo è stato immediatamente rubato – è circa lo 0,3%. Troppo pericoloso? Aggiungiamo altre tre lettere alla password: il numero di combinazioni cresce di un fattore 10000 e più, e la probabilità decresce dello stesso ordine di grandezza. Inutile ricordare che i caratteri della password devono essere scelti casualmente, e non seguendo una qualche regola: “mariomonti” per esempio non funziona.

Potremmo anche introdurre tra i caratteri usati nelle password le cifre, o i segni di interpunzione, oppure ancora usare lettere maiuscole e minuscole: ma considerazioni pragmatiche consigliano di semplificare per quanto possibile il tipo di caratteri usato, al costo di usarne di più. Si può scegliere una soglia di probabilità per craccare la password sufficientemente bassa, e ricavare il numero di caratteri necessari per la password: a questo punto diventa più probabile che i testi vengano ottenuti in altro modo, per esempio direttamente dal ministero con metodi di ingegneria sociale…

Prima di cambiare tutte le vostre password, mi affretto a segnalare che questo caso è particolare, e non può essere automaticamente applicato in ogni situazione. Infatti abbiamo due caratteristiche peculiari: (a) un unico messaggio, e (b) la necessità di segretezza per un tempo relativamente limitato. In casi come questo non ha senso seguire le tecniche spiegate dall’Economist (e riportate anche dal Post) per generare la “password perfetta”, non dovendo infatti memorizzarla né usarla per molto tempo. In altre parole, non c’è una password per tutte le stagioni!