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 5 of 5: Telescope the recurrence

Previous step Next step

In plain words

The totient recurrence counts exactly the coprime ordered pairs grouped by their sum.

M_n=1+\sum_{s=2}^{n}\varphi(s)=N+1

Detailed analysis

For $n=2$ , $M_2=2$ . Summing $M_s=M_{s-1}+\varphi(s)$ for $s=3,\ldots,n$ gives $M_n=1+\sum_{s=2}^n\varphi(s)$ . For each $s$ , the ordered positive pairs $(x,y)$ with $x+y=s$ and $\gcd(x,y)=1$ are counted by $\varphi(s)$ , so $N=\sum_{s=2}^n\varphi(s)$ . Therefore $M=N+1$ .