сортировка случайными вставками

[Руст]

Да упустил, что первые числа меняются после установления уё на место, а потом 2 на место.

[TOTAL]

Dandan писал(а):

это неправильно

Что именно неправильно, сможете сказать?

--------------------------------------------------------------------------------------------------------------

ИСН писал(а):

TOTAL, подходы на локальных инвариантах бесперспективны, потому что локальности у нас нет. Конкретно, в описанной ситуации ничто не мешает единице и числу $P$ потом отдрейфовать вправо, так что это число сможет опять "своим ходом" прыгнуть через единицу, только в другую сторону.

Правее позиции $P$ единица не может дрейфовать,
так как все прыжки через единицу меньших $P$ чисел уже закончены.

--------------------------------------------------------------------------------------------------------------

Ещё решение.

Обозначим $M(P)$ - количество отрицательных (с большего номера на свой номер) прыжков числа $P.$
Очевидно, $M(1) \le 1.$
Так как между каждыми двумя отрицательными прыжками числа $P$ должен быть хотя бы один
отрицательный прыжок меньшего числа, то $M(P) \le M(1)+ \ldots + M(P-1) +1 \le 2^{P-1}.$
Таким образом, всего не более $2^{N-1}-1$ отрицательных прыжков.

[xaxa3217]

без дополнительных функций, все по-школьному:
Стандартная индукция по длине, если кубик со значением $n$ крайний справа, то предположение индукции продвигает насдальше. Иначе, если девочка умеет вводить мальчика в цикл, то выберем начальное расположение кубиков так, что черезконечное число шагов оно вновь повторится. Пусть кубик со значением $n$ стоит на $k$-ой позиции ($k<n$). Назовемлевой стороной набор кубиков с позицией $< k$, правой стороной набор кубиков с позицией $> k$. Под шагом будем подразумевать такой набор элементарных вставок, которые сдвигают кубик (назовем его центральный) созначением n. Понятно, что индукцию можно было бы обобщить так, чтобы не произошло цикла без единого сдвигацентрального кубика. Обозначим за $A$ набор кубиков $a_i$ принадлежащих левой стороне, таких что $a_i \geq k$, а за$B$ принадлежащих правой и $a_i\leq k$. Элементарные вставки не составляющие целого шага не меняют левые и правыестороны, рассмотрим первый целый шаг. Пусть для определенности центральный кубик сдвинулся влево (вправо аналогично),тогда $A$ потеряет один элемент и он уйдет в правую сторону. Рассмотрим максимальную последовательность шагов(указаний девочки) сдвигающую центральный кубик влево, до первого "поворота" направо. Пусть он остановился напозиции $l<k$, тогда левая сторона потеряет (а правая соответственно приобретет) какие-то кубики со значениями точно$>l$, то есть поворот центрального кубика вправо должен происходить за счет некоторого кубика из $B$, тк любыедругие в правой стороне имеют значения $>l$. Итак, один шаг вправо сделан. Теперь движемся вправо до некоторойпозиции $r$ (за которой точно следует шаг влево), в случае $r\leq k$: в левую сторону будут добавляться лишь кубики созначениями $<r$ соотв. $<k$, то есть к $A$ точно не вернется первый ушедший кубик; если же $r > k$, то остановимсяна $r$, далее сдвигаемся на шаг влево, конечно за счет некоторого кубика с левой стороны со значением $\geq r$ исоотв. $>k$, но в левую сторону добавлялись лишь кубики со значением $<r$, поэтому это будет один из кубиков набораA (не добавленных в процессе движения вправо! а именно из начального набора). Пусть значение кубика ушедшего из $A$$i$, а из $B$ $j$ ($i>j+1$ тк их разделяет центральный кубик). Докажем теперь, что между любым двумя поворотами в левой стороне есть один кубик из $B$ или в правой один кубик из $A$, то есть конфигурация на любом шаге не будет совпадать с исходной, а это и будет доказательством исходного утверждения. С помощью индукции по числу шагов, начиная с текущего и следующим предположением: после любого поворота в левой стороне существует кубик из $B$, со значением $j$, а в правой из $A$, со значением $i$, такие что центральный кубик за все время движения не выходил за пределы отрезка $[j,i]$. Как было показано выше для текущего шага это верно. Пусть для определенности центральный кубик оказался на позиции $i$, тогда движемся по необходимости вправо до $r>=i$, но поворот влево может произойти лишь за счет кубика из $A$ поскольку правее мы ни разу не двигались и соотв. из правой стороны в левую могли приходить кубики лишь со значениями $<r$, вот и все, осталось запомнить значение $i'$ ушедшего кубика из $A$ в правую сторону и заявить, что правее $i'$ движения не было. Совершенно аналогично слева.

[Dandan]

TOTAL писал(а):

Ещё решение.

Обозначим $M(P)$ - количество отрицательных (с большего номера на свой номер) прыжков цифры $P.$
Очевидно, $M(1) \le 1.$
Так как между каждыми двумя отрицательными прыжками цифры $P$ должен быть хотя бы один
отрицательный прыжок меньшей цифры, то $M(P) \le M(1)+ \ldots + M(P-1) +1 = 2^{P-1}.$
Таким образом, всего не более $2^{N-1}-1$ отрицательных прыжков.

о, вот это уже понятно Правда пока не понятно, как достигнуть максимальной оценки

[TOTAL]

$2, 3, \ldots, n, 1$
Этот набор нормальный человек упорядочил бы за 1 шаг. Но наш Вася не из таких.
Он будет тянуть резину $2^{n-1} - 1$ дней, переставляя в $k$-ый день число $(2+k_2)$,
где $k_2$ - степень двойки в разложении числа $k$ на простые сомножители.

[Руст]

TOTAL писал(а):

$2, 3, \ldots, n, 1$
Этот набор нормальный человек упорядочил бы за 1 шаг. Но наш Вася не из таких.
Он будет тянуть резину $2^{n-1} - 1$ дней, переставляя в $k$-ый день $(2+k_2)$-ое число,
где $k_2$ - степень двойки в разложении числа $k$ на простые сомножители.

Не очень понятно. Правильно ли я понял, если перед k- ым днём последовательность имеет вид $p(1),...,p(n)$ то в k- ый день переставляется число $p(2+v_2(k))$ на свое место, где $v_2(a)=max(k|| 2^k|a)$. Тогда в $2^{n-3}$ день число n переставится на последнее место и дальше с этого места не сдвинется. Поэтому остаётся не более $2^{n-2}-1$ ходов, т.е. количество ходов не превысит $2^{n-3}+2^{n-2}-1=2^{n-1}-2^{n-3}-1$.
По видимому, правильнее будет в k-ый день передвигать число на месте $1+v_2(k)$. Правда это не работает. Например $n=3$, начальное положение $231$. В первый день двигается первое число и получаем $321$ на второй день должны опять двигать второе число, которое уже на месте.
Вроде работает, если каждый день передвигаем первое число на свое место. Начинаем с этого же положения $23...n1$.

[TOTAL]

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

TOTAL писал(а):

$2, 3, \ldots, n, 1$
Этот набор нормальный человек упорядочил бы за 1 шаг. Но наш Вася не из таких.
Он будет тянуть резину $2^{n-1} - 1$ дней, переставляя в $k$-ый день $(2+k_2)$-ое число,
где $k_2$ - степень двойки в разложении числа $k$ на простые сомножители.

Не очень понятно.

Исправляю неудачное выражение.
В $k$-ый день переставляется число $(2+k_2)$

Пояснение.
Пусть $P$ - это последовательность чисел, которые указывают, каким числом надо делать ход.
Если последовательность $P_n$ (в которую не входит число 1) упорядочивает за $2^{n-1} -1$ ходов набор
$2, 3, \ldots, n, 1$
то последовательность $P_{n+1}=\{P_n, n+1, P_n\}$ упорядочивает за $2^{n} -1$ ходов набор
$2, 3, \ldots, n, n+1, 1$

Пример.
Последовательность $P_3=\{2,3,2\}$ упорядочиват набор $2,3,1$
Последовательность $P_4=\{P_3, 4, P_3\} = \{2,3,2,4,2,3,2 \}$ упорядочиват набор $2,3,4,1$

-------------------------------------------------------------------------------------------------------

Такое впечатление, что верно более общее утверждение (и вдруг его доказать будет проще?).
Пусть на позициях от $1$ до $n$ как-то расположены $n$ различных чисел. Если выбрать $k$ чисел и разрешить делать ходы (по тем же правилам) только ими, то можно сделать не более $2^{k} -1$ ходов.

[Руст]

Так понятно. Заметьте, что сдвиги всегда назад первого числа так же работает. Правда это показывает на небольшой пробел в вашем доказательстве. Все $2^{n-1}-1$ операций только вперёд, и ни одного вперёд, а там вы считаете операции назад.
Более экономный функционал можно выбирать так. Считаем

$$S=\sum_j 2^{s_j}(p(j)\ge j)$$

, где $s(j)$ есть число тех $k<j$, что $p(k)>k$. Ясно, что $S$ убывает и $S\le 2^{n-1}-1$ . Вроде это совпадает с максимальным числом ходов при правильной стратегии Оли.

[TOTAL]

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

Так понятно. Заметьте, что сдвиги всегда назад первого числа так же работает. Правда это показывает на небольшой пробел в вашем доказательстве. Все $2^{n-1}-1$ операций только вперёд, и ни одного вперёд, а там вы считаете операции назад.

Пробел большой, ведь я не доказал, что всего не более $2^{n-1}-1$ операций, а только доказал, что не более $2^{n-1}-1$ ходов назад и не более $2^{n-1}-1$ ходов вперёд. То есть всего не более $2(2^{n-1}-1)$ ходов. Легко доказать, что не более $1.5(2^{n-1}-1)$ ходов, но это не спасает. Сделать только назад $2^{n-1}-1$ ходов можно из $n, 1,2,3, \ldots,n-1$ (У меня "назад" - это в сторону меньших позиций).

Добавлено спустя 49 минут 47 секунд:

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

Считаем

$$S=\sum_j 2^{s_j}(p(j)\ge j)$$

, где $s(j)$ есть число тех $k<j$, что $p(k)>k$. Ясно, что $S$ убывает и $S\le 2^{n-1}-1$ .

Здесь $j$ - номер позиции, а $p(j)$ - число на позиции $j$?
Тогда для $n,1,2, \ldots,n-1$ получаем $S=1$, правильно?

[Руст]

Здесь опять не учёл двойственную составляющую. Для определения экономного функционала надо определит функции $a(j)=1,b(j)=1,c(j)=0, p(j)>j$, $a(j)=0,b(j)=1,c(j)=1,p(j)=j$, $a(j)=-1,b(j)=0,c(j)=1,p(j)<j$. Определит сигнатуры слева и справа $s_l(j)=\sum_{k\le j}a(k),s_r(j)=\sum_{k\ge j}a(k)$ (возможно суммирование не по всем k).
Далее определяется

$$S=\sum_j[2^{s_l(j)-1}]b(j)+[2^{s_r(j)-1}]c(j).$$

Максимум функционала для $n,1,2,...,n-1$ и $2,3,...,n,1$ и равно $2^{n-1}$ и он убывает.

[TOTAL]

Для $n,1,2, \ldots, n-2,n-1,1$ такой функционал обещает очень мало ходов?
Хотя на этом раскладе можно сделать $2^{n-2}$ хода.

[maxal]

Статья по теме:

M. Aigner, D. B. West "Sorting by insertion of leading elements". Journal of Combinatorial Theory Series A, 45(2), 1987, 306-309.

[maxal]

Задача опубликована также в Математическом Просвещении №18 (2014).

Задача также обсуждается в статье Л. Радзивиловский, Г.Юргин "Задача о книжной полке" в номере 19 (стр. 254-256), где доказана верхняя оценка $2^n - 2^{n/2}$.