Problem 6

Let

n\ge2

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,\ldots,n

such that each label is used exactly once; two such labellings are considered the same if one can be obtained from the other by a rotation of the circle. A labelling is called 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

Step 4 of 5: Count extensions of nonlinear and linear rings

Previous step Next step

In plain words

A nonlinear ring has one insertion position for n, while a linear ring has the two positions adjacent to 0; the linear rings are counted by Euler's totient.

L_{n-1}=\varphi(n),\qquad M_n=M_{n-1}+\varphi(n)

Detailed analysis

For a nonlinear ring, pseudo-parallel n-chords leave at most one possible position for n; inserting it there is beautiful, since any forbidden crossing would reflect across the n-chords to a forbidden crossing already present. For a linear ring, n must be immediately clockwise or counter-clockwise from 0, and both insertions are beautiful. A linear ring on $\{0,\ldots,n-1\}$ is determined by a step coprime to n, so there are $\varphi(n)$ of them. If $L_{n-1}$ is their number, then $M_n=M_{n-1}+L_{n-1}=M_{n-1}+\varphi(n)$ .