, 2021

Solution:

How many routes are there if we are restricted to $n$ available points, and we must use all $n$ of them? The answer is $n 2^{n-2}$: first choose the starting point, then each move after that must visit one of the two neighbors of your expanding region of visited points (doing anything else would prevent you from visiting every point). Now simply sum over all possible sets of points that you end up visiting:
$$\binom{8}{8}\left(8 \cdot 2^{6}\right)+\binom{8}{7}\left(7 \cdot 2^{5}\right)+\cdots+\binom{8}{2}\left(2 \cdot 2^{0}\right)=8744.$$

Solution:

We use recursion. Let $f(n)$ be the answer for $n$ points, with the condition that our path must start at $P_{n}$ (so our final answer is $8 f(8)$). Then $f(1)=0$ and $f(2)=1$.

Now suppose $n \geq 3$ and suppose the second point we visit is $P_{i}$ ($1 \leq i < n$). Then we can either stop the path there, yielding one possibility. Alternatively, we can continue the path. In this case, note that it may never again cross the chord $P_{i} P_{n}$. If the remainder of the path is among the points $P_{1}, \ldots, P_{i}$, there are $f(i)$ possible routes. Otherwise, there are $f(n-i)$ possible routes. As a result,
$$f(n)=\sum_{i=1}^{n-1} 1+f(i)+f(n-i)=(n-1)+2 \sum_{i=1}^{n-1} f(i)$$
From here we may compute: