Matemáticas del cubo de Rubik

En 2010, un equipo internacional de investigadores demostró que, por muy revuelto que estuviera un cubo de Rubik, no se necesitarían más de 20 movimientos para resolverlo. Su prueba, sin embargo, se basó en el equivalente a 35 años de cálculo numérico en una buena computadora moderna.

Para cubos más grandes que el cubo de Rubik estándar, el escrutinio adecuado de las posiciones iniciales puede estar más allá de la capacidad computacional de todas las computadoras del mundo. Pero en septiembre, Erik Demaine (derecha), profesor asociado de ciencias de la computación e ingeniería, dirigió un equipo que incluía a su padre, el profesor visitante de CSAIL Martin Demaine (izquierda), que demostró la relación matemática entre el número de cuadrados en un cubo y el número de movimientos en la solución más corta a su estado más revuelto.

La forma estándar de resolver un cubo de Rubik es encontrar un cuadrado que esté fuera de posición y moverlo a su lugar dejando el resto del cubo lo menos cambiado posible. Eso produce una solución en el peor de los casos cuyo número de movimientos es proporcional a N2, donde N es el número de cuadrados por fila. Pero el equipo vio que, en algunas circunstancias, una sola secuencia de giros podría mover varios cuadrados a su lugar.

Describir matemáticamente esas circunstancias no fue tarea fácil. En la primera hora, vimos que tenía que ser al menos N2 / log N, dice Erik Demaine. Pero luego pasaron muchos meses antes de que pudiéramos demostrar que N2 / log N eran movimientos suficientes.

esconder