¿Cómo se puede probar que el cubo de Rubik volverá a su estado original si repite algún algoritmo varias veces?

Answer 1

Los movimientos en el cubo de Rubik forman un grupo llamado grupo Cubo de Rubik. Como cada elemento de grupo g en un grupo finito tiene un orden finito O (g), repetir el movimiento O (g) veces devolverá el cubo al estado original.

Si no conoce la teoría de grupos, aquí hay una explicación. Primero, tenga en cuenta que el cubo de Rubik solo puede estar en un número finito (aunque enorme) de estado. Un algoritmo es solo una secuencia fija de movimientos en el cubo. La observación importante es que, dado que cada movimiento en el algoritmo es invertible, el algoritmo en sí es invertible. Como resultado, dos estados diferentes no pueden, en la aplicación del algoritmo, dar como resultado el mismo estado.

Con estas observaciones, la prueba es simple. Comience con cualquier estado y siga aplicando el algoritmo repetidamente. Como el número de estados es finito, debe volver a algún estado anterior. La primera vez que se repite un estado ya visitado, tiene que ser el estado inicial, una consecuencia de la invertibilidad que discutimos anteriormente.

PD : Utkarsh y yo habíamos hecho un problema de concurso de programación sobre esto hace algún tiempo: cubo de Rubik

Answer 2

Permítanme formalizar los razonamientos anteriores. Mantendré toda la explicación muy simple; No hay teoría de grupo, solo intuición básica. Acordemos que por “Algoritmo” quieres decir una “secuencia fija de rotaciones aplicadas al cubo”.

Sea s un estado del cubo y ss sea el estado especial “resuelto”.
Sea A cualquier algoritmo (secuencia fija de rotaciones).
Por A (s) me refiero al nuevo estado resultante de comenzar en el estado sy aplicar el algoritmo A. Para el entero k, defina

A (0, s) = s
A (k, s) = A (A (k-1, s)) si k> 0

En otras palabras, A (k, s) es el nuevo estado resultante de comenzar en el estado sy aplicar k veces el algoritmo A. Su pregunta significa
“¿Por qué para cualquier A existe un número entero k tal que A (k, ss) = ss?”

Thm: Para cualquier A existe un número entero k tal que para cualquier s, A (k, s) = s.

Prueba:
Como lo mencionaron Raziman y Joshua , para cualquier s si considera la secuencia de estados A (0, s), A (1, s), A (2, s), A (3, s), … eventualmente debe repetirse porque el número de estados posibles es finito.

Supongamos que A (j, s) es el primer estado que se repite en la secuencia anterior, y digamos que es una repetición del estado A (i, s) con i Ahora te convenceré de que para cualquier s, tenemos A (k, s) = s.

Primero, debe estar convencido de que A (k, s ‘) = s’. Eso es porque s ‘= A (i, s) = A (j, s), por lo tanto A (k, s’) = A (k, A (i, s)) = A (k + i, s) = A (j, s) = s ‘.
Si comienza en el estado sy aplica A para las repeticiones i, llega a s ‘. Entonces, si aplica A otra ji veces, llega a A (j, s) = s ‘. Así, A (ji, s ‘) = A (k, s’) = s ‘.

Ahora te convenceré de que para cualquier estado s, tenemos A (k, s) = s. Si tiene el cubo en estado s, use etiquetas Post-It y vuelva a etiquetar el cubo para indicar s ‘(ocultando las etiquetas originales de estado s). Ahora sabe que A (k, s ‘) = s’, entonces aplique A para k repeticiones a s ‘y regrese a s’. Elimine las etiquetas Post-It y su cubo aún se encuentra en el estado s. La aplicación de A para k repeticiones no ha movido ninguna etiqueta Post-It al despegar y volver a pegar, ¿verdad? Entonces, la propiedad de A (k, s ‘) = s’ es en realidad independiente de s ‘.

Entonces, para j e i definidos como arriba y para k = ji es el caso de cualquier s, obtenemos A (k, s) = sy en particular A (k, ss) = ss. QED

Answer 3

Esta no es una prueba matemática, pero piénselo por un segundo. Digamos que tiene un algoritmo que nunca vuelve al estado original. Cada vez que lo usa, tendría que darle un estado diferente (no el estado en el que comenzó). Sin embargo, el Cubo de Rubik no tiene un número infinito de estados posibles. Esto significa que si tiene un algoritmo que le da un estado diferente cada vez que se usa, debe haber un límite superior finito en la cantidad de veces que se debe usar cualquier algoritmo para devolverlo a su estado original, es decir, El número de estados posibles de un cubo de Rubik.

Answer 4

Después de realizar un algoritmo desde un cubo resuelto, puede caracterizar el algoritmo por la permutación que realiza en los cubos del cubo. La permutación se puede dividir en una serie de ciclos, algunos ciclos entre los bordes, algunos ciclos entre las esquinas y posiblemente involucrando volteos de los bordes o giros de las esquinas.

La ejecución del algoritmo varias veces recorrerá los bordes y las esquinas a lo largo de estos ciclos. Si un ciclo tiene [math] k [/ math] cubos de longitud, luego de [math] nk [/ math] repeticiones del algoritmo se resolverán los cubies involucrados en ese ciclo.

Esto significa que si tiene un ciclo de longitud [matemática] k [/ matemática] y otro ciclo de longitud [matemática] l [/ matemática], luego de las repeticiones de [matemática] kl [/ matemática] ambos ciclos serán “resueltos “.

Dado que todos los algoritmos producen permutaciones que consisten en un número finito de ciclos de longitud finita, entonces, después del producto de todas las repeticiones del algoritmo del cubo de todas las longitudes de ciclo (o incluso solo el máximo común común de todas las longitudes de ciclo).

Answer 5

Algún algoritmo?

¿Qué pasaría si su algoritmo fuera para seleccionar un movimiento que separe tantos cuadrados de colores del mismo color como sea posible? Nunca resolverías tu cubo incluso si aplicaras el algoritmo un número ilimitado de veces.

Creo que necesitas una definición más restrictiva del algoritmo.