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

Leggendo quanto ho scritto sull’induzione, Gnugnu mi ha scritto, suggerendomi un teorema che si può dimostrare con l’induzione forte: ogni intero può essere scritto in un unico modo come somma di numeri di Fibonacci distinti e non consecutivi. Per chi non se lo ricordasse, i numeri di Fibonacci sono definiti così: F₁ = F₂ = 1, e poi F_n+1 = F_n + F_n-1. In questo caso, però, i primi due numeri di Fibonacci non sono 1 e 1 ma 1 e 2, in modo che tutti i numeri siano distinti. Se volete provare a dimostrare il teorema, smettete di leggere ora! Se invece della dimostrazione non ve ne può importare nulla, saltate i due paragrafi seguenti che sono sì semplici, ma anche piuttosto noiosi.
Per dimostrare che una cosa si può fare in un solo modo, in genere si inizia a domostrare che la si può fare, e poi si fa vedere che se la si fa in due modi questi sono in realtà lo stesso. Vediamo allora innanzitutto che ogni numero può essere scritto come somma di numeri di Fibonacci distinti e non consecutivi. I casi 1, 2 e 3 sono banali: la “somma” è il singolo numero stesso. Andiamo avanti, e prendiamo un n qualunque. Sia F_k=f il più grande numero di Fibonacci minore o uguale a n. Se f=n siamo a posto; altrimenti sia d=n–f. Sicuramente d<f, visto che tranne nel caso di 1 e 2 ciascun numero di Fibonacci è minore del doppio del precedente; cerchiamo ora il più grande numero di Fibonacci minore o uguale a d. Tale numero non può essere F_k-1, perché altrimenti se n ≥ F_k+F_k-1 allora è maggiore o uguale a F_k+1, contro la nostra ipotesi. Ma d è esprimibile come somma di numeri di Fibonacci distinti e non consecutivi per ipotesi induttiva, quindi siamo a posto per quanto riguarda la prima parte.
E per la seconda? Beh, prendiamo il più piccolo numero n esprimibile in due modi diversi come somma di numeri di Fibonacci distinti e non consecutivi. Il più grande F_k nello sviluppo dei due numeri deve essere per forza diverso: altrimenti anche n-F_k sarebbe esprimibile in due modi diversi, e quindi n non sarebbe il più piccolo. A questo punto ci occorre un lemma che mostri come – per quanto grande possa essere un numero come da ipotesi il cui sviluppo abbia come termine maggiore F_k – sarà sempre strettamente minore di F_k+1. Di nuovo, possiamo usare l’induzione. 1, 2, 3 non danno problemi perché il loro sviluppo contiene un solo numero. Per un k generico, un numero m il cui sviluppo abbia come termine maggiore F_k avrà al più come secondo termine F_k-2; quindi per ipotesi induttiva m – F_k < F_k-1 da cui m < F_k + F_k-1 = F_k+1, come volevasi dimostrare.
Dal lemma otteniamo così che non è nemmeno possibile che i due modi diversi per esprimere n abbiano come maggior numero di Fibonacci nel loro sviluppo due numeri diversi, e quindi la nostra tesi è ottenuta.
Detto tutto questo, e dando il bentornato a chi non ha avuto voglia di infilarsi in quei conti che sembravano essere infiniti, aggiungo che se io dovessi presentare una dimostrazione di questo teorema la farei in maniera completamente diversa e, almeno a mio parere, molto più intuitiva. Però prima di farla mi tocca fare qualche altro post…

Ultimo aggiornamento: 2010-03-11 07:00

Qualche giorno fa ho
iniziato a parlare dell’induzione matematica.
Dopo aver parlato di induzione solo dal punto di vista teorico, vediamo un esempio esplicito di dimostrazione per induzione, mostrando che la somma dei numeri dispari da 1 a 2n+1 è uguale a (n+1)². Il passo iniziale è semplicissimo: quando n=0, la somma dei numeri da 1 a 1 fa 1, che è esattamente il quadrato di 1. Più facile vederlo che spiegarlo. Immaginiamo ora che l’ipotesi valga fino a un certo n, e proviamo a vedere cosa succede con n+1. La somma dei numeri dispari da 1 a 2(n+1)+1, cioè da 1 a 2n+3, è pari a 2n+3 più la somma dei numeri dispari da 1 a 2n+1, che per ipotesi induttiva è (n+1)², cioè n²+2n+1. Facendo la somma otteniamo n²+4n+4, che guarda caso vale proprio (n+2)². Fine della dimostrazione: con un solo caso generale abbiamo dimostrato l’ipotesi per gli infiniti casi particolari.
Tutto questo è bellissimo, ma siete stati attenti c’è qualcosa che non va.Il guaio non è nella dimostrazione, che non è poi così difficile: si fanno giusto un po’ di giochetti formali coi numeri e si arriva al risultato, e questo capita spesso quando si usa l’induzione, tanto che a volte mi chiedo se nessuno abbia mai fatto un sistema di intelligenza artificiale che sappia risolvere problemi per induzione. Ma come facevamo a sapere che il risultato era proprio quello indicato nel teorema? Chi ce l’ha suggerito? Insomma, l’induzione è un bieco trucco; riusciamo solo a dimostrare qualcosa che conosciamo già. La cosa è spiazzante soprattutto per chi è rimasto alla concezione che purtroppo viene insegnata a scuola, vale a dire che la matematica sia qualcosa di perfettamente lucidato, con i teoremi che sono così perché non potrebbero essere diversi, e che scendono dall’alto come novelli deus ex machina. No, non è affatto così. La matematica avanza per tentativi ed errori, ed è solo in un secondo tempo che ci si affretta a togliere tutte le impalcature e lasciare solo il risultato finale per l’ammirazione del popolo. Per quanto riguarda l’induzione, quello che succede di solito è che il matematico fa un’ipotesi su quale possa essere il risultato, e poi controlla se ha ragione; proprio come un meccanico che ascolta il rumore di un motore e fa una diagnosi. Il vantaggio del matematico, se volete, è che non si sporca le mani… a meno che la penna con cui sta scrivendo non perda inchiostro!
Do solo un accenno a un’estensione del principio di induzione, che potete tranquillamente lasciar che è un parallelo della teoria cantoriana degli infiniti. L’induzione classica si applica all’infinito numerabile, ma si può anche parlare di induzione transfinita; in questo caso su dice che “se una proprietà P vale per zero, e quando vale per tutti gli ordinali minori di ψ, allora P vale anche per ψ, allora vale per tutti gli ordinali.” Come in tutte queste eteree proprietà logiche, l’induzione transfinita è indipendente da quella standard, nel senso che uno può accettarla oppure no e il resto della matematica va avanti tranquillo; se lo si accetta, però, l’induzione standard ci viene data gratis. Un esempio a riguardo è il teorema di Goodstein, che non è decidibile usando gli assiomi di Peano ma è vero se si ammette l’induzione transfinita.
Termino con un paradosso matematico basato sull’induzione, che “dimostra” come tutti i cavalli sono dello stesso colore. Prendiamo un insieme di n cavalli. Nel caso n=1 la tesi è banalmente vera. Per un n qualunque, numeriamo i cavalli e togliamo il numero 1. Rimangono n-1 cavalli, che per ipotesi induttiva sono tutti dello stesso colore. Ma se rimettiamo il numero 1 e ne togliamo un altro, abbiamo di nuovo n-1 cavalli, che sono sempre dello stesso colore di prima. A questo punto, visto che i due insiemi hanno un’intersezione in comune, è chiaro che tutti e n i cavalli sono dello stesso colore. O no?

Ultimo aggiornamento: 2010-03-08 07:00