A fly proceeds along the edges of a cube from one corner to the diagonally opposite cornerHow many different paths can it take?

Answer 1

Let the "points" of the cube be vertices and lines between then edges. These are graph theory terms because this is really a graph theory problem. If we assume the fly can only go in one direction, that is it cannot backtrack, then we have what is known as a digraph. Now A path is a sequence of edges where the tail of one edge is the same vertex as the head of the next edge in the sequence,

So what we really want to know if how many paths there are from one vertex to its diagonal vertex. I suggest you start with the length of each path. Let's let n be the length of the path.

Now if we look at n=1, we would need the fly to move along an path from one diagonal to the opposite one, but that edge does not exists so we have 0 paths.

Now how about n=2. Once again, we can't do it, we can get to the opposite corner of the face of a cube but not the diagonal vertex. Now for n=3, we can do it in several ways.

Take a cube and find how many? Next try n=4, 5 etc?

Seems like a lot of work? I will give you some help. Use a matrix to represent the edges of the cube and use 1 or 0 depending on if there is an edge between the vertices.

I am including a link you can use to solve the problem using these matrices known as

adjacency matrices. For example, if you have vertices A, B, C and D and they are the corners of a square with a directed or not directed edge between A and B and D and A, then in the first row of the matrix you would have 0 1 0 1. Remember, 1 means there is an edge ( NOT A PATH) and 0 means there is not. So.....

The matrix would have columns labeled A B C D and rows labeled the same way.

The 0 in the 1,1 position means there is no edge between A and A. The 1, after that 0, means there is an edge ( a directed or not) between A and B. The next 0 means no edge between A and C and the next 1 means an edge between A and D.

Now think of the edge has a path on length 1 for A to B or A to C or A to D.

A 1 means there is such a path and a 0 means there is not.

Just to give you a little more clue, we can multiply the adjacency matrix by itself.

Call the matrix A. Then A will tell us the number of path of length a from i to j just be seeing if we have a 0 or a 1. But A2 will tell us the number of paths of length 2 for i to j.

This will still be 0 for what you are asking. Now A3 will be the number of paths of length 3.

This is what I mentioned above.



In general AN is the number of paths of length N from i to j.

So this method will answer your question.

You might need to say for sure if the fly can only go in one direction?