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 1 of 5: Classify beautiful rings as linear or nonlinear

Previous step Next step

In plain words

The induction depends only on where the largest label can be inserted after deleting it.

\text{A ring is linear if its labels form an arithmetic progression modulo }n+1

Detailed analysis

Call a labelling of the equally spaced points a ring, and call it linear if the labels around the circle form an arithmetic progression modulo $n+1$ . Delete the point labelled n to obtain a ring on $\{0,\ldots,n-1\}$ . We will prove that every nonlinear ring has exactly one beautiful extension by n, while every linear ring has exactly two.