¿Qué tan difícil es revolver el cubo de Rubik?

El cubo de Rubik ha sido uno de los rompecabezas favoritos del mundo durante 40 años. Se han ideado varios métodos diferentes para resolverlo, como se explica en innumerables libros. Los «speedcubers» expertos pueden resolverlo en cuestión de segundos.

Además de estas hazañas de destreza asombrosa, hay muchas preguntas matemáticas fascinantes relacionadas con el Cubo de Rubik. Un movimiento del cubo consiste en girar una de las seis caras 90, 180 o 270 grados. Se pueden obtener 43.252.003.274.489.856.000 estados posibles aplicando secuencias de movimientos al estado resuelto.

A pesar de esta complejidad, se demostró en 2010 que el cubo de Rubik siempre se puede resolver en 20 movimientos o menos, independientemente del estado inicial. Este número se conoce como» el número de Dios», ya que todos los métodos de solución conocidos utilizados por los seres humanos suelen utilizar significativamente más movimientos que este valor óptimo.

Cubo de Rubik en el estado resuelto. Mike Gonzalez (TheCoffee)

Pero ¿qué pasa con la pregunta opuesta: cuántos movimientos se requieren para mezclar un cubo resuelto? A primera vista, esto suena como una pregunta mucho más fácil que calcular el número de Dios. Después de todo, a diferencia de resolver un cubo, revolver uno no requiere habilidad alguna.

Preguntas similares han sido respondidas con éxito para el barajado de cartas. Un ejemplo famoso es el estudio de 1990 de la» barajadura de rifles » por los matemáticos Dave Bayer y Perci Diaconis. Una baraja de cartas se define como «mixta» si su orden es aleatorio, y cada orden posible tiene la misma probabilidad de aparecer. Bayer y Diaconis demostraron que siete barajas de rifles son necesarias y suficientes para mezclar aproximadamente una baraja estándar de naipes.

El año pasado, los matemáticos publicaron un estudio similar del rompecabezas 15, que consiste en un cuadrado de 4×4 lleno de 15 baldosas deslizantes y un espacio vacío.

¿Qué significa que un cubo esté revuelto?

Una persona típica que intenta mezclar un cubo de Rubik realizaría repetidamente movimientos aleatorios en él. La secuencia aleatoria de estados resultante es un caso especial de lo que los matemáticos llaman una cadena de Markov. La propiedad clave es que, dado el estado actual, la probabilidad de cuál será el siguiente estado no depende de ninguno de los estados anteriores.

Aplicando la teoría de las cadenas de Markov a la mezcla de cubos, se deduce que a medida que aumenta el número de movimientos aleatorios, la probabilidad de estar en cualquiera de los estados posibles se vuelve cada vez más cercana a 1/43,252,003,274,489,856,000. Los matemáticos llaman a esto una» distribución de probabilidad uniforme», ya que cada estado posible ocurre con la misma probabilidad.

Después de cualquier número dado de movimientos aleatorios, el estado del cubo será aleatorio, pero su distribución de probabilidad no será exactamente uniforme; algunos estados tendrán más probabilidades de ocurrir que otros.

Deje que d (t) describa cuánto difiere la distribución de probabilidad después de t movimientos aleatorios de la distribución de probabilidad uniforme. A medida que aumenta el número de movimientos aleatorios (t), el valor de d(t) disminuirá. El cubo que se codifica corresponde a que d(t) es pequeño.

Cadena de Markov Monte Carlo

En la teoría de las cadenas de Markov, esta disminución de d (t) se denomina «mezcla». Además de barajar cartas y mezclar rompecabezas, la teoría de la mezcla de cadenas de Markov también tiene aplicaciones prácticas muy serias. Una de las herramientas computacionales más importantes de la ciencia y la ingeniería modernas es el método de Monte Carlo. Este método, como el famoso casino que le da nombre, se basa fundamentalmente en el azar. En esencia, intenta resolver aproximadamente problemas matemáticos difíciles utilizando múltiples conjeturas aleatorias.

En la práctica, las cadenas de Markov se utilizan a menudo para producir estos estados aleatorios. Para comprender la precisión de estos métodos de Monte Carlo de cadena de Markov, la tarea clave es estimar la rapidez con la que d(t) disminuye a medida que t aumenta.

El cubo de bolsillo

Cubo de bolsillo en estado codificado. Mike Gonzalez (TheCoffee)

Estudiar el problema de codificación para el cubo de Rubik de 3x3x3 estándar es actualmente un desafío fascinante sin resolver. Sin embargo, se vuelve bastante manejable si dirigimos nuestra atención a una versión más pequeña de 2x2x2, llamada el cubo de bolsillo.

En este cubo, las piezas de borde y centro están ausentes y solo quedan las piezas de esquina. El cubo de bolsillo tiene solo 3.674.160 estados posibles, y su número de Dios es solo 11.

En el gráfico de abajo, trazamos d (t) para el cubo de bolsillo. Después de 11 movimientos, d(t) sigue siendo muy grande, en 0,695. El primer valor de t que produce un valor de d(t) por debajo de 0,25 (a menudo llamado «el tiempo de mezcla» en la teoría de la cadena de Markov) es 19. Después de 25 movimientos, d (t) es 0.092; después de 50 movimientos, es 0.0012; y después de 100 movimientos es 0.00000017.

Distancia de la distribución del cubo de bolsillo del uniforme después de los movimientos t. Eric Zhou

Entonces, ¿cuántos movimientos debe usar para mezclar completamente un cubo de bolsillo? La respuesta depende de lo pequeño que quieras que sea d (t). Sin embargo, es cierto que el número de movimientos de Dios es insuficiente. Como mínimo, uno no debe usar menos de 19 movimientos. Más detalles, incluido el código para calcular d(t), están disponibles aquí.

Y, por supuesto, una vez que hayas revuelto tu cubo, todo lo que queda por hacer es resolverlo de nuevo.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *