An ant on a cube

  • Thread starter humanino
  • Start date
2,400
6

Main Question or Discussion Point

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.
 

Answers and Replies

854
16
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.
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.
 
2,400
6
Can I assume that it is ok to arrive at the destination vertex early?
Yes !

The partial result is correct as well.
 
854
16
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
 
2,400
6
I disagree : those results are less partial :biggrin:

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...
 
662
3
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.
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
 
2,400
6
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?
Yes !
Are we looking for all the paths of length N that start at C, but can end at any other vertex *other* than C?
That would be 3^N, not very interesting in that case...
Or are we looking for the number of paths starting from A-H and ending at any separate vertex?
8 time 3 to the power N from previous. Same case, not very challenging. :smile:
 
662
3
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
 
854
16
2,400
6
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
This strategy is not exactly how I solved it, but any strategy should as good as any other. However, as
How about V = 0?
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:
P(0,0) = 1
P(0,1) = 0
P(0,2) = 0
P(0,3) = 0
Code:
P(1,0) = 0
P(1,1) = 1
P(1,2) = 0
P(1,3) = 0
Code:
P(2,0) = 3
P(2,1) = 0
P(2,2) = 2
P(2,3) = 0
Code:
P(3,0) = 0
P(3,1) = 7
P(3,2) = 0
P(3,3) = 6
....
Code:
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)
 
662
3
How about V = 0?
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
 
2,400
6
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
Unless I misunderstood the notation, this is in disagreement with what I wrote previously.
 
2,400
6
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.
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.
 
662
3
Ah, but in math we usually take the "or" statement differently from the "nor" one.
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.

Unless I misunderstood the notation, this is in disagreement with what I wrote previously.
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:
  |   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
 
2,400
6
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.
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 :smile:

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 [tex]N_{V_{i}}(n)[/tex] with [tex]i\in[1,8][/tex] the components of a column vector [tex]\vec{N}(n)[/tex], equal to the number of paths of length [tex]n[/tex] from say the vertex [tex]V_{1}[/tex] to all the vertices [tex]\left.V_{i}\right|_{i\in[1,8]}[/tex]. Assuming we know [tex]\vec{N}(n)[/tex] for a given [tex]n[/tex], then we can write

[tex]\vec{N}(n+1)=C \vec{N}(n)[/tex]

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

[tex]\vec{N}(n)=C^{n} \vec{N}(0)[/tex]

With a specific choice of vertex numbering, we could explicitely get :
[tex]
\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)
[/tex]
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 :
[tex]
\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)
[/tex]

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:
              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:

Related Threads for: An ant on a cube

  • Last Post
Replies
16
Views
3K
  • Last Post
Replies
19
Views
7K
  • Last Post
3
Replies
61
Views
7K
Replies
2
Views
2K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
4
Replies
85
Views
56K
  • Last Post
Replies
8
Views
2K
Top