[Trotil]

У Васи есть набор кубиков пронумерованных числами от 1,2,...,n, которые выстроены в ряд в некотором порядке. Вася пытается расставить их в порядке возрастания номеров следующим образом. Найдя некоторый (произвольный) кубик, стоящий не на своем месте, он его вынимает и вставляет его на правильное место, сдвигая остальные кубики, не меняя порядка их следования. Сумеет ли Вася гарантированно закончить сортировку кубиков за конечное время?

Представьте, что на кубик для перемещения ему указывает вредная девочка Оля, которая хочет, чтобы Вася сортировал бесконечно долго. Сможет ли она добиться этой цели или же Вася рано или поздно все-таки отсортирует кубики, вопреки Олиному желанию?

Comments

[Дилетант]

Мне почему-то кажется, что по индукции можно доказать, что Олю ждёт разочарование.
*Думала про цикличность-ацикличность перестановок, но тут по-моему это никак не влияет.

[Trotil]

Забыл предупредить, что задача фактически олимпиадного уровня.

[Заболекарь]

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

Легко доказать, что это не могут быть точно два: если их два, то они должны чередоваться первый-второй-первый-второй, тик-так-тик-так, без других вариантов между ними. Вынуть-вставить за один шаг можно только один кубик. Вот мы вынули некий кубик А, вставили, получили из первого порядка второй. Чтобы из второго порядка получить опять первый, необходимо как минимум переместить кубик А обратно. Поскольку кубик А уже на своём месте, переместить его обратно методом "вынуть-вставить" не получится. Значит, его надо переместить перемещением другого кубика, а так он сдвинется максимум на одну позицию. Значит, его изначальная позиция должна отличаться от «правильной» на единицу. Кроме того, для того, чтобы ход вообще произошёл, необходимо переместить какой-нибудь кубик Б на правильное место. Естественно, для кубика Б действует абсолютно та же логика, что и для А. Его позиция при втором порядке тоже отличается от позиции при первом на единицу. Также второй и первый кубик не могут быть по разные стороны от «правильной» позиции любого из кубиков (ибо тогда тот, который сейчас стоит на правильной позиции, там и останется, а это значит, что он во всех позициях стоит на одном и том же месте, чего быть не может по определению). Но по одну сторону они тоже не могут быть: если это позиция того кубика, что подальше, то расстояние между ним и его правильной позицией больше единицы, а если того, что поближе, то тот, что подальше, от перемещения не сдвинется (а это значит, что он во всех позициях стоит на одном и том же месте, чего быть не может по определению). Единственный оставшийся вариант: у обоих кубиков одна и та же правильная позиция. Но тогда у них и номер одинаковый, а этого быть не может.

Щас буду думать дальше.

[Хазг]

"за конечное время" что подразумевается по этой фразой?

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

[Слушатель]

Trotil

Для заданного множества {1...n} множество его перестановок конечно и его мощность равна n!. Значит для любого члена из множества перестановок можно придти к требуемому члену который есть монотонно возрастающая посл-ть за конечное число шагов.

[Amicus Plato]

Слушатель
дело же не совсем в этом.
Мы можем образовать бесконечно длинную последовательность состояний (под состоянием имеется в виду одна любая перестановка), которая никогда не сойдется к заданной. (Нигде ведь не сказано, что перестановки не должны повторяться).
То есть вопрос в том, можно ли этого добиться, используя метод, описанный Тротилом.
Это, например, как в игре "15". В ней есть такие начальные состояния из которого конечное состояние недостижимо.
А здесь наш главный фактор: вредная девочка Оля.
Т.е. нужно доказать или опровергнуть принципиальную остановку машины Тьюринга, "поставленной в такие условия".

[Слушатель]

Amicus Plato

Тогда так: вредная девочка Оля может указать на кубик уже стоящий на своём месте или на кубик стоящий не на своём месте. В первом случае - пустой ход т.е. Вася ничего не делает и Оле необходимо указать на другой кубик. Во втором случае Вася переносит кубик на своё место и задача ставится для n - 1 кубика. Число кубиков с каждым ходом Васи который зависит от указания Оли или постоянно или уменьшается на 1. Число кубиков конечно и равно n. Значит Вася придёт к состоянию отсортированного по возрастанию массива.

[Trotil]

вредная девочка Оля может указать на кубик уже стоящий на своём месте

не может по условию.

Во втором случае Вася переносит кубик на своё место и задача ставится для n -1 кубика.

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

[Заболекарь]

Мы можем образовать бесконечно длинную последовательность состояний (под состоянием имеется в виду одна любая перестановка), которая никогда не сойдется к заданной.

Собственно, я уже доказал, что для двух состояний не можем. Может, у кого-нибудь есть идеи, как доказать то же самое для n состояний?

[Дилетант]

Заболекарь

Собственно, я уже доказал, что для двух состояний не можем. Может, у кого-нибудь есть идеи, как доказать то же самое для n состояний?

Я думала об этом изначально. Только никак не могу до конца додумать. Это можно доказать по индукции.
Для n=2 доказали.
Теперь предположим, что это верно для n, и докажем, что верно для n+1.
Для этого нам надо (всего лишь) поставить первый кубик на первое место, или последний на последнее. И тогда задача для n+1 сведется к задаче для n, которая предполагается решенной.
Всё без изъяна, если бы не Оля.
Вот надо как-то доказать, что в ее руках рано или поздно окажется первый или последний кубик.

Для произвольно указанного в цепи кубика, назавём его беспорядком
количество всех кубиков с большими чем у него номерами, но
располагающимися слева от него.
Назовём беспорядком всей цепи сумму беспорядков всех её кубиков.
Будем считать, что кубик не на своём месте
если непосредственно слева от него торчит кубик с большим чем у него номером.
Если Оля указывает на кубик не на своём месте, то
перемещаем его влево на одну позицию до те пор, пока он оказывается не на своём месте.
Такая операция строго уменьшает беспорядок цепи.
Следовательно, через конечное число таковых цепь окажется упорядоченной.

[Stauffenger]

Amicus Plato:
нужно доказать..принципиальную остановку машины Тьюринга, "поставленной в такие условия".

А не задействовать ли тут Бритву Оккама?

Crowood:
Будем считать, что кубик не на своём месте
если непосредственно слева от него торчит кубик с большим чем у него номером.

В силу чего,
получаем правиьное решение, но .. совсем другой задачи!
Случается, смотришь одно, видишь другое, а понимать надо третье ..

Дилетант:
Мне .. кажется, по индукции можно доказать то, что Олю ждёт разочарование.

Очень правильно кажется!
И посколку вопрос уже довольно застоялся, думаю, пора сделать подсказку,
А именно,
пусть кубики с номерами выше некоторого M для Оли неприкасаемы
и каждый из таковых аккуратно завёрнут в фольгу, скажем от шоколадки,
так, что номерами своими они глаза ей не мозолят.
Поставим тот же самый вопрос, но лишь в отношинии прикасаемых!
• • •