8 bunnies and 3 directions

Question

There are 8 bunnies placed on the cubical corners and each bunny has three directions to move( can move only on edges) find the probability that all bunnies move simentaneously in random directions ( any one of those 3 directions) and do not collide with each other.

Answer 1

Because you require that each of them pick one direction, and do not run into each other, we know the following:

1. For each vertice (a bunny), there is one outgoing arrow along one of the three edges connecting to that vertice;
2. No two vertices point to each other, as that means two bunnies will collide on the edge connecting those two vertices;
3. No two vertices point to the same vertice, as that means two bunnies will collide on a vertice.

Those 3 thing taken together means that the vertices and the edges those bunnies choose form a directed graph where each vertice is in a loop. Just follow the edges, you must return to where you started as otherwise two vertices will be pointing to the same vertice. Moreover, there are no loop of length 2 (as no two vertices point to each other).

On a cube, there are only loops of even length: 2, 4, 6, 8. Now we are partitioning the 8 vertices into loops, and we cannot use loops of length 2. That means we cannot use loops of length 6 either. So basically the question is how many ways there are to partition a cube into loops of length 4 or 8.

Well, you can either have one loop of length 8 or two loops of length 4:

1. There are 12 loops of length 8. To count this, notice that every loop of length 8 partitions the cube into two C shapes of three connected surfaces. In fact, those two C shapes correspond precisely to the two orientations of the loop. You can count that there are 12 C shaps (2 for each surface). So there are 12 loops of length 8.
2. There are 12 ways to partition the cube into two 4-loops: 3 ways to partition into two opposing surfaces, 2 orientations for each surface. So together, $3 \times 4 \times 4 = 12$.

Thus 24 ways.

Code (in Python) using Hamming cube.

def count(n, f):
  if n < 8:
    for i in xrange(3):
      f[n] = n^(1 << i)
      count(n+1, f)
  else:
    sign = 1
    for i in xrange(8):
      for j in xrange(i):
        if f[i] == f[j]: sign = 0
      if i == f[f[i]]: sign = 0
    if sign == 1: 
      print f[0:8]
      f[n] += 1

f = [0 for i in xrange(9)] 
count(0, f)
print f[8]

Results:

[1, 3, 0, 2, 5, 7, 4, 6]
[1, 3, 0, 2, 6, 4, 7, 5]
[1, 3, 0, 7, 6, 4, 2, 5]
[1, 3, 6, 2, 0, 4, 7, 5]
[1, 5, 3, 7, 0, 4, 2, 6]
[1, 5, 0, 2, 6, 4, 7, 3]
[1, 5, 6, 2, 0, 4, 7, 3]
[1, 5, 6, 2, 0, 7, 4, 3]
[2, 0, 3, 1, 5, 7, 4, 6]
[2, 0, 3, 1, 6, 4, 7, 5]
[2, 0, 3, 7, 5, 1, 4, 6]
[2, 0, 6, 1, 5, 7, 4, 3]
[2, 3, 6, 7, 0, 1, 4, 5]
[2, 5, 3, 1, 0, 7, 4, 6]
[2, 5, 6, 1, 0, 4, 7, 3]
[2, 5, 6, 1, 0, 7, 4, 3]
[4, 0, 3, 1, 5, 7, 2, 6]
[4, 0, 3, 7, 5, 1, 2, 6]
[4, 0, 3, 7, 6, 1, 2, 5]
[4, 0, 6, 2, 5, 1, 7, 3]
[4, 3, 0, 2, 6, 1, 7, 5]
[4, 3, 0, 7, 5, 1, 2, 6]
[4, 3, 0, 7, 6, 1, 2, 5]
[4, 5, 0, 1, 6, 7, 2, 3]
24