# An ant on a cube

1. Apr 11, 2008

### humanino

Hi,

An ant is walking along the edges of a unit cube. The goal is to find the number of paths of length N from one vertex to another.
Any path is allowed along the edges, back and forth any number of times.

2. Apr 11, 2008

### Jimmy Snyder

Can I assume that it is ok to arrive at the destination vertex early? For example, take a path of length N-2 from one vertex to another, go to another vertex and come back.

I already have a partial result for the puzzle:

If there is a path from one vertex to another that takes an odd number of steps, then the number of paths of length N between these vertices is zero if N is even. Similarly, if there is a path from one vertex to another that takes an even number of steps, then the number of paths of length N between these vertices is zero if N is odd.

eom.

3. Apr 11, 2008

### humanino

Yes !

The partial result is correct as well.

4. Apr 12, 2008

### Jimmy Snyder

More partial results:

For N = 1, the number of paths is either 1 if the pair of vertices are adjacent, or 0 otherwise.
For N = 2, the number of paths is either 3 if the pair of vertices are the same, 2 if the pair of vertices are on the diagonal of a face, and 0 otherwise.
For N = 3, the number of paths is either 7 if the pair of vertices are adjacent, 6 if the pair of vertices are diagonally separated, and 0 otherwise.

If the pair of vertices are the same, and N is an even number, then the number of paths is 3 times the number of paths between adjacent vertices for N - 1. For instance, since there are 7 paths between adjacent vertices for N = 3, there are 21 paths between a vertex and itself for N = 4.

eom

5. Apr 12, 2008

### humanino

I disagree : those results are less partial

In fact, the last result is on the verge of the principle for the principle leading to the solution I know.

hints :
Consider the cube sitting in front of you, concentrate on the upper face, call A the top-left-near vertex and turning counterclockwise call B, C and D the top-right-near, top-right-far and top-left-far vertices respectively. Then on the lower face, by the same token, call E, F, G and H the bottom-left-near, bottom-right-near, bottom-right-far and bottom-left-far vertices. Long way to describe the labels for them... Now assign white color to A, black color to the adjacent B, D and E, then white again for next adjacent C, F, and H and finally black to G which is diagonally opposed to A in the cube. If you start your path from A, as you can see passing from N to N+1 you switch colors. This gives you the result that if there are path of length N from one vertex to another, there are no path of length N+1 between the same. Observing the even-odd rule for low-length paths, you obtain it for any length by recurrence.

even stronger hint (continued) :

But more importantly, this hints toward the idea that you can compute the number of paths of lengths N+1 between A and any (or all) black vertex (vertices) from the knowledge of the number of the number of paths of length N between A and all white vertices. In fact, sperating black and white vertices is a good idea implementing the previous results of odd and even lengths, but ignoring this result you could also come to the conclusion that if you had the knowledge of the number of paths of length N between A and all vertices, you could easily compute the number of paths of length N+1 between A and all vertices...

6. Apr 16, 2008

### davee123

Can someone explain the goal of this problem more clearly?

1st off-- if we have 8 vertices on the cube, A,B,C,D,E,F,G, and H-- are we looking for the number of paths of length N that are ONLY from (say) C to G? Are we looking for all the paths of length N that start at C, but can end at any other vertex *other* than C? Or are we looking for the number of paths starting from A-H and ending at any separate vertex?

DaveE

7. Apr 16, 2008

### humanino

Yes !
That would be 3^N, not very interesting in that case...
8 time 3 to the power N from previous. Same case, not very challenging.

8. Apr 16, 2008

### davee123

Let V = shortest distance between start and destination vertices (1, 2, or 3).
Let P(N,V) = # of paths of length N going to a vertex that's V vertices away.

Base case:
P(1,1) = 1
P(1,2) = 0
P(1,3) = 0

For V = 1,3 P(N,V) = 0 if N % 2 = 0
For V = 2 P(N,V) = 0 if N % 2 = 1

P(N,1) = P(N,3)+1
P(N,2) = P(N-1,1) * 3 - 1
P(N,3) = P(N-1,2) * 3

DaveE

9. Apr 16, 2008

### Jimmy Snyder

10. Apr 16, 2008

### humanino

This strategy is not exactly how I solved it, but any strategy should as good as any other. However, as
it seems to me in that case you need also consider P(N,0), that is the number of path of length N to go back to the starting point. And the system I get looks like
Code (Text):

P(0,0) = 1
P(0,1) = 0
P(0,2) = 0
P(0,3) = 0

Code (Text):

P(1,0) = 0
P(1,1) = 1
P(1,2) = 0
P(1,3) = 0

Code (Text):

P(2,0) = 3
P(2,1) = 0
P(2,2) = 2
P(2,3) = 0

Code (Text):

P(3,0) = 0
P(3,1) = 7
P(3,2) = 0
P(3,3) = 6

....
Code (Text):

P(N+1,0) = 3*P(N,1)
P(N+1,1) =   P(N,0) + 2*P(N,2)
P(N+1,2) =   P(N,3) + 2*P(N,1)
P(N+1,3) = 3*P(N,2)

11. Apr 17, 2008

### davee123

I assumed that was explicitly forbidden by the problem, since it said "from one vertex to another", however I guess that's... a conceivable interpretation. Well, it's pretty trivial at least:

P(N,0) = P(N,2) + 1
P(N,1) = P(N,3) + 1
P(N,2) = P(N-1,1) * 3 - 1
P(N,3) = P(N-1,2) * 3

DaveE

12. Apr 17, 2008

### humanino

Unless I misunderstood the notation, this is in disagreement with what I wrote previously.

13. Apr 17, 2008

### humanino

Ah, but in math we usually take the "or" statement differently from the "nor" one. Well, you could in principle exclude paths that go back through the initial vertex. In fact, that does not make it more or less complicated. It breaks the symmetry of the cube however.

14. Apr 17, 2008

### davee123

The question stated "find the number of paths of length N from one vertex to another." Saying "one vertex" explicitly specifies a vertex that is distinct from "another". "Another", technically means "an other", as in "other", or a distinct entity from the subject. And since the subject in this case is "one vertex", then "another" MUST refer to a vertex "other" than the one in question. Hence, V cannot be 0, by the wording of the question. But it's pretty trivial to add it.

Well, the notation is accurate, I just forgot to stipulate:
For V = 0,2 P(N,V) = 0 if N % 2 = 1

P(N,0) = P(N,2) + 1

P(1,0) = 0 (because N % 2 = 1)
P(2,0) = P(2,2)+1 = 2 + 1 = 3
P(3,0) = 0 (because N % 2 = 1)
P(4,0) = P(4,2)+1 = 20 + 1 = 21
...

I also didn't provide a base case for N=0, since it was naturally excluded when V cannot be 0.

But either way, the result is the same:
Code (Text):

|   0     1     2     3
=========================
0 |   1     0     0     0
1 |   0     1     0     0
2 |   3     0     2     0
3 |   0     7     0     6
4 |  21     0    20     0
5 |   0    61     0    60
6 | 183     0   182     0
7 |   0   547     0   546
8 |1641     0  1640     0
9 |   0  4921     0  4920
...

DaveE

15. Apr 17, 2008

### humanino

I realize now that my statement was indeed quite confusing. Sorry about that. I will not blame the fact that english is not my native language

The relations you gave are correct. However, it is a bit frustrating that you provided neither the rational which lead you to them not the explicit solution. I will provide mine now, since in principle at least, only a few more manipulations are required from your relations.

Let me note $$N_{V_{i}}(n)$$ with $$i\in[1,8]$$ the components of a column vector $$\vec{N}(n)$$, equal to the number of paths of length $$n$$ from say the vertex $$V_{1}$$ to all the vertices $$\left.V_{i}\right|_{i\in[1,8]}$$. Assuming we know $$\vec{N}(n)$$ for a given $$n$$, then we can write

$$\vec{N}(n+1)=C \vec{N}(n)$$

where $$C$$ is a 8x8 matrix, whose components $$C_{i,j}$$ are equal to 1 if there is an edge between $$V_{i}$$ and $$V_{j}$$, and 0 otherwise. It is now easy to see that

$$\vec{N}(n)=C^{n} \vec{N}(0)$$

With a specific choice of vertex numbering, we could explicitely get :
$$\left(\begin{array}{c} N_{V_{1}}(n)\\ N_{V_{2}}(n)\\ N_{V_{3}}(n)\\ N_{V_{4}}(n)\\ N_{V_{5}}(n)\\ N_{V_{6}}(n)\\ N_{V_{7}}(n)\\ N_{V_{8}}(n)\\ \end{array}\right) = \left(\begin{array}{cccccccc} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ \end{array}\right)^{n} \left(\begin{array}{c} N_{V_{1}}(0)\\ N_{V_{2}}(0)\\ N_{V_{3}}(0)\\ N_{V_{4}}(0)\\ N_{V_{5}}(0)\\ N_{V_{6}}(0)\\ N_{V_{7}}(0)\\ N_{V_{8}}(0)\\ \end{array}\right)$$
This kind of matrix is called the connectivity matrix of the cube, considered as a graph. We could construct more complicated graphs, automatically generalizing to an arbitrary polyhedron, and we can even take into account fluxes constraints such as different speeds in the edges if for instance you say the ant goes slower up along the vertical edges, or faster down. The actual calculation is not very intersting anymore from this point (such as diagonalization of the matrix). We finally get :
$$\left(\begin{array}{c} \\ P(n,0)\text{ for Dave}\\ P(n,1)\text{ for Dave}\\ P(n,2)\text{ for Dave}\\ P(n,3)\text{ for Dave}\\ \end{array}\right) = \left(\begin{array}{c} \\ N_{V_{1}}(n)\\ N_{V_{2}},N_{V_{4}},N_{V_{5}}(n)\\ N_{V_{3}},N_{V_{6}},N_{V_{8}}(n)\\ N_{V_{7}}(n)\\ \end{array}\right) = \left(\begin{array}{cc} \text{n even}&\text{n odd}\\ \frac{3^n+3}{4} & 0\\ 0 & \frac{3^n+1}{4}\\ \frac{3^n-1}{4} & 0\\ 0&\frac{3^n-3}{4}\\ \end{array}\right)$$

It is actually worth noting that this construction, although quite general, does not make any use of the symmetries of the problem, such as the white-black vertices I introduced earlier. This in fact is apparent in Dave's relations. Using those lines of reasoning, one avoids the large number of 0s in the matrix. I prefered to present the general case, which is the one one is lead to when first constructing the solution from first principles, and most important for the general picture. Any specific case would display other kind of symmetries.

Code (Text):

1              0              0              0
0              1              0              0
3              0              2              0
0              7              0              6
21              0             20              0
0             61              0             60
183              0            182              0
0            547              0            546
1641              0           1640              0
0           4921              0           4920
14763              0          14762              0
0          44287              0          44286
132861              0         132860              0
0         398581              0         398580
1195743              0        1195742              0
0        3587227              0        3587226
10761681              0       10761680              0
0       32285041              0       32285040
96855123              0       96855122              0
0      290565367              0      290565366
871696101              0      871696100              0
0     2615088301              0     2615088300
7845264903              0     7845264902              0
0    23535794707              0    23535794706
70607384121              0    70607384120              0
0   211822152361              0   211822152360
635466457083              0   635466457082              0
0  1906399371247              0  1906399371246
5719198113741              0  5719198113740              0
0 17157594341221              0 17157594341220

Last edited: Apr 17, 2008