Combinatorics – Walking Around a Cube to Return to Starting Point

combinatorics

Suppose I have a cube of side length $1$ unit and I am supposed to walk $6$ units in total, starting from one vertex of the cube. I can move from one vertex to only any other adjacent vertex through the edge of the cube. In how many ways can I start and end at the same vertex?

My work

Suppose I start from any one of the vertices. Then I have noted that one way to satisfy given constraints is by moving to any adjacent vertex and moving back to the origin a total of 3 times. This gives me 27 possible ways for this case.

I also think that it has something to do with how many edges of a face are traversed which determines if the condition can be satisfied. But I can not work out anything concrete.

However if I try to do some casework I immediately find that the number of cases are too many to count and hence I’m unable to conclude anything useful. Help is appreciated.

Best Answer

As another way to see it, note that we can describe any path along the cube as a string of $X$'s, $Y$'s, and $Z$'s, where X means "change your $x$-coordinate from 0 to 1 or vice versa," and similarly for $Y$ and $Z$. What's more, the string corresponding to any closed path along the edges of the cube will have an even number of $X$'s, $Y$'s, and $Z$'s.

So the cases are:

  1. Strings with 6 identical symbols. There are three such strings: $XXXXXX$, $YYYYYY$, and $ZZZZZZ$.

  2. Strings with four symbols of one type and two of another. For a given choice of the two types of symbol ($X$ and $Y$ respectively, say) there are $\frac{6!}{4! 2!} = 15$ such strings. There are further 6 possible choices for the types of symbols in the string (noting that, for example, 4 $X$'s and 2 $Y$'s is distinct from 4 $Y$'s and 2 $X$'s.) So we have $15 \times 6 = 90$ such strings.

  3. Strings with two symbols of each type. There are $\frac{6!}{2!2!2!}=90$ such strings.

So all in all there are $3 + 90 + 90 = 183$ such strings and therefore 183 such paths on the cube.

Related Question