Минимизировать би-тонность вектора

[blondinko]

Исходная задача была (пусть и не до конца корректно) поставлена здесь. Далее — мой перевод с исправлениями.

Имеется вектор $a = [a_0, a_1, ... ~ a_{|a|-1}], a_i, a_j \in \mathbb{N}, a_i \neq a_j ~ \forall i, j = \overline{0, |a|-1}, i \neq j$.
Введём понятие би-тонности $a$ (словообразование по аналогии с термином «монотонность»): $B(a)\;=\displaystyle\sum_{i=1}^{|a|-1}\mbox{sgn}(a_i-a_{i-1})$
Введём понятие перестановки $a$: $S_{ij}(a) : [... ~ a_i, ... ~ a_j, ...] \rightarrow [... ~ a_j, ... ~ a_i, ...] ~ \forall i, j = \overline{0, |a|-1}, i \neq j$

Очевидно, что $|B(a)|$ не может быть меньше 1 для чётных $|a|$, и соответственно меньше 0 для нечётных, а за каждую перестановку изменяется на чётное число единиц.

Задача: найти минимальное число $S$ перестановок входного вектора $a$, такое что $|B(S_{{i_1}{i_2}}(S_{{i_3}{i_4}}(... S_{{i_n}{i_k}}(a)...)))| \leq 1$.


Так вот, проблема в том, что я чисто на интуиции сформулировал три теоремы, доказать из которых (и то пока что нестрого — но да ладно: как добавить строгости в первую, я знаю) удалось лишь одну.

$1. ~ |B(S_{ij}(a)) - B(a)| \leq 4 ~ \forall a, S_{ij}(a)$ (доказана)
$2. ~ \forall a : |B(a)| \geq 2 ~ \exists S_{ij}(a) : |B(S_{ij}(a))| = |B(a)| - 2$
$3. ~ \forall a : |B(a)| \geq 4 ~ \exists S_{ij}(a) : |B(S_{ij}(a))| = |B(a)| - 4$

Из этих теорем следует решение: $S \; = \displaystyle\left\lfloor \frac{|B(a)|}{4} \right\rfloor + \left\lfloor \frac{|B(a)| \mod 4}{2} \right\rfloor$

Автор вопроса в некоторой мере подтвердил мою правоту, т.к. ему удалось создать корректное решение на моих тезисах — но формального доказательства своей догадки я так и не смог привести. И по сему, обращаюсь за помощью к математическому сообществу.

P.S.: для [2] очевидно, что при существовании в $a$ сегмента из 4 или более последовательно монотонных элементов, доказательство тривиально: нужно просто поменять местами два средних элемента. Но как быть с векторами, где существуют только И-образные и N-образные сегменты (3 последовательно монотонных элемента в середине, и по одному, ломающему монотонность — по краям), ума не приложу.

[grizzly]

blondinko в сообщении #1238831 писал(а):

$1. ~ |B(S_{ij}(a)) - B(a)| \leq 4 ~ \forall a, S_{ij}(a)$ (доказана)
$2. ~ \forall a : |B(a)| \geq 2 ~ \exists S_{ij}(a) : |B(S_{ij}(a))| = |B(a)| - 2$
$3. ~ \forall a : |B(a)| \geq 4 ~ \exists S_{ij}(a) : |B(S_{ij}(a))| = |B(a)| - 4$

Из этих теорем следует решение: $S \; = \displaystyle\left\lfloor \frac{|B(a)|}{4} \right\rfloor + \left\lfloor \frac{|B(a)| \mod 4}{2} \right\rfloor$

Допустим 1.--3. доказаны. Поясните, пожалуйста, как Вы из этого выводите минимальность Вашего $S$.

[svv]

blondinko в сообщении #1238831 писал(а):

$S \; = \displaystyle\left\lfloor \frac{|B(a)|}{4} \right\rfloor + \left\lfloor \frac{|B(a)| \mod 4}{2} \right\rfloor$

Чуть проще $S=\left\lfloor \dfrac{|B(a)|+2}{4}\right\rfloor$. Ручаюсь лишь за эквивалентность, не за правильность.

[blondinko]

svv в сообщении #1238872 писал(а):

Чуть проще $S=\left\lfloor \dfrac{|B(a)|+2}{4}\right\rfloor$. Ручаюсь лишь за эквивалентность, не за правильность.

Бесспорно. Но я умышленно оставил в том виде, что есть: см. ниже.

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

Допустим 1.--3. доказаны. Поясните, пожалуйста, как Вы из этого выводите минимальность Вашего $S$.

Для начала, пусть взято такое $a$, что $\displaystyle\left\lfloor \frac{|B(a)|\, \mbox{mod}\, 4}{2} \right\rfloor = 0$, т.е. $|B(a)| = 4k + (|a|+1)\, \mbox{mod}\, 2, ~ k \in \mathbb{N}$.
Тогда если предположить, что $\exists S' < \displaystyle\left\lfloor \frac{|B(a)|}{4} \right\rfloor$, где также достигается минимум, т.е. $(|a|+1)\, \mbox{mod}\, 2$, то имеем противоречие:

$$\begin{cases} |B(\overbrace{S_{{i_1}{i_2}}(S_{{i_3}{i_4}}(... S_{{i_n}{i_k}}}^{S'}(a)...)))| = |B(a)| - 4S' > 4k + (|a|+1)\, \mbox{mod}\, 2 - 4k = (|a|+1)\, \mbox{mod}\, 2 \\ |B(\underbrace{S_{{i_1}{i_2}}(S_{{i_3}{i_4}}(... S_{{i_n}{i_k}}}_{S'}(a)...)))| = (|a|+1)\, \mbox{mod}\, 2 \end{cases}$$

Аналогично, если $\displaystyle\left\lfloor \frac{|B(a)|\, \mbox{mod}\, 4}{2} \right\rfloor = 1$, то $|B(a)| = 4k + 2 + (|a|+1)\, \mbox{mod}\, 2, ~ k \in \mathbb{N}$. Если $\exists S' \leq \displaystyle\left\lfloor \frac{|B(a)|}{4} \right\rfloor$, то, согласно [2] и [3], имеем:

$$\begin{cases} |B(\overbrace{S_{{i_1}{i_2}}(S_{{i_3}{i_4}}(... S_{{i_n}{i_k}}}^{S'}(a)...)))| \geq |B(a)| - 4 \left\lfloor \frac{|B(a)|}{4} \right\rfloor = 4k + 2 + (|a|+1)\, \mbox{mod}\, 2 - 4k \\ |B(\underbrace{S_{{i_1}{i_2}}(S_{{i_3}{i_4}}(... S_{{i_n}{i_k}}}_{S'}(a)...)))| = (|a|+1)\, \mbox{mod}\, 2 \end{cases}$$

И вот оно, второе противоречие.

[grizzly]

blondinko
То был глупый вопрос.

blondinko в сообщении #1238831 писал(а):

для [2] ... Но как быть с векторами, где существуют только И-образные и N-образные сегменты (3 последовательно монотонных элемента в середине, и по одному, ломающему монотонность — по краям)

А какие с этим могут быть проблемы? Отдельное И или N даёт нулевую сумму, так ведь? Тогда проблема только в стыках? Разве сложно рассмотреть все возможные варианты состыковки двух блоков?

[blondinko]

grizzly, да, отдельный N или отдельный И даёт нуль. Проблема в том, что они могут друг на друга накладываться, и тогда изменения одного влекут изменения соседнего наложенного — и есть такие ситуации, при которых $B(a)$ остаётся без изменений. Но да, чуть позже я сюда попробую прислать на рецензию полное доказательство [2].
А вот что делать с [3], где также можно набрать $\pm 4$ зацеплением И-ев или N-ов — и при том не исключено, что через «гребёнку» суммы $\pm 1$, которая аннулирует всяческие зависимости величин в смежных И или N? Там есть парочка очень нетривиальных условий, без исполнения которых ничего не выйдет. И то ли я что-то упускаю, то ли одно из двух — но не всегда они могут соблюдаться.

[grizzly]

blondinko в сообщении #1238882 писал(а):

А вот что делать с [3]

Да, это проблема. Я пока не знаю, как подступиться, чтобы искать красивое решение. Но всё же кажется, что и в этом случае не настолько много вариантов, чтоб их нельзя было перебрать полным перебором (с использованием компьютера). Но сначала нужно какие-то ограничения наложить аналитически.

blondinko в сообщении #1238882 писал(а):

Там есть парочка очень нетривиальных условий, без исполнения которых ничего не выйдет. И то ли я что-то упускаю, то ли одно из двух — но не всегда они могут соблюдаться.

Да, Вы расскажите, пожалуйста, подробнее, что уже было замечено и что не получается -- чтобы вместе не блудить в одних и тех же соснах.

[svv]

К сожалению, гипотеза 3 неверна. Минимальное число элементов, для которых существует плохая расстановка, равно 11. Вот одна из них:
$0,7,8,3,4,10,1,6,9,2,5$
Её битонность равна $4$, но ни одна из $55$ расстановок, получаемых из неё перестановкой двух элементов, не имеет битонность $0$.
Интересно, что битонность $6$ из неё тоже нельзя получить. Поэтому она заслуживает названия «болото».
Проверьте, пожалуйста, мои утверждения.

Мораль: если что-то упорно не удаётся доказать...

[blondinko]

Охохо, позор мне Я с трёх до десяти перебирал…
Похоже, стóит попытаться выделить свойства таких «болот».

[svv]

Вашей вины тут нет (на каком-то количестве Вы же должны были остановиться), но как теперь быть?..

[blondinko]

Наверное, доказывать наконец [2] и заменять [3] на методику построения трассы перестановок, не проходящей через болота, если такая возможна.