Bellezza

Quando lavoro a un problema non penso mai
alla bellezza, penso a risolvere il problema. Ma
quando ho finito, se la soluzione non è bella, so
che ho sbagliato qualcosa.

Richard Buckminster FULLER

Dal calendario dei Rudi Matematici.

Il piacere della matematica

A mio figlio E., 6 anni, piace l'aritmetica. La sua maestra In prima elementare ha appena terminato di spiegare le somme in colonna, ma a lui è andato parecchio avanti per conto suo. Gli piace fare semplici somme a mente, e ha appena scoperto da solo le tabelline. Gli piace giocare con i numeri.

Stasera a cena per farlo divertire un po' gli ho spiegato i numeri pari e i dispari, e la divisibilità per 3 e per 5. E, tanto per non farli mancare niente, gli ho spiegato il concetto di numero primo. Penso abbia capito tutto, più o meno, perché rispondeva alle semplici domande che gli ponevo per gioco.

Invece, probabilmente ci vorrà ancora un bel po' perché capisca il concetto di infinito. "Papà, ma i numeri non finiscono mai?", "no, perché se scrivi un numero lunghissimo puoi sempre allungarlo mettendo un'altra cifra davanti." "Ma poi finisce il foglio!" "Beh, prendi un foglio più grande", "ma finisce anche quello!", "e tu ne prendi uno più grande! pensa a un foglio lungo da qui a Marsala", "Seee, ma poi finisce anche quello".

Non l'ho convinto, glielo leggevo negli occhi. Evidentemente, i numeri naturali e le operazioni aritmetiche di base sono concetti abbastanza semplici e intuitivi per l'essere umano, mentre il concetto di non-finitezza è davvero innaturale, e richiede capacità di astrazione di livello superiore.

A me piace spiegare, a lui piace imparare, ci siamo divertiti da matti. Per dire che la matematica può essere divertente se introdotta come gioco fin da piccoli!

So long

Addio caro Martin, e grazie per le ore di passione e di divertimento che ci hai regalato.

(hat tip, gli studenti di oggi).

Il mio numero di Erdos

Ho appena scoperto di avere numero di Erdos pari a 4. Ho pubblicato con Sanjoy Baruah, che ha pubblicato con Greg Plaxton, che ha pubblicato con E. Szemeredi, che ha pubblicato con Paul Erdos.

Il mio prossimo obiettivo è pubblicare direttamente con Plaxton (che però non conosco), così magari scendo a 3! (meno di così mi sembra oggettivamente mooolto difficile).

(in figura, il Collaboration Graph di co-autori di Erdos).

Il resto

Ieri avevo postato la seguente domanda:

Qual'è il resto della seguente divisione intera?

2¹⁰⁰¹ mod 31

(dove l'operazione mod indica appunto il resto della divisione fra i due numeri interi. Ad esempio, 16 mod 7 = 2).

La risposta corretta è 2. Siete stati bravissimi naturalmente, e velocissimi! La mia domanda sul tempo di risposta aveva un fondamento "scientifico": stiamo preparando il test di ammissione a questo corso. Il test consisterà di una serie di domande a risposta multipla. Una sezione è dedicata a quiz di questo tipo, e vorrei capire quanto ci metterebbe in media uno con una laurea triennale in informatica a rispondere a questo quesito. Naturalmente i 10 lettori del mio blog non sono un campione significativo, lo so, era giusto per gigioneggiare. Tipicamente, prevediamo 2 minuti a risposta, per 60 domande mettiamo un limite di 2 ore circa (e senza PC con python a disposizione, non so se mi spiego ... :) ). Metteremo un test di esempio sul sito, magari poi ve lo passo e potrete divertirvi a sapere se sareste ammessi al nostro corso!

Tornando al problema, si tratta un tipico calcolo di aritmetica modulare, una branca molto bella della matematica. Nell'informatica si usa per tante cose, principalmente in crittografia. Di sotto elaboro un minimo le soluzioni di Zar e Riccardo.

Nell'aritmetica modulare, due numeri interi p e r si dicono congruenti modulo q, e si scrive

p = r (mod q)

se esiste un intero k tale che

q = k p + r.

L'aritmetica modulare ha delle proprietà simili a quelle dell'aritmetica normale. Qui ci interessano le seguenti:

per qualunque intero c, se p = r (mod q) allora c p = c r (mod q) (1)

per qualunque intero k, se p = r (mod q) allora p^k = r^k (mod q) (2)

Sono entrambe banalmente dimostrabili e ve ne potete convincere con qualche piccola prova.
Nel nostro caso specifico, è ovvio che

2⁵ = 1 (mod 31)

Usando la relazione (2), possiamo scrivere

2¹⁰⁰⁰ = (2⁵)²⁰⁰ = 1 (mod 31)

A questo punto, sfruttando (1), si conclude

2¹⁰⁰¹ = 2 (mod 31)

Va beh, scusate, l'ho fatta lunghissima, ci ho messo quasi 1220 mod 11 minuti a scrivere 'sto post!

Quiz veloce

Qual'è il resto della seguente divisione intera?

2¹⁰⁰¹ mod 31

(dove l'operazione mod indica appunto il resto della divisione fra i due numeri interi. Ad esempio, 16 mod 7 = 2).

Se volete, potete mettete la risposta nei commenti, insieme al tempo che ci avete messo a ricavarla (per un mia personalissima statistica! anzi per una sorta di scommessa con un mio collega). Domani sera la soluzione.

Indovinello

Stimolato da un'intervista a Paolo Gargini segnalatami da Francesco vorrei cominciare a parlare di qualcosina che ha a che fare con la mia ricerca. E comincio da un indovinello semplice semplice.

Mario è un esperto di barbecue e adora cucinare le bistecche sulla graticola per sua moglie e suo figlio. Il suo fornellino è piccolo, e ci sta su una sola bistecca. Per cuocere un lato di una bistecca ci mette circa 3 minuti. Quindi, per cuocere 3 bistecche ci mette 18 minuti (3 minuti per ogni lato di ogni bistecca). Per ridurre l'attesa decide di comprare un altro fornellino identico, cosicché egli possa cuocere due bistecche in parallelo.

1) Qual'è il tempo minimo necessario per cuocere tutte e 3 le bistecche sui due fornellini?

2) Supponiamo di avere N bistecche e K fornellini, con N > K (ad esempio 5 bistecche su 3 fornelli). Riuscite a ricavare una formula per calcolare il tempo minimo necessario?

Le soluzioni e un po' di discussione nei prossimi post.

Le storielle dei matematici

Eccone una molto divertente. Il mio calcolo era molto più a spanne di quello fatto da "Arthur Dent", e abbastanza vicino a quello degli autori del post.

Relativismo e logica

Il '900 è purtroppo finito, e nel nuovo secolo sembra esserci sempre meno spazio per il buon vecchio relativismo. Il '900 è stato la culla del relativismo, inteso come movimento culturale che ha avuto la sua influenza su molteplici discipline, dalla matematica, alla fisica teorica, alla logica, alla letteratura, all'arte figurativa.

Mi piace qui ricordare uno dei miei eroi personali del '900, il logico matematico Kurt Gödel, forse il più grande logico di tutti i tempi. E' il mio eroe per alcuni motivi. Innanzitutto era un matematico, e io ho una particolare predilezione per la matematica. Secondo, era un pò matto (soffriva di manie di persecuzione e altri disordini psicologici). Era anche ingenuamente matto. Secondo un aneddoto leggendario, al momento di prendere la cittadinanza americana, accompagnato dal buon Albert Einstein, si mise a disquisire con il giudice che esaminava la sua conoscenza della costituzione di un "baco logico" presente nella costituzione stessa che avrebbe permesso ai democratici Stati Uniti d'America di trasformarsi legalmente in una dittatura (*) (**).

Ma il principale motivo per apprezzarlo è il suo risultato scientifico più importante e conosciuto: il teorema di incompletezza che porta il suo nome. Non voglio annoiarvi con i particolari tecnici, quindi cercherò di spiegarvi l'idea che sta dietro prendendo a prestito materiale dall'ottimo "Gödel, Escher e Bach: un'eterna ghirlanda brillante", di Douglas Hofstadter.

Premessa: avete presente il paradosso del mentitore? Esso consiste nella seguente frase: "in questo momento sto mentendo". Tale frase non può essere considerata né vera, né falsa. Un'altra versione più semplice è la seguente:

Socrate: "Platone dice il falso"
Platone: "Socrate dice il vero"

Se assumiamo la prima frase come vera, la seconda risulta vera, e come conseguenza la prima risulta falsa. Frasi del genere sono quanto meno "fastidiose" nella matematica formale. Esse non possono essere dimostrate vere, né false. Bisognerebbe evitare che cose del genere si "infilino" in sistemi matematici formali. Fine della premessa.

All'inizio del '900 il matematico positivista David Hilbert cercava di assiomatizzare tutta la matematica. Egli cercava di arrivare a un sistema completo e coerente, con delle basi solide, a partire dal quale fosse possibile costruire il resto della matematica.

La fisica aveva già avuto i primi sentori dell'avvicinarsi della rivoluzione: la teoria della relatività era alle porte. Ma la matematica è scienza astratta e interamente costruita nella mente dell'uomo. Era quindi più che plausibile, anzi era altamente desiderabile che la matematica poggiasse su solidissime basi logiche. La matematica deve essere scienza certa! Da certe premesse, si deve arrivare sempre a conclusioni certe. I matematici cercavano quindi di selezionare un insieme minimo di assiomi iniziali a partire dai quali tutto discendesse automaticamente.

Per chi si ricorda della matematica delle scuole medie: i primi cinque assiomi di Euclide sono le basi su cui è costruita tutta la geometria euclidea, comprese le cose più astruse e difficili, le costruzioni geometriche più complicate. Se si cambia uno degli assiomi, si ottengono altri tipi di risultati (ad esempio le geometrie non-euclidee).

I matematici cominciarono a individuare nell'aritmetica dei numeri naturali la miglior candidata per fare da base al resto della matematica. E in fondo cosa c'è di più elementare dell'aritmetica? Contiamo con le nostre dita fin da piccoli. I numeri interi sono la cosa più semplice ed elementare che possiamo immaginare. Partendo da 0 e 1, e aggiungendo le operazioni di somma e moltiplicazione, possiamo costruire tutti gli interi. Con pochi altri assiomi costruiamo tutta l'aritmetica (il sistema formale corrispondente viene anche detto aritmetica di Peano).

E che fa il nostro eroe? con il suo teorema di incompletezza, ci dice che un sistema formale "semplice" come l'aritmetica può contenere affermazioni che non sono né vere né false, più o meno come il paradosso del mentitore. Ovvero, ci sono affermazioni (teoremi) che non possono essere derivate automaticamente dagli assiomi. Inoltre, se le assumiamo vere (cioè se le aggiungiamo al sistema di assiomi), giungiamo ad una contraddizione. Idem se le assumiamo false.

Questo risultato, in fondo semplice, distrusse il sogno di fondare tutta la matematica a partire da un sistema semplice come l'aritmetica. Gödel dimostrò anche l'incompletezza della teoria assiomatica degli insiemi. L'influenza che ebbe sulla matematica, e ancora di più sull'informatica, è enorme.

Cosa ha a che fare Gödel con il relativismo? nel distruggere il progetto di un formalismo universale per la matematica, in un certo senso egli rese la matematica una scienza relativa: non tutto è riconducibile ad un sistema "assoluto" di riferimento, a partire dal quale costruire il nostro castello di astrazioni. Una cosa in fondo semplice, basilare ed astratta come l'aritmetica, contiene in se il germe del paradosso.

Per questo motivo, ogni tanto nel tempio astratto della mia mente, accendo un cero virtuale al grande Kurt.