Time for all ants to traverse cube Let $n$ be a positive integer, and consider a hypercube of dimension $2n$ with $2^{2n}$ points given by $(a_1,a_2,\ldots,a_{2n})$, where $a_i\in\{0,1\}$. Two points are connected by an edge if and only if they differ in exactly one coordinate. At the beginning, exactly one ant is at each of the vertices of the hypercube. 
An ant at point $(a_1,a_2,\ldots,a_{2n})$ wants to get to the point $(a_{n+1},a_{n+2},\ldots,a_{2n},a_1,a_2,\ldots,a_n)$. At the beginning of each second, it considers the foremost bit (i.e., the earliest bit from the left) in which its current position differs from its destination, and wants to take the edge to fix that bit. However, each edge can be traversed by at most one ant in a second. The traversal of one edge takes exactly one second.
What is the minimum time for all ants to reach their destination? Asymptotics or bounds are also welcome.
 A: Note that an ant needs to move to a position where its $1$st and $(n+1)$st bits are exchanged, its $2$nd and $(n+2)$nd bits are exchanged, etc. Sometimes there is not literally a need to exchange bits in position pairs like this, if they already match. But consider points like $(1,1,0,0)$ when $n=2$. Ants starting at a point like this will have to have all their bits flipped to reach their destination. So $2n$ is a lower bound on total steps taken for the entire march of ants. But we can actually accomplish the march in $2n$ steps, as described below.
Some ants start out at their final destination. For example, with $n=2$, the ant at $(0,1,0,1)$ is already where it needs to be. (There are $2^n$ such ants, corresponding to any sequence for the first $n$ coordinates, repeated for the last $n$ coordinates.) Call these points "level $0$". In general, we say that a point is at "level $k$" if there are $k$ pairs of bit positions $i$ and $i+n$ that don't match (and so need to be exchanged if an ant starts there). The highest level is level $n$, since we could leave a point's first $n$ bits alone and toggle its last $n$ bits to make $n$ such pairs.)
Ants who start in positions $(0,a,b,\ldots\big|0,z,y,\ldots)$ or $(1,a,b,\ldots\big|1,z,y,\ldots)$ do not need the $1$st or $(n+1)$st bits flipped in comparison to their final destination. But ants who start in $(0,a,b,\ldots\big|1,z,y,\ldots)$ or $(1,a,b,\ldots\big|0,z,y,\ldots)$ need both of these positions flipped.


*

*Step $1$: For all ants who need to flip the bits in positions $1$ and $n+1$, have them walk to the point that flips the first bit. Note that this reduces the level of the point that the ant is standing at, because now the bits at positions $1$ and $n+1$ are equal. Since these ants all start in different places, there is no repeated use of an edge where two ants walked it in the same direction. Since this movement was universally a reduction in level, there was no repeated use of an edge from two ants walking in opposite directions.

*Step $2$: For the ants who just moved in Step $1$, have them walk to the point that flips the $(n+1)$st bit. This movement will now raise the level of where these ants are standing. The combination of these two steps permutes the positions of these ants who needed their $1$st and $(n+1)$st bits flipped. (An ant who was at $(0,a,b,\ldots\big|1,z,y,\ldots)$ is now at $(1,a,b,\ldots\big|0,z,y,\ldots)$ and vice versa). So we are back in a state where each point on the hypercube has one ant. Therefore no two ants just walked the same edge in the same direction. And again the universal (this time upward) change in level implies no two ants shared an edge walking in opposite directions either.

*Step $3$, $4$: Repeat steps $1$ and $2$ but applied to the $2$nd and $(n+2)$nd bits. Since we ended step $2$ with one ant on each point, we will again execute movement without any two ants using the same edge at the same time.

*Step $5$, $6$: Repeat, applied to the $3$rd and $(n+3)$rd bits.

*...

*Step $2n-1$, $2n$: Repeat, applied to the $n$th and $2n$th bits.


And now, after $2n$ steps, every ant has reached its final destination. As noted before, $2n$ is a lower bound for a complete march of the ants to their destinations, but now we see it is an upper bound for the most efficient march as well.
