Теория Рамсея

[grizzly]

Ниже будем рассматривать перестановки порядка $N \in \mathbb N$ без повторений, то есть упорядоченные наборы $\{a_i \in \{1,..,N\}, i=1,...,N; a_i \neq a_j, i \neq j\}$. Пусть также на элементы перестановок наложены дополнительные $M$-ограничения: $j-M \leq a_j \leq j+M, j=1,...,N,$ для некоторого фиксированного $M\in \mathbb N$.

Доказать, что для любого $M\in \mathbb N$ существует $N_0\in \mathbb N$ такое, что в любой перестановке порядка $N\geq N_0$ с $M$-ограничением найдётся тройка элементов $a_j, a_k, a_l,$ значения и индексы которых составляют арифметические прогрессии. Другими словами, для этих элементов одновременно выполнены следующие условия:

$l = 2k - j$;
$a_l = 2a_k - a_j$.