Thread by @pgroisma

¿Se puede resolver el cubo mágico (Rubik) al azar?

🆃🅴🅾🆁🅴🅼🅰
Sí (pero puede llevar un buen tiempo).

(1/n)

Si queremos hablar de teoremas, lo primero es meter a esta pregunta en el mundo de la matemática. Para eso tenemos que transformarla en una pregunta matemáticamente precisa y rigurosa. Hay muchas formas de hacerlo, acá vamos a elegir una, pero muchas otras son también válidas.

Antes de eso, vale la pena notar que el que cubo Rubik se presta para hacer un montón de matemática súper interesante. Está lleno de preguntas, muchas aún sin respuesta. Preguntas de las buenas, de esas que sirven para aprender un montón sobre cuestiones relevantes.

Algunas pregunta al vuelo:

1. ¿Cuántas configuraciones posibles tiene el cubo Rubik?

Antes que eso

0. ¿Cómo hacer para distinguir las diferentes configuraciones?

2. ¿Cuántos movimientos se requieren para resolver el cubo? A este número se lo llama Número de Dios y la definición precisa es el menor número N de movimientos tal que empezando desde cualquier configuración posible es posible resolver el cubo en a lo sumo N pasos.

Ese número sabemos -desde julio de 2010- que es 20, luego de haber pasado por varias cotas superiores...

... 52 en 1981, 42 en 1990, 29 en 2000, 22 en 2008 y finalmente el 20 obtenido gracias a que Google donó el equivalente a 36 años de CPU para resolver el cubo desde todas las posibles configuraciones en menos de 21 movimientos.

3. Más general que el número de Dios, ¿cuál es la distancia entre dos configuraciones cualesquiera? Entiéndase por la mínima cantidad de movimientos necesarios para pasar de una a la otra.

El Número de Dios corresponde a la distancia máxima entre la configuración "cubo resuelto" y todas las demás configuraciones. Los invito a calcular la distancia máxima posible entre dos configuraciones.

3. Más general que el número de Dios, ¿cuál es la distancia entre dos configuraciones cualesquiera? Entiéndase por la mínima cantidad de movimientos necesarios para pasar de una a la otra.

El Número de Dios corresponde a la distancia máxima entre la configuración "cubo resuelto" y todas las demás configuraciones. Los invito a calcular la distancia máxima posible entre dos configuraciones.

4. Ya sabemos que el Número de Dios es 20, pero hay muchas configuraciones iniciales que pueden resolverse en menos de 20 pasos. De hecho las que requieren de 20 son poquísimas, unas 490 millones aprox...

... que son muy pocas porque las chances que te toque una de esas si elegís al azar es de una en mil millones.

Las chances de que toque una que se resuelve en 19 pasos son más de uno en cien. Mucho más alta. ¿Qué pasa con todas las demás? ¿cuál es la chance de que te toque una que se resuelve en 2, 3, 4, 5, etc.?

5. ¿Cuántos movimientos se requieren para desordenarlo? Notar que esta pregunta no está bien definida y entonces el primer trabajo es hacerla rigurosa, asi que…

6. ¿Qué significa que el cubo esté desordenado?

7. ¿Cuál es la mejor estrategia para desordenarlo?¿existe alguna?

Además de prestarse para hablar de cuestiones muy relevantes relacionadas con el azar, el cubo se presta naturalmente para hablar de Teoría de grupos. De hecho varios de los algoritmos para resolverlo se basan en este hecho.

Por sesgo de quien escribe, acá nos vamos a concentrar en el aspecto azaroso.

La pregunta de si se puede resolver el cubo con movimientos al azar se asemeja mucho, como varios notaron por acá, a la de si un mono tipeando teclas al azar va a tipear alguna vez Hamlet.

Incluso se parece más aún a la de si revolviendo un pote de m&m, puede pasar que ocurra esto.

De hecho este video se asemeja mucho a ver un cubo al azar que se resuelve solito con movimientos al azar.

Todas están muy vinculadas a las críticas que hacía Zermelo a la Teoría cinética de los gases de Boltzmann.

Boltzmann decía que se podía explicar la termodinámica a partir de choques aleatorios entre las moléculas que componen un gas y Zermelo decía que esa teoría era absurda ya que permitía cosas como las del video de m&m, que todos sabemos que no pueden ocurrir.

Reversibilidad vs. irreversibilidad.

Borel y otros, se ocuparon de imaginar metáforas como la del mono tipeando en la máquina de escribir para dilucidar el asunto.

Probaron que como la probabilidad de que eso ocurra era ínfima pero positiva, eso iba a ocurrir infinitas veces, si disponemos de infinito tiempo.

Infinitas veces el mono tipeará Hamlet, infinitas veces veremos los m&m acomodarse espontáneamente, infinitas resolveremos el cubo mágico con movimientos al azar.

Pero la clave está en calcular el tiempo necesario para que eso ocurra por primera vez, que es de una magnitud tan grande, que millones de veces el tiempo de vida del universo no alcanzaría para que podamos verlo. Ni por casualidad. Ninguno de todos esos hechos.

En el caso del cubo Rubik, podemos hacer la cuenta de varias formas. Una es usar el Número de Dios y basarnos en ese hecho para decir que si el azar nos lleva a hacer correctamente 20 movimientos seguidos, resolveremos el cubo.

La cantidad de posibles movimientos en cada paso podemos acordar que es 12, o 18 si prefieren. Entonces la probabilidad de hacer 12 movimientos mágicos de casualidad es (1/18)^20.

Y acá voy a apelar a su buena voluntad para convencerles de que la cantidad de veces que debemos "repetir el experimento" para observar un éxito es, en promedio, 18^20.

Pero también podemos hacer una cuenta mucho más precisa que además no requiere del Número de Dios. Consiste en pensar el proceso de intentar resolver el cubo a la buena de Dios como un paseo al azar.

Como el del borracho que apareció en los comentarios de la encuesta, pero acá es un paseo al azar por las distintas configuraciones.

En lugar de ser un paseo al azar en la recta, en el plano o el espacio es un paseo al azar por las distintas configuraciones del cubo.
Un paseo al azar en un grupo. Un paseo al azar en el grupo de permutaciones de los números 1, 2, … 48. Un paseo al azar en un grafo.

El grafo podemos construirlo poniendo un nodo por cada configuración y una arista entre dos nodos si podemos pasar de una configuración a la otra en un paso.

Los paseos al azar en grafos (y en grupos) son objetos muy estudiados y en nuestro caso, afortunadamente, la situación es bastante simple porque todos los nodos tienen la misma cantidad de vecinos.

Cuando eso pasa, la distribución de equilibrio del paseo al azar, es decir, las chances de encontrarlo en los diferentes nodos después de mucho tiempo de estar caminando, es uniforme. Todos los nodos tienen la misma probabilidad.

Como la cantidad de configuraciones posibles es

8!x3^7x12!/2x2^11 = 43.252.003.274.489.856.000

cada configuración tiene probabilidad igual a 1 dividido ese número. En particular la configuración "cubo resuelto".

Y ahora apelo nuevamente a su buena voluntad para que me crean la fórmula de Kac, que dice que el tiempo medio que debemos esperar para llegar a esa configuración (en equilibrio) es 1 dividido esa probabilidad, es decir,

43x10^18

Bastante mejor que la estimación anterior ¡y sin usar el Número de Dios! El dato de color es que la edad del universo en segundos es aproximadamente

43x10^16.

Así que si alguien comenzó a intentarlo junto con el Big Bang, todavía no tuvo tiempo de lograrlo, pero no le falta mucho (en promedio), tan solo 100 veces más la edad del universo (😉).

Si llegaste hasta acá, sos más valiente que quienes intentan resolver el cubo con movimientos al azar.

#TeRegaloUnTeorema

@sebacampanario

@julielffman no te preocupes que a este lo considero nivel de avanzado para arriba. Además de largo.

Acá deberia decir 20 movimientos mágicos en lugar de 12.