Problem: Let $n \ge 3$ be an integer, and consider a circle with $n + 1$ equally spaced points marked on it.
Consider all labellings of these points with the numbers
$0, 1, \dots , n$ such that each label is used exactly once;
two such labellings are considered to be the same if
one can be obtained from the other by a rotation of the circle.
A labelling is called \emph{beautiful} if, for any four labels $a < b < c < d$ with $a + d = b + c$,
the chord joining the points labelled $a$ and $d$
does not intersect the chord joining the points labelled $b$ and $c$.
Let $M$ be the number of beautiful labellings,
and let $N$ be the number of ordered pairs $(x, y)$ of positive integers
such that $x + y \le n$ and $\gcd(x, y) = 1$.
Prove that $M = N + 1$.

\end{enumerate}

Solution: First, here are half of the beautiful labellings up to reflection for $n = 6$,
just for concreteness.

\begin{center}
\begin{asy}
size(9cm);

pair g(int n) { return dir(90 + 60*n); }

picture ring(int a, int b, int c, int d, int e, real r) {
  picture pic = new picture;
  draw(pic, unitcircle);
  draw(pic, dir(90)--dir(r), dotted+blue);
  draw(pic, g(a)--g(e), dotted+blue);
  draw(pic, g(b)--g(d), dotted+blue);
  dot(pic, "$0$", dir(90), dir(90));
  dot(pic, "$1$", g(a), g(a));
  dot(pic, "$2$", g(b), g(b));
  dot(pic, "$3$", g(c), g(c));
  dot(pic, "$4$", g(d), g(d));
  dot(pic, "$5$", g(e), g(e));
  dot(pic, "$6$", dir(r), dir(r), red);
  return pic;
}

add(shift(3,6)*ring(2,4,5,1,3,0));
add(shift(0,6)*ring(3,1,4,2,5,240));
add(shift(3,3)*ring(4,2,5,3,1,0));
add(shift(0,3)*ring(2,3,4,5,1,240));
add(shift(3,0)*ring(1,2,3,4,5,50));
add(shift(0,0)*ring(1,2,3,4,5,130));
\end{asy}
\end{center}

Abbreviate ``beautiful labelling of points around a circle'' to ring.
Moreover, throughout the solution we will allow degenerate
chords that join a point to itself;
this has no effect on the problem statement.

The idea is to proceed by induction in the following way.
A ring of $[0,n]$ is called \emph{linear}
if it is an arithmetic progression modulo $n+1$.
For example, the first two rings in the diagram
and the last one are linear for $n = 6$,
while the other three are not.

Of course we can move from any ring on $[0,n]$
to a ring on $[0,n-1]$ by deleting $n$.
We are going to prove that:
\begin{itemize}
  \ii Each linear ring on $[0,n-1]$ yields exactly two
  rings of $[0,n]$, and
  \ii Each nonlinear ring on $[0,n-1]$ yields exactly one
  rings of $[0,n]$.
\end{itemize}
In light of the fact there are obviously $\varphi(n)$ linear rings on $[0,n]$,
the conclusion will follow by induction.

We say a set of chords (possibly degenerate) is \emph{pseudo-parallel}
if for any three of them, one of them separates the two.
(Pictorially, one can perturb the endpoints along the circle
in order to make them parallel in Euclidean sense.)
The main structure lemma is going to be:
\begin{lemma*}
  In any ring, the chords of sum $k$
  (even including degenerate ones) are pseudo-parallel.
\end{lemma*}
\begin{proof}
  By induction on $n$.
  By shifting, we may assume that one of the chords is $\{0,k\}$
  and discard all numbers exceeding $k$; that is, assume $n = k$.
  Suppose the other two chords are $\{a, n-a\}$ and $\{b, n-b\}$.
  \begin{center}
  \begin{asy}
    size(5cm);
    draw(unitcircle);
    pair O = dir(210);
    pair N = dir(330);
    draw(O--N);
    pair A1 = dir(100);
    pair A2 = dir(140);
    pair B1 = dir( 80);
    pair B2 = dir( 40);
    draw(A1--A2);
    draw(B1--B2);
    pair U = dir(200);
    pair V = dir(340);
    draw(U--V, blue);
    pair X = dir(250);
    pair Y = dir(310);
    draw(X--Y, red);
    draw(O--X, blue+dashed);
    dot("$a$", A1, A1);
    dot("$b$", B1, B1);
    dot("$n-a$", A2, A2);
    dot("$n-b$", B2, B2);
    dot("$u$", U, U, blue);
    dot("$v$", V, V, blue);
    dot("$u+v$", X, X, red);
    dot("$n-(u+v)$", Y, Y, red);
    dot("$0$", O, O);
    dot("$n$", N, N);
  \end{asy}
  \end{center}
  We consider the chord $\{u,v\}$ directly above $\{0,n\}$, drawn in blue.
  There are now three cases.
  \begin{itemize}
      \ii If $u+v = n$, then delete $0$ and $n$
      and decrease everything by $1$.
      Then the chords $\{a-1, n-a-1\}$, $\{b-1, n-b-1\}$, $\{u-1, v-1\}$
      contradict the induction hypothesis.

      \ii If $u+v < n$, then search for the chord
      $\{u+v, n-(u+v)\}$.
      It lies on the other side of $\{0, n\}$
      in light of chord $\{0,u+v\}$.
      Now again delete $0$ and $n$ and decrease everything by $1$.
      Then the chords $\{a-1, n-a-1\}$, $\{b-1, n-b-1\}$, $\{u+v-1, n-(u+v)-1\}$
      contradict the induction hypothesis.
      %% MAX LU: this case can't occur at all;
      %% nowhere to put $n-u$ without $0+n = u+(n-u)
      %% and $v + (n-(u+v))$.

      \ii If $u+v > n$, apply the map $t \mapsto n-t$ to the entire ring.
      This gives the previous case as now $(n-u)+(n-v) < n$.
      \qedhere
  \end{itemize}
\end{proof}

Next, we give another characterization of linear rings.
\begin{lemma*}
  A ring on $[0,n-1]$ is linear if and only if the point $0$
  does not lie between two chords of sum $n$.
\end{lemma*}
\begin{proof}
  It's obviously true for linear rings.
  Conversely, assume the property holds for some ring.
  Note that the chords with sum $n-1$ are pseudo-parallel and encompass every point,
  so they are \emph{actually} parallel.
  Similarly, the chords of sum $n$ are \emph{actually} parallel
  and encompass every point other than $0$.
  So the map
  \[ t \mapsto n-t \mapsto (n-1)-(n-t) = t-1 \pmod n \]
  is rotation as desired.
\end{proof}

\begin{lemma*}
  Every nonlinear ring on $[0,n-1]$ induces exactly one ring on $[0,n]$.
\end{lemma*}
\begin{proof}
  Because the chords of sum $n$ are pseudo-parallel,
  there is at most one possibility for the location $n$.

  Conversely, we claim that this works.
  The chords of sum $n$ (and less than $n$) are OK by construction, so
  assume for contradiction that there exists $a,b,c \in \{1,\dots,n-1\}$
  such that $a + b = n + c$.
  Then, we can ``reflect'' them using the (pseudo-parallel)
  chords of length $n$ to find that $(n-a) + (n-b) = 0 + (n-c)$,
  and the chords joining $0$ to $n-c$ and $n-a$ to $n-b$ intersect,
  by definition.
  \begin{center}
  \begin{asy}
    size(5cm);
    draw(unitcircle);
    draw(dir(140)--dir(220), blue+dotted);
    draw(dir(250)--dir(110), blue+dotted);
    draw(dir(340)--dir(20), blue+dotted);
    draw(dir(60)--dir(300), blue+dotted);
    draw(dir(220)--dir(60), lightred);
    draw(dir(340)--dir(110), lightred);
    draw(dir(140)--dir(300), orange+dashed);
    draw(dir(250)--dir(20), orange+dashed);
    dot("$0$", dir(140), dir(140));
    dot("$n$", dir(220), dir(220), red);
    dot("$n-a$", dir(250), dir(250));
    dot("$n-c$", dir(300), dir(300));
    dot("$b$", dir(340), dir(340));
    dot("$n-b$", dir(20), dir(20));
    dot("$c$", dir(60), dir(60));
    dot("$a$", dir(110), dir(110));
  \end{asy}
  \end{center}
  This is a contradiction that the original numbers on $[0,n-1]$ form a ring.
\end{proof}

\begin{lemma*}
  Every linear ring on $[0,n-1]$ induces
  exactly two rings on $[0,n]$.
\end{lemma*}
\begin{proof}
  Because the chords of sum $n$ are pseudo-parallel,
  the point $n$ must lie either directly to the left or right of $0$.
  For the same reason as in the previous proof, both of them work.
\end{proof}