Комбинаторика на устном туре Турнира Городов

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

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

Воспользуемся методом математической индукции. Понятно, что для такая инструкция есть. Это база индукции. Теперь покажем, как из инструкции для сделать инструкцию для и для этого будет достаточно. Обозначим или Инструкция для будет выглядеть так:

I группа: сначала все пары вида в любом порядке

Если нечетно, сюда приходится добавить все пары вида при (назовём эти команды дополнительными).

II группа: инструкция для первых коробочек из индукционного предположения

III группа: все пары различных чисел вида в любом порядке

При длина этой инструкции не превышает

При длина этой инструкции не превышает Теперь почему она работает. Есть тот цвет, которого не больше , назовём его основным. Покажем, что можно выполнить часть инструкций I группы так, чтобы все шарики основного цвета лежали среди первых коробочек, и при этом конфигурация среди первых коробочек будет тоже непрерывной.

Есть четыре варианта того, как могут располагаться шарики основного цвета.

1) Они идут подряд, и все они среди левых коробок — ничего делать не надо;

2) Они идут подряд, и все они среди правых коробок — используем все пары вида ;

3) Они есть и среди левых коробок, и среди остальных правых, при этом они идут подряд. Заметим, что ни в какой паре вида нет двух шариков основного цвета. Все основные шарики тогда перенесем справа налево (тогда шарики не основного цвета будут среди первых шариков лежать подряд.

4) Шарики основного цвета — самые первые и самые последние. Перенеся последние влево (при нечётном используя дополнительные операции), получаем требуемое.

(Про это всё проще думать, если мыслить расположение коробочек не в ряд, а по окружности.)

После этого применим часть инструкций II группы, чтобы среди первых коробочек слева оказались все шарики основного цвета.

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