Número de movimientos necesarios para resolver el cubo de Rubik por pura casualidad

Question

Número de movimientos necesarios para resolver el cubo de Rubik por pura casualidad

expectativa
Matemáticas
probabilidad
Cubo de rubik

Pedro

Supongamos que se realizan movimientos aleatorios para resolver el cubo de Rubik. Un movimiento consiste en un $90$ -grado-rotación de algún lado. La posición inicial también es aleatoria.

Qué es $E(X)$ , dónde $X$ Cuál es el número de movimientos hasta que se resuelve el cubo?
Cuantas movidas se deben hacer, para que la probabilidad de que se resuelva el cubo, exceda $99$ %?

marca bennet

Supongo que te refieres a la probabilidad de que el cubo se haya resuelto antes de mover

n + 1

$n+1$ para la segunda pregunta. ¡Espero que obtengas una respuesta interesante!

Hagen von Eitzen

¿No sería la respuesta a la primera simplemente: el orden del grupo?

Teófilo

@HagenvonEitzen Dado que los movimientos están restringidos a un conjunto de generadores, ¿eso no hace la diferencia? Me parece que la respuesta sería el orden del grupo solo si pudieras hacer un movimiento arbitrariamente complejo cada vez (es decir, uno que fuera una combinación de varios

90^{\circ}

$90^\circ$ rotaciones).

Pedro

@mark sí, "la probabilidad de que el cubo se resuelva en algún momento, si

n

$n$ se hacen movimientos" es lo que quise decir.

Hagen von Eitzen

@ Théophile Tienes razón. hice el calculo con

S_{3}

$S_3$ y generadores

(1 2), (2 3)

$(1\,2),(2\,3)$ :

E (X) = 5.8 \bar{3}

$E(X)=5.8\overline 3$ en lugar de

6

$6$ . Con

S_{4}

$S_4$ y generadores

(1 2), (1 2 3 4)

$(1\,2),(1\,2\,3\,4)$ :

E (X) \approx 28.82

$E(X)\approx 28.82$ en lugar de

24

$24$ ; con un tercer generador

(4 3 2 1)

$(4\,3\,2\,1)$ :

E (X) \approx 32.09

$E(X)\approx 32.09$ . Podemos esperar

E (X)

$E(X)$ volverse más grande que

| G |

$|G|$ , mientras más relaciones haya entre los generadores, supongo

Enrique

@HagenvonEitzen: Quizás un ejemplo más fácil del problema podría ser una caminata aleatoria en

n

$n$ puntos en la circunferencia de un círculo (

Z_{n}

$\mathbb{Z}_n$ si lo desea) donde parece estar el número esperado de pasos

\frac{n^{2} - 1}{6}

$\frac{n^2-1}{6}$ .

Ed Pegg

En 1999, David Singmaster estaba en un programa de televisión y luego le entregaron un cubo de Rubik. Escribió el primer libro de soluciones, pero no era un solucionador experimentado. Entonces solo trató de resolver una cara, con la intención de explicar los pasos después de eso. Cuando terminó la cara, se dio cuenta de que solo necesitaba un cuarto de vuelta para terminar la solución, así que lo hizo y simplemente dejó el cubo.

cínico borracho

Esta pregunta parece estar reflejada en mathoverflow: mathoverflow.net/questions/115178/…

COMO

Heurística de agrupamiento de Poisson:

X \overset{d}{\approx} Exp (\frac{π_{s}}{mi C})

$X\overset{d}≈\exp\left(\frac {\pi_s} {EC}\right)$ dónde

π_{s} = P (X_{t} = s) = \frac{1}{N}

$\pi_s=P(X_t=s)=\frac 1 N$ y

E C

$EC$ se espera la hora local de estancia a las

s

$s$ para

X_{0} = s

$X_0=s$ . Hay

m = 6 \times 2

$m=6\times 2$ movimientos y las únicas relaciones de "rango cercano" son

X^{4} = 1

$X^4=1$ , y

X Y = Y X

$XY=YX$ dónde

X

$X$ y

Y

$Y$ son movimientos en las caras opuestas. Aparte de estas "cancelaciones", hay que retroceder los pasos para volver a

s

$s$ (

X X^{- 1} = 1

$XX^{-1}=1$ ). Explícitamente, solo obtuve

P (τ_{s} = 2) = p

$P(\tau_s=2)=p$ ,

P (τ_{s} = 4) = 14 p^{3}

$P(\tau_s=4)=14p^3$ para

p = m^{- 1}

$p=m^{-1}$ por lo que podemos aproximarnos muy crudamente

E C ≳ \frac{1}{1 - p - 14 p^{3}}

$EC\gtrsim\frac 1{1-p-14p^3}$

COMO

@Hagen Sí, cuanto más simples sean las relaciones entre los movimientos, más "pegajosa" será la caminata localmente y más grande

E C

$EC$ (y por lo tanto

E (X)

$E(X)$ ) es. Pero

E (X) \geq \frac{| G | - 1}{2}

$E(X)\ge \frac {|G|-1}{2}$ para cualquier

| G |

$|G|$ y

E (X) > | G | - 2

$E(X) > |G|-2$ para cualquier cadena de Markov reversible independientemente de las relaciones entre movimientos (

X = 0

$X=0$ posible).

Respuestas (3)

Número de movimientos necesarios para resolver el cubo de Rubik por pura casualidad

Supongo que te refieres a la probabilidad de que el cubo se haya resuelto antes de mover $n+1$ para la segunda pregunta. ¡Espero que obtengas una respuesta interesante!
¿No sería la respuesta a la primera simplemente: el orden del grupo?
@HagenvonEitzen Dado que los movimientos están restringidos a un conjunto de generadores, ¿eso no hace la diferencia? Me parece que la respuesta sería el orden del grupo solo si pudieras hacer un movimiento arbitrariamente complejo cada vez (es decir, uno que fuera una combinación de varios $90^\circ$ rotaciones).
@mark sí, "la probabilidad de que el cubo se resuelva en algún momento, si $n$ se hacen movimientos" es lo que quise decir.
@ Théophile Tienes razón. hice el calculo con $S_3$ y generadores $(1\,2),(2\,3)$ : $E(X)=5.8\overline 3$ en lugar de $6$ . Con $S_4$ y generadores $(1\,2),(1\,2\,3\,4)$ : $E(X)\approx 28.82$ en lugar de $24$ ; con un tercer generador $(4\,3\,2\,1)$ : $E(X)\approx 32.09$ . Podemos esperar $E(X)$ volverse más grande que $|G|$ , mientras más relaciones haya entre los generadores, supongo
@HagenvonEitzen: Quizás un ejemplo más fácil del problema podría ser una caminata aleatoria en $n$ puntos en la circunferencia de un círculo ( $\mathbb{Z}_n$ si lo desea) donde parece estar el número esperado de pasos $\frac{n^2-1}{6}$ .
En 1999, David Singmaster estaba en un programa de televisión y luego le entregaron un cubo de Rubik. Escribió el primer libro de soluciones, pero no era un solucionador experimentado. Entonces solo trató de resolver una cara, con la intención de explicar los pasos después de eso. Cuando terminó la cara, se dio cuenta de que solo necesitaba un cuarto de vuelta para terminar la solución, así que lo hizo y simplemente dejó el cubo.
Esta pregunta parece estar reflejada en mathoverflow: mathoverflow.net/questions/115178/…
Heurística de agrupamiento de Poisson: $X \overset{d}{\approx} Exp (\frac{π_{s}}{mi C})$ $X\overset{d}≈\exp\left(\frac {\pi_s} {EC}\right)$ dónde $\pi_s=P(X_t=s)=\frac 1 N$ y $EC$ se espera la hora local de estancia a las $s$ para $X_0=s$ . Hay $m=6\times 2$ movimientos y las únicas relaciones de "rango cercano" son $X^4=1$ , y $XY=YX$ dónde $X$ y $Y$ son movimientos en las caras opuestas. Aparte de estas "cancelaciones", hay que retroceder los pasos para volver a $s$ ( $XX^{-1}=1$ ). Explícitamente, solo obtuve $P(\tau_s=2)=p$ , $P(\tau_s=4)=14p^3$ para $p=m^{-1}$ por lo que podemos aproximarnos muy crudamente $EC\gtrsim\frac 1{1-p-14p^3}$
@Hagen Sí, cuanto más simples sean las relaciones entre los movimientos, más "pegajosa" será la caminata localmente y más grande $EC$ (y por lo tanto $E(X)$ ) es. Pero $E(X)\ge \frac {|G|-1}{2}$ para cualquier $|G|$ y $E(X) > |G|-2$ para cualquier cadena de Markov reversible independientemente de las relaciones entre movimientos ( $X=0$ posible).

el mismo río dos veces · Answer 1

Cada arista tiene 2 caras, proporcionando $12!\times 2^{12}$ posibilidades.

Cada vértice tiene 3 caras, proporcionando $8!\times 3^8$ posibilidades.

Por lo tanto, si desmontas el cubo, se puede volver a montar en 519 024 039 293 878 272 000 estados posibles.

Gracias a Gerry Myerson por esto: De acuerdo con las Notas de Singmaster sobre el cubo mágico de Rubik, la permutación total de los cubos de aristas y vértices debe ser uniforme. Luego, si orientas todos los bordes excepto uno, el restante es forzado, y de manera similar para los vértices, por lo que solo 1 de cada 12 ensamblajes posibles del cubo es en realidad un estado "soluble" o "al que se puede llegar por rotación".

Por lo tanto, dividir el número anterior por 12 confirma el resultado de Turner y Gold (que no he visto de primera mano) de que el número de estados "al que se puede llegar por rotación" es $43,252,003,274,489,856,000$ .

Por lo tanto, cualquier movimiento aleatorio dado tiene probabilidad $1/43,252,003,274,489,856,000$ de completar el cubo.

Por tan alto $n$ la binomial se aproximará a la distribución normal, por lo que el número esperado de movimientos será la media.

Creo que Wolfram Alpha tuvo problemas con el procesamiento de números en mi última respuesta, así que lo resolví por sustitución:

$0.5=\binom{n}{0}p^0q^n$ dónde $q=(1-1/43,252,003,274,489,856,000)$

$0.5=(1-1/43,252,003,274,489,856,000)^n$

$n\approx 3×10^{19}$ movimientos es el número esperado de movimientos para resolverlo.

Repitiendo la sustitución de 0.01:

$n\approx 1.992*10^{20}$ movimientos es el número esperado de movimientos para alcanzar el 99% de confianza.

El uso del binomio en esta respuesta hace la suposición técnicamente incorrecta de que la probabilidad de resolver en cualquier movimiento en particular no está relacionada con la probabilidad de resolver en un movimiento n pasos antes. (es decir, no hay correlación serial). Sin embargo, como usuario experimentado de cubos, sé que el cubo diverge muy rápidamente de su posición actual debido a movimientos aleatorios y, por lo tanto, el efecto de la correlación serial será muy bajo.

Esta divergencia se ilustra claramente por el hecho de que se desprende del resultado de 2010 de Rokicki, Kociemba, Davidson y Dethridge que se necesitan como máximo 20 movimientos de Singmaster para llevar el cubo a cualquier estado obtenible que desee. Compare esos 20 movimientos con el número esperado de movimientos aleatorios para resolver el cubo y obtendrá una idea de cuán mínima será la correlación serial.

Siéntete libre de corregir el $3\times 10^{19}$ número a $2.16\times 10^{19}$ si sabes que esto es cierto. Tuve algunos problemas con el procesamiento de números, parece probable que el número medio de movimientos sea exactamente la mitad de la inversa de la probabilidad de resolver cualquier movimiento aleatorio, pero olvidé mis reglas de distribución binomial (¡son 25 años!)

tímidopueo · Answer 2

La respuesta a su primera pregunta es un poco más que la cantidad de configuraciones de cubo posibles (quizás un 25% más). Dado que un cubo de 3x3x3 tiene aproximadamente 43 quintillones de configuraciones, estimaría que se necesitarían alrededor de 54 quintillones de movimientos aleatorios para llegar a un estado resuelto esperado.

Para explicar cómo llegué aquí, considere la pregunta "si elegí una posición al azar, ¿cuál es el número esperado de selecciones hasta que obtenga el estado resuelto?" Es lo mismo que lanzar un dado (muy, muy) grande numerado 1 al número de configuraciones de cubo. Y luego contar cuántos lanzamientos se necesitarían para sacar un 1. La respuesta a esta pregunta es, en expectativa, se necesitaría la cantidad de configuraciones de cubo (alrededor de 43 quintillones).

Su primera pregunta es similar a mi pregunta, excepto que en lugar de saltar a posiciones aleatorias, solo puede ir un turno a la vez. Lo que significa que es relativamente probable que pases a una nueva posición y luego, al azar, retrocedas a esa posición original. Esto hace que el proceso de su pregunta sea "menos aleatorio" que mi pregunta. Esto significa que la respuesta a su pregunta será mayor que el número de configuraciones de cubo.

La buena noticia es que todavía es bastante aleatorio. Lo que quiero decir con eso es que si tomas un cubo y haces (digamos) 100 movimientos al azar, terminarás en una posición lo suficientemente aleatoria. No tengo una definición formal de "suficiente" o por qué eso es cierto... Me estoy saliendo de mi intuición como aficionado a la resolución de cubos, y también del hecho de que el Número de Dios es 20. Esto significa que la respuesta a su pregunta no será MUCHO mayor que la cantidad de configuraciones de cubo (personalmente estimo alrededor de un 25% mayor).

Creo que la respuesta exacta a su pregunta es difícil de obtener. ¡Aquí hay un video de Mathologer que hace exactamente su pregunta, pero no la responde! (En el video, él estima el valor de un cubo de 2x2x2. Esto es en lo que basé mi estimación del 25 %). En el video, llama a la respuesta que buscas el Número Mono del cubo de Rubik. Sin embargo, la pregunta que SÍ responde es "¿cuál es el número esperado de movimientos para llegar a un estado resuelto, si comienza desde un estado resuelto?" Aquí, da una prueba bastante ingeniosa, y la respuesta resulta ser exactamente el número de configuraciones del cubo.

el mismo río dos veces · Answer 3

Los cuadrados centrales de cada cara en realidad no se mueven independientemente uno del otro, giran, pero dado que cada orientación de ese cuadrado es indistinguible de los otros tres, hay $4^6= 32,768$ soluciones terminadas aceptables para el cubo, no solo 1, considerando solo las permutaciones de las piezas entre sí, lo que quizás no sea obvio para todos.

Una vez resuelto, también se puede sostener con una selección de 6 caras mirando hacia el suelo y cada una de ellas se puede rotar en 4 posiciones únicas, haciendo, dependiendo de cómo permutes tus posibilidades, 786,432 posibles soluciones "correctas".

Para eliminar esto, si fijamos los ejes y las caras centrales, que de todos modos se rige por la fabricación del cubo, mantenemos una cara en el suelo, no rotamos ningún cuadrado central y no movemos ninguno de los ejes, nos quedan 12 "cubos de aristas" y 8 "cubos de vértices".

Cada arista tiene 2 caras, proporcionando $12!\times 2^{12}$ posibilidades.

Cada vértice tiene 3 caras, proporcionando $8!\times 3^8$ posibilidades.

Por lo tanto, ignorando los cuadrados centrales y las orientaciones idénticos para todos los efectos del cubo, el cubo tiene 519,024,039,293,878,272,000 estados posibles.

La probabilidad de resolverlo en cualquier movimiento aleatorio dado es, por lo tanto, de 1 en 519 billones de billones.

Alcanzar una probabilidad de $99\%$ es por lo tanto una simple probabilidad binomial... y es posible que tengas que corregir este bit ya que hace 25 años que no hice matemáticas:

Nuestro resultado deseado se considera más simplemente como la probabilidad de "no tener ningún éxito", es decir $1-P(x=0)$

$0.99=1-\binom{n}{0}p^0q^n$ dónde $q=(1-1/519024039293878272000)$

$0.01=(1-1/519024039293878272000)^n$

$n=6.4812×10^{14}$ movimientos, que Wolfram Alpha me ha informado de forma fiable que son 32 movimientos por glóbulo rojo en su cuerpo.

Debo agregar a esta respuesta que, por supuesto, es fatalmente defectuosa porque no tiene en cuenta el hecho de que las posiciones del cubo están correlacionadas en serie y, por lo tanto, si uno comienza en una posición que está "más distante" de completo, es es más probable que uno pase repetidamente por esas permutaciones distantes que moverse a través de permutaciones que tienen una probabilidad promedio de éxito.

Esto tiene el efecto de hacer que las soluciones "rápidas" sean más rápidas en promedio y las soluciones "lentas" más lentas que el estimador binomial y, por lo tanto, el intervalo de confianza del 99%, al ser un intervalo distante, generalmente tomará un poco más de tiempo que el estimador binomial. $6.4812\times 10^{14}$ movimientos estimados. Sin embargo, si necesita una respuesta precisa que tenga en cuenta eso, ¡sospecho que esperará mucho tiempo!

Esta aproximación a una distribución normal para grandes $n$ , el número estimado de movimientos necesarios para resolverlo será aproximadamente la mitad del intervalo del 99%, digamos $3.2\times 10^{14}$ se mueve

Lo siento, me acabo de dar cuenta de que también pediste E (X), que supongo que es un estimador imparcial de la cantidad de movimientos que tomará. Dame la oportunidad de buscar el estimador imparcial del binomio y lo agregaré a mi respuesta.
Con tan bajo $p$ y un alto $n$ , esto se aproximará a una distribución normal muy amplia y baja.
Ok, he puesto un estimador rápido para la cantidad de movimientos a resolver. Los números para el binomio parecen demasiado pequeños, pero eso es lo que Wolfram Alpha me está dando. Por favor, siéntase libre de editar y corregir.
Muy interesante para este problema (¡y afortunadamente para un matemático básico como yo!), cada movimiento posible del cubo implica rotar 4 cubos de vértices y 4 cubos de aristas en relación con los 16 cubos móviles restantes y, como tal, el movimiento de cada cuadrado es igualmente probable. independientemente de su tipo y como tal, el método binomial es igualmente fuerte que los (hermosamente elegantes) pero innecesariamente complejos métodos basados en grupos de rotación.
En realidad, una reflexión final... Hay un posible error en mi respuesta, ya que supone que no hay una disposición de las partes del cubo que solo se pueda lograr desmontando y volviendo a montar, una posibilidad que el método del grupo de rotación no permitirá. sufrir de.

Número de movimientos necesarios para resolver el cubo de Rubik por pura casualidad

Pedro

marca bennet

Hagen von Eitzen

Teófilo

Pedro

Hagen von Eitzen

Enrique

Ed Pegg

cínico borracho

COMO

COMO

Respuestas (3)

el mismo río dos veces

el mismo río dos veces

tímidopueo

el mismo río dos veces

el mismo río dos veces

el mismo río dos veces

el mismo río dos veces

el mismo río dos veces

el mismo río dos veces

Resolución aleatoria de un cubo de Rubik.

Intercambiar la tercera carta más grande entre 222 manos de cartas

Tiempo de espera previsto para el próximo tren

En promedio, ¿dónde está el ascensor?

Pago esperado de una tirada de dados con retiradas

Maximiza el resultado en tiradas de dados repetidas

¿Por qué los límites de esta integral no consideran ambas igualdades?

¿Cuál es la probabilidad de que esté vivo dentro de un mes?

¿Cuál es la probabilidad de que una caminata aleatoria que comienza en 0 llegue a +2 en 2 pasos, 3 pasos, 4 pasos, etc.? [duplicar]

¿Por qué cambia la probabilidad de un evento en un experimento binomial con el cambio proporcional de éxitos y fracasos?