Математические бусы

Для каждого натурального числа можно определить его возможных соседей, не превосходящих данное число \(n\) (начните с малых \(n\)). Так у вас появятся однозначно определяемые «сцепки» из трех или более чисел. Подумайте теперь, как их соединить вместе.

Покажем, что при \(n=32\) расстановка возможна.

Начнем с того, что нарисуем по кругу точки и пронумеруем их от 1 до 32. Соединим отрезками те пары точек, номера которых в сумме дают квадрат. Точка с номером 1 будет соединена с четырьмя точками 3, 8, 15 и 24 (потому что соответствующие сумму равны 4, 9, 16 и 25). Точку с номером 2 — с тремя точками 7, 14 и 23, и так далее. Проведя все возможные отрезки, мы получим схему, изображенную на рис. 1.

Рис. 1.

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

Из вершин нашего графа выходит от 2 до 4 ребер. Если мы хотим построить замкнутый маршрут, проходящий по всем вершинам графа, то, значит, маршрут должен зайти в каждую вершину и выйти из нее. Обратим внимание на вершины с номерами 16, 25, 26, 27, 28, 29, 30, 31 и 32. В них сходятся ровно по два ребра, поэтому эти ребра обязательно должны быть в маршруте нашего обхода. Выделим их синим цветом (рис. 2).

Рис. 2.

Заметим, что точки с номерами 7, 9 и 20 теперь приходит по два синих ребра. Следовательно, остальные ребра с концами в этих точках нужно удалить. После удаления ребра 2–7 в точке номер 2 останется два ребра (2–14 и 2–23), а значит, они должны быть включены в маршрут (и покрашены синим). Теперь в вершине номер 23 есть два синих ребра, и поэтому ребро 23–13 лишнее, удаляем его. Тогда в вершине 13 остаются два ребра 13–3 и 13–12, которые надо выделить. Текущее состояние графа показано на рис. 3.

Рис. 3.

Рассмотрим выделенную двухзвенную ломаную 6–30–19: ее концы не могут быть соединены, ведь тогда получится изолированный цикл, вершины которого не войдут в маршрут. Значит, ребро 6–19 нужно удалить, что повлечет выделение ребра 19–17, удаление ребра 17–8 и выделение ребра 8–1 (рис. 4).

Рис. 4.

До этого момента выделение и удаление ребер графа происходило однозначно. Далее решение разветвляется на три случая. Рассмотрим вершину номер 3. В ней есть одно выделенное ребро (3–13), а вот вторым выделенным ребром может быть одно из ребер 3–1, 3–6 и 3–22 (отмечены красным цветом на рис. 5).

Рис. 5.

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

На рис. 6 слева показан маршрут, проходящий все 32 вершины графа, который и дает единственное решение задачи: осталось лишь выписать по кругу номера точек, следуя построенному маршруту. Результат изображен на рис. 6 справа.

Рис. 6.

Оказывается, что \(n=32\) — наименьшее, при котором искомая расстановка возможна. То есть при \(n\le31\) задача не имеет решения. Докажем это.

    1) Случаи \(n=1\), \(n=2\) и \(n=3\) тривиальные.

    2) Если \(4\le n\le 30\), то в каждом наборе есть хотя бы одно число, которое является слагаемым только одной «квадратной» суммы. На рис. 7 выписаны все наборы и в каждом наборе такие числа выделены красным цветом. Наличие хотя бы одного такого числа в наборе делает невозможным построение замкнутого маршрута (ведь в нем у каждого числа по два соседа, дающих с ним в сумме полный квадрат). На языке теории графов это звучит так: если в графе есть вершина степени меньше 2, то в нем не существует гамильтонова цикла.

Рис. 7.

    3) Наконец, остался случай \(n=31\). В этом случае в наборе уже нет «удачного» числа, которое входит менее, чем в две «квадратные» суммы, поэтому доказывать будет потруднее. Придется провести рассуждения, аналогичные случаю \(n=32\), и показать, что строящийся маршрут будет обрываться, раньше, чем в него войдут все вершины.

Итак, расставим числа от 1 до 31 по кругу и рассмотрим соответствующий граф.

Соединим отрезками пары точек, номера которых в сумме дают квадратное число. Снова заметим, что есть точки, из которых выходит ровно по два ребра. Выделим все такие ребра цветом (рис. 8, слева). Удалим ребра 7–2, 8–1, 9–7, 20–5 и 19–6, так как в вершины, номера которых указаны первыми, уже приходит по два отмеченных ребра (рис. 8, в середине). Выделим цветом оставшиеся два ребра в вершине 2. Удалим ребро 23–13. Выделим цветом оставшиеся два ребра в вершине 13 (рис. 8, справа).

Рис. 8.

До этого момента удаление и выделение ребер при построении искомого маршрута шло однозначно. Далее решение разветвляется на три случая. Рассмотрим вершину номер 3. В ней есть одно выделенное ребро 3–13, а вот вторым выделенным ребром может быть либо ребро 3–1, либо ребро 3–6, либо ребро 3–22 (они отмечены красным цветом на рис. 9). Имеем три случая, каждый из которых однозначно доводится до завершения. Проанализируем полученные маршруты.

Рис. 9.

Если мы выберем ребро 3–1, то сразу получим замкнутый маршрут, проходящий по всем вершинам графа, кроме вершины номер 4, а это нам не годится. В случае ребра 3–6 построены два независимых циклических маршрута: один содержит 11 ребер, другой — 20 ребер. Значит, и в этом случае нет решения. Наконец, в случае ребра 3–22 тоже получается два независимых цикла: в одном 14 ребер, во втором — 17. То есть и тут нет решения. Тем самым мы показали, что при \(n=31\) искомой расстановки не существует.

А что, если \(n\ge33\)? Существуют ли расстановки чисел в этих случаях?

Попробуем найти расстановку при \(n=33\). Конечно, это можно сделать с помощью графов (аналогично тому, что мы делали в решении), но это долгий способ. Нам-то ведь всего лишь нужно в набор с уже известной расстановкой добавить одно число 33, про которое известно, что его соседями могут быть только три числа — 3, 16 и 31.

«Выпрямим» круговую расстановку чисел, являющуюся решением задачи при \(n=32\), то есть запишем ее в виде строки и попробуем вставить в нее число 33. Потенциальные соседи числа 33 выделены жирным шрифтом: 1-8-28-21-4-32-17-19-30-6-3-13-12-24-25-11-5-31-18-7-29-20-16-9-27-22-14-2-23-26-10-15.

Попробуем переставлять блоки чисел так, чтобы два выделенных числа оказались рядом, следя при этом за тем, чтобы свойство квадратности сумм соседних чисел сохранялось. Здесь нам повезло и все делается буквально в один шаг. Рассмотрим выделенный красным цветом блок чисел от 31 до 20: 1-8-28-21-4-32-17-19-30-6-3-13-12-24-25-11-5-31-18-7-29-20-16-9-27-22-14-2-23-26-10-15.

Запишем его в обратном порядке, получив новую расстановку, в которой выделенные числа 31 и 16 оказались рядом. При этом пары соседних чисел не изменились, кроме одной: появилась новая пара 5–20, сумма чисел которой, по счастливому совпадению, равна 25: 1-8-28-21-4-32-17-19-30-6-3-13-12-24-25-11-5-20-29-7-18-31-16-9-27-22-14-2-23-26-10-15.

Остается между числами 31 и 16 вставить число 33 и получится расстановка, являющаяся решением задачи при \(n=33\): 1-8-28-21-4-32-17-19-30-6-3-13-12-24-25-11-5-20-29-7-18-31-33-16-9-27-22-14-2-23-26-10-15.

На рис. 10 показана она же, но числа записаны по кругу.

Рис. 10.

Аналогично, переставляя блоки чисел в полученном решении для \(n=33\), можно перейти к расстановке для \(n=34\). Соседями числа 34 могут быть числа 2, 15 и 30 (ведь только с этими числами оно в сумме дает квадрат). Значит, какие-то два из них нужно сделать соседями, переставляя блоки. Пусть, например, это будут числа 15 и 30. Возьмем расстановку для \(n=33\) и выделим в ней блок чисел от 6 до 15: 1-8-28-21-4-32-17-19-30-6-3-13-12-24-25-11-5-20-29-7-18-31-33-16-9-27-22-14-2-23-26-10-15.

Если записать его обратном порядке, то числа 15 и 30 окажутся соседями, но в конце окажется число 6, которое не сочетается с числом 1 (их сумма не является квадратом): 1-8-28-21-4-32-17-19-30-15-10-26-23-2-14-22-27-9-16-33-31-18-7-29-20-5-11-25-24-12-13-3-6.

К счастью, ситуация легко поправима. Вспомним, что при решении задачи было отмечено, что тройка чисел 6–30–19 обладает свойством цикличности: любые два из этих трех чисел в сумме дают квадрат. Поэтому в полученной расстановке число 6 можно вставить между числами 19 и 30. Последним в окажется число 3, которое зацикливается с 1. Осталось, как и планировалось, число 34 вставить между 15 и 30: 1-8-28-21-4-32-17-19-6-30-34-15-10-26-23-2-14-22-27-9-16-33-31-18-7-29-20-5-11-25-24-12-13-3.

Общего алгоритма построения расстановок я не придумал. Может, кому-то из читателей это удастся сделать? Рассмотренный способ перестановки числовых блоков в расстановке для \(n\) первых чисел и вставки числа \(n+1\), похоже, работает, но только индуктивный переход не доказан!

Этим же способом была найдена расстановка для \(n=35\), привожу ее без подробных объяснений: 1-8-28-21-4-32-17-19-6-30-34-15-10-26-23-2-14-22-27-9-16-20-5-11-25-24-12-13-3-33-31-18-7-29-35.

Такие расстановки исследовал Уильям Маршалл — математик-любитель из Новой Зеландии. Проведя компьютерное исследование задачи при значениях \(n\ge32\), он установил, что задача имеет решение для всех натуральных значений \(n\) от 32 до 47 включительно. Более того, для каждого такого \(n\) он нашел число различных решений. Например, при \(n=33\) существует тоже единственная расстановка, а при \(n=34\) задача имеет 11 решений. Все его результаты отражены в таблице:

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