¿Quién gana el juego del cubo de Rubik?

Question

Este juego tiene dos jugadores, Spoiler y Solver. Empezamos con un cubo de rubik 3x3x3 resuelto (para facilitar el problema).

Solver y Spoiler se turnan para hacer giros de 90 grados (empezando por Solver). El cubo tiene prohibido repetir una posición (además de la posición inicial). Esto garantiza que el juego sea finito.

Si en algún momento (además del comienzo), el cubo de rubik se encuentra en un estado resuelto, gana el Solver. Si la partida termina antes (porque se entra en una posición sin movimientos válidos), gana Spoiler.

Un ejemplo de juego sería F,F;F,F (utilizando el notación del cubo de rubik ). El solucionador gana esta partida. Si un juego pasa por cada posición que está a un movimiento del estado resuelto, y después pasa a algún estado no resuelto, Spoiler ganará (ya que ahora es imposible llegar al estado resuelto).

Entonces, ¿qué jugador tiene la estrategia ganadora?

EDIT: Puede ser más sencillo considerar el mismo problema con el 15 rompecabezas primero.

Answer 1

No es una respuesta, sino una o dos reflexiones sobre el problema. Con la métrica del cuarto de vuelta, el grafo de Cayley es un grafo 12-regular. A cada elemento del grupo de Rubik se le puede asignar un "rango", el valor del menor número de movimientos para volver al origen. Haciendo un argumento de paridad, podemos ver que un cuarto de vuelta (movimiento en el grafo de Cayley) siempre cambia este número en 1 o -1. Así que podríamos organizar el gráfico de Cayley como un diagrama de Hasse.

Creo que entender el tamaño de los distintos niveles (no estoy seguro de si ese es el término, sino la colección de elementos que tienen el mismo número mínimo de resolución) podría ser clave para entender cualquier estrategia para cualquier jugador. Por ejemplo, en el primer turno el estado del cubo está en el nivel 1. El Solucionador no puede deshacer este movimiento y se verá obligado a pasar al nivel 2. El Spoiler claramente no movería el estado de vuelta al nivel 1, así que se mueve al 3. Creo que una estrategia ingenua para el Spoiler podría ser tratar de mover el rompecabezas hacia arriba en el nivel todo el tiempo. Hay más estados de nivel 3 que de nivel 2, así que (siendo generoso con la simetría y la estructura del grafo de Cayley) sospecho que puede moverse a suficientes estados de nivel 3 cada vez que el puzzle vuelva a un estado de nivel 2 y agotar las posibilidades de nivel 2 para el Solucionador, cerrándole así el paso a la victoria.

Esto es sólo mi opinión inicial. Actualizaré si se me ocurre algo más, o si la estructura del grafo de Cayley resulta estar estructurada de tal manera que impida esta estrategia. Avísenme si alguien logra desarrollar esta idea.

EDIT: Según https://www.cube20.org/qtm/ El nivel más grande es el 21. Siendo impar, estos son estados a los que el Spoiler mueve el puzzle. Creo que si el Spoiler intenta mantener el rompecabezas en el 21, entonces podría ser capaz de agotar el nivel 20 o el 22, antes de que se agoten los estados del nivel 21.