17 votos

El número de Dios para el $n \times n \times n$ -cubo

Esta es una pregunta sobre Cubo de Rubik y las generalizaciones de este rompecabezas, como La venganza de Rubik , El cubo del profesor o en general el $n \times n \times n$ cubo.

Dejemos que $g(n)$ sea el número más pequeño $m$ de tal manera que toda disposición realizable de los $n \times n \times n$ cubo se puede resolver con $m$ se mueve. En otras palabras, este es el "radio" del gráfico de Cayley del $n \times n \times n$ grupo cúbico con respecto al sistema generador canónico.

Tenemos $g(1)=0$ , $g(2)=11$ y - muy recientemente - en 2010 se demostró que $g(3)=20$ : El número de Dios es el 20 .

Pregunta. ¿Se sabe algo sobre $g(4)$ o $g(5)$ ?

Supongo que el número exacto no se conoce, ya que el cálculo del cubo de Rubik ya llevó tres décadas. Sin embargo, ¿hay algún trabajo en curso? ¿Se conoce algún límite inferior o superior?

Me gustaría hacer la misma pregunta sobre $g(n)$ para $n>5$ o mejor dicho:

Pregunta. ¿Se sabe algo sobre el valor asintótico de $g(n)$ ?

16voto

Jon Galloway Puntos 320

No soy un experto, pero recuerdo haber visto este comunicado de prensa del MIT no hace mucho tiempo. El artículo arXiv correspondiente debería responder a su segunda pregunta.

8voto

Owen Puntos 2951

Basado en esta discusión de 2015, el número de Dios para el cubo de 4x4x4 se encuentra entre 35 y 55 (inclusive) para la métrica de giro del bloque exterior, siendo los límites correspondientes 32 y 53 para la métrica de giro de una sola rebanada, y 29 y 53 para la métrica de giro del bloque. Desplázate hasta los comentarios para ver los límites óptimos.

La elección de la métrica es irrelevante para los resultados asintóticos de Demaine, Demaine, Eisenstat, Lubiw y Winslow que da $\Theta(n^2/\log(n))$ como respuesta a la segunda pregunta.

Desde que se hizo esta pregunta por primera vez, cube20.org afirma haber demostrado también que el número de Dios para la métrica del cuarto de vuelta es el 26.

En cuanto al 5x5x5, se puede encontrar este puesto reclamando un límite superior de 130 para la métrica de giro del bloque exterior.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X