Настройка равенства

[grizzly]

Предлагаю посмотреть на весьма оригинальную задачу, взятую с Math.SE и там пока не решённую, несмотря на обещанный за неё приз.

Дана перестановка чисел $\{a_{i}, i=1,...,2016\}$ на множестве $A=\{1,...,2016\}$, такая что

$$ \forall i,j\in A, \ i\neq j, \quad \dfrac{a_{i}-a_{j}}{i-j}\neq 1. $$

Доказать, что для некоторых $p,q\in A$ выполняется равенство:

$$ |p-q|+|a_{p}-a_{q}|=2014. $$

[iancaple]

Начало решения. введем 4031 множество $D_{-2015},D_{-2014},...D_0,...D_{2015}$ условием $D_i=\{(k,a_k):a_k-k=i\}$ , на графике это диагонали вправо -вверх. Условие задачи означает ровно то, что на каждой диагонали не более одной точки графика, а всего их 2016. Некоторая аналогия с расстановками ферзей Введем теперь отношение эквивалентности $D_i\sim D_j$, если $i\equiv j \pmod{2014}$. В классах с представителями $D_2,...D_{2012}$ по 2 исходных диагонали, присутствие двух точек в этом классе- зхначит они на разных диагоналях, значит для них выполнено заключение задачи (полупериметр координатного прямоугольника, построенного на этой паре точек как на диагонали, равен 2014). Для применения принципа Дирихле заметим, что в классах $D_{2013},D_{2014},D_{2015}$, содержащих по 3 исходных диагонали, не более чем по 2 точки графика, и в тех, в которых их две, они на двух удаленных друг от друга диагоналях. Максимум точек получился 2017.Если их не менее 2016 (иначе работает Дирихле), то среди точек графика есть угловая: $(1;2016)$ или $(2016,1)$. Тогда все можно свести к отображению 2015 точек в себя, рекурсия и снова то же рассуждение (додумать)

[iancaple]

UPD: посмотрел снова, все нормально. Случаи $a_1=2016$ и $a_{2016}=1$ рассмотрим в начале доказательства, как разминку читателя. Введем $b_k:=a_{k-1},k=2,...2016$ или $b_{k}:=a_k -1,k=1,...2015$ соответственно , и все рассуждения проделаем для отображения 2015 чисел в себя
Введем 4029 множеств $D_{-2014},D_{-2013},...D_0,...D_{2014}$ условием $D_i=\{(k,b_k):b_k-k=i\}$ , на графике это диагонали вправо -вверх. Условие задачи означает ровно то, что на каждой диагонали не более одной точки графика, а всего их 2015. Введем теперь отношение эквивалентности (раскрасим в 2014 цветов) $D_i\sim D_j$, если $i\equiv j \pmod{2014}$. В классах с представителями $D_1,...D_{2013}$ по 2 исходных диагонали, присутствие двух точек в этом классе- зхначит они на разных диагоналях, значит для них выполнено заключение задачи (полупериметр координатного прямоугольника, построенного на этой паре точек как на диагонали, равен 2014). Для применения принципа Дирихле заметим, что в классе $D_{-2014}\cup D_0 \cup D_{2014}$, 3 исходных диагонали, не более чем 2 точки графика, если их две, они на диагоналях-точках$D_{-2014}, D_{2014}$.В последнем случае снова сведем к меньшей задаче, с 2013 точками: $c_{k-1}:=b_{k}-1,k=2,...2014$.. Максимум точек получился 2014, работает Дирихле. Теперь рассмотрим основную ветвь (предыдущий пост)
И за это приз? Если не ошибаюсь, там добавились верные частные соображения. Нормальная была задачка для семинара по дискретке со студентами где-нибудь в Саратове, на тему "биекции конечного множества в себя". А то во всех учебниках "график отношения", а какая от него польза, не показывают. Польза, что все видно.
UPUPD: давайте над этой Exchange постоянное шефство возьмем, только в какой форме: ссылки сюда, пусть учат русский, или все-таки не лень переводить на инглиш, тогда кто? я пас

[Vince Diesel]

У них есть гугл-переводчик

[NSKuber]

iancaple в сообщении #1053713 писал(а):

они на разных диагоналях, значит для них выполнено заключение задачи

Мне кажется, это неверно. Из того, что они на разных диагоналях, следует $a_k-k=i$, $a_l-l=i+2014$ для некоторых $k,l$. Отсюда $(a_l-a_k)+(k-l)=2014$, но в условии задачи модули! И если $(a_l-a_k)$ и $(k-l)$ разных знаков, то заключение задачи не будет выполнено. Выразим $a_l-a_k=2014-(k-l)$ и при $k-l>2014$ как раз получаем разные знаки, аналогично $l-k=-2014+(a_l-a_k)$ и $(a_l-a_k)>2014$. Например, $(2016,2),(1,1),(2,2016)$ - три точки на трёх эквивалентных диагоналях, но никакие две решением задачи не являются. Или вот целое семейство пар, лежащих на эквивалентных диагоналях, но так же не подходящих: $(2016, k+1),(1, k),k=1, \ldots, 2015$.

[iancaple]

NSKuber, спасибо. Это довольно редкие примеры. Подумаю , как подправить.

[iancaple]

NSKuber в сообщении #1053739 писал(а):

Например, $(2016,2),(1,1),(2,2016)$ - три точки на трёх эквивалентных диагоналях

И вот только этот пример "обломал" все доказательство (есть еще пример, симметричный этому, а больше подобных нет). Рекурсия к эквивалентной задаче с 2013 элементами $b_{k-2}=a_k-2,k=3,4...2015$, при этом запрещена диагональ (она же класс) $D_0$, остается 2013 точек в 2013 классах, вполне могли быть. Сравним с задачей о расстановке ферзей на доске $2013\times 2013$. Здесь "ферзи другие".В чем-то слабее (по той диагонали, что влево-вверх, не ходят как хотят) Зато одновременно с ходом по диагонали вправо-вверх "имеют право" переместиться ровно на 1007 клеток вдоль диагонали влево-вверх. Ну и еще для расстановки запрещена главная диагональ. Вряд ли кто так задачу ставил раньше. Но решение ее эквивалентно ответу на эту.
Если бы не было двух модулей, с условием $|p-q-a_p+a_q|=2014$ - решено.
А данная нет. Приношу извинения, кто из-за меня не взялся вовремя решать

[grizzly]

iancaple
Вопрос из простого любопытства (пока я не в этом танке :)
Но если ответ не очевиден, большая просьба не тратить усилия:
Даёт ли Ваша идея решение для других чисел (вместо 2016 и 2014) или, быть может, целого класса зависимостей между ними? На MSE в комментах привели примеры, что если "2016" положить 10, а "2014" -- 8, то требуемые $p,q$ существуют далеко не всегда. Но если появляется решение для какого-то класса чисел, то потенциально появляется перспективное направление, в котором можно копать (возможно, другими методами).

[12d3]

grizzly в сообщении #1053808 писал(а):

На MSE в комментах привели примеры, что если "2016" положить 10, а "2014" -- 8, то требуемые $p,q$ существуют далеко не всегда.

Вдобавок к проверенным там 4,6,8,10 посмотрел 12 и 14, для них тоже не всегда существуют нужные $p,q$. Чем же 2016 так замечательно?
UPD Для 16 также нашелся контрпример.

[iancaple]

Обобщение (исправлено в цитате)

grizzly в сообщении #1053708 писал(а):

Дана перестановка чисел $\{a_{i}, i=1,...,N\}$ на множестве $A=\{1,...,N\}$, такая что

$$ \forall i,j\in A, \ i\neq j, \quad \dfrac{a_{i}-a_{j}}{i-j}\neq 1. $$

Доказать, что для некоторых $p,q\in A$ выполняется равенство:
А)

$$ |p-q|+|a_{p}-a_{q}|=M.$$

Б)

$$ |p-q-a_{p}+a_{q}|=M. $$

Пусть $M<N$.
Число непустых диагоналей в плоскости графика-$2N-1$
Число классов, в которых 3 диагонали (назовем эти классы "двухместными клетками Дирихле") $2N-2M-1$(теоретически). Общее число классов $M$. Число мест в классах $2N-M-1$ (теоретически), но рассмотрение эффектов в углах, где не все места могут быть заняты одновременно, снижает число мест еще на 2
Условие применимости принципа Дирихле в задаче Б) $2N-M-3\leq N-1$,отсюда$M=N-1$ или $N-2$
Но именно при $M=N-2$ и только в задаче А) возможны эти "новосибирские тройки", делающие одну клетку из двухместной - трехместной, и все ломается. При $M=N-1$ утверждение верное и легкое. И задача Б) всегда легкая. Чем задача А) естественнее задачи Б) -не вижу. Пока у меня все.