3.3. A circle is divided into $2 n$ equal arcs by $2 n$ points $A_{1}, A_{2}, A_{3}, \ldots, A_{2 n}$. A chip is placed at point $A_{1}$. It is allowed to move the chip either to an adjacent point or to the diametrically opposite point. How many ways are there to visit all $2 n$ points exactly once and return to point $A_{1}$?

## Fourth Round
3.3. Solution. Consider the corresponding graph. We will count the number of cycles containing all vertices (Hamiltonian cycles). Since a cycle can be transformed into a traversal in two ways, we need to multiply the obtained answer by two. Note that there is one cycle that does not contain any diameter. Now let's assume that our traversal contains at least one diameter. It is obvious that one diameter is not enough, so there must be at least two. Suppose in our traversal there are diameters from points numbered 1 and $k$, and from points numbered $2, 3, \ldots, k-1$ no diameters are drawn. Then the vertices from 1 to $k$ are connected by the sides of the $2n$-gon, and similarly, the vertices from $n+1$ to $n+k$. All the described edges form a cycle, so it must contain all vertices, which means $k=n$. There are exactly $n$ such cycles. Finally, if

![](https://cdn.mathpix.com/cropped/2024_06_04_b1380f2021d62732a78bg-21.jpg?height=566&width=991&top_left_y=54&top_left_x=538)

Fig. 20: to the solution of problem 4.2

the diameters described above are not present, we get that all diameters are drawn. If $n$ is even, then there are no such cycles, and if $n$ is odd, then there are two such cycles. The answer is: there are $n+1$ cycles for even $n$ and $n+3$ cycles for odd $n$. As mentioned above, the obtained answers need to be multiplied by two.

## Fourth Round