|
|
 |
Условие
В ряд слева направо стоят $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$ коробочек сначала идут подряд камни одного цвета, а потом камни другого. То есть мы пришли либо к искомой ситуации, либо к зеркальной. Перестановками третьей группы, если надо, отразим конфигурацию, и получим требуемое.
