|
|
 |
Условие
В ряд слева направо стоят N коробок, занумерованных подряд числами 1, 2, \ldots, N.
В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми.
Инструкция состоит из последовательно выполняемых команд вида «поменять местами содержимое коробок № i и № j», где i и j – числа. Для каждого ли N существует инструкция, в которой не больше 100N команд, со свойством: для любой начальной раскладки указанного вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее коробок без шариков?
Решение
Давайте считать, что все шарики синие. В пустые коробки положим по красному шарику. Теперь пустых коробок нет. Покажем даже более сильное утверждение: что для любого N есть инструкция не длиннее чем 3N с данным свойством.
Пусть в N коробочках, стоящих в ряд, лежат красные и синие шарики, причём для хотя бы одного из цветов шарики этого цвета лежат подряд (такие конфигурации назовём непрерывными). Тогда можно вычеркнуть часть строк и получить инструкцию, после выполнения которой все синие шарики будут левее всех красных шариков, а также можно получить инструкцию, после которой все красные шарики левее всех синих (нумерация коробок слева направо).
Понятно, что для N=1 такая инструкция есть. Покажем, как из инструкции для k\geqslant 1 сделать инструкцию для 2k и для 2k-1, этого будет достаточно. Обозначим N = 2k или 2k-1.
Инструкция для N будет выглядеть так:
I группа: сначала все пары вида (i, k+i) в любом порядке
Если N нечетно, сюда приходится добавить все пары вида (i+1,i+k) при i\geqslant 1 (назовём эти команды дополнительными).
II группа: инструкция для k первых коробочек из индукционного предположения
III группа: все пары различных чисел вида (i, N+1-i) в любом порядке
При N=2k длина этой инструкции не превышает k + 3k + k = 5k \leqslant 3N. При N=2k-1 длина этой инструкции не превышает 2(k-1) + 3k + (k-1) = 6k-3= 3N.
Теперь покажем, почему она работает. Есть тот цвет, которого не больше k, назовём его основным. Покажем, что можно выполнить часть инструкций I группы так, чтобы все камни основного цвета лежали среди первых k коробочек, и при этом конфигурация среди первых k коробочек будет тоже непрерывной.
Есть четыре варианта того, как могут располагаться камни основного цвета.
- они идут подряд, и все они среди левых k коробок – ничего делать не надо;
- они идут подряд, и все они среди правых коробок – используем все пары вида (i, k+i);
- они есть и среди левых k коробок, и среди остальных правых, при этом они идут подряд. Заметим, что ни в какой паре вида (i, i+k) нет двух камней основного цвета. Все основные камни тогда перенесем справа налево (тогда камни не основного цвета будут среди первых k камней лежать подряд.
- Камни основного цвета – самые первые и самые последние. Перенеся последние влево (при нечётном N используя дополнительные операции), получаем требуемое.
(Чтобы понять алгоритм, можно представить расположение коробочек не в ряд, а по окружности.)
После этого применим часть инструкций II группы, чтобы среди первых k коробочек слева оказались все камни основного цвета.
После этого окажется, что среди N коробочек сначала идут подряд камни одного цвета, а потом камни другого. То есть мы пришли либо к искомой ситуации, либо к зеркальной. Перестановками третьей группы, если надо, отразим конфигурацию, и получим требуемое.
