giovedì 7 luglio 2011

Il numero di Dio

Immaginate di dover raggiungere un luogo della vostra città dove non siete mai stati, assolutamente entro una certa ora. Potete aiutarvi con il navigatore, o affidarvi alla vostra conoscenza della città, o ancora chiedere indicazioni a qualche passante. In ogni caso non vi basta semplicemente arrivare, ma avete bisogno di trovare un tragitto ottimale, possibilmente il più breve possibile.
Esistono infatti moltissimi, addirittura infiniti percorsi per arrivare in un certo luogo, e uno di essi è quello che permette di giungere a destinazione nel minor tempo possibile.
Se invece di raggiungere un luogo dovete cimentarvi con un rompicapo, ad esempio il celeberrimo cubo magico di Rubik, o il gioco del quindici, di cui ho parlato in un mio precedente post, la situazione non è molto diversa. Potreste accontentarvi di risolvere “semplicemente” il gioco, cioè portare il cubo, probabilmente disordinato, nella configurazione ordinata con tutte le facce colorate di un solo colore, oppure spostare le tessere del gioco del quindici in modo che i numeri siano tutti in sequenza. Ma se siete giocatori provetti, questo non vi basta: volete trovare la via più breve, che conduce sempre alla disposizione finale ordinata nel minor numero di mosse. Se la trovaste davvero, probabilmente sareste talmente orgogliosi di voi stessi da sentirvi “come un dio”: e ne avreste ben donde! Non a caso un algoritmo, cioè un procedimento ben definito, che consenta di risolvere un rompicapo come il cubo di Rubik o il gioco del quindici con il numero minimo possibile di mosse e riducendo al minimo la quantità di memoria utilizzata viene chiamato “algoritmo di Dio”.
Se il riferimento all’essere supremo può sembrarvi esagerato, sappiate che escogitare una procedura di questo tipo, in genere, non è compito facile. La clausola sull'utilizzo della memoria è a questo proposito importante: riferendoci per esempio al cubo di Rubik, sarebbe facile, in linea di principio, pensare ad una enorme tabella precompilata in cui ad ogni configurazione possibile del cubo viene fatta corrispondere la sequenza ottimale per risolvere il rompicapo. Ma si dà il caso che il giocattolo di Rubik può assumere 43 miliardi di miliardi di possibili configurazioni: produrre e utilizzare una simile tabellona sarebbe poco maneggevole perfino per i computer più potenti.
Albert Einstein disse "Quando la soluzione è semplice, Dio sta rispondendo". Potremmo anche immaginare Dio come un risparmiatore, che predilige le vie che consentono di sprecare meno risorse possibili: non solo il tempo, ma anche lo spazio, cioè la memoria.
Un degno algoritmo di Dio per il cubo di Rubik, quindi, dovrebbe essere sempre capace di determinare la sequenza di mosse più breve per riordinare il diabolico marchingegno, senza ricorrere a giganteschi indici. La ricerca di una procedura di questo tipo è strettamente collegata ad una domanda che molti di noi, giocherellando con il famoso rompicapo, ci siamo posti: quante mosse sono necessarie per risolvere questo puzzle? Equivalentemente: qual è il numero minimo di mosse con cui possiamo certamente risolvere il cubo partendo da una configurazione qualsiasi? Sono certo che avrete già immaginato come i matematici hanno chiamato questo numero. Proprio così: il numero di Dio.
Già nel 1981, quando il cubo magico era all'apice del suo successo in tutto il mondo, il matematico Morwen Thistlethwaite dimostrò che 52 mosse sono sempre sufficienti per risolvere il cubo, partendo da qualsiasi configurazione. Questo significava che il numero di Dio non poteva essere maggiore di 52: ma probabilmente era più basso. Dal 1981 in poi, molti altri matematici cercarono di abbassare quel numero, e ci riuscirono. Nel 1990 si era già arrivati a 42, nel 1992 si scese a 37, e nel 1995 si arrivò a quota 29.
In questo stesso anno Michael Reid si cimentò nel compito opposto: trovare un limite inferiore al numero di Dio, cioè un numero di mosse sotto il quale non si può andare per configurazioni particolarmente "rognose". Reid fissò questo limite a 20.
Il numero di Dio era quindi compreso tra 20 e 29. Il limite superiore non scese per dieci anni, ma nel 2005 scoprì che 28 mosse sono sempre sufficienti. Tra il 2006 e il 2008 il gioco si fece duro, e l'asticella si abbassò per cinque volte, toccando quota 22 nell'agosto 2008.
La ricerca del numero di Dio era ormai giunta alla sua fase decisiva. La risposta definitiva arrivò esattamente un anno fa, nel luglio 2010, quando Morley Davidson, Tomas Rokicki, Herbert Kociemba e John Dethridge dimostrarono che bastano sempre 20 mosse per riordinare i colori del cubo.
Il numero di Dio è quindi 20. Ma come hanno fatto questi matematici a determinarlo? Utilizzando calcolatori potentissimi e software molto sofisticati che hanno esplorato in modo intelligente l'enorme numero di possibili configurazioni. Gli studi di Davidson e colleghi hanno determinato che su un totale di 43 miliardi di miliardi di possibili configurazioni, circa 300 milioni necessitano di esattamente 20 mosse, mentre la stragrande maggioranza delle configurazioni possono essere risolte in un numero di mosse compreso tra 15 e 19.
Per chi volesse saperne di più:
http://www.cube20.org/
http://www.bbc.co.uk/news/technology-10929159

2 commenti:

  1. Complimenti Paolo, per il contenuto interessantissimo del post e per la chiarezza espositiva. Grazie.
    Maria Intagliata

    RispondiElimina
  2. Mi permetto di segnalare questo recente risultato sul Cubo di Rubik
    http://web.mit.edu/newsoffice/2011/rubiks-cube-0629.html
    Antonio P.

    RispondiElimina

La top ten dei miei video su YouTube (1° posto)

Rullo di tamburi! Eccoci finalmente in vetta! E, devo dire, la vetta della classifica dei miei video su YouTube appare per il momento davver...