Resolución aleatoria de un cubo de Rubik.

Como puede ver al leer las respuestas a esta pregunta que involucra un giro del caballo en un tablero de ajedrez, podemos determinar el tiempo de retorno esperado para cualquier cadena de Markov irreducible al encontrar la distribución estacionaria única; si la masa de la distribución en un estado dado es$p$, entonces el tiempo de retorno esperado 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 promedio entre los retornos al estado es$\frac{1}{p}$.)

En el caso de un paseo aleatorio en un gráfico$G$, la distribución estacionaria única se obtiene haciendo que la masa en cada vértice sea proporcional a su grado. Cuando la gráfica es regular (como es el caso aquí), cada vértice tendrá la misma masa, es decir$\frac{1}{|G|}$. Entonces, el tiempo de retorno esperado para cada vértice será exactamente$|G|$.

Por tanto, 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.

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$se requieren tiros es$q^{n-1}p$, dónde$q = 1-p$. Entonces el número esperado de lanzamientos es$\sum_{n=1}^\infty nq^{n-1}p = \dfrac{p}{(1-q)^2} = \dfrac{1}{p}$. Tenga en cuenta en particular que esto es finito!

Ahora deja$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$de acuerdo con la métrica de media vuelta, y$N=26$según la métrica de cuarto de vuelta (ver 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 solucionable también es finito.

Suponga que el número de movimientos disponibles en cada turno es$m$. Tu dices eso$m=6n$, y no voy a discutir con eso; 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 hacer esto por casualidad es al menos$p=m^{-N}$.

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

El cubo de Rubik 2x2x2 consta de 8 esquinas. Todas las permutaciones de estos son posibles, ¡así que son 8! = 40320 permutaciones posibles. Cada pieza también tiene tres orientaciones posibles, separadas 120 grados (cualquiera de los 3 colores de la pieza puede mostrarse en la cara superior o inferior). El análisis detallado mostrará que si se especifican las orientaciones de 7 piezas, solo 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. Al multiplicarlos, hay 88179840 estados posibles para el cubo de Rubik de 2x2x2. Si consideramos diferentes rotaciones del cubo completo como equivalente, 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 borde, que se pueden organizar en cualquiera de las 12!=479001600 permutaciones. Cada borde también tiene 2 orientaciones posibles, y de manera similar a las esquinas, si se especifica la orientación de 11 bordes, solo es posible una orientación del borde 12 (los cubores de Rubik llaman a esto "paridad de giro"), por lo tanto, hay 2 ^ 11=2048 posibles estados de orientación. Multiplicándolos juntos, el número total de estados para los bordes es 980995276800.

Hay un tercer tipo de paridad en el cubo de Rubik llamado paridad de intercambio, lo que significa que la permutación general de las piezas debe ser par (es decir, esquinas pares y bordes pares, o esquinas impares y bordes impares). Entonces, el número total de estados es 88179840 x 980995276800/2=43252003274489856000 (Debido a que los centros de las caras ofrecen una referencia fija, no se aplica la división por 24 para rotaciones de todo el conjunto de esquinas).

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