2013 IMO Shortlist C7

Let $n \geq 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 \leq a, b, c, d \leq 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 \leq n$ and $\operatorname{gcd}(x, y)=1$. Prove that $$M=N+1$$ (Russia)

设 $n \geq 2$ 为整数。考虑数字 $0,1, \ldots, n$ 的所有循环排列；排列的 $n+1$ 轮次被认为是相等的。如果对于任何四个不同的数字 $0 \leq a, b, c, d \leq n$ 且 $a+c=b+d$ 来说，圆形排列被称为美丽的，并且和弦连接数字 $a$ 和 $c$ 不与和弦连接数字 $b$ 和 $d$ 相交。令$M$ 为$0,1,\ldots,n$ 的漂亮排列的数量。令 $N$ 为正整数对 $(x, y)$ 的数量，使得 $x+y \leq n$ 且 $\operatorname{gcd}(x, y)=1$。证明$$M=N+1$$(俄罗斯)