Grandi numeri
La scorsa settimana ho postato sul mio blog uno dei miei soliti quizzini della domenica, il cui testo mi era stato inviato da Marcello Semboli. Una cassaforte si apre infilando tre schede nelle rispettive serrature. Le schede esternamente sono identiche: quando vengono infilate tutte e tre, quelle messe nella posizione sbagliata chiudono la loro serratura mentre quelle nella posizione giusta ne cambiano lo stato: da aperta a chiusa e viceversa. Noi non possiamo conoscere lo stato delle singole serrature, a meno che non siano tutte aperte e quindi la cassaforte si apra. Stamattina però qualcuno ha giocato con le chiavi: la cassaforte è chiusa e le tre chiavi sono sul tavolo, non si sa in che ordine. È possibile trovare una successione di mosse che apra la cassaforte?
La risposta è sì, e potete andare a leggere qua qual è la successione di mosse necessaria. A me ci è voluta una pausa pranzo per risolverlo, your mileage may vary. Ma io, da buon matematico, una volta risolto il problema ho subito pensato alle possibili generalizzazioni: avere N serrature e non solo tre, e avere schede che quando non sono inserite al posto giusto non fanno nulla invece che chiudere la serratura. L’idea di questa seconda generalizzazione nasce vedendo che nella mia dimostrazione avevo sfruttato il fatto che una scheda sbagliata chiude la serratura. Un po’ di studio mi ha fatto trovare una soluzione in entrambi i casi. Il caso con una singola serratura è banale; ma anche quello con due lo è perché le schede o sono inserite entrambe giuste o entrambe sbagliate, e quindi basta metterle prima in un ordine e poi nell’altro per aprire la cassaforte. No, non è l’inizio di una dimostrazione per induzione, non preoccupatevi.
Nel caso di N serrature con le schede sbagliate che chiudono la loro serratura, numeriamole a 1 a N, e iniziamo a testare se per caso la combinazione corretta sia 1,2,…,N. Per fare ciò, iniziamo con la combinazione sicuramente sbagliata 2,3,…,N,1, che nella nostra ipotesi chiude tutte le serrature, e poi continuiamo con 1,2,…N. Se la cassaforte non si apre, vuol dire che la nostra ipotesi era errata, e ne proviamo un’altra. Visto che in totale ci sono N! permutazioni dei numeri da 1 a N, ci occorreranno al massimo 2N! tentativi. Uun bel numero, visto che cresce più che esponenzialmente con N; ma nel secondo caso si fa ben di peggio.
Supponiamo infatti di avere sempre N serrature, ma dove stavolta le chiavi sbagliate non fanno nulla. Anche in questo caso iniziamo a testare se la combinazione corretta è 1,2,…,N. Lo stato iniziale delle serrature sarà XXX…X, dove X può essere “aperto” o “chiuso”; ogni X, se si infila la scheda giusta, diventerà lo stato opposto Y. Nella nostra ipotesi, lo stato con tutte le serrature aperte sarà dato da una combinazione di X e Y: noi possiamo cambiare lo stato di una singola serratura, lasciando la scheda presunta corretta in quella posizione e ruotando le altre. Per esempio, 2,3,…,N−1,1,N cambia lo stato dell’ultima serratura. È possibile ottenere tutte le 2N combinazioni di X e Y in esattamente 2N passi in cui si cambia un solo simbolo per volta: cercate “Codice Gray” per ulteriori informazioni, o aspettate che io mi decida a scriverne. Finito tutto il giro, se la cassaforte non si è aperta possiamo essere certi che 1,2,…,N non è la permutazione giusta: ne abbiamo solo altre N!−1 da provare…
In questo caso l’algoritmo funziona, ma è ancora più lento, richiedendo 2N×N! passi per essere certi di aprire la cassaforte. Per dare un’idea, con 10 serrature potrebbero occorrere quasi 4 miliardi di tentativi e con 20 serrature ce ne vorrebbero circa 2,5×1024. Indubbiamente la fiamma ossidrica inizia ad avere una sua bella convenienza… Ma un matematico, oltre a non essere molto bravo con la fiamma ossidrica, non si è mai curato se un numero é grande o piccolo quando dimostra un teorema di esistenza. Il record di numero minimo lo si cercherà poi di fare in seguito.
L’esempio più famoso di grande numero usato in matematica è il numero di Skewes. Un minimo di storia: per approssimare il conteggio dei numeri primi inferiori a un numero dato, che si indica con la funzione π(n), Gauss inventò una funzione, il logaritmo integrale, che si indica con Li(n). Sembrerebbe che Li(n) sia sempre maggiore di π(n), e anzi la differenza tra i due valori cresce al crescere di n; ma nel 1914 il matematico britannico John Littlewood dimostrò che non era così, e le due funzioni continuavano a rincorrersi, passando in testa infinite volte ciascuna. Restava da capire quando avveniva il primo sorpasso, e qui entra in gioco il matematico sudafricano Samuel Skewes.
Innanzitutto Skewes suppose vera l’ipotesi di Riemann, e quindi che la distribuzione dei numeri primi fosse il meno irregolare possibile: in quel caso nel 1933 dimostrò che il sorpasso avviene prima di un numero S1, il primo numero di Skewes, pari a eee79, un numero che non saprei nemmeno come scrivere in altro modo. Non pago di questo numerone, nel 1955 riuscì a trovare un limite superiore anche nel caso non valga l’ipotesi di Riemann. Questo nuovo limite S2, il secondo numero di Skewes, è pari a 1010101000 e fa sembrare il precedente numero di Skewes un nanerottolo…
Per la cronaca, il primo sorpasso avviene molto prima di questi valori: al momento si suppone che sia intorno a 1,37×10316. Non che questo sia un numero “piccolo”, intendiamoci: l’universo contiene un numero di particelle elementari molto, molto inferiore. Insomma nella pratica il logaritmo integrale sarà sempre maggiore di π(n); ma quando mai un matematico è preoccupato dalla pratica?
Leave a comment