1. There are exactly $N+1$ ordered pairs of positive integers $(a,b)$ satisfying these three conditions: (i) $a,b\leq n$ (ii) $a+b>n$ (iii) $\gcd(a,b)=1$

Let us call an ordered pair $(a,b)$ good if it satisfies all three conditions above, and bad otherwise. Define the type of a labeling as the ordered pair $(a,b)$, where $a$ immediately follows $0$ and $b$ immediately precedes $0$ when going clockwise, like this: $\ldots, b, 0, a,\ldots$, and define the position of an integer $i$ in a labeling by starting at $0$ (at position 0) and go clockwise i.e. $a$ is in position $1$, and $b$ is in position $n$. We denote the position of an integer $i$ by $p(i)$. 2. If $(a,b)$ is bad then there are no beautiful labelings of type-$(a,b)$

3. If $(a,b)$ is good then there is exactly one beautiful labeling of type-$(a,b)$

Thus we have $M=N+1$.

We claim that beautiful labelings can be characterized as follows: Let $x,y$ be relatively prime positive integers with $x\le y\le n$. Then a beautiful labeling is of the form $A_1,A_2,\ldots,A_x$ wrapped around the circle, where $A_i$ consists of the nonnegative integers $k$ at most $n$ with $y\mid k-xi$ sorted in descending order. Notably, this always ends in $0$, so we count each labelling once. For example, if $x=2,y=5,n=16$, then this becomes \[12,7,2,14,9,4,16,11,6,1,13,8,3,15,10,5,0.\]Now, suppose that $a+d=b+c$ and that $a,b,c,d$ belong to the blocks $A_p,A_q,A_r,A_s$ respectively. Then, we know that $a+d\equiv b+c\pmod y\implies x^{-1}(a+d)\equiv y^{-1}(b+c)\pmod y\implies p+s\equiv q+r\pmod y$. It is easy to see now that a chord between $A_p$ and $A_s$ cannot intersect a chord between $A_q$ and $A_r$ if $p\ne q,r$. Otherwise, assume that $p=q,r=s$. It is also easy to see now that by the descending property of the $A_i$ blocks that the case of $p=q,r=s$ does not cause a chord intersection, so such labelings are beautiful. Now, let's show that these are the only labelings that are beautiful. We proceed using induction on $n$, with the base case of $n\le 3$ clear. In particular, given $x$ and $y$, the labeling is unique, with the first number being the largest number at most $n$ that is $x\pmod y$ and the last number before $0$ being $y$. For the inductive step, note that in a beautiful labeling with $n=k$, removing $k$ from the circle or removing $0$ from the circle and decrementing every number in the circle results in a beautiful labeling with $n=k-1$. Hence, all we need to do is show that the only ways of beautifully inserting $k$ into a beautiful labeling with $n=k-1$ are the ways described in our characterization. If $1$ is the first number in the sequence, then the sequence must be $1,2,\ldots,k-1,0$. There are clearly only two places to insert $k$: in the beginning or right before the $0$. It is easy to see that both of these labelings are accounted for in our characterization. If $k$ is inserted right before $1$, then after removing $0$ and decrementing, we have that $y=k-1$. The labeling is now uniquely determined by the number after $0$, as just the permutation of $1,2,\ldots,k-1$ of $\{\alpha i\}\pmod{k-1}$ followed by $0$. It is easy to see that after incrementing and putting back $0$, the position of the $0$ makes it so that this labeling is a part of our characterization. Now, suppose that $k$ is not inserted right before $1$ and that $1$ is not the first number in the sequence. Let $y'+1$ right before $1$. If we remove $0$ and decrement, this $y'$ uniquely determines the position of $k-1$ given the new positions of $0,1,\ldots,k-2$ (in the beginning of the block of numbers that are $k-1\pmod y'$. Increasing everything by $1$ and putting $0$ back at the end of its block before decrementing, we obtain a characterized labeling. The only complication that may arise is if $k$ and $0$ are inserted into the same spot under this. But it is easy to see that if the new sequence ends $0,k$ we obtain the characterized labeling for the old $x$ and $y$ and $n=k$, and if the new sequence ends $k,0$ we obtain the characterized labeling for the old $x$ and $y=n=k$. Finally, by our argument above the total number of beautiful labelings is $\sum_{i=1}^n\varphi(i)$, and it is easy to see that this is $N+1$, as desired.

We start by constructing $N+1$ $n$-beautiful labelings. Set the circumference of the circle to 1 and let $\alpha$ be an irrational number. Place point $k$ a distance $k\alpha$ counterclockwise around the circle from 0. Then all the $s$-chords (for each $s$) are parallel, so they do not meet, and we obtain a beautiful labeling. [asy][asy] unitsize(75); pair pp(int k, real a) { return rotate(360 * a * k + 90, origin) * (1, 0); } int n = 12, s = 12; real a = (1+sqrt(5))/2; draw(unitcircle); for (int i = 0, j = s; i <= j; i += 1, j -= 1) { if (j <= n) draw(pp(i, a)--pp(j, a), heavycyan); } for (int i = 0; i <= n; i += 1) { pair P = pp(i, a); dot(P); label((string)i, P, dir(P)); } for (int i = 0; i < n; i += 1) { draw(pp(i, a)--pp(i+1, a), dotted); } [/asy][/asy] By constraining $\alpha$ to $(0, 1)$, we obtain $N+1$ beautiful $n$-labelings, depending on the location of $\alpha$ in the Farey sequence of order $n$. Let us show that they are all different. Construct a nonnegative integer sequence $\alpha_1, \dots, \alpha_n$ as follows: If the counterclockwise arc $k \to k+1$ does not include 0, set $\alpha_{k+1} = \alpha_k$. If the counterclockwise arc $k \to k+1$ includes 0, set $\alpha_{k+1} = \alpha_k + 1$. Then $\alpha_k = \lfloor k\alpha \rfloor$, so the $N+1$ $\alpha_1, \dots, \alpha_n$ sequences are all distinct. But the sequence is an intrinsic property of the labeling and not of $\alpha$, so the $N+1$ labelings must all be different. Now, we show that these are all the $n$-beautiful labelings. Note that an $n$-beautiful labeling can be converted into an $(n - 1)$-beautiful labeling by (i) deleting $n$ or (ii) deleting $0$ and decrementing the remaining numbers by 1. Call a group of three chords aligned if one of them separates the other two, and call a group of any size aligned if any three of them are aligned. Lemma. In any beautiful labeling, the $s$-chords are aligned. Proof. Induction on $n$. If $s < n$, then no $s$-chord contains $n$, and we may delete $n$ and use the inductive hypothesis. If $s > n$, then no $s$-chord contains $0$, and we may delete $0$, decrement, and use the inductive hypothesis. Suppose $s = n$. The chords $(1, n - 1), \dots, (n - 1, 1)$ must all be aligned by inductive hypothesis. Suppose chord $(0, n)$ is not aligned with them. Then, it follows that $0$ and $n$ must be adjacent on the circle (otherwise there would be an $n$-chord on either side of $(0, n)$, forcing it to be aligned). Let $a$ and $b$ be the numbers adjacent $0$ and $n$ respectively. Suppose $a + b < n$. Then the chords $(a, b)$ and $(0, a+b)$ must not meet, which is impossible. Similarly if $a + b > n$ there is an issue with $(a, b)$ and $(n, a+b-n)$. (This is basically JMO 2012/4.) Thus $a + b = n$ and $(0, n)$ is indeed aligned. $\square$ Now we return to the main problem, proceeding by induction on $n$. Consider an $(n-1)$-beautiful labeling where $a$ and $b$ are the numbers adjacent to $0$. Then considering the $n$-chords, If $a + b \neq n$, there is one potential location for $n$. If $a + b = n$, there are two potential locations for $n$. Consider a labeling with $a+b = n$. Let $x_0, \dots, x_{n-1}$ be the numbers around the circle in order, with $x_0 = 0$. [asy][asy] unitsize(75); pair pp(int k, real a) { return rotate(360 * a * k + 90, origin) * (1, 0); } int n = 12; real a = (1+sqrt(5))/2; draw(unitcircle); for (int i = 0, j = n; i <= j; i += 1, j -= 1) { if (j <= n) draw(pp(i, a)--pp(j, a), heavycyan); } for (int i = 0, j = n+1; i <= j; i += 1, j -= 1) { if (j <= n) draw(pp(i, a)--pp(j, a), blue); } for (int i = 0; i <= n; i += 1) { pair P = pp(i, a); dot(P); label((string)i, P, dir(P)); } [/asy][/asy] Since the $(n-1)$-chords are aligned, there exists a $k$ with \[x_r + x_{k-r} = n - 1 \equiv -1 \pmod{n} \quad \forall r\](indices mod $n$). Since chord $(0, 0)$ is aligned with the $n$-chords by hypothesis $a+b = n$, there exists an $\ell$ with \[x_r + x_{\ell-r} \equiv 0 \pmod{n} \quad \forall r\]and combining the relations, \[x_{r + \lambda} \equiv x_r + 1 \pmod{n} \quad \forall r\]for $r = \ell - k$. This forces $\gcd(n, \lambda) = 1$. There are $\varphi(n)$ possible choices of $\lambda \pmod{n}$, and by inductive hypothesis there are $\varphi(1) + \dots + \varphi(n-1) + 1$ $(n-1)$-beautiful labelings. Thus the number of $n$-beautiful labelings is at most \[\big(\varphi(1) + \dots + \varphi(n-1) + 1\big) + \varphi(n) = N+1\]as desired.

After many many hours, here it finally is. I would greatly appreciate if someone could check my solution, as it is possible there is some small flaw that makes it fall apart.

. For reference, here are all the possibilities for $n=3$ (modulo reflection). We will cite this often for the base case.

We start with an important lemma. Lemma 1 The set of chords of the form $\{a,b\}$ (where potentially $a=b$) such that $a+b=\chi$ for some fixed $\chi$ is self-parallel.

The proof of the lemma leads to an algorithm that generates all the valid configurations for $n$ starting with the ones for $n-1$.

from before. By doing this for all labellings with $n-1$, we claim we get all labellings for $n$.

The key claim is the following. Claim 3 For every pair $(a,b)$ with $a+b>n$, $a,b\le n$, and $\gcd(a,b)=1$, there is a unique valid labelling on $0,\ldots,n$ such that $a,0,b$ are consecutive. Furthermore, every valid labelling is of this form.

Of course, one could finish the problem here by simply counting the number of pairs $(a,b)$ that satisfy the condition of claim 3, but here is a slightly more motivated way to finish.

Remarks The finish suggests that there is probably no nice bijection from the solutions to labellings, as at each step some labellings expand to two symmetric labellings and the others just stay. We would have to break symmetry to assign different solutions to the two symmetric labeling. Also, the only property of gcd that we used was that $\gcd(n-b,b)=\gcd(b,n)$. This kind of suggests that this could be some sort of model for executing the Euclidean algorithm, but I'm not really sure what I even mean.

Note: If $f_n(a)$ is the number of beautiful labellings for a given $n$, such that $a$ is adjacent to zero, and lies in the clockwise direction with respect to it, then, $f_n(a) = \phi(a)$ for $1 \leq a \leq n$.

Hope this isn't fake . The first step will be to find $N+1$ beautiful labellings. The second will then be to show that they are the only ones. In the following, we will let "left" be counterclockwise and "right" be clockwise.

$\square$

In this solution, we will denote clockwise as right, and counterclockwise as left. Furthermore, denote the position of 0 as 0, and positions increase by 1 mod n when going to the right. Claim 1: There are $\phi(n)$ beautiful labelings with $n\ge 2$ at position 1. Proof: To show that there are at least $\phi(n)$, just consider the arrangement $0,n,a,2a,\ldots (n-1)a$, where $a$ is relatively prime to $n$, and all numbers are taken $\pmod n$. It is not hard to verify that this works. Now, we show this is the only class of solutions. Given 2 numbers $a,b$ in the arrangement, note that if $a+b\pmod n$ is between them (i.e. on the arc between them which doesn't include $0,n$), then the segments formed by $(a,b)$ and $(a+b\pmod n, 0\text{ or }n)$ will intersect, contradicting the problem statement. Now, suppose the number at position 2 is $a$, and at position $n$ is $b$. We have all nonzero residues between $a$ and $b$, so we must have $a+b\equiv 0\pmod n\implies b\equiv a(n-1)\pmod n$. Now, if $\gcd(a,n)\neq 1$, consider the number $c$ closest to $0$ such that $\gcd(\gcd(a,n),\gcd(c,n))=1$. Then, as the arc between $0$ and $c$ contains no numbers satisfying this property. So, the number $a+c\pmod n$ must be between $c$ and $a$, which is a contradiction. Therefore, we know $a$ and $n$ are relatively prime. Now, simply note that $(k+1)a\pmod n$ must have a higher position than $ka\pmod n$, since it can't be between $a$ and $ka$. So, $a,2a,\ldots (n-1)a$ appear in that order, implying that the aforementioned labeling is the only one. Claim 2: Given a beautiful labeling with $x$ at position 1, there is exactly one way to insert the numbers between $x+1$ to $n$ into the labeling. Proof: Once again, we start with a construction. In the given labeling, each number between $0$ and $x-1$ appear exactly once, and we will interpret them as residue classes. All numbers with residue $r\pmod x$ will be sorted in ascending order and be placed in a contiguous block following $r$. For example, if the initial labeling is $0,3,1,2$, with $n=10$, then we will fill in like: $0,3,6,9,1,4,7,10,2,5,8$. To see that this works, suppose the contrary, namely $a+b=c+d$ and $ab,cd$ intersect. If they leave remainders $a',b',c',d'$, note that $ab,cd$ intersecting is equivalent to $a'b',c'd'$ intersecting, since all residues occur in contiguous blocks. We know that the beautiful labeling, from Claim 1, must follow the structure: $0,x,a,2a,\ldots,(x-1)a$, with $\gcd(a,x)=1$, so we can write $a',b',c',d'$ as $mx,(s-m)x,nx,(s-n)x$. WLOG $m<n$, the construction tells us that $a',c',d',b'$ occur on the circle in that order, so the chords don't intersect - contradiction. Therefore, this is a valid construction. To show that it is unique, we induct on $n$. The base case is trivial, so suppose that $n-1$ has unique labeling, which, of course, satisfies the above format. Suppose that $n\equiv r\pmod n$, where $r<n$. The chord $(0,n)$ cannot intersect $(x,n-x)$, so $n$ must be to the right of $n-x$. However, $(r+1,n-1)$ cannot intersect $(n,r)$, and these two conditions force $n$ to be between $n-x$ and $r+1$, as desired. Finally, suppose that $1$ is in position 1. Then, $x+1$ must be to the right of $x$, or else the chords $(0,x+1)$, $(1,x)$, so the arrangement must be $0,1,\ldots, n$. So, to compute $M$, we just do casework on what number is in position 1. Using Claim 2, if it is $x$, then there are $\phi(x)$ beautiful labelings. Therefore, $M=1+\phi(2)+\phi(3)+\ldots+\phi(n)$. $N$ is trivially $\phi(2)+\ldots+\phi(n)$, so we are done.

Nice problem, but sadly this has taken me too long to solve Notice that $N = \sum_{i = 2}^{n} \varphi(i)$. It suffices to prove that \[ M = \sum_{i = 1}^{n} \varphi(i) \]We shall proceed by induction. We'll consider two types of cases: Call a labelling $\textbf{unique}$ if it forms an arithmetic progression modulo $n$ when ordered clockwise, and otherwise call it non-$\textbf{unique}$. Notice that there are exactly $\varphi(n)$ unique labelling. So, we just need to prove that from $n \to n + 1$, each non-unique labelling gives exactly 1 configuration and each unique labelling gives 2 configuration. Call a set of lines "almost parallel" if we can move the points without switching the order of the points such that the set of lines are indeed parallel. $\textbf{Claim 01.}$ Any three lines of sum $k$ are almost parallel. $\textit{Proof.}$ Suppose otherwise, there exists a set of three lines such that they are not almost parallel: This means that if $a,b,c,d,e,f$ are in clockwise order, $(a,b), (c,d), (e,f)$ are connected. Now, we can wlog that $(0,k)$ is one among those, cause otherwise we could just switch one of the lines with $(0,k)$. Now, notice that we could suppose that it is $0,k,k-b-a,a + b, k - a, a$ in order. (The other cases are similarly approached). Then, by considering $(k - b, 0), (k - a - b, a)$ and $(a,k),( k - b, a + b)$, we get that $k - b$ must be in between $k$ and $k - b - a$. Similarly, by considering $(k - b, b)$ and $(k,0)$ and $(k - a - b, b), (k - a,0)$, we get that $b$ must be in between $a+b$ and $k - a$. Then consider $(k - b,k-a)$ and $(k - a - b, k)$, this contradicts. $\textbf{Claim 02.}$ The configuration of $[0,n-1]$ is $\textbf{unique}$ if and only if $0$ is not between two chords with sum $n$. $\textit{Proof.}$ The only if part is trivial by hand check. Now, it suffices to prove the if part. Suppose $0$ is between two chords with sum $n$. Notice that the chords with sum $n-1$ and $n$ are almost parallel. Therefore, we could consider the map \[ a \to n - a - 1 \to a + 1 \]Since we assume that the configuration is $\textbf{unique}$, this is essentially a rotation. Therefore, by rotation if necessary, we could prove that both points beside $0$ must be eventually connected (otherwise, rotate, and eventually the value of the point will be less than the sum desired, and hence had to be connected.) Therefore, the two chords we have that is beside $a$ (after a number rotation), must be $a - k$ and $a + k$. But after $a$ number of rotations, the value of the chords must have sum $2a$. Therefore, the other end of both chords must be $a + k$, and $a - k$, a contradiction. $\textbf{Claim 03.}$ The $\textbf{unique}$ configuration of $[0,n-1]$ produce 2 possible configuration for $[0,n]$. $\textit{Proof.}$ By Claim 01 and Claim 02, there are only 2 possible places we can put $n$: left or right of $n$. We will prove that both of them work. Suppose there is a configuration such that chords $(n,a - b), (n - b,a)$ intersect where $a > b$, and $a,b < n$. Since chords with sum $n$ are almost parallel, we then have $(0, n - a + b), (b, n - a)$ intersect as well, contradicting the assumption of $[0,n-1]$ being a unique configuration. $\textbf{Claim 04.}$ The non-$\textbf{unique}$ configuration of $[0,n-1]$ produce 1 possible configuration for $[0,n]$. $\textit{Proof.}$ By Claim 02, we know that there are two chords of sum $n$ beside both direction of $0$. Therefore, $n$ cannot be in the same side with $0$ with respect to the center of the circle. Hence, there are only $1$ possible placement for $n$, which is the opposite side of the arc. To prove that this is possible, just mimic the proof for $\textbf{Claim 03.}$.

Solved with eisirrational. It is not hard to show \[N+1=\varphi(1)+\varphi(2)+\cdots+\varphi(n).\]Before we tackle $M=N+1$, we need some preliminary results. Say a chord is an $m$-chord if the sum of its endpoints is $m$. Claim: Given any three $m$-chords, there is a line intersecting all of them. Proof. Assume not. Note that we can replace one of the three $m$-chords with $(0,m)$ while still violating the claim hypothesis.

Thus it suffices to prove the number of labelings of $0$, $1$, $\ldots$, $n-1$ with $0$ on an edge slice is $\varphi(n)$. Place $n$ in the circle as shown in the above diagram, so the task is to count the number of beautiful labelings of $0$, $1$, $\ldots$, $n$ with $n$ directly clockwise to $0$. Let $p(k)$ be the distance between $0$ and $k$; for instance, in the above diagram, $p(1)=3$. In fact, $p(n-1)$ determines everything. Claim: $p(n-k)\equiv kp(n-1)\pmod n$ for all $k$. (Note modulo $n$, not $n+1$.) Proof. The result is by induction on $k$; for the base cases $k=0,1$ there is nothing to prove. Since all points except $n/2$ (which we have already located) lie on an $n$-chord, and all points except $n$ and $(n-1)/2$ (which we have already located) lie on an $(n-1)$-chord, we can check that the quantities $p(i)+p(n-i)$ and $p(i)+p(n-1-i)$ are fixed modulo $n$ for all $i$. Hence $p(n-1-i)-p(n-i)$ is fixed modulo $n$ for all $i$. Taking $i=0$ shows that this always equals $p(n-1)$, and so $p(n-1-k)-p(n-k)\equiv p(n-1)\pmod n$, as desired. $\blacksquare$ But $p(k)$ is distinct for all $k$, so $p(n-1)$ must be relatively prime to $n$. In particular, the labeling is unique, thus the number of such labelings is $\varphi(n)$. This completes the proof.

Hi everyone, I feel really dumb posting this, but I am having a hard time making the problem statement work for $n = 4$. I think I have found $10$ such beautiful labelings: $0, 4, 1, 2, 3$ $0, 1, 2, 3, 4$ $0, 4, 2, 1, 3$ $0, 2, 4, 1, 3$ $0, 2, 1, 3, 4$ $0, 4, 3, 1, 2$ $0, 3, 1, 4, 2$ $0, 3, 1, 2, 4$ $0, 4, 3, 2, 1$ $0, 3, 2, 1, 4$ However, there are only $5$ ordered pairs $(x, y)$ satisfying the problem's conditions: $(1, 1), (1, 2), (2, 1), (1, 3), (3, 1)$. So $M = 10$ and $N = 5$. What am I missing?

goodar2006 wrote: $0, 2, 1, 3, 4$ $1+4=2+3$, and the corresponding two chords intersect.

Got it! For some reason I was under the impression that $a + d\le n$, perhaps because of the second half of the question. Thanks!

Beautiful problem.

Firstly, note that $N+1 = \phi(1) + \ldots + \phi(n)$. This can easily be proved by considering the ordered pairs $(x,y)$ satisfying $x+y = k$ and $\gcd(x,y) = k$ for $k \leq n$. Firstly, we characterise all beautiful labellings.

We prove that the labellings described above are precisely all such beautiful labellings. For now, consider the labelling in a clockwise direction and relax it to a line. Let $t$ be positioned directly adjacent to $0$, and define the sets as previous. Lemma 1: For each $k$, the elements of $S_k$ occur in the labelling in increasing size order (but they are not necessarily adjacent). Proof: Suppose contrariwise, then there exists $x$, $y$ satisfying $x-y = t$ with $y$ occuring after $x$. But then this means that $x+0 = y +t$ which contradicts the fact that these segments don’t intersect. Hence we are done. Lemma 2: If $x$ occurs before $y$, and $x \not\equiv y \pmod t$ then $x+t$ occurs before $y+t$ in the labelling for $x,y \leq n-t$. The converse also holds. Proof: Suppose contrariwise. But then we obtain that the segment joining the integers $y+t$ and $x$ intersects with the segment joining the integers $x+t$ and $y$, which is a contradiction. Hence we are done. Claim 1: Each beautiful labelling can be characterised by a permutation of all the $S_i$’s with $S_0$ occurring first. Proof: We first prove that this is indeed the case for $S_0$, and then the proof is identical for the other sets. Suppose the contrary. Then consider the first positive integer $y$ that occurs after a term of $S_0$. By Lemma 1 we obtain that $y < t$. The first $k+1$ terms of the labelling look like the following: $0, t, 2t, …, kt, y$, with $(k+1)t \in S_0$, with $k \geq 1$ (otherwise there is nothing to prove). Firstly, we have that $y$ occurs before $(k+1)t$ in the labelling by assumption. Now, the term $(k+1)t - y$ occurs strictly before $(k+1)t$, otherwise the segment connecting $(k+1)t - y$ and $y$ intersects the segment connecting $(k+1)t$ and $0$. But since $(k+1)t - y > kt$, we have that by the converse of Lemma 2 that $kt- y$ occurs before $kt$ in the labelling, contradicting our assumption that $y$ was the first such integer. Now, by repeating this proof with the other sets we obtain that the beautiful labelling is $S_0 \ldots S_i$ for some permutation of the sets. Now, it isn’t too hard to show that the set that occurs after $S_0$ is $S_y$ for some $y$ satisfying $\gcd(y,t) = 1$, which immediately implies that the precise set is $S_0 S_y \ldots S_{(t-1)y}$, by reducing $\mod t$, as claimed.

Beautiful! Let the circle be the unit circle, and consider equivalence under continuous mappings that preserve the cyclic order of the vertices, releasing the condition that the points are equally spaced. Key Claim: Every beautiful labelling $0, 1, 2, \ldots n$ is equivalent to $(1, x, x^2, x^3, \ldots, x^n)$ for some $x = e^{2\pi is}$ for $0 \leq s < 1$. Proof: We proceed via induction. $n = 1$ is trivial. Now for $n = k+1$, by the inductive hypothesis the first $k$ vertices are equivalent to $(1, x, \ldots, x^k)$ then slowly move the point corresponding to $k+1$ closer to $x^{k+1}$ along the circular arc between $1$ and $x^{k+1}$ which contains the point. This is always possible since the cross ratio $(x, y ; 1, xy) = \frac{2-2\textrm{Re}(x)}{2 - 2\textrm{Re}(y)} \in \mathbb{R}^+$ so it can be checked easily that they are in proper order along the unit circle in all configurations according to this motion. By the same ratio, the resulting configuration is always beautiful. Now notice that the order of the vertices corresponds precisely to which fractions of the form $\frac{a}{b}$ for $1 \leq a < b \leq n$ that $s$ lies in between, and these fractions divide $[0, 1)$ into precisely $N + 1$ intervals, finishing since each interval corresponds to a unique equivalence class of beautiful configurations.

First observation about $N$: Notice that $N$ is the number of reduced fractions $\frac{a}{b}$ with $0 < a < b < n$. Thus, $N+1$ is the number of intervals $[0, 1)$ is split into by these fractions. Characterization of beautiful labelings: We claim that a labeling $0, 1, 2, \ldots, n$ of the points (whose set we call $S$) is beautiful if and only if there is $\ell$ satisfying $\left\lfloor \ell \right\rfloor = 0$ and if $x=e^{2\pi i \ell}$, then the points $(1, x, x^2, x^3, \ldots, x^n)$ where $x^k$ has label $k$ for each $0 \le k \le n$ have the same cyclic order as $S$ and induce a beautiful labeling. First of all, notice that $(1, x, x^2, x^3, \ldots, x^n)$ always induces a beautiful labeling because the cross ratio over $\mathbb{P}_\mathbb{C}^1$ of the unit circle points $1, x, y, xy$ is \[ (x, y ; 1, xy) = \frac{1-\text{Re}(x)}{1 - \text{Re}(y)} >0. \] We finish with induction. Notice that the base case $n=1$ is trivially true. Suppose $n=k$ works. Then for $n=k+1$, use the inductive hypothesis to see that the first $k$ points can WLOG be $(1, x, \ldots, x^k)$ (and the cyclic ordering is preserved), and move the point with label $k+1$ near $x^{k+1}$ along the arc between $1$ and $x^{k+1}$. Thus the cyclic ordering in this case is also preserved, which completes the inductive step. The finish: Notice that as we move $\ell$ along the interval $[0, 1)$, the ordering of $(1, x, \ldots, x^n)$ changes whenever $x$ is a reduced fraction of the form $\frac{a}{b}$ with $0 < a < b < n$. Moreover, the the ordering of $(1, x, \ldots, x^n)$ changes when $\ell$ is in a different interval than it already is. Hence, the number of possible labelings is the number of intervals that $[0, 1)$ is split into by the fractions, which is $N+1$, as desired.

\begin{remark*} Solved with peeks at \textbf{62861}'s solution. This seems like the problem you'd expect to see on an IMO, because it's adhoc but somehow just feels like your stereotypical combo problem Here's an outline of the solution, I spent a the whole day today (a few hours) with a 2.5 sleep hour break in between solving only this problem, sadly wish i could be like others and solve like 6 isl c7s per day so don't want to waste too much time typing it as i've understood it largely on paper Prepare for a wall of text. \end{remark*} Allow degenerate chords so that even n definitions are extended. Proceed by induction, base case n=3 obvious. $M\ge N+1$ is evident by spacing each point inductively from the previous a distance of $\alpha$ counterclockwise around the circle. If we constrain $\alpha$ within the Farey fractions that have sum of top and bottom at most n. Construct a sequence $~_{i=1}^{n}a_i$ by adding 1 to the $a_{k+1}$ from $a_k$ iff that arc from k to k+1 passes through 0 (which WLOG is at the top of the circle). Then $\alpha_k = \lfloor k\alpha \rfloor$, so the $N+1$ $\alpha_1, \dots, \alpha_n$ sequences are all distinct and hence so are the labelings. Call a group of chords \emph{separated} if some groups of three of chords that have the same value of the sum of vertices they have are s.t. one separates the other two. \begin{claim*} In any beautiful labeling, the chords are separated. Furthermore, there are two ways to build inductively if the two numbers a and b next to 0 satisfy a+b=n, and only one way if $a+b\ne n$. \end{claim*} The first part follows by induction, by considering the chord a -- b right above 0 -- n; if a+b=n, there's contradiction by inductive hypothesis by deleting 0 and n and subtracting everything by 1, if a+b<n, using 0 -- (a+b) chord we deduce the chord (a+b) -- (n-(a+b)) lies on the other side of 0 -- n as a -- b, so deleting 0 and n and reducing contradiction again, similarly for a+b>n. Now consider an n-1 beautiful labeling. For the second part, if $a+b\ne n$, then n is forced in between the chords a -- n-a and b -- n-b, so there's one way, which works because if FTSOC there was some $a,b,c\in\{1,...,n-1\}:a+b=n+c$, we reflect over the diameter that is the perp. bisector of the 0 -- 12 chord to get that n-a -- n intersects 0 -- n-c, but this is a contradiction with inductive hypothesis because n-a+n-b=0+n-c and each of those values is <n. On the other hand, if a+b=n, then n must be directly to the left or right of zero; removing 0 -- n and subtracting everything by 1 and inducting, these two ways work. \qed \textit{Enumeration step.} We'll prove that there are $\varphi(n)$ ways for beautiful labelings when a+b=n; this suffices because \[M_n=M_{n-1}+\text{a+b=n labelings}=(N_{n-1}+1)+\text{a+b=n labelings}=\big(\varphi(1) + \dots + \varphi(n-1) + 1\big) + \varphi(n) = N_n+1,\]where $M_n,N_n$ denote M and N for points from 0 to n (n+1 points). Indeed, if we take indices mod n, there exists FIXED i and j (using separation claim) s.t. the following holds for the points $x_0,...,x_{n}$ labeled counterclockwise around the circle: \[x_k + x_{i-k} = n - 1 \equiv -1,x_k + x_{j-k}\equiv 0 \pmod{n}\implies\exists m:x_{k + m} \equiv x_k + 1 \pmod{n}\forall k,\]where $m = j - i$. So $\gcd(m,n) = 1$, which has $\varphi(n)$ possible choices of $m \pmod{n}$, done.

Let the labels be $a_0, a_1, \dots, a_n$ in order, where $a_0=0$. Let $R_a(b)$ denote the remainder when $b$ is divided by $a$. Let $F_{r, k}(m) = (R_r(m(k^{-1}\pmod{r})), m)$. Order these pairs in lexicographic order. Claim: There exists relatively prime $r, k$ with $r\ge k$ such that $F_{r, k}(a_i)$ is increasing in $i$. Proof: We will prove this by induction on $n$. Case 1: $a_1 = n$ We will prove by induction on $i$ that for $i\ge 2$, $a_i = R_n((i-1)a_2)$. Consider some $a_i$. Let $j<i$. Then, $a_j + R_n(a_i-a_j) \in \{a_i+n, a_i+0\}$. So, $R_n(a_i-a_j)\in \{a_0,\dots, a_{i-1}\}$. So, $R_n(a_i - a_2)\in \{a_0,\dots, a_{i-1}\}$. So, $a_i\in \{R_n(a_2), R_n(2a_2),\dots, R_n((i-1)a_2)\}$. Since $a_i$ isn't equal to any previous value, $a_i=R_n((i-1)a_2)$. So, $r = n$, $k = a_2$ satisfies the desired conditions. Case 2: $a_n=n$ This is the previous case in reverse. So, the labels are \[0, R_n(x), R_n(2x),\dots, R_n((n-1)x), n\]in that order for some $x$. If $x=1$, then $r=k=1$ satisfies the desired conditions. Otherwise, $r=x$ and $k = R_x(-n)$ satisfies the desired conditions. Case 3: $a_1, a_n \neq n$ By the inductive hypothesis, if we remove the point labelled $n$, the claim is true for some $r, k$. Consider where $n$ can be added back in. It must be on the same side as $0$ of the chord from $a_1=r$ to $n-r$. Also, it is on the same side as $0$ of the chord from $R_r(n+k)$ to $a_n$. Since $n$ cannot be next to $0$, it must be between $n-r$ and $R_r(n+k)$.$\blacksquare$ Because the configuration is uniquely determined by $r$ and $k$, the number of configurations is at most the number of ways to choose $r$ and $k$, which is $N+1$. Claim: For each relatively prime $r, k$ with $n\ge r\ge k$, ordering the labels such that $F_{r, k}(a_i)$ is increasing works. Proof: Assume $0\le a, b, c, d\le n$ such that $a+b=c+d$. Assume toward a contradiction that $F(a)<F(c)<F(b)<F(d)$. Case 1: $b\equiv c\pmod{r}$ Then, $a\equiv d\pmod{r}$. So, $R_r(a(k^{-1}\pmod{r})) = R_r(d(k^{-1}\pmod{r}))$. Therefore, \[a\equiv b\equiv c\equiv d\pmod{r}.\]So, $a<c<b<d$, which contradicts $a+b=c+d$. Case 2: $b\not\equiv c\pmod{r}$ and $a\equiv c\pmod{r}$ Then, $b\equiv d\pmod{r}$. So, $a<c$ and $b<d$, a contradiction. Case 3: \[R_r(a(k^{-1}\pmod{r})) < R_r(b(k^{-1}\pmod{r})) < R_r(c(k^{-1}\pmod{r})) < R_r(d(k^{-1}\pmod{r}))\] Let $a' = R_r(a(k^{-1}\pmod{r}))$ and define $b'$, $c'$, $d'$ similarly. Then, $a'+b'\equiv c'+d'\pmod{r}$. However, $a'+ b' < c'+d' < b'+d' < a'+b'+r$, a contradiction. $\blacksquare$ This shows that $M\ge N+1$.

Solved with ohiorizzler1434. Unfortunately again this is probably going to be similar to solutions above. This is going to be a much more sketchy solution than the ones before since this is really hard to formalise. The key idea is to realise that the entire data structure of the ring of numbers is in fact highly inductive! Indeed we can just delete all but a specific interval of numbers and the condition should still hold, amazing! First define 3+ chords to be combinatorially parallel or just parallel for short. We actually claim that each colouring on $[0,n]$ can be associated with an irrational number $\alpha\in(0,1)$ such that if the circumference of the ring is $1$, $\{\alpha k\}$ is the distance clockwise that is taken to go from $0$ to $k$. We are going to induct on $n\ge3$, with the base cases $n=3,4$ easily done by a case bash which I don't want to do. For the inductive step, we are going to split into two different types of circle rings: Linear rings, which are just rings such that if we label the numbers in clockwise order $(a_i)_{i=0}^{n}$, then $a_i=ai\bmod{n+1}$ for some $a$ such that $\gcd(a,n+1)=1$. The set of linear rings on the interval $[0,n]$ is denoted $L_n$. Nonlinear rings, which are rings that do NOT fit into $L_n$. The set of such rings is denoted $N_n$. We have the following claims: Claim: A ring $R\in L_n$ will admit two rings in $L_{n+1}\cup N_{n+1}$, whilst a ring $R\in N_n$ will only admit one ring in $L_{n+1}\cup N_{n+1}$. Notice that in a linear ring, if we consider the chords with endpoints summing to some number mod $n+1$, they are all parallel which is easy to see. Hence there are at most two spots that $n+1$ can go (this is due to the fact that $a$ and $n+1-a$ are neighbours of $0$ which is easy to see), which are the two spots next to $n+1$. To see that this actually works (!) recall the parallel nature of the chords with constant sum mod $n+1$; considering those with some sum $b\bmod{n+1}$ then we can just replace $0$ with $n+1$, which are still parallel with the original chords, which works. In fact if you let $\alpha$ be the irrational number associated with the linear labelling then the positioning of $n+1$ is merely dependent on whether $\alpha$ exceeds $\frac{a}{n+1}$ or not for some $\gcd(a,n+1)=1$. Now for the non-linear rings. Delete $0$ first and now add $n+1$ back in. Notice that since this ring is in $[1,n+1]$, if we just shift everything down by $1$ then we get a valid ring $R'\in L_{n}\cup N_{n}$. Now notice that both $R'$ and $R$ have the same associated irrational number $\alpha$ so they must be the same ring. We now claim in order to prove the our original proposition that $0$ and $n+1$ are not in the same region. This is done by a simple contradiction argument and the fact that $\{x\}$ acts as $x\bmod{1}$ in a sense, which completes the proof sketch. So since each new linear ring gives $2$ more new rings whilst each new nonlinear ring gives only $1$ more new ring, if $a_n$ is the number of rings in $[0,n]$, $a_{n+1}=\varphi(n+1)+a_{n}$ (because there are very clearly only $\varphi(n+1)$ linear rings in $[0,n]$ by definition). Now if $b_n$ is the number of pairs of coprime integers $(x,y)$ such that $x+y\le n$ then $b_{n+1}=\varphi(n+1)+b_{n}$ because $x+y=n+1$ and $\gcd(x,n+1-x)=1$ forces $\gcd(x,n+1)=1$ which then completes the proof because of the base case calculations.

This problem is pretty rigid in the sense that behavior is pretty forced. Let the labels / points along the circle be $a_1, a_2, \dots, a_n$ taken $\pmod{n+1}$. Denote a line between labels $i, j$ as $\overline{i,j}$. Given $n$ points on a circle, if we connect $\left\lfloor \frac{n}{2} \right\rfloor$ lines. We say that this configuration of lines is pretty if there exists some $i$ such that $a_j$ and $a_{i-j}$ are connected for all $j, 2j \ne i$. For example, here's a pretty configuration. [asy][asy] size(5cm,0); pair[] vertices; int n = 11; path p; for (int i = 0; i < n; ++i) { vertices.push(dir(360/n * i)); p = p--(dir(vertices[i])); label("$a_{" + ((string) i) + "}$", vertices[i], dir(vertices[i])); } // Draw the vertices: for (pair vertex : vertices) dot(vertex); for (int i = 0; i < n/2; ++i) { draw(vertices[i]--vertices[n-1-i], green); } draw(p); [/asy][/asy] Say that a labelling $S$ on $0, 1, 2, \dots, n+1$ is the parent of a labelling $T$ on $0, 1, 2, \dots, n$ if $T$ results from removing $n+1$ from $T$, and define a child similarly. Say a label is pretty if the lines configuration consisting of $\overline{0n}, \overline{1,n-1}$, and $\overline{i, n-i}$ in general is pretty. Claim: Any beautiful labelling $L$ on $0, 1, 2, \dots, n$, for any $0 \le a < b \le n$, is pretty. Furthermore, the beautiful parent(s) of $L$ exist for exactly one to two positions of $n+1$ such that the parents are also pretty labels, where there are two positions iff the neighbors of $0$ sum to $n+1$. Proof. We can shift a subconfiguration only considering points $a, \dots, b$ to $1, \dots, b+a-1$ so it remains to show this inductively. Take the base case of $|a-b| \le 3$ which is easy to check. We now classify the parents of $L$ which as above which finishes as every beautiful labelling has a child. Note that the line configurations $\overline{1,n}, \overline{2, n-1}, \dots$ is pretty (which we draw in red), and suppose $0$ lies between $a, b$. If $a + b = n+1$, then $n+1$ must lie in one of the two positions next to $0$ in arc between $a, b$ containing $0$, which makes the parent pretty. [asy][asy] size(5cm,0); pair[] vertices; string[] labels = {"2", "6", "3", "0", "7", "4", "1", "5"}; int n = 8; path p; for (int i = 0; i < n; ++i) { vertices.push(dir(360/n * i)); if (i == 1 || i == 2 || i == 5) { draw(vertices[i-1]--vertices[i]); } label(labels[i], vertices[i], dir(vertices[i])); } for (int i = 0; i < (n-1)/2; ++i) { if (i == 3) { draw(vertices[i]--vertices[n-1-i], red+dashed); } else { draw(vertices[i]--vertices[n-1-i], red); } } draw(vertices[3]--vertices[1], blue); draw(vertices[6]--vertices[7], blue); draw(vertices[0]--vertices[5], blue); draw(vertices[7]--vertices[3], green); draw(vertices[6]--vertices[5], green); draw(vertices[3]--vertices[5], orange); draw(vertices[2]--vertices[6], orange); draw(vertices[3]--vertices[2], purple); draw(vertices[0]--vertices[6], purple); // Draw the vertices: for (int i = 0; i < n; ++i) { dot(vertices[i]); } [/asy][/asy] If $a + b \ne n+1$, then $n+1$ either lies in the arc between $a, b$ containing $0$ or the empty arc between $n-a, n-b$. The first case is impossible because $a+b-(n+1)$ is nonzero and lies somewhere giving an intersection. The second case makes the parent pretty. [asy][asy] size(5cm,0); pair[] vertices; string[] labels = {"4", "1", "6", "3", "0", "5", "2"}; int n = 7; path p; for (int i = 0; i < n; ++i) { vertices.push(dir(360/n * i)); if (i == 2 || i == 3 || i == 6) { draw(vertices[i-1]--vertices[i]); } label(labels[i], vertices[i], dir(vertices[i])); } for (int i = 0; i < (n-1)/2; ++i) { if (i == 2) { draw(vertices[i]--vertices[n-1-i], red+dashed); } else { draw(vertices[i]--vertices[n-1-i], red); } } draw(vertices[4]--vertices[5], blue); draw(vertices[3]--vertices[6], blue); draw(vertices[0]--vertices[1], blue); draw(vertices[0]--vertices[4], green); draw(vertices[1]--vertices[3], green); draw(vertices[3]--vertices[4], orange); draw(vertices[1]--vertices[6], orange); // Draw the vertices: for (int i = 0; i < n; ++i) { dot(vertices[i]); } [/asy][/asy] We now show that the pretty parent of a beautiful labelling $L$ is also pretty. This follows since if there is some contradiction where $\overline{n+1, a}, \overline{b, c}$ intersect with $n+1 + c = a+b$, then $\overline{0, n+1-a}, \overline{n+1-b, n+1-c}$ intersect. Since $a, b, c > 0$, this contradicts $L$ being pretty. $\blacksquare$ Now, let $M_n, N_n$ denote the corresponding values for $n$ points. Then we can notice that \[ N_{n+1} - N_n = \sum_{i=1}^n [\gcd(i, n+1-i) = 1] = \varphi(n+1). \]On the other hand, by the above lemma, $M_{n+1} - M_n$ is the number of beautiful labels where the neighbors of $0$ sum to $n+1$. Claim: There are exactly $\varphi(n+1)$ beautiful labels on $0, 1, 2, \dots, n$ where the neighbors $a, b$ of $0$ sum to $n+1$. Proof. In fact, here's a direct classifaction of the labels. Take any $a$ coprime to $n+1$, and take the ordering of points \[ 0, a \pmod{n+1}, 2a \pmod{n+1}, 3a \pmod{n+1}, \dots, (n-1)a \pmod{n+1}. \]We can verify directly for the $a = 1$ case that if $a + b \equiv c + d \pmod{n+1}$ for distinct $a, b, c, d$, then $\overline{ab}, \overline{cd}$ don't intersect. This means that the configurations after multiplying by $a$ and taking the result $\pmod{n+1}$ also work. We now show all configurations are of this form. Shift such that $a_0 = 0$, and we will induct on $a_i \equiv ia \pmod{n+1}$ holding for $-k \le i \le k$ for $1 \le k \le \frac{n-2}{2}$, with base case $k = 1$ and $a_1 = a$. We show that this also holds for $i \equiv \pm (k+1)$, which finishes by taking $k = \left\lfloor \frac{n-2}{2} \right\rfloor$. Note that due to being pretty, we have that $a_i + a_{-i} = n+1$ for $i \not\equiv 0 \pmod{n+1}$. As such, one of $a_{k+1} - a_i$ and $a_{-(k+1)} - a_{-i}$ is positive for $1 \le i \le k$ since the two are additive inverses. This means by using the beautiful characterization that \[ a_{\pm k+1} \mp ia \in \{0, \pm a, \pm 2a, \dots, \pm ka, a_{\pm k+1}\} \pmod{n+1} \]Due to the symmetry, we can ssume the sign is in fact positive. If $ia \equiv 0 \pmod{n+1}$ or $a_{k+1} \equiv \pm ia$, then this is a contradiction by the distinctness of labels and we finish. Else, \[ a_{k+1} - \{a, 2a, \dots, ka\} \in \{0, a, 2a, \dots, ka\} \pmod{n+1} \]which means that $a_{k+1} \in \{ka, (k+1)a\}$ and thus the result follows by distinctness. [asy][asy] size(8cm,0); pair[] vertices; string[] labels = {"$a_{-2} = (n+1) -a_{2}$", "$a_{-1} = (n+1)-a_1$", "0", "$a_1 = a$", "$a_2 = 2a$", "$a_3 = b$", "", "$a_{-3} = (n+1)-b$"}; int n = 8; path p; for (int i = 0; i < n; ++i) { vertices.push(dir(360/n * i)); p = p--vertices[i]; label(labels[i], vertices[i], dir(vertices[i])); } draw(vertices[7]--vertices[2]--vertices[5], green); // Draw the vertices: for (int i = 0; i < n; ++i) { dot(vertices[i]); } draw(p--cycle); [/asy][/asy] As such, if $\gcd(a, n+1) \ne 1$ then no labelling exists, and elsewise its the above labelling we described. $\blacksquare$ We are done by the above.