# Get from one vertex to the opposite - dodecagon

Let $x$ be a regular dodecagon. Starting from one vertex, an ant wants to reach the opposite vertex of the dodecagon, moving to adjacent vertices. If $p_n$ is the number of such paths with length $n$, compute $p_1+p_2+p_3...+p_{12}$.

Obviously we can't have a path of length $1$,$2$, $3$, or $4$. It's easy to find the amount of cases in which we have path lengths of $5$, $6$, or $7$. However, I need help finding the cases beyond this. Can anyone help me.

Note that 12 is too few steps to go clear around the dodecagon, so the ant must move a net of 6 steps either clockwise or counterclockwise to end up at the opposite vertex. So if he takes $n$ total steps, 6 of them give that net displacement, and the remaining $n-6$ must cancel out, i.e. half clockwise and half counterclockwise. Hence $(n-6)/2$ has to be an integer, so there are no paths with $n$ odd.
When $n$ is even, the number of such paths of length $n$ is just the number of ways to choose $(n-6)/2$ steps one way and the remaining steps the other way, i.e. $p_n = 2\times\binom{n}{(n-6)/2}$, where the factor of 2 is because the path can go either clockwise or counterclockwise.
Hence the total number of paths is $\sum_{n=1}^{6} p_{2n} = \sum_{n=1}^{6} 2\binom{2n}{(2n-6)/2} = 548$.
• Why are there no paths with $n$ odd? – Sean Roberson Dec 23 '17 at 2:53