Задача М1267‍‍

Предположим, что среди чисел $r_1$‍,‍ $r_2$‍,‍ $\ldots$‍,‍ $r_n$‍‍ всего $m$‍‍ различных. Заметим, что лишь для одного $k$‍‍ может выполняться равенство $r_{k+1}=r_k$‍‍ (когда $a_{k+1}=n$‍).‍ Для всех остальных $k$‍‍ от 1 до $n-1$‍‍ разности $r_{k+1}-r_k$‍‍ — различные числа. Но из $m$‍‍ разных чисел можно составить лишь $m(m-1)$‍‍ разных упорядоченных пар и тем самым не более $m(m-1)$‍‍ разных разностей. А их должно быть не меньше $n-2$‍.‍ Таким образом, $m(m-1)\ge n-2$‍.‍ Если бы $m$‍‍ было меньше $\sqrt{n}$‍,‍ то получилось бы (при $n \ge 4$‍)‍ противоречие: $n-\sqrt{n} \gt n-2$‍.‍ Для $n=3$‍‍ легко убедиться непосредственной проверкой, что среди трёх остатков $r_1$‍,‍ $r_2$‍,‍ $r_3$‍‍ всегда не менее двух различных. Таким образом, утверждение доказано.