[Questo è un vero articolo di matematica light, nel senso che ho eliminato equazioni e dimostrazioni. Chi volesse fare le cose un po’ più sul serio, può andare a leggere la versione completa su una Prestigiosa Rivista Matematica]
Immagino che abbiate già sentito parlare del Triangolo di Tartaglia, magari sotto il nome di Triangolo di Pascal. È un triangolo (ma vah?) infinito, che ha in punta e sui due lati tutti 1; gli altri numeri si calcolano sommando i due numeri immediatamente al di sopra. Il triangolo di Tartaglia, come tante strutture matematiche, spunta da tante parti; ad esempio, i coefficienti dello sviluppo binomiale (1+a)n sono proprio gli elementi della riga n del triangolo di Tartaglia. Ah: la prima riga, quella per intenderci dove si trova solo il numero 1, è la “riga zero”. I matematici amano partire da zero.
Oltre alla formula ricorsiva per ricavare i numeri del triangolo di Tartaglia, ce n’è anche una che permette di calcolare esplicitamente il k-simo elemento della n-sima riga; esso vale n!(k!(n–k)!), dove l’esclamativo indica la funzione fattoriale. Ah, il primo elemento, quello per intenderci più a sinistra, è l'”elemento zero”. Vi ho già detto che i matematici amano partire da zero?
Ma immaginiamo che non ci interessi sapere il valore esatto dei vari elementi del triangolo di Tartaglia, ma solo se sono pari o dispari. Proviamo a disegnare il triangolo mettendo un pixel nero se il numero è dispari e uno bianco se è pari: il risultato, come vedete, sembra una specie di merletto e ha l’aspetto di tipo frattale. In effetti la figura limite è nota come Triangolo di Sierpinski: se siete romantici, potete anche vederla così. Spesso i frattali hanno una descrizione semplice, e anche in questo caso in effetti c’è un modo per trovare rapidamente se un pixel è bianco o nero, cioè se il numero corrispondente è pari o dispari. Guardando la figura, vediamo che ci sono delle righe tutte nere, altre righe quasi tutte bianche, e ancora altre righe un po’ alternate, il che però non ci dice molto; la spannometria è utile, ma in questo caso non ci basta.
Il matematico che scoprì la regola è un poco conosciuto francese vissuto nell’Ottocento: Edouard Lucas. Lucas è forse più noto ai matematici ricreativi che a quelli accademici, anche se il test che permette di annunciare ogni tanto la scoperta di un numero primo enorme è stato inventato da lui e poi affinato da Lehmer. Non è un caso che il test di primalità valga per i numeri della forma 2n-1: Lucas era affascinato dai numeri scritti in notazione binaria, e purtroppo per lui era nato con un secolo di anticipo, perché altrimenti sarebbe stato deliziato dagli elaboratori elettronici che in base 2 ci lavorano. Un altro esempio di questa sua infatuazione è la creazione del gioco della Torre di Hanoi, nella cui soluzione le potenze di due giocano un ruolo fondamentale.
Torniamo al nostro triangolo, e prendiamo un elemento a caso; quello in posizione k nella riga n, ricordandoci sempre che si inizia a contare da zero. Scriviamo ora k e n in formato binario, e mettiamoli uno sotto l’altro, aggiungendo se necessario degli zeri a sinistra di k perché siano della stessa lunghezza. Cerchiamo ora tutti i bit di k che hanno valore 1 e vediamo il bit corrispondente di n; se per ciascuno di quei bit di k anche quello corrispondente di n vale 1, allora il nostro elemento sarà dispari, altrimenti sarà pari. Lo so, detto così è incomprensibile; quindi faccio un esempio pratico. Se n vale 19, cioè 10011 in notazione binaria, ci saranno esattamente otto valori di k per cui l’elemento del triangolo sarà dispari: quelli della forma x00xx, dove x può valere 0 oppure 1. Andando a scalare, ci saranno così 10011 in formato binario, cioè 19; 10010=18, 10001=17, 10000=16, 00011=3, 00010=2, 00001=1, e… 00000=0. Quest’ultimo risultato può sembrare un po’ strano: in fin dei conti non ci sono mica bit di k che valgano 1, e quindi si direbbe che l’ipotesi non valga. Ma i matematici amano parlare delle mirabolanti proprietà dell’insieme vuoto: se ci pensate, questo caso è la stessa cosa che dire “se non faccio, non sbaglio”. Poi dovreste fidarvi, visto che l’elemento in posizione zero è il primo della riga (vi ho già detto che i matematici amano partire da zero?) e quello vale sicuramente 1.
Vi faccio ancora qualche esempio facile. Le righe 2, 4, 8, 16… del triangolo, vale a dire la terza, la quinta, la nona… sono quelle dove gli unici pixel neri sono i due estremi, dove cioè k = 0 e k = n; in effetti n è della forma 1000…000 e non si può fare molto. In compenso, le righe appena sopra di esse, cioè la 1, 3, 7, 15, … sono completamente nere, e in effetti se n è della forma 1111…111 si può scegliere un k qualsiasi, perché tanto i bit sopra sono tutti a 1. Se ci si pensa un po’ su, si può capire perché ci siano i triangoli bianchi che man mano si riducono (aiutino: dipende da quanti 1 ci sono a destra nella rappresentazione binaria di k); ma si può anche lasciar perdere tutto questo e limitarsi ad apprezzare il risultato. Qui si vuole essere light, in fin dei conti!
Ultimo aggiornamento: 2014-03-05 11:05
Bella questa, non la sapevo. Adesso per colpa tua passerò il resto della mattina con il triangolo di Tartaglia-Lucas-Sierpinski invece che con l’Average Case Complexity. :-P
bello bello…
però ogni tanto potresti venire a leggerci! :-) :-)
scherzo… proprio in questo periodo “ci abbiamo lavorato su”!
se vai un po’ in giù ancora in home….
ciao!
g
@giovanna: il triangolo di Tartaglia è sicuramente fonte di tante, tante curiosità :-)
(il mio post è nato a fine gennaio, mentre ero lontano da internette… solo che dovevo aspettare la pubblicazione ufficiale)
… e meno male che per una volta la “pubblicazione ufficiale” non è uscita in ritardo :-)
@piotr: ho una recensione di libro ferma da una decina di giorni, e stasera ne preparo un’altra che resterà pure ferma in attesa di pubblicazione ufficiale (altrove). Tanto notiziole ce ne sono sempre!
@Piotr: in effetti ho ricevuto la NL il 02/03/2009 alle 0.05 ed ho immediatamente (o quasi) scaricato il numero… Andando, lo ammetto, diretto ai Paraphernalia: colpa della tua segnalazione nella NL :-)
@.mau.: se non erro c’e’ un piccolo refuso, quando nel coefficiente binomiale semplifichi il n! al numeratore ed il (n-k)! a denominatore dovrebbe restarti a numeratore un prodotto n(n-1)…(n-k+1) e non n(n-1)…(n-k), visto che il fattore (n-k) e’ “morto” assieme all'(n-k)! del denominatore. Ma e’, credo, un banale refuso che non ha alcun effetto sulla logica della dimostrazione. Dimostrazione che non hai reso certo immediata, almeno non a me… Ma buona parte del divertimento e’ capirla e scoprirne i meccanismi.
C’e’ solo un punto che mi lascia perplesso. E’ possibile dimostrare questo risultato in termini puramente combinatori?
In genere, si sfrutta il fatto che il coefficiente binomiale dia le combinazioni, e si puo’ prendere questo come punto di partenza per costruire dimostrazioni “combinatorie” piuttosto che “algebriche”.
Curioso che tu sottolinei le difficolta’ dell’insieme vuoto, o meglio, la difficolta’ fondamentale di convincere il prossimo che l’insieme vuoto e’ sottoinsieme di qualsiasi insieme e quindi far visualizzare il singoletto che contiene l’insieme vuoto.
A tale proposito si e’ espresso anche il Lolli nella sua guida alla teoria degli insiemi, testo rivolto a chi si occupa di didattica della matematica, ed ovviamente riporta simili difficolta’ anche in merito all’insieme potenza…
@Alessandro: sì, hai ragione sul refuso.
Non so se si possa fare una dimostrazione combinatoria pura: il mio modo di vedere le cose è spesso non-standard, e in questo caso il punto chiave è stato proprio il vedere i blocchettini di pixel nero che si spostavano in maniera beneducata.
Sull’insieme vuoto, la mia esperienza dice che è un concetto che i non matematici fanno fatica a comprendere. È vero che in questo consesso non ci dovrebbero essere problemi di questo tipo, ma non si sa mai.
@.mau.: anche tu alla fine sei ricorso alla logica per “convincere” i lettori delle proprieta’ dell’insieme vuoto…
Anche PGO ha scritto un papero divulgativo “Godel for children”, diretto pero’ a bimbi che quanto meno hanno masticato parecchia logica predicativa.
Insomma, scusa la ridondanza ma sono veramente interessato a chiarire cosa si debba intendere per “divulgazione”.
:-)
@Alessandro: mica ho detto di essere perfetto :-P
@.mau.: ma tu sai tutto, salvo un insieme a misura nulla, quindi non si accettano simili giustificazioni! :-)
Su PGO devo ammettere che la notiziola in cui riferivi della sezione “Odifreddi” da Feltrinelli mi ha abbastanza depresso.
Ho molto apprezzato i PRIMI libri di PGO, e persino un suo seminario in cui per 3/4 del tempo ha parlato di zichicche e solo alla fine ha concesso un po’ di spazio alla logica (beh, era ospite del dipartimento di tecnologie cognitive e della comunicazione, qualcosa doveva pur dirla di attinente).
Ora pero’ scrive veramente di tutto e su qualsiasi argomento.
Il libercolo su Darwin, ad esempio, non e’ certo all’altezza di opere divulgative come quelle di Dawkins, ed e’ nel complesso molto deludente (IMHO, ovviamente).
E diciamocela tutta, la scusa “chi campa di libri deve scriverne parecchi” non si adatta al nostro “prezzemolo”, che magari non a tempo pieno ma e’ pur sempre un professore di prima fascia, quindi riceve uno stipendio piu’ che decente, o almeno tale da non giustificare questo zelo nello sfornare nuovi libri.
Torniamo al problema della divulgazione ed al rischio della banalizzazione…
Tra parentesi, sono il solo ad avere avuto l’impressione che Nash prendesse sottilmente in giro PGO durante l’intervista al festival della Matematica senza che “prezzemolo” se ne avvedesse? :-)