Ants Walking Around a Cube: Find Number of Paths of Length N

  • Thread starter humanino
  • Start date
  • Tags
    Cube
In summary: N that are ONLY from (say) C to G?We are looking for the number of 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?2nd off-- what if we only have 5 vertices on the cube? If we only have 5 vertices on the cube, then we are only looking for the number of paths of length N that are ONLY from A to H.
  • #1
humanino
2,527
8
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.
 
Physics news on Phys.org
  • #2
humanino said:
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.
 
  • #3
jimmysnyder said:
Can I assume that it is ok to arrive at the destination vertex early?
Yes !

The partial result is correct as well.
 
  • #4
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
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...
 
  • #6
humanino said:
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
 
  • #7
davee123 said:
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:
 
  • #8
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
davee123 said:
Let V = shortest distance between start and destination vertices (1, 2, or 3).
How about V = 0?
 
  • #10
davee123 said:
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
jimmysnyder said:
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)
 
  • #11
jimmysnyder said:
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
 
  • #12
davee123 said:
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.
 
  • #13
davee123 said:
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.
 
  • #14
humanino said:
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.

humanino said:
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
 
  • #15
davee123 said:
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 preferred 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:

1. What is the concept behind "Ants Walking Around a Cube"?

The concept behind "Ants Walking Around a Cube" is a mathematical problem that involves finding the number of possible paths that a group of ants can take when walking around the edges of a cube for a given length of time.

2. How is the number of paths calculated?

The number of paths can be calculated using a mathematical formula that takes into account the number of possible directions the ants can take and the length of time they are walking. This formula can be derived by using combinatorics and graph theory.

3. What factors affect the number of paths?

The main factors that affect the number of paths are the number of ants, the length of time they are walking, and the number of possible directions they can take at each edge of the cube. Other factors may include any restrictions or obstacles that may be present on the cube.

4. How is this problem relevant in real life?

This problem may have practical applications in fields such as computer science and transportation planning. It can also be used to study the behavior of ants and other insects in their natural habitats.

5. Are there any variations to this problem?

Yes, there are variations to this problem that involve ants walking on different shapes such as spheres or cylinders. There are also variations that involve multiple starting and ending points for the ants. These variations may require different mathematical approaches to find the number of paths.

Similar threads

Replies
2
Views
177
  • General Math
Replies
21
Views
2K
  • Science Fiction and Fantasy Media
Replies
0
Views
881
  • Quantum Physics
Replies
16
Views
1K
Replies
21
Views
1K
Replies
1
Views
1K
  • Quantum Physics
Replies
22
Views
411
Replies
4
Views
1K
  • Mechanical Engineering
Replies
2
Views
690
  • Topology and Analysis
Replies
5
Views
774
Back
Top