backup del Post

La magia delle soluzioni

Domenica scorsa ho postato sul mio blog personale un “problema della domenica”: quizzini generalmente non troppo complicati, che sto raccogliendo su una pagina apposita. Stavolta però il problema era più complicato del solito, e nessuno l’ha risolto: non solo, ma ci sono state lamentele sulla soluzione da me fornita. Eccovi il problema:

Dimostrate che dato un qualunque numero intero k, il prodotto di k interi consecutivi è divisibile per k!, dove il punto esclamativo indica il fattoriale e cioè il prodotto dei numeri da 1 a k. Per esempio, il prodotto degli undici interi da 13 a 23 è divisibile per 11!.

Se volete cimentarvici, smettete di leggere: la soluzione è qui sotto.

La prima risposta che potrebbe venire in mente è questa: «In un gruppo di k numeri consecutivi ce ne dev’essere per forza uno divisibile per 2, uno per 3, uno per 4, e così via fino a uno divisibile per k.» Questa effettivamente è stata anche la mia prima “dimostrazione” del teorema: peccato che non funzioni. Nell’esempio citato sopra con i numeri da 13 a 23, infatti, 18 è l’unico che è divisibile per 6 e per 9, e quindi viene contato due volte nel procedimento.

La soluzione canonica è questa: il prodotto di k interi positivi a partire da n è dato da (k+n-1)!/(n-1)!, numero che ricorda sospettosamente – per la precisione, è un suo multiplo – (k+n-1)!/(k!(n-1)!). Quest’ultima espressione corrisponde a C(k+n-1,k), cioè al numero di modi di scegliere k oggetti in un insieme di k+n-1. Siccome questo numero è evidentemente un intero, a fortiori lo sarà anche il nostro numero iniziale.

Dal mio punto di vista la soluzione non fa una grinza, anzi è persino elegante: ma zar ha espresso dei dubbi sulla sua validità (attenzione, non sulla sua correttezza! Se avete una mentalità matematica, la differenza è evidente: una soluzione corretta è accettata, però ci si può lamentare perché non è abbastanza “bella”). Per i curiosi, la discussione si è tenuta qui: in pratica, zar ritiene che la dimostrazione canonica sia quasi magia, e avrebbe preferito una dimostrazione algebrica del problema.

Io una dimostrazione algebrica ce l’ho anche, a dire il vero. Parte dalla dimostrazione errata qui sopra: però non considera i numeri da 1 a k ma i loro fattori primi. Per fissare le idee, prendiamo il fattore 2. Indicando con [x] la parte intera di x, in k! abbiamo [k/2] multipli di 2, [k/4] multipli di 4, [k/8] multipli di 8 e così via (quando arriviamo a una potenza di 2 superiore a k il valore corrispondente sarà zero, il che ci va benissimo: è uno dei casi in cui tornano utili le mirabolanti proprietà dell’insieme vuoto). Ma in qualunque successione di k interi consecutivi ne abbiamo [k/2] multipli di 2, [k/4] multipli di 4, [k/8] multipli di 8 e così via: quindi stavolta l’associazione è perfetta, perché togliamo man mano un fattore 2 a tutte le coppie di numeri pari (saltandone magari uno: se invece che i numeri da 11 a 23 nel nostro esempio avessimo preso quelli da 10 a 22 ce ne sono sei pari contro i cinque dei numeri da 1 a 11), un secondo fattore 2 ai multipli di 4, e così via. Riapplicando lo stesso ragionamento a tutti i numeri primi minori di k arriviamo alla risposta. Non c’è più il “problema del 18”: gli toglieremo regolarmente il fattore 9, mentre il 6 = 2·3 verrà preso altrove.

Ecco. La dimostrazione puramente algebrica c’è. Peccato che sia una schifezza. Può darsi ce ne sia qualcuna di più semplice: parafrasando Ennio De Giorgi, il problema è uno ma le soluzioni sono tante. Resta il mio assunto di base: perché mi devo sforzare di fare una dimostrazione algebrica quando ce ne ho una combinatorica a portata di mano?

Se proprio dobbiamo parlare di “magia delle soluzioni”, ci sono almeno due significati diversi che mi vengono in mente. Il primo si può riassumere come «ma come diavolo ti è venuto in mente di provare quell’approccio? È pura magia!». Ci sono effettivamente casi, come capita spesso nei problemi più bastardi delle competizioni matematiche, in cui è praticamente impossibile tirare fuori la dimostrazione “magica”. Questo capita quando il problema è costruito a posteriori a partire da un teorema che si stava dimostrando, notando che l’enunciato poteva essere cucinato in altro modo e presentato all’ignaro competitore. Oserei dire che questo non è il caso: almeno dal mio punto di vista il passaggio logico “scrivere esplicitamente il numero come rapporto tra due fattoriali” porta immediatamente a pensare al numero di combinazioni. Il secondo significato è invece «ma come è possibile che due campi a prima vista così lontani della matematica siano invece intimamente legati? È pura magia!». Beh, in questo caso sono d’accordo: è magia. Ma è anche il bello della matematica: spesso le conoscenze sono progredite proprio perché qualcuno si è magicamente accorto che un problema poteva essere visto in un altro modo e a quel punto si potevano applicare le tecniche di un’altra branca della matematica. Vi assicuro che è una sensazione favolosa.

Voi che ne pensate? La matematica è magia a prescindere, come diceva Clarke per la tecnologia troppo avanzata, oppure ci sono cose per voi più o meno magiche?