4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I initially misread the problem as concerning a "dodecahedron" rather than "dodecagon". I think this is a cool misinterpretation, so I posed it as a question of it's own: math.stackexchange.com/questions/2577433/… $\endgroup$ – Yly Dec 23 '17 at 2:51
  • $\begingroup$ Why are there no paths with $n$ odd? $\endgroup$ – Sean Roberson Dec 23 '17 at 2:53
  • 3
    $\begingroup$ @SeanRoberson Colour the vertices red, blue, red, blue alternately. Starting on a red vertex, the opposite is also red. But after an odd number of steps the ant can only be on a blue vertex, so can't have reached the opposite. $\endgroup$ – B. Mehta Dec 23 '17 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.