54-я Международная Математическая OлимпиадаКолумбия, Санта Марта, 2013 год

Пусть $n\ge 3$ — целое число. Рассмотрим окружность и $n+1$ точек на ней, разбивающих её па равные дуги. Рассмотрим все способы пометить эти точки числами $1$, $2$, $\ldots$, $n$так, что каждое число использовано ровно один раз. Два способа, отличающихся поворотом, считаются одинаковыми. Способ пометки называется красивым, если для любых четырех меток $a < b < c < d$ таких, что $a+d=b+c$, хорда, соединяющая точки с метками $a$ и $d$, не пересекает хорду, соединяющую точки с метками $b$ и $c$.
Пусть $M$ — количество красивых способов пометки. Пусть $N$ — количество упорядоченных пар $\left( x,y \right)$ натуральных чисел, удовлетворяющих условиям $x+y\le n$ и НОД$\left( x,y \right)=1$. Докажите, что $M=N+1$.

Комментарий/решение

Допустим это неверно. Но по условию это надо доказать, что значит, что это является верным утверждением. А значит это противоречие предположению. Поэтому это верно => доказано