Problem

Source: Flanders Math Olympiad 2020 p4

Tags: combinatorics



There are $n$ hoops on a circle. Rik numbers all hoops with a natural number so that all numbers from $1$ to $n$ occur exactly once. Then he makes one walk from hoop to hoop. He starts in hoop $1$ and then follows the following rule: if he gets to hoop $k$, then he walks to the hoop that places $k$ clockwise without getting into the intermediate hoops. The walk ends when Rik has to walk to a hoop he has already been to. The length of the walk is the number of hoops he passed on the way. For example, for $n = 6$ Rik can take a walk of length $5$ as the hoops are numbered as shown in the figure. (a) Determine for every even $n$ how Rik can number the hoops so that he has one walk of length $n$. (b) Determine for every odd $n$ how Rik can number the hoops so that he has one walk of length $n - 1$. (c) Show that for an odd $n$ there is no such numbering of the hoops that Rik can make a walk of length $n$.