Estonian Mathematical Olympiad

Let $n$ be odd. Write the number $1$ at some point on the circle and, after every $\frac{2}{n}$ full turns, write the next number by size (Fig. 45 shows the case for $n=11$). In this way, all the numbers from $1$ to $n$ can be written in different points. Choosing any number on the circle and the number two positions away from it, we have either consecutive integers or the numbers $n$ and $1$. In both cases, the chosen numbers are coprime.

If $n$ is divisible by $4$, let $n=2m$, where $m$ is an even number. Like described for odd $n$, write the numbers from $1$ to $m$ on the circle and in the remaining points, write the numbers from $m+1$ to $n$ in order (Fig. 46 shows the case for $n=12$). Choosing any number on the circle and the number two positions away from it, we have either consecutive integers or the numbers $m$ and $1$ or the numbers $n$ and $m+1$. In the first two cases, the chosen numbers are coprime. If the numbers $n$ and $m+1$ had a common divisor $d$, then $d$ would also be a divisor of $n-(m+1)$, that is, $m-1$, and also a divisor of $(m+1)-(m-1)$, that is, $2$. But $d\ne 2$ because $m$ is even, so $m+1$ is odd and has no factor $2$. Thus, the only possibility is $d=1$, meaning $\gcd (n,m+1)=1$. Therefore, the chosen numbers are coprime in all cases.

Fig. 45 Fig. 46

Now let $n$ be an even number that is not divisible by $4$, i.e., $n=2m$, where $m$ is an odd number. Suppose that the positive integers from $1$ to $n$ are arranged in some order on a circle. This divides these numbers into two groups, each containing $m$ numbers: the first group contains the number $1$ and all those that can be reached by repeatedly jumping to the number two positions away, while the second group contains all the remaining numbers. Among all the written numbers, there are $m$ even numbers, and at least half of them must belong to one group; since $m$ is odd, more than half of the even numbers must belong to one group. This means that there must be two even numbers that are consecutive within the group, i.e., one is two positions away from the other on the circle. These two numbers have a common factor $2$. Therefore, it is not possible to arrange the numbers from $1$ to $n$ on the circle such that every number is coprime with the number two positions away from it.