Новогодняя елка

Значительно легче решать задачу, если известна сумма чисел в каждой гирлянде и число, записанное в вершине елки. Эти числа вычисляются однозначно. Найти их можно, например, составив две системы уравнений, а для составления этих уравнений используйте сумму всех расставляемых чисел от 1 до 31.

Пусть в вершине елочки записано число \(x\), а сумма чисел в каждой гирлянде равна \(S\). Сумма всех чисел от 1 до 31 равна 496. Эту сумму можно подсчитать двумя способами. Если суммировать горизонтальными гирляндами, то получим \(5S+x=496\). Если суммировать гирляндами, спускающимися сверху вниз, то получим \(6S — 5x = 496\). Решая систему этих уравнений, найдем \(x = 16\) и \(S = 96\).

Теперь нужно расставить числа, чтобы выполнялись все условия задачи. Запишем в вершине елочки число 16 и временно уберем из рассмотрения эту ячейку (рис. 2). Трапециевидную сетку из оставшихся свободных ячеек можно деформировать так, чтобы получилась прямоугольная сетка \(5\times6\), в которую нужно расставить числа от 1 до 15 и числа от 17 до 31. Причем так, чтобы сумма шести чисел в каждом горизонтальном ряду равнялась 96, а сумма пяти чисел в вертикальных рядах равнялась \(96-16 = 80\).

Рис. 2.

Нетрудно разбить расставляемые числа на пять групп по шесть чисел так, чтобы сумма чисел в каждой группе равнялась 96. Например так: {1, 9, 11, 14, 30, 31}; {2, 12, 13, 19, 22, 28}; {3, 6, 10, 24, 26, 27}; {4, 8, 15, 21, 23, 25}; {5, 7, 17, 18, 20, 29}. Запишем их в порядке возрастания в таблицу \(5\times6\) построчно (рис. 3, слева). Понятно, что в полученной таблице построчные суммы удовлетворяют условию задачи, а вертикальные суммы нет. Если переставлять числа внутри строки, то сумма всех чисел строки не изменится и останется равной 96, а в вертикальных рядах сумма будет меняться. Наша цель теперь, переставляя числа внутри строки, добиться такого расположения чисел, чтобы суммы чисел в вертикальных рядах были равны по 80. Это нетрудно сделать, пример такой расстановки показан на рис. 3, справа.

Рис. 3.

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

Рис. 4.

Задача имеет много решений. Только из приведенного на рис. 4 решения можно получить много других, меняя местами горизонтальные гирлянды или переставляя гирлянды, спускающиеся с вершины елочки вниз. Число решений можно посчитать: перестановок горизонтальных гирлянд — 5!, перестановок гирлянд, спускающихся вниз, — 6!, поэтому всего получим \(\frac{5!\cdot6!}{2}=43200\) решений. Деление на 2 исключает решения, симметричные относительно вертикальной оси елочки.

Елочку из нашей задачи условно назовем пятиэтажной (поскольку в ней пять горизонтальных гирлянд). «Трехэтажный» вариант предлагался младшеклассникам в журнале «Квантик». В преддверии Нового года украсить гирляндами четырехэтажную елочку предлагалось читателям-решателям задач на сайте diofant.ru. Для 80% решателей задача оказалась по зубам и играла скорее роль поздравительной открытки. Красивого алгоритма расстановки чисел по ячейкам гирлянды никто не придумал.

Интересно и то, что задача обобщается на случай для \(n\)-этажной елочки. Найдем число, стоящее в вершине елочки, и магическую сумму для такой елочки. Отметим, что \(n\)-этажная елочка содержит \(n\) горизонтальных гирлянд, и \(n+1\) гирлянд, спускающихся с ее вершины вниз. Каждая гирлянда содержит по \(n+1\) числу. Пусть в вершине \(n\)-этажной елочки записано число \(x\), а сумма чисел в каждой гирлянде равна \(S\). Ячейки \(n\)-этажной елочки заполняются натуральными числами от 1 до \(N=n(n+1)+1=n^2+n+1\). Сумму всех чисел от 1 до \(n^2+n+1\) можно посчитать, используя формулу суммы членов арифметической прогрессии: она равна \(\frac12(n^2+n+2)(n^2+n+1)\).

Пользуясь гирляндой, эту сумму можно подсчитать двумя способами. Если суммировать горизонтальными гирляндами, то получим, что она равна \(nS+x\). Если суммировать гирляндами, спускающимися сверху вниз, то получим, что она же равна \((n+1)S-nx\). Решая систему этих уравнений, найдем \(x=\frac12(n^2+n+2)=\frac12n(n+1)+1\) и \(S=\frac12(n+1)(n^2+n+2)\).

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

Рис. 5.

На этом рисунке можно заметить несколько числовых последовательностей. Удивительно, но они уже имеются в Энциклопедии целочисленных последовательностей Нила Слоуна (OEIS).

Например, в вершинах елочек желтым цветом выделены числа 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, ... Это последовательность с номером A000124. В Энциклопедии она зовется «последовательностью ленивого ресторатора» (Lazy caterer's sequence), поскольку члены последовательности равны максимальному количеству кусков пиццы (то есть круга), которое резчик пиццы может получить, сделав \(n\) прямых разрезов. На рис. 6 показано, что происходит при \(n=1, \ldots,5\). Удивительным образом эти числа тоже задаются формулой \(\frac12n(n+1)+1\). Объяснить, почему в двух настолько разных ситуациях получается одна и та же последовательность, пока не удалось. Если у кого-то из читателей найдется объяснение этому, буду рад ознакомиться с ним.

Рис. 6.