представление чисел скалярным произведением перестановок

[maxal]

Будем трактовать перестановоки порядка $n$ как векторы размерности $n$ и для двух перестановок $\pi=(\pi_1,\dots,\pi_n)$ и $\sigma=(\sigma_1,\dots,\sigma_n)$ рассмотрим их скалярное произведение:

$$(\pi,\sigma)=\sum_{i=1}^n \pi_i \sigma_i.$$

При этом, согласно перестановочному неравенству, значение скалярного произведения ограничено:

$$f(n) = \frac{n(n+1)(n+2)}{6} = \sum_{i=1}^n i (n-i) \leq (\pi,\sigma) \leq \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = g(n).$$

Докажите, что при $n\geq 4$ каждое целое число из отрезка $[f(n),g(n)]$ представляется скалярным произведением двух перестановок порядка $n$.

P.S. Понятно, что одну из перестановок можно зафиксировать равной тождественной. Тогда для каждого числа $m$ из отрезка $[f(n),g(n)]$ нужно показать существование такой перестановки $\pi$ порядка $n$, что

$$m=\sum_{i=1}^n i\cdot \pi_i.$$

P.S. По сути эта задача соответствует доказательству формулы для A126972.

[Руст]

Чтобы можно было назвать это векторами, нужно хотя бы сумма любых двух векторов была так же вектором. Без этого использование векторной терминологии получается просто запудриванием мозгов.
Лучше формулировать так для любого взаимно однозначного отображения $T: (1,2,..,n)\to (1,2,...,n)$ и любого $f(n)=\frac{n(n+1)(n+2)}{6}\le N\le \frac{n(n+1)(2n+1)}{6}=g(n)$ существует взаимно однозначное отображение T, что $$\sum_{k=1}^n kT(k)=N$ за исключением одного натурального случая n=3 (не представляется 12).
Доказывается индукцией по n. Вначале проверим для n=4. Далее проводим индукцию фиксировав одно значение.

[maxal]

Руст писал(а):

Доказывается индукцией по n. Вначале проверим для n=4. Далее проводим индукцию фиксировав одно значение.

Как именно? В этом вся соль задачи.

[Руст]

Это же очевидною. Рассмотрим перестановки с T(n)=n. Для них значение соответствующей суммы меняется от $f(n-1)+n^2=\frac{n^3+6n^2-n}{6}$ до $g(n-1)+n^2=g(n).$ Расмотрим так же перестановки с условием T(1)=n,T(n)=1 - они переставляют множество 2,3,...,n-1. При этом за счёт сдвига множества из n-2 элементов значения суммы будут принимать от $2n+\frac{(n-1)(n-2)}{2}+f(n-2)=f(n)$ до $2n+\frac{(n-1)(n-2)}{2}+g(n-2)=\frac{n(n-1)(n-5)}{3}$.
Полученные две оценки полностью перекрывает интервал (f(n),g(n)) если крайние оценки второго верхнего не меньше чем первого нижнего минус 1, т.е $n^3-18n^2+11n+6\ge 0$.
Однако такое перекрытие имеется только при n>=18. Чтобы не проверять это свойство до n=17 включительно, рассмотрим ещё случай фиксирования T(1)=1. В этом случае перекрывается интервал $1+\frac{n(n-1)}{2}+f(n-1)=\frac{n^3+3n^2-4n+6}{6}\le N\le 1+\frac{n(n-1)}{2}+g(n-1)=\frac{n^3-n+3}{3}$.

[maxal]

Чуть обобщим:

Докажите, что начиная с некоторого $n$, числа вида

$$\sum_{i=1}^n \pi_i\cdot \sigma_i^2,$$

где $\pi$ и $\sigma$ перестановки чисел $1,2,\dots,n$ представляют каждое число в отрезке:

$$\left[\sum_{i=1}^n (n+1-i)\cdot i^2,\;\sum_{i=1}^n i^3\right].$$

Каково это наименьшее $n$?

[Руст]

maxal в сообщении #532378 писал(а):

Чуть обобщим:

Докажите, что начиная с некоторого $n$, числа вида

$$\sum_{i=1}^n \pi_i\cdot \sigma_i^2,$$

где $\pi$ и $\sigma$ перестановки чисел $1,2,\dots,n$ представляют каждое число в отрезке:

$$\left[\sum_{i=1}^n (n+1-i)\cdot i^2,\;\sum_{i=1}^n i^3\right].$$

Каково это наименьшее $n$?

Это не обобщение, а новая задача. Обобщением будет например:
Найти интервал значений для $\sum \pi_i^k\sigma_i^m$. Думаю аналогично (по индукции) доказывается, что все значения находятся в интервале $[\sum_i i^k(n+1-i)^m, \sum_i i^{m+k}]$ и начиная с некоторого n принимаются все значения из этого интервала.

[maxal]

Руст в сообщении #532467 писал(а):

Найти интервал значений для $\sum \pi_i^k\sigma_i^m$. Думаю аналогично (по индукции) доказывается, что все значения находятся в интервале $[\sum_i i^k(n+1-i)^m, \sum_i i^{m+k}]$

Эта часть тривиально следует из перестановочного неравенства.

Руст в сообщении #532467 писал(а):

и начиная с некоторого n принимаются все значения из этого интервала.

А вот это уже нетривиальная вещь. Соответственно неплохо было бы этот факт доказать для $k=1$, $m=2$.

[Руст]

На самом деле верна более общая теорема:
Пусть имеется две положительные последовательности $0\le a_1\le a_2\le ...\le a_n, 0\le b_1\le b_2\le ...\le b_n$.
Тогда

$$\sum_{i=1}^n a_ib_{n+1-i}\le \sum_{i=1}^n a_i*b_{\pi (i)} \le \sum_{i=1}^n a_i*b_i.$$

Доказывается элементарно (возможно это неравенство даже приводилось в "Кванте").
Что касается второй части оно неверно для степеней больше 1.
Рассмотрим элементарную перестановку двух элементов $i<j$ (любая перестановка разлагается в произведение таких).
Пусть $c=a_ib_i+a_jb_j, d=a_ib_j+a_jb_i$. Легко проверяется $c^2-d^2=(a_2^2-a_1^2)(b_2^2-b_1^2)\ge 0$, откуда получается доказательство теоремы и почему важно положительность.
Разница $c-d$ показывает на сколько уменьшается сумма после перестановки. В нашем случае эта разница не может быть равна 1, а следовательно не все значения "скалярного произведения" принимаются после перестановки.

[maxal]

Руст в сообщении #532534 писал(а):

На самом деле верна более общая теорема:
Пусть имеется две положительные последовательности $0\le a_1\le a_2\le ...\le a_n, 0\le b_1\le b_2\le ...\le b_n$.
Тогда

$$\sum_{i=1}^n a_ib_{n+1-i}\le \sum_{i=1}^n a_i*b_{\pi (i)} \le \sum_{i=1}^n a_i*b_i.$$

Доказывается элементарно (возможно это неравенство даже приводилось в "Кванте").

Это и есть перестановочное неравенство. См. статью в википедии по ссылке в первом сообщении темы.

-- Sun Jan 29, 2012 01:58:31 --

Руст в сообщении #532534 писал(а):

Разница $c-d$ показывает на сколько уменьшается сумма после перестановки. В нашем случае эта разница не может быть равна 1, а следовательно не все значения "скалярного произведения" принимаются после перестановки.

А кто сказал, что все значения можно последовательно перебрать только такими уменьшающими скачками? Может, сначала мы уменьшаем, скажем, на 10 одной транспозицией элементов, а затем увеличиваем на 9 другой и т.п.
Так что, твой вывод не обоснован.

[Руст]

Любую перестановку можно разложить на произведение транспозиций $(i,j),i<j$ так, чтобы она применялось не более одного раза. Допустим имеется перестановка $\pi$ на n элементах и допустим , что это доказано для всех перестановок с $n-1$ элементами. Тогда, если $\pi(n)=n$ доказывать ничего, иначе существует $i<n: \pi(i)=n$ и $\pi=\sigma *(i,n)$, где $\sigma$ перестановка $n-1$ элементов множества $(1,2,...,i-1,i+1,...,n)$ (без i-го элемента). Для этого множества теорема доказана по индукции. Более того, если упорядочить "скалярные произведения" по росту, то соседние будут отличаться только на одно из $n-1$ величин $\Delta_i=a_ib_i+a_{i+1}b_{i+1}-a_ib_{i+1}-a_{i+1}b_i=(a_{i+1}-a_i)(b_{i+1}-b_i).$

[maxal]

Руст в сообщении #532629 писал(а):

Более того, если упорядочить "скалярные произведения" по росту, то соседние будут отличаться только на одно из $n-1$ величин $\Delta_i=a_ib_i+a_{i+1}b_{i+1}-a_ib_{i+1}-a_{i+1}b_i=(a_{i+1}-a_i)(b_{i+1}-b_i).$

Я оспаривал как раз это утверждение. Почему соседние "скалярные произведения" будут отличаться лишь на $\Delta_i$, а не, например, $\Delta_i - \Delta_j$ для каких-то $i,j$ ?
То есть, с какой стати соседние по величине "скалярные произведения" будут соответствовать соседним (отличающимся на одну транспозицию) перестановкам?

[Руст]

maxal в сообщении #532761 писал(а):

Руст в сообщении #532629 писал(а):

Более того, если упорядочить "скалярные произведения" по росту, то соседние будут отличаться только на одно из $n-1$ величин $\Delta_i=a_ib_i+a_{i+1}b_{i+1}-a_ib_{i+1}-a_{i+1}b_i=(a_{i+1}-a_i)(b_{i+1}-b_i).$

Я оспаривал как раз это утверждение. Почему соседние "скалярные произведения" будут отличаться лишь на $\Delta_i$, а не, например, $\Delta_i - \Delta_j$ для каких-то $i,j$ ?
То есть, с какой стати соседние по величине "скалярные произведения" будут соответствовать соседним (отличающимся на одну транспозицию) перестановкам?

Имея некоторую перестановку, можем еще менять $i,i+1$ элементы для некоторого i, такого, чтобы получилось увеличение.

[maxal]

Руст в сообщении #532772 писал(а):

Имея некоторую перестановку, можем еще менять $i,i+1$ элементы для некоторого i, такого, чтобы получилось увеличение.

Но почему минимальное увеличение обязано достигаться одной лишь транспозицицией?

[Руст]

То, что до любой перестановки можно добраться уменьшениями одной транспозицией $(i,j),i<j$ (или увеличением от обратного упорядочивания) я уже показывал, и этого достаточно для того, чтобы показать, что не все значения "скалярного произведения" реализуются, достаточно взять уменьшенное на одно значение от максимума или увеличенное на одно от обратноного значение. То, что соседние значения скачков всегда реализуется соседними транспозициями я высказал как некоторое усиление, над которым еще надо подумать, может оно неверно.

[maxal]

Руст в сообщении #532804 писал(а):

чтобы показать, что не все значения "скалярного произведения" реализуются, достаточно взять уменьшенное на одно значение от максимума или увеличенное на одно от обратноного значение

Это верно, однако стоит чуть отойти от краев (т.е. максимума и минимума) и там уже будет интервал, в котором каждое число представимо. Интересно было бы найти границы этого интервала.