[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)ⁿ 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 2ⁿ-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!