Quanto è difficile rimescolare il Cubo di Rubik?

Cubo di Rubik è stato uno dei puzzle preferiti del mondo per 40 anni. Diversi metodi sono stati ideati per risolverlo, come spiegato in innumerevoli libri. Esperti “speedcubers” possono risolverlo in pochi secondi.

Oltre a tali imprese di incredibile 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. Uno sconcertante 43.252.003.274.489.856.000 stati possibili 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 è indicato come “numero di Dio”, come tutti i metodi di soluzione noti utilizzati dagli esseri umani in genere utilizzano significativamente più mosse di questo valore ottimale.

Cubo di Rubik nello stato risolto. Mike Gonzalez (TheCoffee)

Ma per quanto riguarda la domanda opposta: quante mosse sono necessarie per rimescolare un cubo risolto? A prima vista, questo suona come una domanda molto più facile che calcolare il numero di Dio. Dopo tutto, a differenza di risolvere un cubo, rimescolando uno prende alcuna abilità di sorta.

Domande simili sono state risolte con successo per il rimescolamento delle carte. Un esempio famoso è lo studio del 1990 del “riffle shuffle” dei matematici Dave Bayer e Perci Diaconis. Un mazzo di carte è definito “misto” se il suo ordine è 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 del puzzle 15, che consiste in un quadrato 4×4 riempito con tessere scorrevoli 15 e uno spazio vuoto.

Che cosa significa per un cubo da strapazzate?

Una tipica persona che cerca di rimescolare un cubo di Rubik eseguirebbe ripetutamente mosse casuali su di esso. La sequenza casuale risultante di stati è un caso speciale di ciò che i matematici chiamano una catena di Markov. La proprietà key è 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 allo scrambling del cubo, ne consegue che all’aumentare del numero di mosse casuali, la probabilità di trovarsi in uno dei possibili stati diventa sempre più vicina 1/43,252,003,274,489,856,000. I matematici chiamano questa una “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 saranno più probabili di altri.

Sia d(t) descrivere quanto la distribuzione di probabilità dopo t mosse casuali differisce dalla distribuzione di probabilità uniforme. All’aumentare del numero di mosse casuali (t), il valore di d(t) diminuirà. Il cubo che viene criptato corrisponde a d (t) che è piccolo.

Markov-chain Monte Carlo

Nella teoria delle catene di Markov, questa diminuzione di d(t) è chiamata “miscelazione”. Oltre al rimescolamento delle carte e al rimescolamento dei puzzle, la teoria della miscelazione della catena di Markov ha anche applicazioni pratiche molto serie. Uno degli strumenti computazionali più importanti nella scienza moderna e nell’ingegneria è il metodo Monte Carlo. Questo metodo, come il famoso casinò da cui prende il nome, si basa fondamentalmente sulla possibilità. In sostanza, tenta di risolvere approssimativamente problemi matematici difficili usando più ipotesi casuali.

In pratica, le catene di Markov sono spesso utilizzate 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 all’aumentare di T.

Il cubo tascabile

Cubo tascabile in stato criptato. Mike Gonzalez (TheCoffee)

Studiare il problema di scrambling per il cubo di Rubik 3x3x3 standard è attualmente un’affascinante sfida irrisolta. Tuttavia, diventa abbastanza gestibile se rivolgiamo la nostra attenzione a una versione 2x2x2 più piccola, chiamata pocket cube.

In questo cubo, i pezzi di bordo e centro sono assenti e rimangono solo i pezzi d’angolo. Il cubo tascabile ha solo 3.674.160 stati possibili e il numero del suo Dio è solo 11.

Nel grafico sottostante, tracciamo d(t) per il cubo tascabile. Dopo 11 mosse, d (t) è ancora molto grande, a 0,695. Il primo valore di t che produce un valore d (t) inferiore a 0,25 (spesso chiamato “il tempo di miscelazione” 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.

Distanza della distribuzione del cubo tascabile dall’uniforme dopo t mosse. Eric Zhou

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

E, naturalmente, una volta che hai strapazzato il cubo, tutto ciò che resta da fare è risolverlo di nuovo.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *