10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Anatoly "At the beginning, an ant is at each of the vertices of the hypercube." That means every vertex has an ant at the beginning. $\endgroup$ – simmons Nov 6 '14 at 15:23
  • $\begingroup$ "foremost bit" = "with highest index"? "However, each edge can be traversed by at most one ant in a second." Second=step? Does that mean that in each step each one of the ants attemps to move simultaneously, and that two ants can share a point but if so they can't share the movement? $\endgroup$ – leonbloy Nov 6 '14 at 16:47
  • $\begingroup$ @leonbloy I've edited -- hope it's clearer. And yes, in each second each one of the ants attempts to move simultaneously, and two ants can share a point but if so they can't share the movement in that second. $\endgroup$ – simmons Nov 6 '14 at 17:37
  • $\begingroup$ "and wants to take the edge to fix that bit" If it can't, can it transverse another edge, or must it wait? $\endgroup$ – leonbloy Nov 6 '14 at 17:39
  • $\begingroup$ @leonbloy It must wait. $\endgroup$ – simmons Nov 6 '14 at 17:41
1
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Read the discussion carefully and see that you aren't allowed to alter the sequence in wich the ants attempt to toggle their bits, thus step 2 is invalid. You may only chose wich ant gets precedence on a "collision edge". $\endgroup$ – AlexR Nov 11 '14 at 18:28
  • $\begingroup$ Relevant quote by @simmons: (at)AlexR If by "AI" you mean the order in which the ants "fix their bits", that's deterministic. Now, as to which ant gets precedence when two ants want to traverse the same edge, you can choose that (in order to minimize the total time until all ants reach their destination.) $\endgroup$ – AlexR Nov 11 '14 at 18:28
  • $\begingroup$ @AlexR I interpret "that's deterministic" to mean that I, as the author of the algorithm, may determine the order that they fix their bits. As opposed to a process where an ant chooses a bit to flip based on some kind of random process. Perhaps OP can clarify. $\endgroup$ – alex.jordan Nov 11 '14 at 18:39
  • $\begingroup$ @alex.jordan Actually I meant the interpretation that AlexR gave. However, your answer is also very nice (for your interpretation), so please keep it. :) $\endgroup$ – simmons Nov 11 '14 at 20:19
  • $\begingroup$ OK, but can you help me understand what you want ants to do? They are supposed to try to toggle their first bit first, if that is needed? And once they have accomplished that, then they are supposed to attempt to toggle their second bit (if needed)? And if they have to wait because of an edge conflict, then they wait until they can toggle their second bit without conflict? $\endgroup$ – alex.jordan Nov 11 '14 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.