IMO 2013 Problem 6

Question

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)$$

Answer 1

Here is the solution , But this is not official :

http://imomath.com/index.php?options=785

Assume that $a$ and $b$ are distinct elements of $\{1,2,\dots, n\}$ . A beautiful labeling will be called $(a,b)$ -labeling if $a$ and $b$ are respectively right and left neighbor of $0$. We will prove that $(a,b)$ -labeling exist if and only if $\mbox{gcd }(a,b)=1$ and $a+b> n $. Moreover, if $\mbox{gcd }(a,b)=1$ and $a+b> n$ we will prove that the $(a,b)$ -labeling is unique.

Notice that an $(a,b)$ -labeling does not exist if $a+b\leq n$, since the chords $[0,a+b]$ and $[a,b]$ would intersect in that case.

Assume that $a+b> n$ . Assume that $R$ is one $(a,b)$ -labeling. For given $c\in\{1,2,\dots, n\}$ let us define the sequence $(z^c_k)_{k\geq 0}$ in the following way: $z^c_0=c$ , and for $k\geq 0$ : $$\begin{eqnarray*} z^c_{k+1}&=&\left\{\begin{array}{ll} z^c_k+a& \mbox{if } z^c_k\leq n-a,\newline z^c_k-b&\mbox{if }z^c_k>n-a\mbox{ and }z^c_k\geq b,\newline z^c_k+a-b&\mbox{otherwise.} \end{array}\right. \end{eqnarray*}$$

Notice that for each $k\geq1$ at least one of the following three equalities hold: $$\begin{eqnarray*} z^c_{k+1}+0&=&z^c_k+a\newline z^c_{k+1}+b&=&z^c_k+0\newline z^c_{k+1}+b&=&z^c_k+a. \end{eqnarray*}$$ Therefore, the ordering of the labels on the circle must be $b,0,a,z^c_k,z^c_{k+1} $. This means that the numbers $b , 0 , a , z^c_1 , \dots , z^c_m$ must appear in that order on the circle.

If $\mbox{gcd }(a,b)> 1 $, then the sequence $(z^1_k)_{k\geq 0}$ will not contain the term $0 $. This contradicts the fact that the sequence has finitely many elements.

We have concluded that if $(a,b)$ -labeling exists, then $\mbox{gcd }(a,b)=1 $. Let us now prove that if $\mbox{gcd }(a,b)=1 $, then $(a,b)$ -labeling must be unique. Consider the sequence $(z_k^0)_{k\geq 0} $. Notice that we always have $z_{k+1}\equiv z_k+a (\mod a+b )$, or $z_{k+1}\equiv z_k+2a (\mod a+b )$. Therefore the sequence $(z_k^0)_{k\geq 0}$ is obtained when the numbers greater than n are removed from the sequence of residues of $a , 2a , \dots$ modulo $a+b$ . Thus $z^0_1 , \dots , z^0_n$ is a uniquely determined permutation of $\{1,2,\dots, n\} $, proving the uniqueness of the labeling

Let $L_n$ be the number of pairs $(a,b)\in\{1,2,\dots, n\}^2$ such that $\mbox{gcd }(a,b)=1$ and $a+b> n$. We have that $M=L_n $. It remains to prove that $L_n=N_n+1 $, where $N_n$ is the number of pairs $(a,b)\in\{1,2,\dots, n\}^2$ such that $\mbox{gcd }(a,b)=1$ and $a+b\leq n $. Consider the matrix $(D_{i,j})_{i,j\geq 1}$ such that $$D_{i,j}=\left\{\begin{array}{ll}1&\mbox{if gcd }(i,j)=1,\\ 0&\mbox{otherwise.}\end{array}\right.$$

We will use the induction to prove that $L_n-N_n=1 $. The statement clearly holds for $n=3 $. The number $N_n$ represents the number ones in the matrix $D_{i,j}$ that lie on and above the diagonal $i+j=n $. The number $L_n$ represents the number of ones in the matrix $D_{i,j}$ that lie below the diagonal $i+j=n$ and for which $i\leq n$ and $j\leq n$ . We need to show that $(L_{n+1}-N_{n+1})-(L_n-N_n)=0 $. Let us denote by $G_{n+1}$ the number of ones on in the $n+1$ -st column that are on or above the $n+1$ -st row. Let $H_{n+1}$ be the number of ones on the diagonal $i+j=n+1 $. Then we have $(L_{n+1}-N_{n+1})-(L_n-N_n)=2G_{n+1}-2H_{n+1}$ since the new difference $L_{n+1}-N_{n+1}$ will gain all the ones in the $n+1$ -st row and $n+1$ -st column but loose all the ones on the diagonal. It remains to notice that $G_{n+1}=H_{n+1}=\varphi(n+1) $, where $\varphi(x)$ is the number of integers smaller than $x$ and relatively prime to $x$.

Answer 2

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.

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$.

2. 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$.