An ant is at a vertex of a cube. Every $$10$$ minutes it moves to an adjacent vertex along an edge. If $$N$$ is the number of one hour journeys that end at the starting vertex, find the sum of the squares of the digits of $$N$$.

Number the vertices of the cube by the binary triples $$000,100,010,001,110,101,011,111$$ and choose $$000$$ as the starting vertex.

For every move (one edge along the cube) the ant changes exactly one coordinate, so the Hamming distance from the start changes by $$\pm1$$. Hence at any vertex the distance from the start can only be

  • 0 (the start itself)   • 1   • 2   • 3 (the body-diagonal opposite vertex)

Let $$a_n,\;b_n,\;c_n,\;d_n$$ denote the number of $$n$$-step paths that end at distance $$0,1,2,3$$ respectively.

Initial state (before any move): $$a_0=1,\;b_0=c_0=d_0=0$$.

From the connectivity of the cube:

  • A distance-0 vertex is adjacent to the 3 distance-1 vertices.
  • A distance-1 vertex is adjacent to 1 distance-0 and 2 distance-2 vertices.
  • A distance-2 vertex is adjacent to 2 distance-1 and 1 distance-3 vertices.
  • The single distance-3 vertex is adjacent to the 3 distance-2 vertices.

This gives the linear recurrences

$$\begin{aligned} a_{n+1}&=b_n,\\ b_{n+1}&=3a_n+2c_n,\\ c_{n+1}&=2b_n+3d_n,\\ d_{n+1}&=c_n. \end{aligned}$$

Now iterate for six moves (one hour = 60 minutes = 6 moves):

Step 1 :  $$(a_1,b_1,c_1,d_1)=(0,3,0,0)$$

Step 2 :  $$(a_2,b_2,c_2,d_2)=(3,0,6,0)$$

Step 3 :  $$(a_3,b_3,c_3,d_3)=(0,21,0,6)$$

Step 4 :  $$(a_4,b_4,c_4,d_4)=(21,0,60,0)$$

Step 5 :  $$(a_5,b_5,c_5,d_5)=(0,183,0,60)$$

Step 6 :  $$(a_6,b_6,c_6,d_6)=(183,0,546,0)$$

Thus $$N=a_6=183$$ closed walks of length 6 start and end at the original vertex.

Digits of $$N$$: $$1,8,3$$. Sum of the squares: $$1^2+8^2+3^2=1+64+9=74$$.

Final Answer: 74