Resolución aleatoria de un cubo de Rubik .

Question

Después de jugar un poco con un cubo de Rubik se me ocurrió el siguiente problema :

Supongamos que empezamos con un cubo de Rubik resuelto (uno general, con $n^3$ cubos) . A continuación, elegimos una de las jugadas, cada una de las cuales tiene una probabilidad de $\frac{1}{6n}$ de ser elegido , y aplicarlo en nuestro cubo . Seguimos haciéndolo ( eligiendo un nuevo movimiento al azar y aplicándolo y así sucesivamente...) , hasta llegar de nuevo a la posición resuelta . ¿Cuál es el número esperado de movimientos necesarios para resolver el cubo de esta manera?

Lo he pensado y creo que la respuesta debería ser $\infty$ (al menos para $n \geq 3$ ) porque hay un montón de secuencias aleatorias de movimientos que tardarán mucho tiempo en resolver el cubo, pero no tengo una forma rigurosa de demostrarlo.

Para $n=2$ No estoy tan seguro de si la respuesta debe ser finita o infinita (pero sigo pensando que es infinita).

Gracias por su tiempo para ayudarme.

Answer 1

Como puede ver al leer las respuestas a esta pregunta que implica un recorrido de caballos en un tablero de ajedrez, podemos determinar el tiempo de retorno esperado para cualquier cadena de Markov irreducible encontrando la única distribución estacionaria; si la masa de la distribución en un estado dado es $p$ entonces el tiempo esperado de retorno a ese estado es $\frac{1}{p}$ . (Intuitivamente, si procesamos la cadena de Markov durante mucho tiempo, esperamos estar en el estado dado con probabilidad $p$ por lo que la distancia media entre los retornos al estado es $\frac{1}{p}$ .)

En el caso de un paseo aleatorio sobre un grafo $G$ la distribución estacionaria única viene dada por hacer la masa en cada vértice proporcional a su grado. Cuando el gráfico es regular (como es el caso), cada vértice tendrá la misma masa, es decir $\frac{1}{|G|}$ . Así, el tiempo de retorno esperado para cada vértice será exactamente $|G|$ .

Así, el número esperado de vueltas necesarias para volver al estado inicial de cualquier tipo de cubo de Rubik es igual al número de posiciones del cubo.

Answer 2

Considere un escenario más simple: suponga que tiene una moneda sesgada, que muestra Cara con probabilidad $p > 0$ . ¿Cuál es el número esperado de intentos necesarios para lanzar una cabeza? La probabilidad de que exactamente $n$ los lanzamientos son necesarios es $q^{n-1}p$ , donde $q = 1-p$ . Así que el número esperado de lanzamientos es $\sum_{n=1}^\infty nq^{n-1}p = \dfrac{p}{(1-q)^2} = \dfrac{1}{p}$ . Obsérvese, en particular, que es finito.

Ahora, dejemos que $N$ sea el número máximo de movimientos necesarios para resolver un $n \times n \times n$ Cubo de Rubik. Gracias a los esfuerzos de innumerables investigadores dedicados, sabemos que para $n=3$ tenemos $N=20$ según la métrica de media vuelta, y $N=26$ según la métrica del cuarto de vuelta (véase por ejemplo este enlace ). Pero el valor exacto de $N$ no importa; el número de posiciones es finito, y por lo tanto el número máximo de movimientos necesarios para resolver una posición resoluble también es finito.

Supongamos que el número de movimientos disponibles en cada turno es $m$ . Usted dice que $m=6n$ y no voy a discutirlo; de nuevo, lo importante es que $m$ es finito. Entonces todo lo que tienes que hacer para resolver una posición en $N$ movimientos o menos es elegir el movimiento óptimo cada vez. La probabilidad de hacerlo por azar es de al menos $p=m^{-N}$ .

Así que si consideras que un "lanzamiento de moneda" es $N$ movimientos aleatorios en su cubo de Rubik, entonces el número esperado de lanzamientos de monedas es como máximo $\dfrac{1}{p} = m^N$ . Así que el número esperado de movimientos es como máximo $\dfrac{N}{p} = Nm^N$ .

Answer 3

El cubo de Rubik 2x2x2 consta de 8 piezas de esquina. Todas las permutaciones de éstas son posibles, por lo que son 8! = 40320 permutaciones posibles. Además, cada pieza tiene tres orientaciones posibles, separadas 120 grados (cualquiera de los 3 colores de la pieza puede aparecer en la cara superior o inferior). Un análisis detallado mostrará que si se especifican las orientaciones de 7 piezas, sólo hay una orientación posible para la última pieza (los cubos de Rubik llaman a esto "paridad de giro"), por lo que hay 3^7=2187 estados de orientación posibles. Multiplicando todo esto, hay 88179840 estados posibles para el cubo de Rubik 2x2x2. Si consideramos que las diferentes rotaciones del cubo entero son equivalentes, debemos dividir esto por 24, dando 3674160 estados posibles.

El cubo de Rubik 3x3x3 tiene, además de lo anterior, una pieza central y 6 centros de caras que no se mueven. También tiene 12 piezas de arista, que pueden disponerse en cualquiera de las 12!=479001600 permutaciones. Cada arista también tiene 2 orientaciones posibles, y de forma similar a las esquinas, si se especifica la orientación de 11 aristas sólo es posible una orientación de la 12ª arista (los cubos de Rubik llaman a esto "paridad de volteo"), por lo que hay 2^11=2048 estados de orientación posibles. Multiplicando todo esto, el número total de estados para las aristas es de 980995276800.

Existe un tercer tipo de paridad en el cubo de rubik llamado paridad de intercambio, que significa que la permutación global de las piezas debe ser par (es decir, esquinas pares y aristas pares, o esquinas impar y aristas impar.) Así que el número global de estados es 88179840 x 980995276800/2=43252003274489856000 (Como los centros de las caras ofrecen una referencia fija, no se aplica la división por 24 para las rotaciones de todo el conjunto de esquinas).

Es un número grande, pero ciertamente no infinito. Para el análisis de cómo calcular la probabilidad, ver las otras respuestas a esta pregunta.