Question 34
Let $n \geqslant 2$ be an integer. Consider all circular arrangements of the numbers $0,1, \ldots, n$; the $n+1$ rotations of an arrangement are considered to be equal. A circular arrangement is called beautiful if, for any four distinct numbers $0 \leqslant a, b, c, d \leqslant n$ with $a+c=b+d$, the chord joining numbers $a$ and $c$ does not intersect the chord joining numbers $b$ and $d$.
Let $M$ be the number of beautiful arrangements of $0,1, \ldots, n$. Let $N$ be the number of pairs ( $x, y$ ) of positive integers such that $x+y \leqslant n$ and $\operatorname{gcd}(x, y)=1$. Prove that
$$
M=N+1 .
$$
Let $M$ be the number of beautiful arrangements of $0,1, \ldots, n$. Let $N$ be the number of pairs ( $x, y$ ) of positive integers such that $x+y \leqslant n$ and $\operatorname{gcd}(x, y)=1$. Prove that
$$
M=N+1 .
$$