Il cubo di Rubik è da 40 anni uno dei puzzle preferiti al mondo. Sono stati escogitati diversi metodi per risolverlo, come spiegato in innumerevoli libri. Gli "speedcuber" esperti possono risolverlo in pochi secondi.

Oltre a tali imprese di sorprendente destrezza, ci sono molte affascinanti domande matematiche relative al cubo di Rubik. Una mossa del cubo consiste nel ruotare una delle sei facce di 90, 180, o 270 gradi. Un incredibile 43, 252, 003, 274, 489, 856, 000 possibili stati possono essere ottenuti applicando sequenze di mosse allo stato risolto.

Nonostante questa complessità, è stato dimostrato nel 2010 che il cubo di Rubik può sempre essere risolto in 20 mosse o meno, indipendentemente dallo stato iniziale. Questo numero è chiamato "numero di Dio, " poiché tutti i metodi di soluzione noti utilizzati dagli esseri umani in genere utilizzano un numero significativamente maggiore di mosse rispetto a questo valore ottimale.

Ma per quanto riguarda la domanda opposta:quante mosse sono necessarie per mescolare un cubo risolto? A prima vista, sembra una domanda molto più semplice del calcolo del numero di Dio. Dopotutto, a differenza della risoluzione di un cubo, rimescolarne uno non richiede alcuna abilità.

Domande simili hanno avuto risposta con successo per il mescolamento delle carte. Un famoso esempio è lo studio del 1990 sul "riffle shuffle" dei matematici Dave Bayer e Perci Diaconis. Un mazzo di carte è definito "misto" se il suo ordinamento è casuale, con ogni possibile ordine che ha la stessa probabilità di apparire. Bayer e Diaconis hanno dimostrato che sette riffle shuffle sono necessari e sufficienti per mescolare approssimativamente un mazzo standard di carte da gioco.

L'anno scorso, i matematici hanno pubblicato uno studio simile sul puzzle 15, che consiste in un quadrato 4x4 riempito con 15 tessere scorrevoli e uno spazio vuoto.

Cosa significa per un cubo essere rimescolato?

Una persona tipica che cerca di mischiare un cubo di Rubik eseguirà ripetutamente mosse casuali su di esso. La sequenza casuale di stati risultante è un caso speciale di ciò che i matematici chiamano catena di Markov. La proprietà chiave è che, dato lo stato corrente, la probabilità di quale sarà lo stato successivo non dipende da nessuno degli stati precedenti.

Applicando la teoria delle catene di Markov alla rimescolatura dei cubi, ne consegue che all'aumentare del numero di mosse casuali, la probabilità di trovarsi in uno qualsiasi dei possibili stati si avvicina sempre di più a 1/43, 252, 003, 274, 489, 856, 000. I matematici la chiamano "distribuzione di probabilità uniforme, " poiché ogni possibile stato si verifica con la stessa probabilità.

Dopo un dato numero di mosse casuali, lo stato del cubo sarà casuale, ma la sua distribuzione di probabilità non sarà esattamente uniforme; alcuni stati avranno maggiori probabilità di verificarsi rispetto ad altri.

Permettere d(t) descrivere quanto la distribuzione di probabilità dopo T mosse casuali differisce dalla distribuzione di probabilità uniforme. Come il numero di mosse casuali ( T ) aumenta, il valore di d(t) diminuirà. Il cubo che viene rimescolato corrisponde a d(t) essere piccolo.

Markov-catena Monte Carlo

Nella teoria delle catene di Markov, questa diminuzione in d(t) si chiama "miscelazione". Oltre a mescolare le carte e mescolare i puzzle, la teoria della miscelazione a catena di Markov ha anche applicazioni pratiche molto serie. Uno degli strumenti di calcolo più importanti nella scienza e nell'ingegneria moderne è il metodo Monte Carlo. Questo metodo, come il famoso casinò da cui prende il nome, si affida fondamentalmente al caso. In sostanza, tenta di risolvere approssimativamente problemi matematici difficili utilizzando più ipotesi casuali.

In pratica, Le catene di Markov sono spesso usate per produrre questi stati casuali. Per comprendere l'accuratezza di questi metodi Monte Carlo a catena di Markov, il compito chiave è stimare quanto velocemente d(t) diminuisce come T aumenta.

Il cubo tascabile

Lo studio del problema di rimescolamento per il cubo di Rubik 3x3x3 standard è attualmente un'affascinante sfida irrisolta. Però, diventa abbastanza gestibile se rivolgiamo la nostra attenzione a una versione 2x2x2 più piccola, chiamato cubo tascabile.

In questo cubo, i pezzi di bordo e centrale sono assenti e rimangono solo i pezzi d'angolo. Il cubo tascabile ha solo 3, 674, 160 possibili stati, e il suo numero di Dio è solo 11.

Nel grafico sottostante, noi complottiamo d(t) per il cubo tascabile. Dopo 11 mosse, d(t) è ancora molto grande, a 0,695. Il primo valore di T che produce a d(t) un valore inferiore a 0,25 (spesso chiamato "tempo di mescolamento" nella teoria della catena di Markov) è 19. Dopo 25 mosse d(t) è 0,092; dopo 50 mosse è 0.0012; e dopo 100 mosse è 0,00000017.

Quindi quante mosse dovresti usare per rimescolare completamente un cubo tascabile? La risposta dipende da quanto piccolo vorresti d(t) essere. Però, è certamente vero che il numero di mosse di Dio è insufficiente. Come minimo indispensabile, non si dovrebbero usare meno di 19 mosse. Maggiori dettagli, compreso il codice per calcolare d(t) , sono disponibili qui.

Ed ovviamente, una volta che hai rimescolato il tuo cubo, non resta che risolverlo di nuovo.

Questo articolo è stato ripubblicato da The Conversation con una licenza Creative Commons. Leggi l'articolo originale.