Cubo di Rubik Math

Nel 2010, un team internazionale di ricercatori ha dimostrato che, indipendentemente da quanto un cubo di Rubik possa essere rimescolato, non sarebbero necessarie più di 20 mosse per risolverlo. La loro prova, tuttavia, si basava sull'equivalente di 35 anni di calcolo numerico su un buon computer moderno.

Per i cubi più grandi del cubo di Rubik standard, un'adeguata ricerca delle posizioni di partenza potrebbe essere al di là della capacità di calcolo di tutti i computer del mondo. Ma a settembre, Erik Demaine (a destra), professore associato di informatica e ingegneria, ha guidato un team che includeva suo padre, il professore in visita CSAIL Martin Demaine (a sinistra), che ha dimostrato la relazione matematica tra il numero di quadrati in un cubo e la numero di mosse nella soluzione più breve al suo stato più confuso.

Il modo standard per risolvere un cubo di Rubik è trovare un quadrato fuori posizione e spostarlo al suo posto lasciando il resto del cubo il meno modificato possibile. Ciò produce una soluzione nel caso peggiore il cui numero di mosse è proporzionale a N2, dove N è il numero di quadrati per riga. Ma il team ha visto che in alcune circostanze, una singola sequenza di colpi di scena potrebbe spostare più quadrati in posizione.

Descrivere matematicamente quelle circostanze non era un compito facile. Nella prima ora, abbiamo visto che doveva essere almeno N2/log N, dice Erik Demaine. Ma poi sono trascorsi molti mesi prima che potessimo dimostrare che N2/log N era abbastanza mosse.

nascondere