М655. О чиновниках и циклах

Задача из журнала «Квант». Выпуск №11 1980 года.

М655. На столе у чиновника Министерства околичностей лежит $n$ томов Британской энциклопедии, сложенных в несколько стопок. Каждый день, придя на работу, чиновник берет из каждой стопке по одному тому и складывает взятые тома в новую стопку, затем располагает стопки по количеству томов (в невозрастающем порядке) и заполняет ведомость, в которой указывает количество томов в каждой стопке. Кроме сказанного выше, чиновник никогда ничего не делает.

а) Какая запись будет сделана в ведомости через месяц, если общее кол-во томов $n = 3, n = 6, n = 10$ (начальное расположение произвольно)

б) Докажите, что если общее число томов $n=\frac{1}{2} k (k+1),$ где $k$ — натуральное, то, начиная с некоторого дня, ведомость будет заполняться одинаковыми записями.

в) Исследуйте, что будет через много дней работы при других значениях $n.$

Решение

При $n = 3$ возможны всего три расположения:
$(1, 1, 1)$ — три стопка по одному тому;
$(3)$ — одна стопка из трех томов;
$(2, 1)$ — одна стопка из двух томов и одна стопка из одного тома.

рис. 1

Стрелки на рисунке 1 показывают, во что каждое расположение переходит на следующий день. Из рисунка видно, что, с чего бы мы не начали, не позже, чем через два дня (что записано как $T = 2$), возникает расположение $(2, 1),$ и затем оно будет повторяться. На рисунке 2 показан аналогичный граф для $n = 6.$ Число $m$ возможных расположений здесь равно $11.$ Не позже, чем через $T = 6$ дней после начала работы возникнет расположение $(3, 2, 1),$ и затем оно будет повторяться. Аналогичный граф для $n=10$ имеет $m=42$ вершины, и не позже, чем через $T=12$ дней после начала возникнет расположение $(4, 3, 2, 1),$ и затем оно будет повторяться.

рис. 2

Разумеется, далеко не каждый ориентированный граф из каждой вершины которого выходят одна стрелка, обладает единственной «конечной» вершиной, то есть не всегда, идя по его стрелкам, мы придем в одну и ту же вершину и там останемся (рис. 3). Граф может распадаться на отдельные части, не связанные между собой ни одной стрелкой, может содержать циклы. Поэтому тот факт, что при $n=\frac{1}{2} k (k+1),$ начиная с некоторого дня, получается одно и то же расположение совсем не очевиден, и мы сейчас его докажем. Рассмотрим сразу произвольное $n.$

рис. 3

Вообразим четверть бесконечного листа бумаги в клетку (рис. 4), клетки которого пронумерованы парами натуральных чисел слева направо и снизу вверх: клетка с номером $(x, y)$ стоит в столбце $x$ и в строке $y.$ Изготовим $n$ фишек и разместим их в клетках нашей бумаги следующим образом: в первом столбце столько фишек, сколько томов в первой стопке, во втором столько, сколько томов во второй стопке и т.д. Размещение фишек на рисунке 4 соответствует расположению $(8, 3, 3, 1, 1, 1).$ Преобразование, которое каждый день выполняет чиновник, можно представить в виде трах операций:

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

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

При нашей последовательности операций фишка $(x, y)$ перейдет в клетку $(1, x),$ если $y = 1,$ или $(x+1,y-1),$ если $y>1.$

рис. 5

Назовем $i$-й диагональю совокупность тех клеток $(x, y),$ для которых $x+y=i+1.$ Под действие нашего преобразования фишки, находящиеся на $i$-й диагонали, не сойдут с нее, а будут перемещаться по правилу: $$(1, i)\longrightarrow(2, i-1)\longrightarrow(3, i-2)\longrightarrow…\longrightarrow(i, 1)\longrightarrow(1, i)$$

Теперь дополним преобразование, тем, что в каждой строке, где это возможно, сдвинем все фишки на одно место влево, тем самым упорядочим стопки как надо. Теперь все наше преобразование точно соответствует тому, что делает чиновник. Сдвиг влево означает, что для некоторых фишек величина $x+y$ может уменьшаться, но она по-прежнему не может увеличиваться. Но эта величина — натуральное число, значит она не может уменьшаться бесконечное количество раз. Наступит такой момент, что для всех фишек величина $x+y$ уже не будет уменьшаться. Таким образом каждая фишка займет свою диагональ. Докажем, что тогда для всякого $i$ будет выполняться следующее условие: если $i$-я диагональ не полностью заполнена фишками, то в $(i+1)$-й диагонали нет ни одной фишки.

Докажем от противного: пусть в $i$-й диагонали есть пустая клетка, а в $(i+1)$-й диагонали есть хоть одна фишка. Фишки на $i$-й диагонали (если они есть) передвигаются, попадая через каждые $i$ шагов на прежние места. фишка на $(i+1)$-й диагонали передвигается, попадая через каждые $(i+1)$ шагов на прежнее место. Посмотрим, что происходит в моменты $0, (i+1), 2(i+1), 3(i+1),…,i(i+1).$ Фишка на $(i+1)$-й диагонали в эти моменты оказывается там же, где и была в нулевой момент. Пустое место на $i$-й диагонали как бы двигается вместе с фишками, значит оно побывает на всех клетках $i$-й диагонали, а значит побывает слева от фишки на $(i+1)$-й диагонали. Но тогда эта фишка должна сдвинуться влево, что невозможно, так как мы предположили, что такие перемещения уже закончились.

Что же это за расположение фишек, при котором за неполной диагональю может идти только пустая? Если $n=\frac{1}{2} k (k+1)$, то такое расположение, очевидно, только одно: все диагонали от 1-й до $k$-й заполнены фишками, а все остальные — пустые. Это доказывает утверждение б), так как все фишки не покидают своих диагоналей, и не сдвигаются влево с какого-то момента.

Пусть теперь $n\neq\frac{1}{2} k (k+1)$. Тогда существует такое $k,$ что $$\frac{1}{2} k (k+1)<n<\frac{1}{2} (k+1) (k+2).$$

Положим $r=n-\frac{1}{2} k (k+1).$ В этом случае расположение фишек, при котором за неполной диагональю следуют пустые такое: все диагонали от 1-й до $k$-й заполнены фишками, на $(k+1)$-й диагонали находится $r$ фишек, а следующие диагонали пусты. Фишки, находящиеся на $(k+1)$-й диагонали перемещаются по ней, попадая через каждые $(k+1)$ шагов на свои прежние места. Это ответ на вопрос в).