Pari o dispari?

[Nota: di questo articolo esiste anche la versione più leggera.]

Noi lo chiamiamo Triangolo di Tartaglia. Più o meno tutto il resto del mondo lo chiama Triangolo di Pascal. Credo che per gli arabi sia il Triangolo di Khayyam, e gli svizzeri potrebbero anche definirlo Triangolo di Bernoulli; i cinesi poi ci fanno gentilmente notare come loro lo conoscevano e ne parlavano ben prima che noi europei ne avessimo anche solo una lontana idea. Sicuramente l'avete visto chissà quante volte anche voi: è il triangolo formato dai coefficienti delle potenze nello sviluppo del binomio (1+a) ⁿ al crescere di n. Insomma, lo sviluppo binomiale di Newton, tanto per aggiungere ancora un altro nome alla sfliza di matematici enunciati all'inizio. Se così non vi viene in mente ancora nulla, magari vedere le sue prime righe vi dà qualche idea.

Generare il triangolo è semplice: i due lati del triangolo sono composti da tutti 1, e ogni altro numero è la somma dei due immediatamente sopra di esso. Le proprietà di questo triangolo sono tantissime, e ci si potrebbe scrivere probabilmente un libro sopra; ad esempio, se siete amanti dei numeri di Fibonacci sarete deliziati nello scoprire che è possibile trovare una successione di Fibonacci ben nascosta tra le righe (e le colonne). Scriviamo il triangolo in formato leggermente diverso e facciamo la somma dei numeri sulle diagonali: otteniamo proprio i numeri di Fibonacci. Simpatico, no?

Ma stavolta non voglio parlare di Fibonacci, bensì di un misconosciuto matematico francese dell'Ottocento: Edouard Lucas. In effetti una correlazione c'è, visto che Lucas generalizzò la successione di Fibonacci e in suo onore quella che inizia con 1, 3, 4, 7, 11... si chiama appunto successione di Lucas. Ma Lucas, che fu un semplice professore di liceo, mi sa tanto che sia stato snobbato dai grandi matematici francesi da Cauchy a Poincaré, il che è semplicemente una vergogna. Oltre che esserci simpatico perché era un matematico intuitivo e amava i giochi matematici – ha anche scritto un'opera in tre volumi intitolata Récréations Mathématiques – ha scoperto dell'ottima matematica. Purtroppo per lui, è nato con un secolo di anticipo. Era infatti fissato con la rappresentazione binaria: roba tirata fuori già da Leibnitz ma che non aveva alcun interesse pratico almeno fino a che non sono stati sviluppati i primi elaboratori elettronici. Per fare un esempio, Lucas studiò i numeri di Mersenne (quelli della forma 2ⁿ-1, la cui rappresentazione binaria è quindi composta da tutti 1) e trovò un metodo (relativamente...) molto rapido per verificare se sono primi. Ancora oggi non è un caso che i numeri primi giganteschi che si scoprono ogni tanto siano di Mersenne, perché si usa una variante del suo metodo, detta test di Lucas-Lehmer. Un altro esempio dell'infatuazione di Lucas per la rappresentazione binaria è data dal gioco della Torre di Hanoi, inventato da lui e che - toh! - si risolve esattamente in 2ⁿ-1 passi, ciascuno dei quali ha un immediato corrispondente intuitivo in un numero binario.

Anche la proprietà che Lucas ha scoperto e che ora mi accingo a mostrare e dimostrare è legata ai numeri binari, ed è assolutamente incredibile a prima vista. Innanzitutto, un po' di notazioni per semplificarci la vita dopo. Definiamo B(n,k), con k≤n, il coefficiente (binomiale) di a^k nello sviluppo di (1+a)ⁿ. Se prendiamo ad esempio

(1+a)⁵ = a⁵ + 5a⁴ + 10a³ + 10a² + 5a + 1

Per quanto detto prima, esiste una formula ricorsiva per calcolare B(n,k): se k=0 oppure k=n, esso vale 1, altrimenti vale

B(n-1,k-1) + B(n-1,k).

Non so se avete notato il genio di Lucas al lavoro: per calcolare ad esempio se B(31415,926) è pari o dispari, ci basta trasformare i due numeri in forma binaria (costo dell'operazione O(n log n)) e confrontarli (costo O(n)). Roba che si può fare anche con carta e matita, mentre vi sfido a calcolare i fattoriali oppure fattorizzare tutti i numeri per vedere quante sono le potenze di due nei fattoriali sopra e sotto la divisione. D'altra parte, la cosa ha anche un senso: a noi non interessa sapere il valore del coefficiente binomiale fino all'ultima cifra, ma solo una piccola parte di esso - noi che siamo abituati ai computer diremmo "il bit meno significativo" - e quindi non serve necessariamente dover fare tutti i conti. Ma da qui a scoprire la regola enunciata sopra ce ne vuole! Noi siamo più fortunati di Lucas, perché a differenza sua sappiamo già qual è il risultato che dobbiamo dimostrare. Ma dobbiamo comunque dimostrarlo, no? Ecco qua come ho fatto io, probabilmente seguendo una strada non ottimale ma che ha il vantaggio di "pensare binario", il che mi pare nello spirito di Lucas.

Iniziamo con alcuni casi facili. B(n,n) è uguale a uno, e quindi dispari; e in effetti, visto che k è uguale ad n, è immediato che in ogni posizione in cui nello sviluppo binario di k c'è un 1, anche nella corrispondente posizione di n un 1 c'è per forza. B(n,0) vale anch'esso 1, ma può dare qualche problema in più per verificare la nostra tesi... se non si è abituati a fare matematica e quindi non si conoscono "le mirabolanti proprietà dell'insieme vuoto", come ci raccontavano all'università. La rappresentazione binaria di zero è composta da tutti zeri, il che significa che non c'è alcun 1; detto in altro modo, l'insieme delle posizioni con una cifra 1 è l'insieme vuoto. Ma allora è vero che per tutte le (inesistenti) posizioni dove c'è un 1, c'è un 1 anche nella posizione corrispondente di n! Se non siete ancora convinti della cosa, provo a spiegarlo con la logica formale. L'espressione A → B è logicamente equivalente a NOT B → NOT A. La nostra frase «in ciascuna posizione dove la rappresentazione di k ha un 1 allora la rappresentazione di n ha un 1» diventa «in ciascuna posizione dove la rappresentazione di n non ha un 1 (cioè ha uno 0) allora la rappresentazione di k non ha un 1 (cioè ha uno 0)». Vista così, converrete con me che è assolutamente vero, no? L'ultimo caso che ci serve come base di partenza è B(n,k) per n=2^r e k diverso da 0 e n. Visto che la rappresentazione di n è del formato 1000...000, e quella di k ha per definizione un 1 in un'altra posizione, dobbiamo dimostrare che tutti questi valori sono pari. In effetti, scriviamo B(n,k) nella versione estesa (n(n-1)(n-2)...(n-k))/(1*2*...*k). Quando k è dispari, se si esclude il fattore n si possono accoppiare tra loro tutti gli altri numeri pari, uno al numeratore e uno al denominatore: 2 con n-2, 4 con n-4, e così via. Tutte queste coppie di numeri hanno esattamente lo stesso numero di fattori 2: se non ci credete, scrivetele in formato binario e controllate qual è la cifra 1 che si trova più a destra. Quindi tutti questi fattori 2 si eliminano, e resta solo a numeratore n, cioè 2^r. Se invece k è pari, gli accoppiamenti lasciano liberi a numeratore n e a denominatore k; ci resta pertanto qualche fattore 2 in più da scialare a numeratore, e il risultato continuerà ad essere pari.

A questo punto, siamo pronti ad affrontare il caso generale. Fissiamo n, e prendiamo tutti i B(n,k) visti come i coefficienti delle potenze crescenti – andrebbero anche bene decrescenti per ovvie ragioni di simmetria, ma non stiamo a sottilizzare – di a nello sviluppo di (1+a)ⁿ. Se definiamo polinomio r-binario il polinomio (1+a)^m dove m =2^r, e ci limitiamo a guardare la "firma di parità", vale a dire scriviamo p se il coefficiente è pari e D se il coefficiente è dispari, abbiamo appena visto che la firma di parità di un polinomio r-binario è Dpppp...pppD, dove il primo D corrisponde al coefficiente del termine di esponente 0 e il secondo a quello del termine di coefficiente m, cioè 100...0 se viene scritto in notazione binaria. Scriviamo ora il nostro polinomio (1+a)ⁿ come prodotto di polinomi r-binari e iniziamo a fare il prodotto da quello con r più grande a quello con r più piccolo. Notiamo innanzitutto che ciascun prodotto, dal punto di vista dei coefficienti, consiste nel sommare la firma di parità Q₁Q₂Q₃...Q_t-1Q_t con sé stessa spostata di m =2^s posizioni per qualche s. Per costruzione, è impossibile che nei vari prodotti che si fanno si arrivi a sommare per qualche esponente due valori entrambi dispari, visto che questo significherebbe che la somma di potenze di 2 con esponenti tutti diversi tra loro sia una potenza di due con esponente ancora diverso. Sempre per costruzione, se nel nostro polinomio fattorizzato non c'è l'esponente di indice 2^k allora al passo corrispondente a k non sarà possibile far diventare dispari gli esponenti di formato (2r+1)k e ai passi successivi non potranno quindi diventare dispari quelli tra (2r+1)k e 2(r+1)k-1. Se invece l'esponente di indice 2^k allora quegli esponenti diventano dispari e si può andare avanti... ottenendo così per induzione esattamente il risultato voluto. Visto in questo modo, l'enunciato del teorema sembra assolutamente naturale: ma come ho detto all'inizio, il genio è stato vedere che si poteva lavorare in una configurazione come questa. Lucas è stato un genio, non c'è che dire.

Quando si arriva a un risultato così bello, un matematico pensa subito a come lo si possa generalizzare. Purtroppo non sono riuscito a vedere nulla di fattibile con il modulo 3. Oltre al fatto che non è che io sia un così bravo matematico, credo che conti molto il fatto che 2 sia un numero primo strano, come dicono gli inglesi: "2 is an even prime number, so it is odd". Lascio comunque al lettore la possibilità di generalizzare ;-)

©Maurizio Codogno, 27 febbraio 2009