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 2 of 5: Structural lemma: equal-sum chords do not cross

Previous step Next step

In plain words

The beautiful condition forces all chords whose endpoint labels have the same sum into one parallel-like family.

\text{chords of a fixed sum are pseudo-parallel}

Detailed analysis

Allow degenerate chords and call a family pseudo-parallel if, among any three, one separates the other two. By induction on the number of labels, the chords of any fixed sum k are pseudo-parallel: if three such chords could fail this property, choose one as the reference chord and, according as the endpoints of a fourth chord sum to less than, equal to, or greater than k, delete the extreme labels and subtract 1; the resulting three chords contradict the induction hypothesis (in the last case apply the reflection $t\mapsto n-t$ first). Thus equal-sum chords never cross in the forbidden way.