Тройной ряд

Найдите сумму в нескольких первых множествах M_i и попробуйте установить связь этих сумм с треугольными числами. Эта связь здесь напрашивается сама потому, что общее количество чисел во всех множествах от M₁ до M_n равно треугольному числу.

Повторяющиеся три натуральных числа будем называть тройкой. При разбиении построенного ряда на тройки некоторые их них целиком попадают в одно из множеств, а некоторые тройки разбиваются так, что одно из чисел тройки остается в одном множестве, а два других попадают в следующее множество. Попробуем разобраться, какие тройки разбиваются, а какие нет. В этом нам помогут треугольные числа. В самом деле, суммарное количество чисел в первых \(n\) множествах равно \(1+2+3+4+\ldots+n\), а эта сумма как раз и является по определению \(n\)-м треугольным числом \(T_n=\frac12n(n+1)\).

Выпишем множества построчно. Справа добавим колонку с суммами чисел в каждой строке и колонку с соответствующим треугольным числом.

Выделим желтым цветом множества, номера которых кратны 3. Заметим, что в каждой такой строке последняя тройка помещается полностью и каждое ее число равно трети соответствующего треугольного числа. Почему? Потому что в этом случае суммарное количество чисел в \(n\) первых множествах кратно 3, значит, в нем содержится целое число троек, причем числа последней тройки — это как раз \(\frac13T_n\).

Похожим свойством обладают множества с номером \(3k+2\), то есть строки, идущие непосредственно над желтыми, потому что в этом случае \(T_n\) кратно 3 из-за того, что множитель \((n+1)\) делится на 3. Заметим, что и в этом случае числа последней тройки — это тоже числа \(\frac13T_n\). Выделим их зеленым цветом.

Важный вывод: и желтые, и зеленые строки оканчиваются полными тройками, числа в которых равны \(\frac13T_n\). Теперь можно перейти к ответу на вопросы задачи.

В пункте а) нужно было найти сумму чисел в множестве M₂₄ — то есть в 24-й строке. Можно было бы потрудиться и дописать несколько строк в нашей числовой таблице-пирамиде, увидеть все числа 24-й строки и просуммировать их. Но поскольку нам еще предстоит находить суммы в строках с большими номерами, и мы точно не сможем выписать их полностью, то лучше и здесь воспользоваться универсальными рассуждениями, которые сработают во всех случаях.

Во-первых, строка с номером 24 желтая, потому что ее номер кратен 3. Поэтому она оканчивается тройкой, числа которой равны

Во-вторых, предыдущая строка с номером 23 — зеленая, и поэтому она тоже оканчивается полной тройкой, числа которой равны

Сумму всех чисел в 24-й строке можно найти как утроенную разность между суммой всех чисел от 1 до 100 и суммой всех чисел от 1 до 92:

Конечно, здесь можно просто раскрыть скобки и просуммировать числа от 93 до 100. Так проще, но перспективней найти каждую сумму с помощью формулы суммы первых членов арифметической прогрессии:

Для пунктов б) и в) эти рассуждения можно обобщить. Повторим их для \(n\)-й строки (желтой), где \(n\) кратно 3. Как было показано, и желтые, и зеленые строки оканчиваются полными тройками, числа в которых равны \(\frac{T_n}3\) и \(\frac{T_{n-1}}3\) соответственно, поэтому сумма чисел желтой строки с номером \(n\) равна утроенной разности между такими суммами:

Снова применив формулу для вычисления суммы первых членов арифметической прогрессии, получим

После алгебраических упрощений этой формулы получим, что \(S_n=\frac16(T_n-T_{n-1})(3+T_n+T_{n-1})\). Далее, используя формулы для треугольных чисел \(T_n=\frac12n(n+1)\) и \(T_{n-1}=\frac12n(n-1)\), получим формулу суммы чисел в желтых строках, то есть \(S_n\), когда \(n\) кратно 3, а именно: \(S_n=\frac16n(n^2+3).\)

Рассуждая аналогично, можно получить формулы суммы \(S_n\), когда номер \(n\) строки сравним с числом 2 (это зеленые строки нашей таблицы): в этом случае \(S_n=\frac{n(n^2+3)-2}{6}\), а также формулы суммы \(S_n\), когда номер \(n\) строки сравним с числом 1 (это голубые строки нашей таблицы): в этом случае \(S_n=\frac{n(n^2+3)+2}{6}\). Не приводя полного вывода, насыщенного рутинными преобразованиями, добавим лишь, что в этих случаях надо учитывать, что в зеленых и голубых строках есть по одной неполной тройке — такая «пограничная» тройка разбивается так, что одно число остается в конце голубой строки, а два числа переходят в зеленую строку. Окончательно, формула для вычисления суммы \(S_n\) чисел в множестве \(M_n\) такая:

Теперь, учитывая, что \(1024=3\cdot341+1\) делаем вывод, что числа множества \(M_{1024}\) находятся в голубой строке и их сумма равна \(S_{1024}=\dfrac{1024\cdot(1024^2+3)+2}6=178\,957\,483.\)

Число 2024 имеет вид \(3\cdot674+2\), поэтому числа множества \(M_{2024}\) находятся в зеленой строке и их сумма равна \(S_{2024}=\dfrac{2024\cdot(2024^2+3)-2}6=1\,381\,912\,649.\)

Практически в любой задаче, связанной с рядом натуральных чисел, можно выделить те, или иные числовые последовательности. Например, наша задача «породила» последовательность:

1, 2, 6, 13, 23, 39, 61, 89, 126, 172, 227, 294, 373, 464, 570, 691, 827, 981, 1153, 1343, ..., n-й член которой равен сумме всех чисел в n-й строке. Как показано в решении, а₂₄ = 2316, а₁₀₂₄ = 178 957 483, а₂₀₂₄ = 1 381 912 649. Эту последовательность я отправил в энциклопедию OEIS, она оказалась новой, ее одобрили, сейчас она в базе с номером A370880.

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

Например, рассмотрим последовательность чисел, расположенных на первом месте в каждом множестве M_k, получим последовательность, расположенную на вертикальном «катете» числового треугольника: 1, 1, 2, 3, 4, 6, 8, 10, 13, 16, 19, 23, 27, 31, 36, 41, 46, 52, 58, 64, 71, ... (рис. 1).

Рис. 1.

Заглядываем в энциклопедию OEIS, оказывается эта последовательность там имеется, она давным-давно внесена лично Нилом Слоуном с именем A008748. Формула n-го члена этой последовательности такова: \(a_n=\left[\frac{n(n+1)}6\right]+1\), где квадратными скобками обозначена целая часть числа.

Можно рассмотреть последовательность чисел, расположенных на последних местах в каждом множестве M_k, и получить последовательность, расположенную на «гипотенузе» числового треугольника: 1, 1, 2, 4, 5, 7, 10, 12, 15, 19, 22, 26, 31, 35, 40, 46, 51, 57, 64, 70, 77, ...

Эта последовательность тоже имеется в энциклопедии OEIS под номером A058212, формула ее n-го члена \(a_n=\left[\frac{(n-1)(n+2)}6\right]+1\), где квадратными скобками обозначена целая часть числа.

А вот если рассмотреть числа, расположенные в середине строк с нечетными номерами, а визуально — это числа лежащие на «медиане» числового треугольника, то получим новую последовательность: 1, 2, 5, 9, 14, 21, 29, 38, 49, 61, 74, ...

Удивительно, что ее до сих пор нет в базе, ведь числа, записанные в середине каждой строки с нечетным номером равны среднему арифметическому первого и последнего чисел этой строки, а как мы указали выше и последовательность первых чисел, и последовательность последних чисел уже в базе. Опираясь на это, можно найти формулу n-го члена этой последовательности и отправить последовательность на экспертизу редакторам OEIS, возможно ее опубликуют. Делюсь идеей безвозмездно.

Можно рассмотреть множества чисел в числовых треугольниках, размеры которых с каждым шагом увеличиваются за счет добавления очередной строки. Их суммы тоже образуют новую последовательность (рис. 2): 1, 3, 9, 22, 45, 84, 145, 234, 360, 532, 759, 1053, 1426, 1890, 2460, 3151, 3978, 4959, ... Эта последовательность фактически является последовательностью частичных сумм последовательности, возникшей при решении нашей задачи. Эту последовательность тоже можно считать новой, она отсутствует в базе OEIS.

Рис. 2.

В нашей задаче рассмотрен «утроенный» натуральный ряд. Но можно рассматривать аналогичную задачу для натурального ряда другой кратности, например k, когда каждое число натурального ряда повторено k раз. При некоторых k такие задачи рассмотрены, например, при k = 2 получается задача-предшественница с «удвоенным» натуральным рядом. Ее можно увидеть на сайте «Диофант», где «тусуются» российские (и не только) решатели интересных задач. Задача предлагалась в таком виде:

Задача 2647. Натуральный ряд «удвоили», то есть каждое число записали дважды. Затем полученный ряд разбили на множества: M₁, M₂, M₃, ..., так, что множество M_n содержит n чисел. Ниже вертикальными черточками показано разбиение начала «удвоенного» натурального ряда на множества: 1,|1, 2,|2, 3, 3,|4, 4, 5, 5,|6, 6, 7, 7, 8,|8, 9, 9, 10, 10, 11,|11, 12, 12, 13, 13,... Найдите сумму чисел в множестве M₂₀₂₄.

Задача решается двукратным применением формулы вычисления суммы членов арифметической прогрессии. Попробуйте самостоятельно справиться с этой задачей, учитывая свой опыт общения с «утроенным» натуральным рядом. Мы лишь сообщим, что M₂₀₂₄ = 2 072 868 468.

Понятно, что обычный натуральный ряд можно считать рядом нашей тематике при k = 1.

В журнале «КВАНТ» №8 за 1989 год предлагалась задача, в которой обычный натуральный ряд разбивался на множества. Приведем ее вместе с журнальной иллюстрацией (рис. 3):

Рис. 3.

Задача. Чему равна сумма чисел в десятой строчке числового треугольника, изображенного на рисунке? В сотой строчке? В n-ой строчке?

Для решения задачи достаточно уметь находить сумму m первых натуральных чисел, а именно, знать формулу \(1+2+3+\ldots+m=\frac12m(m+1).\)

Учитывая, что последнее число в \((n-1)\)-й строчке числового треугольника равно \(\frac12n(n-1)\), а последнее число в n-й строчке равно \(\frac12n(n+1)\), можно найти сумму чисел в n-й строчке. Она равна разности между суммой \(\frac12n(n+1)\) первых натуральных чисел и суммой \(\frac12n(n-1)\) первых натуральных чисел. Применяя вышеуказанную формулу, и упрощая выражения, получим, что сумма чисел в n-й строчке числового треугольника равна \(\frac12n(n^2+1)\). Ответив на последний вопрос задачи, легко ответить на два предыдущих: 505; 500050.

Знакомые с магическими квадратами могут заметить, что магическая сумма в магическом квадрате n×n в точности равна \(\frac12n(n^2+1)\) при \(n\ge3\). Неожиданная встреча?! Объясняется она легко. При построении магического квадрата ячейки таблицы n×n заполняются числами от 1 до \(n^2\), их сумма равна \(\frac12n^2(n^2+1)\), а магическая сумма в n раз меньше, то есть равна \(\frac12n(n^2+1)\).

Конечно, любопытные решатели могут углубиться в тему k-кратных натуральных рядов и рассмотреть задачи с разбиением «учетверенного» натурального ряда, «упятеренного» и т. д. Уверен, их ждут интересные встречи на этом пути!