На столе у чиновника Министерства околичностей лежит $n$ томов Британской энциклопедии, сложенных в несколько стопок. Каждый день, придя на работу, чиновник берёт из каждой стопки по одному тому и складывает взятые тома в новую стопку, затем располагает стопки по количеству томов (в невозрастающем порядке) и заполняет ведомость, в которой указывает количество томов в каждой стопке (рис. 2). Кроме сказанного выше, чиновник никогда ничего не делает.
Какая запись будет сделана в ведомости через месяц, если общее количество томов $n=3$, $n=6$, $n=10$ (начальное расположение произвольно)?
Докажите, что если общее число томов $n=\dfrac{k(k+1)}2$, где $k$ — натуральное, то, начиная с некоторого дня, ведомость будет заполняться одинаковыми записями.
Исследуйте, что будет через много дней работы при других значениях $n$.
$(2,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
Разумеется, далеко не каждый ориентированный граф, из каждой вершины которого выходит одна стрелка, обладает единственной «конечной» вершиной, т. е. не всегда, идя по его стрелкам, мы придём в одну и ту же вершину и там останемся (рис. 3). Граф может распадаться на отдельные части, не связанные между собой ни одной стрелкой, может содержать циклы. Поэтому тот факт, что при $n=\dfrac{k(k+1)}2$, начиная с некоторого дня, получается одно и то же расположение $(k,k-1,\ldots,3,2,1)$ совсем не очевиден, и мы сейчас его докажем, тем самым решив пункт б) условия задачи. Рассмотрим сразу произвольное значение $n$.
Вообразим четверть бесконечного листа клетчатой бумаги (рис. 4), клетки которого пронумерованы парами натуральных чисел слева направо и снизу вверх: клетка с номером $(x,y)$ стоит в столбце с номером $x$ и в строке с номером $y$. Изготовим $n$ фишек и разместим их в клетках нашей бумаги следующим образом: в первом столбце столько фишек, сколько томов в первой стопке, во втором столбце столько фишек, сколько томов во второй стопке, и т. д. Размещение фишек на рисунке 4 означает, что в стопках соответственно 8, 3, 3, 1, 1, 1 томов. Преобразование, которое каждый день делает на своём столе чиновник, можно представить на нашем листе в виде следующих трёх операций:
1. Уберём фишки, находящиеся в самой нижней строке (на рисунке 4 они помечены римскими цифрами).
2. Передвинем оставшиеся фишки (они помечены латинскими буквами) на одну клетку вниз и на одну клетку вправо.
3. Теперь выложим на бумагу убранные фишки, но не на нижнюю строку, откуда они были взяты, а на самый левый (освободившийся) столбец в том порядке снизу вверх, в каком они лежали в строке слева направо.
Рис. 4Рис. 5
В результате этих операций рисунок 4 перейдёт в рисунок 5. Правда, результат действия наших трёх операций отличается от того, что делает чиновник, тем, что стопки могут получиться расположенными не в том порядке, какой нужен: на рисунке 5 в самой левой стопке 6 томов, а в следующей за ней — 7 томов. Это легко исправить, передвинув фишку $M$ на одну клетку влево (что показано стрелкой на рисунке 5), но мы таких передвижений пока делать не будем, а ограничимся преобразованием, состоящим из трёх описанных операций. При этом преобразовании фишка, бывшая в клетке $(x,y)$, переходит в клетку $(1,x)$, если $y=1$, или $(x+1,y-1)$, если $y\gt1$.
Назовём $i$-й диагональю совокупность тех клеток $(x,y)$, для которых $x+y=i+1$. Под действием нашего преобразования фишки, находящиеся на $i$-й диагонали, не сойдут с неё, а будут перемещаться по ней по правилу:
$$
\colsep{0pt}{\begin{array}{ccccccc}
(1,i)&{}\to(2,i-1)\to(3,i-2)\to\ldots\to{}&(i,1)\\
\uparrow&&|\\[-8pt]
&\mathclap{\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\text{—}\!\!\text{—}}
\end{array}}
$$
Теперь дополним наше преобразование:
4. В каждой строке, где это возможно, сдвинем все фишки на одно место влево.
Дополненное преобразование уже точно соответствует тому, что делает чиновник. Теперь для некоторых фишек величина $x+y$ может уменьшаться, но она по-прежнему не может увеличиваться. Но величина $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)$, $\ldots$, $i(i+1)$. Фишка на $(i+1)$-й диагонали в эти моменты оказывается там же, где была в нулевой момент. Пустое место на $i$-й диагонали как бы двигается вместе с фишками, и в перечисленные выше моменты времени оно побывает на всех клетках $i$-й диагонали, в том числе окажется слева от клетки, где находится фишка. Но тогда эта фишка передвинется влево, а мы предположили, что все такие передвижения уже закончились. Утверждение доказано.
Что же это за расположение фишек, при котором за неполной диагональю может идти только пустая? Если $n=\dfrac{k(k+1)}2$, то такое расположение только одно: все диагонали от 1-й до $k$-й заполнены фишками, а все следующие диагонали пусты. Это доказывает утверждение б).
Пусть теперь $n\ne\dfrac{k(k+1)}2$. Тогда существует такое $k$, что $$
\dfrac{k(k+1)}2\lt n\lt\dfrac{(k+1)(k+2)}2.
$$
Положим $r=n-\dfrac{k(k+1)}2$. В этом случае расположение фишек, при котором за неполной диагональю следуют пустые, таково: все диагонали от 1-й до $k$-й заполнены фишками, на $(k+1)$-й диагонали находится $r$ фишек, а следующие диагонали пусты. Фишки, находящиеся на $(k+1)$-й диагонали, перемещаются по ней, попадая через каждые $k+1$ шагов на свои прежние места. Это ответ на вопрос в).
Если число фишек на $(k+1)$-й диагонали определяется только общим числом фишек, то их расположение зависит от начального расположения фишек, поэтому при $n\ne\dfrac{k(k+1)}2$ в зависимости от начального расположения томов могут получиться различные наборы периодически повторяющихся записей чиновника (в том числе при одном и том же $n$ может получиться разная длина периода).
Интересно выяснить вдобавок, каково время, достаточное, чтобы из любого начального состояния с $n$ фишками прийти к описанному. Для простоты ограничимся случаем $n=\dfrac{k(k+1)}2$ и обозначим через $T(k)$ наименьшее время, за которое из любого начального расположения томов получается расположение $(k,k-1,\ldots,3,2,1)$.
Докажем, что $T(k)\ge k(k-1)$. Для этого приведём для каждого $k$ конкретное распределение $\dfrac{k(k+1)}2$ томов в стопках, превращающееся в окончательное лишь за $k(k-1)$ шагов: $(k-1,k-1,k-2,k-3,k-4,\ldots,3,2,1,1)$. Его изображение на нашей клетчатой бумаге отличается от изображения окончательного распределения лишь тем, что одна фишка находится не там, где надо: в клетке $(k+1,1)$ вместо клетки $(1,k)$. Под действием нашего преобразования и лишняя фишка на $(k+1)$-й диагонали и «дырка» (т. е. «отсутствие фишки») на $k$-й диагонали начнут передвигаться каждая по своей диагонали. Поскольку $k$-я диагональ короче $(k+1)$-й на единицу, дырка будет опережать фишку и догонит её ровно через $k(k-1)$ шагов.
Подсчёт для случаев $k=1$, 2, 3, 4 даёт значения $T(k)=k(k-1)$, но неясно, как ведёт себя $T(k)$ при больших значениях $k$. Можно доказать, что $T(k)\le C_0\cdot k^5$, где $C_0$ — конкретное число, которое не хочется выписывать, так как вероятнее, что $T(k)$ ведёт себя как степень $k$, меньшая пяти. Интересно было бы доказать или опровергнуть, что $T(k)\le C\cdot k^2$.
