Tiempo para que todas las hormigas atraviesen el cubo

Question

Dejemos que $n$ sea un número entero positivo, y consideremos un hipercubo de dimensión $2n$ con $2^{2n}$ puntos dados por $(a_1,a_2,\ldots,a_{2n})$ , donde $a_i\in\{0,1\}$ . Dos puntos están conectados por una arista si y sólo si difieren exactamente en una coordenada. Al principio, hay exactamente una hormiga en cada uno de los vértices del hipercubo.

Una hormiga en el punto $(a_1,a_2,\ldots,a_{2n})$ quiere ir al grano $(a_{n+1},a_{n+2},\ldots,a_{2n},a_1,a_2,\ldots,a_n)$ . Al principio de cada segundo, considera el bit más adelantado (es decir, el más temprano desde la izquierda) en el que su posición actual difiere de su destino, y quiere tomar el borde para fijar ese bit. Sin embargo, cada arista puede ser recorrida como máximo por una hormiga en un segundo. El recorrido de una arista dura exactamente un segundo.

¿Cuál es el tiempo mínimo para que todas las hormigas lleguen a su destino? También son bienvenidas las asintóticas o los límites.

Answer 1

Obsérvese que una hormiga tiene que desplazarse a una posición en la que su $1$ st y $(n+1)$ st bits se intercambian, su $2$ y $(n+2)$ nd bits se intercambian, etc. A veces no es literalmente necesario intercambiar bits en pares de posiciones como éste, si ya coinciden. Pero considere puntos como $(1,1,0,0)$ cuando $n=2$ . Las hormigas que parten de un punto como éste tendrán que voltear todos sus pedazos para llegar a su destino. Así que $2n$ es un límite inferior del total de pasos dados para toda la marcha de hormigas. Pero en realidad podemos realizar la marcha en $2n$ pasos, como se describe a continuación.

Algunas hormigas comienzan en su destino final. Por ejemplo, con $n=2$ la hormiga en $(0,1,0,1)$ ya está donde tiene que estar. (Hay $2^n$ tales hormigas, correspondientes a cualquier secuencia para la primera $n$ coordenadas, repetidas para el último $n$ coordenadas). Llama a estos puntos "nivel $0$ ". En general, decimos que un punto está en el "nivel $k$ " si hay $k$ pares de posiciones de bits $i$ y $i+n$ que no coinciden (y por lo tanto hay que cambiarlos si una hormiga empieza ahí). El nivel más alto es el nivel $n$ ya que podríamos dejar la primera de un punto $n$ y cambiar su último $n$ bits para hacer $n$ tales pares).

Hormigas que comienzan en posiciones $(0,a,b,\ldots\big|0,z,y,\ldots)$ o $(1,a,b,\ldots\big|1,z,y,\ldots)$ no necesitan el $1$ o $(n+1)$ stos trozos volteados en comparación con su destino final. Pero las hormigas que empiezan en $(0,a,b,\ldots\big|1,z,y,\ldots)$ o $(1,a,b,\ldots\big|0,z,y,\ldots)$ necesito ambos de estas posiciones se volcó.

• Paso $1$ : Para todas las hormigas que necesitan voltear los bits en las posiciones $1$ y $n+1$ Haz que caminen hasta el punto que da la vuelta al primer bit. Obsérvese que esto reduce el nivel del punto en el que se encuentra la hormiga, porque ahora los bits en las posiciones $1$ y $n+1$ son iguales. Dado que todas estas hormigas comienzan en lugares diferentes, no se repite el uso de un borde donde dos hormigas lo recorrieron en la misma dirección. Dado que este movimiento fue universalmente una reducción de nivel, no se repitió el uso de un borde de dos hormigas que caminaron en direcciones opuestas.
• Paso $2$ : Para las hormigas que se acaban de mudar Paso $1$ , haz que caminen hacia el punto que da la vuelta al $(n+1)$ st bit. Este movimiento elevará ahora el nivel del lugar donde se encuentran estas hormigas. La combinación de estos dos pasos permuta las posiciones de estas hormigas que necesitaban su $1$ st y $(n+1)$ st bits volteados. (Una hormiga que estaba en $(0,a,b,\ldots\big|1,z,y,\ldots)$ está ahora en $(1,a,b,\ldots\big|0,z,y,\ldots)$ y viceversa). Así que volvemos a estar en un estado en el que cada punto del hipercubo tiene una hormiga. Por lo tanto, no hay dos hormigas que recorran la misma arista en la misma dirección. Y de nuevo el cambio de nivel universal (esta vez hacia arriba) implica que tampoco dos hormigas compartieron una arista caminando en direcciones opuestas.
• Paso $3$ , $4$ : Repita los pasos $1$ y $2$ pero aplicado a la $2$ y $(n+2)$ nd bits. Como terminamos el paso $2$ con una hormiga en cada punto, volveremos a ejecutar el movimiento sin que dos hormigas utilicen la misma arista al mismo tiempo.
• Paso $5$ , $6$ : Repetir, aplicado a la $3$ rd y $(n+3)$ rd bits.
• ...
• Paso $2n-1$ , $2n$ : Repetir, aplicado a la $n$ y $2n$ de los bits.

Y ahora, después de $2n$ pasos, cada hormiga ha llegado a su destino final. Como se ha señalado antes, $2n$ es un límite inferior para una marcha completa de las hormigas a sus destinos, pero ahora vemos que también es un límite superior para la marcha más eficiente.