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 3 of 5: Characterize linear rings by the n-chords

Previous step Next step

In plain words

The n-chords cover every point except 0; whether 0 lies between them determines whether the labels are an arithmetic progression.

0\text{ lies between two n-chords}\Longleftrightarrow\text{the ring is nonlinear}

Detailed analysis

In a ring on $\{0,\ldots,n-1\}$ , the n-chords join the complementary labels $a$ and $n-a$ and cover every point except 0. By pseudo-parallelism they are genuinely parallel. If 0 lies between two of them, it is the unique nonlinear case. If 0 lies on the same side of all of them, the n-chords and the (n-1)-chords together show that the map $t\mapsto n-1-t\pmod n$ is a rotation; hence the ring is linear. This proves the characterization.