Questo mese tocca ad Annarita ospitare il Carnevale della Matematica, e lo fa come di sua abitudine con un’edizione strepitosa: non solo per i settantaquattro post scritti da ben trenta collaboratori, ma anche per la parte introduttiva sulla bellezza della matematica.
Ricordate che avete solo un mese di tempo prima della prossima edizione, ospitata da Science Backstage.

Ultimo aggiornamento: 2010-05-14 10:40

Di roba ce n’è davvero tanta, quindi accorrete numerosi!

Ultimo aggiornamento: 2010-04-14 09:33

Una delle cose più o meno inutili che piacciono ai matematici è vedere come è possibile ricoprire perfettamente il piano (“tassellarlo”) con figure “carine”. Ad esempio, ci sono diciassette tassellature regolari fondamentalmente distinte, come si può leggere ad esempio su Wikipedia e come sfruttato da Mauritz Cornelius Escher nelle sue litografie. Se si vuole tassellare il piano usando un singolo poligono regolare le uniche possibilità sono date da quadrato, triangolo equilatero ed esagono regolare; se si ammette l’uso di poligoni regolari diversi e si aggiungono però i vincoli di non scorrimento (ogni lato di un poligono combacia esattamente con un lato di un altro poligono) e di identificazione dei vertici (ogni vertice della figura è indistinguibile dagli altri) ci sono solo 11 possibilità.
Ma la cosa più interessante è riuscire a trovare una tassellatura aperiodica del piano; un insieme di figure che ricoprono sì il piano, ma senza nessuna simmetria di traslazione. Detto in altre parole, se avessimo due fogli infiniti di carta con una tassellatura aperiodica del piano che non possono ruotare ma solo scorrere nelle due dimensioni, l’unico modo per sovrapporli esattamente è non spostarli affatto. La cosa sembra incredibile, ma è possibile costruire una simile tassellatura usando solo due rombi, uno più cicciotto e uno più smilzo; Roger Penrose e Robert Ammann hanno mostrato nel 1974 come sia possibile farlo, ottenendo una tassellatura che ha solo una simmetria di rotazione, di 72 gradi per la cronaca. Un altro modo per fare una tassellatura di Penrose consiste nell’usare un quadrilatero convesso (“kite”) e uno concavo (“dart”), come forse avrete visto da qualche parte.
Il Sacro Graal della tassellatura consiste nel trovare una singola forma che ricopra il piano solamente in maniera aperiodica; potete immaginare come io sia saltato sulla sedia dopo aver letto su MathPuzzle che una piastrella simile era stata trovata! Poi sono andato a leggere l’articolo su arXiv (PDF), e ho purtroppo scoperto che la notizia era stata molto pompata. La piastrella esagonale mostrata qui sopra, con le regole indicate nell’articolo, in effetti ricopre il piano in maniera aperiodica, ma non è possibile modificarla aggiungendo denti e buchi in modo che quello sia l’unico modo per tassellare il piano. Gli autori si arrampicano sugli specchi dicendo che però si può forzare l’aperiodicità se a partire dalla piastrella si disegna una figura non semplicemente connessa (composta cioè di pezzi staccati che però per decreto sono considerati parti della stessa forma) oppure andando sulle tre dimensioni, manco fossimo al cinema.
Intendiamoci: il risultato è sicuramente interessante, ma non è la notiziona che ci si aspettava; potete ancora andare alla caccia della tassellatura aperiodica!

Ultimo aggiornamento: 2010-04-13 07:00

Ricordate il problema che avevo postato il mese scorso, in cui si chiedeva di dimostrare che ogni numero intero può essere espresso in uno e un solo modo come somma di numeri di Fibonacci distinti e non consecutivi? Avevo dato una dimostrazione per induzione, ma avevo aggiunto che non avrei mai scelto di dimostrarlo in questo modo perché il tutto mi pareva inutilmente involuto. Adesso vi presento la “mia” soluzione, presentata in modo descrittivo seguendo il ragionamento che ho effetivamente fatto: come vedrete, è un misto di ricorsione e induzione.
Innanzitutto ho iniziato a scrivere i primi numeri che corrispondono alle ipotesi in “base Fibonacci”. Detto in altro modo, proprio come 2718 in base 10 equivale a 8*10⁰ + 1*10¹ + 7*10² + 2*10³, 2718 in base Fibonacci – che scriverò come 2718_F – equivale a 8*F(1) + 1*F(2) + 7*F(3) + 2*F(4), cioè 8*1 + 1*2 + 7*3 + 2*5 = 41. I numeri esprimibili come somma di numeri di Fibonacci distinti e non consecutivi, se scritti in base Fibonacci, saranno composti da soli zero e uno, senza avere mai due uno consecutivi. Ho iniziato così a scrivere i primi di questi numeri, mettendo a fianco il valore corrispondente in base 10.
1_F = 1
10_F = 2
100_F = 3
101_F = 4
1000_F = 5
1001_F = 6
1010_F = 7
10000_F = 8
10001_F = 9
10010_F = 10
10100_F = 11
10101_F = 12
Mi sono subito accorto di una cosa fantastica: abbiamo scritto una e una sola volta tutti i numeri da 1 a 12! Visto che il numero successivo, 100000_F, è già 13, posso immaginare che questo pattern continui all’infinito. A questo punto mi sono messo a cercare una formula ricorsiva per vedere quanti e quali sono i numeri di k cifre in base Fibonacci che soddisfino i vincoli. A parte i casi banali con k ≤ 2, un numero di k cifre inizia con il prefisso 10 e continua usando tutti i numeri con al più k-2 cifre (compreso 0). Il numero di questi numeri è F_k-2 (per ipotesi induttiva); visto che quelli con meno di k cifre sono F_k-1 (sempre per ipotesi induttiva), la loro somma è proprio F_k. Siamo così riusciti a costruire ricorsivamente tutti i numeri con al più k cifre in base Fibonacci che soddisfino i vincoli, e abbiamo scoperto che li abbiamo trovati tutti (e non ce ne sono di uguali, perché se m_F e n_F sono diversi, 10m_F e 10n_F sono anche diversi).
Il tutto è ricorsione oppure no? Qualche passaggio induttivo l’ho usato, e del resto il mio amico gnugnu dice che secondo lui ricorsione, induzione e discesa infinita – una tecnica di dimostrazione per assurdo che Fermat apprezzava molto ma che è davvero complicata da usare – sono poi la stessa cosa. Il mio pragmatismo è un po’ diverso: io vedo i vari metodi in maniera diversa, e trovo appunto una dimostrazione come questa essenzialmente più “visuale” di una prettamente induttiva. Inoltre in questo modo uno si convince del risultato, e riesce anche a capire come possa averlo trovato a chi ha proposto il teorema; sicuramente l’enunciato standard non ve l’avrebbe mai fatto venire in mente.
Voi che ne pensate?

Ultimo aggiornamento: 2010-04-08 07:00

ricorsione, s.f.: vedi ricorsione

L’induzione, di cui ho parlato poco tempo fa, è una brutta bestia: non tanto per la complessità del concetto, quanto perché il modo con cui si impiega generalmente l’induzione è piuttosto astratto. Le dimostrazioni per induzione assomigliano spesso a un gioco di prestigio algebrico, con un po’ di operazioni formali. Insomma, qualcosa che funziona sì, ma non ci dà informazioni su cosa sta effettivamente dietro.
La cosa buffa è che però è relativamente semplice trovare spiegazioni sull’induzione, ma almeno per i matematici non ci sono così tante informazioni su un modo in un certo senso simile per risolvere i problemi matematici: la ricorsione. La mia sensazione è che la ricorsione era sempre stata usata dai matematici del passato, ma veniva considerata una tecnica di serie B e quindi snobbata nelle dimostrazioni “ufficiali”. Poi è arrivata l’informatica, dove la ricorsione è parecchio usata; di nuovo però i matematici pensano che una cosa usata dagli informatici non è poi così importante… Ma lasciamo perdere queste disquisizioni, e vediamo come funziona la ricorsione.
Tecnicamente la ricorsione consiste nel risolvere un problema P con dati in ingresso D riconducendosi alla risoluzione del problema P con dati in ingresso D’, dove i dati D’ sono “più semplici” dei dati D. La frasetta magica “ricondursi al caso precedente” ricorre spesso nelle barzellette create dai fisici per prendere in giro i matematici; ma in questo caso la cosa è piuttosto diversa, e molto più seria. Ecco l’esempio canonico di ricorsione, tanto per mettere le cose più in chiaro: il calcolo del fattoriale.
Come probabilmente ricordate, il fattoriale di un numero intero positivo n, indicato con n!, è il prodotto dei numeri da 1 a n. Per convenzione, 0! e 1! sono uguali a 1. Per calcolare n! si può appunto fare il prodotto dei numeri da 1 a n, ma si può anche operare in altro modo. Un informatico per esempio scriverebbe un programma la cui parte principale dice più o meno così: “Per calcolare la funzione “fattoriale di n“, chiamo la funzione “fattoriale di n-1″ e moltiplico il risultato per n.” Chi non è abituato a queste cose fa un balzo sulla sedia: “Ma come fa questo qua a scrivere una cosa del genere? Com’è possibile definire una funzione per mezzo di sé stessa? Non si sovrappongono i pezzi?” Per quanto riguarda la struttura informatica, vi posso assicurare che non ci sono problemi: quello che viene richiamato non è il programma inteso come archetipo ma una sua istanza, insomma un suo clone. Il punto chiave è che dobbiamo essere certi che il procedimento non si espenda all’infinito, oppure che a un certo punto si ritorni al punto di partenza ottenendo così un circolo vizioso. Ma per fortuna questo non è il caso: il numero di cui si deve calcolare il fattoriale continua a ridursi, e prima o poi diventerà 1 (beh, ammesso che l’input sia stato un numero intero positivo. Ma quello del validare i dati in ingresso è un altro tipo di problema: qui si fa matematica, non informatica). Ma noi sappiamo quanto vale il fattoriale di 1! (per la cronaca, quest’ultimo è un punto esclamativo, non il simbolo di fattoriale), cioè 1. In definitiva, basta aggiungere il caso particolare; “Per calcolare la funzione “fattoriale di n“, verifico se n=1; in caso affermativo il risultato è 1, altrimenti, ecc. ecc.”.
Notata la differenza con l’induzione? Lì partivamo da 1 e salivamo fino all’infinito, grazie al quinto postulato di Peano; qui partiamo da un numero qualunque e scendiamo fino a 1. C’è però un altro punto che in genere viene trascurato. L’induzione parte da una formula chiusa, una cioè dove basta infilare il numero e si ottiene il risultato; con la ricorsione non c’è nulla del genere, e anzi trovare una formula chiusa a partire da quella ricorsiva non è sempre così semplice. Tanto per fare un esempio pratico, prendiamo i numeri di Fibonacci. Come ricordate, la loro definizione è ricorsiva: F₁ = F₂ = 1, e F_n+1 = F_n + F_n-1. È anche possibile avere una formula esplicita per l’n-simo numero di Fibonacci:

dove φ₁ è (1+√5)/2 e φ₂ è (1-√5)/2. Semplice, no? Vero che ce l’avevate sulla punta della lingua? D’accordo, questo è forse un caso limite: ma in genere ci vuole comunque una certa arte per trovare la formula chiusa corrispondente a una formula ricorsiva.
Nonostante tutto, però, la ricorsione almeno a mio parere è un modo più naturale per trovare la soluzione di tutta una classe di problemi, e quindi dovrebbe essere sempre pronta nella borsa degli attrezzi di un matematico.

Ultimo aggiornamento: 2010-04-01 11:43

Non so quanto sia leggera questa matematica qua; diciamo però che la soluzione, quando ve la dicono, è facile.
Come forse ricordate, un polinomio di grado n può essere determinato univocamente se conoscete il suo valore in n+1 punti. Supponiamo però che ci venga detto che il nostro polinomio P sia speciale: i suoi coefficienti sono tutti interi non negativi. In questo caso è concepibile che si possa determinare il polinomio conoscendo un numero minore di valori. Se ci è consentito di scegliere opportunamente per quali numeri x (algebrici) ci venga detto qual è il valore di P(x), quanti ce ne serviranno?
(l’ho visto da God Plays Dice, dove c’è anche la soluzione…)

Ultimo aggiornamento: 2010-03-17 16:22

Vi siete ricordati ieri di festeggiare il Giorno Pi Greco? No? Male. Adesso per fare penitenza andate da Popinga e leggetevi il Carnevale della Matematica – edizione numero 23!

Ultimo aggiornamento: 2010-03-15 11:54