IMO 2013, Day 2-P6

Discussion on International Mathematical Olympiad (IMO)
User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh
IMO 2013, Day 2-P6

Unread post by Masum » Mon Jul 29, 2013 1:15 pm

Let $n\geq 3$ 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,\dots, n$ such that each label is used exactly once; two such labellings are considered to be 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\leq n$ and $\gcd(x,y)=1$. Prove that $M=N+1$.
One one thing is neutral in the universe, that is $0$.

Post Reply