Resolver un lío $3 \times 3 \times 3$ ¡Cubo de Rubik con un máximo de 20 movimientos!

Question

Leí en alguna parte que cualquier forma revuelta de $3 \times 3 \times 3$ El cubo de Rubik puede resolverse utilizando como máximo $20$ se mueve, y acabo de decir "¡guau! Me pregunto si podemos demostrarlo por medios matemáticos. ¿O sólo se puede resolver con ordenadores? No sé ni siquiera cómo pensar en un problema así, así que por favor dime si tienes alguna información al respecto.

[Además, leí un artículo sobre la solución de un $n \times n \times n$ cubo! fue interesante...solo como sugerencia: piensen en encontrar un método para resolver un revuelto dado $n \times n \times n$ Cubo de Rubik].

P.D. puede ver aquí para obtener información sobre el cubo de Rubik y sus movimientos.

Gracias.

Answer 1

Sí, el resultado es muy matemático, aunque se utilizaron ordenadores para muchos de los cálculos. Tomas Rokicki, Herbert Kociemba, Morley Davidson y John Dethridge demostraron este resultado en julio de 2010 y publicaron un muy bonito página web en cube20.org, con algo de historia del problema y sus métodos básicos.

El equipo estaba formado por un programador, un profesor de matemáticas, un matemático y un ingeniero. El problema tiene dos partes: encontrar un método que permita resolver cualquier cubo en M movimientos o menos, y encontrar una posición inicial realmente difícil, que tome al menos N movimientos para resolver. Estos son los límites superior e inferior para el problema - el objetivo es seguir encontrando mejores métodos para resolver cubos, o seguir encontrando posiciones de partida más difíciles, hasta que pueda mostrar M=N .

En 1981, se sabía que algunos cargos tomaban como mínimo 18 movimientos, y Morwen Thistlethwaite tenía un método para resolver cualquier cubo en 52 movimientos o menos. En el sitio web se enumeran los avances de las últimas décadas, hasta llegar al número 20. Parte del progreso se debe a que se dispone de ordenadores más potentes con los que trabajar, pero gran parte se debe a que se tiene una idea mejor (¡matemática!) para simplificar el problema.

He aquí una tabla interesante (copiada directamente de cube20.org ) que muestra cuántas posiciones iniciales requieren 20 movimientos, 19 movimientos, 18 movimientos, etc. Puedes ver que hay muchísimas posiciones de partida; y es realmente difícil encontrar una que requiera 20 movimientos para resolverse.

   Distance Count of Positions

   0        1
   1        18
   2        243
   3        3,240
   4        43,239
   5        574,908
   6        7,618,438
   7        100,803,036
   8        1,332,343,288
   9        17,596,479,795
   10       232,248,063,316
   11       3,063,288,809,012
   12       40,374,425,656,248
   13       531,653,418,284,628
   14       6,989,320,578,825,358
   15       91,365,146,187,124,313
   16       about 1,100,000,000,000,000,000
   17       about 12,000,000,000,000,000,000
   18       about 29,000,000,000,000,000,000
   19       about 1,500,000,000,000,000,000
   20       about 300,000,000

En cuanto a los cubos más grandes, ya hay muchos métodos para resolver cubos más grandes. En realidad, no es mucho más difícil que resolver el cubo de 3x3x3; solo lleva más tiempo. Pero no creo que mucha gente se dedique a encontrar el número óptimo de movimientos para cubos más grandes: será mucho más difícil (probablemente no sea posible con los ordenadores actuales) y no es tan interesante (porque a todo el mundo le interesa más el cubo de 3x3x3).