Let $n\geq 3$ be an integer, and consider a circle with $n+1$ equally spaced points marked on it. Consider all labelings of these points with the numbers $0,1,\dots, n$ such that each label is used exactly once; two such labelings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labeling is called beautiful if, for any four labels $a<b<c<d$ with $a+d=b+c$, the chord joining the points labeled $a$ and $d$ does not intersect the chord joining the points labelled $b$ and $c$.
Let $M$ be the number of beautiful labelings and let $N$ be the number of ordered pairs $(x,y)$ of positive integers such that $x+y\leq n$ and $\gcd(x,y)=1$. Prove that $M=N+1$.
I think this is a very hard problem for the IMO. You can find discussion of it here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=3154371
I don't see a solution there.
my idea: we can $$N(n)-N(n-1)=\varphi(n)$$ and This problem only prove $$M(n)-M(n-1)=N(n)-N(n-1)$$
Best Answer
Summary: In part 1, we explicitly construct the codes with arithmetic sequences modulo something relatively prime. In part 2, we show that there are not many ways to add $n$ to an existing code of length $n$, so we cannot get more than the codes of part 1.
There are at least that many arrangements: For each $a,b < n$ relatively prime and $a+b \ge n$, you can construct a circular code of length $n$ where 0 has left neighbour $a$ and right neighbour $b$, by writing $bk \mod a + b$ for $k=0, 1, \dots, a+b-1$ and then removing numbers larger than $n-1$.
It is easy to see that these codes work because the sum condition is equivalent to the sum condition modulo $a + b$ for these small numbers. Therefore, we just have to understand that the arrangement $0,1, \dots, N-1$ has no crossing diagonals of equal vertex sum, but this is obvious because you move in opposite directions from both vertices to get to the other vertices. (In particular, the pattern of the diagonals of equal sums are always the same simple non-crossing matching that partitions the circle into stripes.)
It is also clear that this gives the required number by looking at the "new" pairs with $a+b=n$ which clearly gives $\phi(n)$ because $a$ determines $b$.
There are not more arrangements: We prove by induction that an arrangement of the type seen in 1 of length $n$ has at most two children (i.e. arrangements that reduce to the given one when $n$ is removed) when the neighbours of 0 sum to $n$ and it has at most one child when the neighbours do not sum to $n$.
This will imply that from length $n$ to length $n+1$, the number of arrangements can grow at most by $\phi(n)$.
Proof of the $a + b= n$ -case: Since the sum of the neighbours of 0 is $n$, and $n+0=n$, we have to put $n$ next to 0. There are only two possibilities to do so.
Proof of the $a+b > n$- case: Now, we are not allowed to put $n$ next to 0 because $a+b =n + x$ and the two diagonals would intersect each other. Any legal placement of $n$ will also give a legal arrangement of length $n-1$ if we remove 0 and substract 1 from each number. The only way that there could be two possibilities is if $n$ is placed on both sides of $1$ (which plays the role of 0 in the smaller arrangement). But the diagonal that connects 1 and $n-1$ will force $n$ to be on the same side as the original 0, so there is at most one possibility that works.
Note that any code remains beautiful when $n$ is taken away, so all codes arise by adding $n$ to a previous code.
Therefore we have found $\sum_{k=1}^{n-1} \phi(k)$ arrangements of length $n$ and we have shown that the number of arrangements grows at most by $\phi(n)$ when going from length $n$ to $n+1$.