How Many Paths Can an Ant Take on a Cube with a Black Hole?

[Canada_Whiz]

Suppose an ant is on a vertex of a cube. On one of the three vertices neighboring the ant, there is a black hole. On each move, the ant travels to one of it's neighboring vertices, being careful not to pass through the black hole. The ant makes N moves in total. How many different paths lead the ant back to his original vertex after these N moves?

NOTE: The answer is in terms of N. Also, the ant may cross an edge he has already crossed, so long as he does NOT go through the black hole.

My Data:
For N=0, there is 1 way
For N=2, there are 2 ways
For N=4, there are 8 ways
For N=2z+1, there are 0 ways


Help is much appreciated!

 

[lanedance]

this closely related to graph theory so may be better posted in the calc and beyond forum

i agree it can't be done in an odd number of moves, however based on a quick count for N = 4, i get 5, not 8? I'm assuming the ant must travel along an edge

 

[Yayness]

I got 10 ways for N = 4.

From a certain angle, the black hole will be on the backside and will therefore not show. For that reason, you can draw a simple 2D-model of the cube. (That is probably not so hard to see.)

Anyway, you could probably divide N by two, and count all the possible paths to a certain vertex and then square the number (to get the number of possible paths back, through this point).
You can then do the same with the other vertices. It makes it easier, at least for the first few values of N.

By doing this, I got:
For N = 4k, the number of possible paths can be written as 2a²+b²+c²
For N = 4k+2, the number of possible paths can be written as 2a²+b²
(for any non-negative integer k, where a, b and c also are integers).

I'll give you more hints if I solve the problem.

I'll work on the problem.

 

[Yayness]

Hmm, I would start by doing one move, and then split the rest of the path into pairs of moves, and then end the path by doing one last move.

 

[tiny-tim]

Let's make this 2D, so it's easier to see …

draw a horizontal rectangle, divide it vertically into two, and join the two bottom corners with a V …

that's 7 vertices, and you have to start from, and return to, the bottom of the V.

 

[lanedance]

...A
../..\
./...\
|\.../|
|.\./.|
.\.|./
..\|/

A is the starting node, and the dots above are just for spacing. Hopefully the picture agrees with what the Yayness said (and is equivalent to Tiny Tim's, after a massage and turned upside down). Imagine the black hole being the node you can't see in a 3D cube giving the above image with 7 nodes & 9 edges

I can still only see 6 different routes for N = 4?

 

[Canada_Whiz]

There are 10 paths for n=4.
I have found the answer, and to quench your curiosity, here it is :)
http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=382116