Математика сломанного лифта

Для получения ответа на первый вопрос достаточно применить соображения четности.

Во втором пункте, попробуйте сначала решить задачу для 11-этажного дома. А затем воспользуйтесь тем, что \(33 = 11\cdot3\).

1) Чтобы побывать на каждом этаже ровно один раз и вернуться, Печкину необходимо совершить ровно 33 поездки. Но после первой поездки Печкин окажется на этаже с четным номером (ведь начинает он с первого этажа). И далее, поскольку сумма и разность двух нечетных чисел четны, после каждой нечетной поездки Печкин будет попадать на этаж с четным номером. Следовательно, он не сможет оказаться на первом этаже после 33 поездок.

2) Для 11-этажного дома задача решается просто. Достаточно всякий раз подниматься на 3 этажа вверх, когда это возможно, а в противном случае спускаться на 8 этажей вниз. Получается такой циклический маршрут: \(1\to4\to7\to10\to2\to5\to8\to11\to3\to6\to9\to1\) (рис. 1).

Рис. 1.

Разумеется, можно проехать по данному маршруту и в противоположном направлении: всякий раз спускаться на 3 этажа, а если это невозможно, то подниматься на 8.

Аналогичные циклические маршруты можно построить и для этажей с 12-го по 22-й и с 23-го по 33-й. Для решения задачи остается «склеить» эти циклы, как показано на рис. 2 (средний цикл посещается в обратном направлении).

Рис. 2.

Очевидно, что при \(u=3\), \(v=8\) требуемый маршрут можно проложить в любом доме, число этажей которого кратно 11. Оказывается, это ограничение важно только для домов с относительно малым числом этажей. Покажем, что, если число этажей достаточно велико, то почтальон Печкин сможет объехать их все, побывав на каждом ровно один раз, и вернуться назад.

Для этого потребуется всего один новый цикл длины 17 (рис. 3).

Рис. 3.

Теперь мы можем с помощью «склейки» получать циклические маршруты для домов с числом этажей, являющимся линейной комбинацией чисел 11 и 17 с целыми неотрицательными коэффициентами. Но числа 11 и 17 взаимно просты (они просты и сами по себе, но для нас важна именно взаимная простота), а это значит, что любое натуральное число, большее 11·17 − 11 − 17 = 159, имеет требуемое представление.

То, что само число 159 не представимо, легко проверить, убедившись в том, что среди неотрицательных чисел вида \(159-18i\) нет ни одного кратного 11. Зато легко представить (убедитесь в этом самостоятельно) следующие 11 чисел 160, 161, ..., 170. Но это означает, что представимы и все последующие числа — ведь каждое из них получается добавлением числа, кратного 11, к одному из этих 11 чисел.

Разумеется, требуемые маршруты могут получаться не только путем склеивания циклов длины 11 и 17. Например, на рис. 4 представлен маршрут для 21-этажного дома.

Рис. 4.

Можно показать, что Печкин может проложить требуемый маршрут для всех домов, с числом этажей более 40, а также — для домов с 11, 17, 21, 22, 27, 28, 31, 32, 33, 34, 36, 37, 38 и 39 этажами.

Выше мы обобщили второй пункт задачи, отойдя от конкретики, связанной с числом 33, но не трогали при этом параметров 3 и 8. Для дальнейших обобщений удобно забыть про Печкина и сломанный лифт и изложить задачу на языке теории графов.

Пусть \(u\) и \(v\) — натуральные числа и \(u<v\). Обозначим через \(G(u,v,n)\) граф, вершинами которого являются натуральные числа от 1 до \(n\). Две вершины этого графа будем считать смежными, если соответствующие числа отличаются друг от друга на \(u\), либо на \(v\).

Граф называется гамильтоновым, если в нем есть простой (без повторов промежуточных вершин) цикл, содержащий все вершины. Сам такой цикл также называется гамильтоновым. В общем случае проверка графа на гамильтоновость — NP-полная задача. Однако для конкретных классов графов иногда удается найти эффективные критерии гамильтоновости. Выше мы выяснили, при каких \(n\) графы \(G(3,8,n)\) гамильтоновы. А как же обстоит дело для других \(u\) и \(v\)?

Очевидно, что при \(n<u+v\) граф \(G(u,v,n)\) не может быть гамильтоновым (у него слишком мало ребер). Ясно также, что граф не может быть гамильтоновым, если \(u\) и \(v\) не взаимно просты. В этом случае граф будет состоять из нескольких связных компонент: в одной компоненте могут находиться только числа (вершины), имеющие равные остатки при делении на \(\mathrm{НОД}(u,v)\). Наконец, граф не может быть гамильтоновым (даже при взаимно простых \(u\) и \(v\)), если все три числа \(u\), \(v\), \(n\) — нечетны. В этом случае граф будет двудолен (четные вершины могут быть смежны только нечетным, а нечетные — только четным). Легко понять, что длины циклов двудольного графа могут быть только четны. На примере графа \(G(3,5,9)\) (рис. 5) хорошо видно, что, стартовав из синей доли, можно вернуться в синюю вершину только после четного числа поездок. Поэтому при нечетном \(n\) у двудольного графа не может быть простого цикла, содержащего все вершины.

Рис. 5.

Итак, допустим, что числа \(u\) и \(v\) взаимно просты, имеют разную четность и \(u+v\ge n\).

Точно так же, как и для \(u=3\), \(v=8\) легко проверяется, что граф \(G(u,v,u+v)\) гамильтонов. Причем для построения гамильтонова цикла в этом случае ничего не надо делать, граф сам является простым циклом, содержащим все вершины. Применяя склейку, можно показать, что гамильтоновыми будут и графы при \(n\), кратных \(u+v\). Чтобы доказать, что графы \(G(u,v,n)\) будут гамильтоновы для всех \(n\), начиная с некоторого, нам достаточно найти хотя бы одно значение \(n\), взаимно простое с \(u+v\), для которого граф будет гамильтонов.

А далее проходят те же рассуждения, что и для частного случая \(u=3\), \(v=8\). А именно: пусть натуральные числа \(a\) и \(b\) взаимно просты, тогда \(ab-a-b\) — наибольшее натуральное число, которое нельзя представить в виде линейной комбинации чисел \(a\) и \(b\) с целыми неотрицательными коэффициентами. Доказать это можно так.

Пусть \(a\) — меньшее из взаимно простых натуральных чисел \(a\) и \(b\). Рассмотрим список из \(a\) чисел \(ab-a-b\), \(ab-a-2b\), ..., \(ab-a-ab\). Докажем, у всех этих чисел разные остатки от деления на \(a\). Пусть это не так и числа \(ab-a-ib\) и \(ab-a-jb\), где \(1\le i<j\le a\), имеют равные остатки. Тогда их разность \((j-i)b\) будет кратна \(a\). Но \(b\) взаимно просто с \(a\). Поэтому на \(a\) должно делиться число \(j-i\), но это невозможно, поскольку \(0<j-i<a\). Итак, у всех этих чисел разные остатки. А поскольку этих чисел \(a\) штук, то каждый остаток встречается ровно один раз. В том числе и остаток 0. Разумеется, делится на \(a\) без остатка последнее число списка. Но оно (и только оно) отрицательно. Значит, вычитая из исходного числа несколько раз число \(b\), нельзя получить неотрицательное число, кратное \(a\). Но это и означает, что \(ab-a-b\) не представимо в виде линейной комбинации \(a\) и \(b\) с целыми неотрицательными коэффициентами.

То, что последующие \(a\) чисел (а значит, и все последующие числа) имеют требуемое представление, доказывается просто. Заметим, что, если ко всем числам нашего списка прибавить некое число \(k\) (\(0<k<a\)), то полученные числа вновь будут иметь разные остатки от деления на \(a\). Следовательно, одно из них будет кратно \(a\). Но теперь это будет не последнее число. Оно-то и обеспечит требуемое представление. Если же ко всем числам нашего списка прибавить по \(a\), то кратным \(a\) вновь станет последнее число. Но при этом оно перестанет быть отрицательным, давая очевидное представление числа \(ab-b\) в виде \(a-1\) экземпляра числа \(b\).

Число \(ab-a-b\), в частности, дает ответ на вопрос: какую наибольшую сумму нельзя набрать монетами двух взаимно простых номиналов \(a\) и \(b\). Оно называется числом Фробениуса, хотя формула для его нахождения была известна еще Джеймсу Сильвестру в середине XIX столетия. А Георг Фробениус исследовал эту задачу для произвольного количества номиналов. В таком виде задача оказалась гораздо сложнее. Так, формула для нахождения числа Фробениуса для трех номиналов была получена только в 2015 году (A. Tripathi, 2017. Formulae for the Frobenius number in three variables).

Вернемся к нашей задаче. Будем называть ребра видов \(\{x,x+u\}\) и \(\{x,x+v\}\) соответственно u-ребрами и v-ребрами. В графе \(G(u,v,n)\) имеется \(n-u\) u-ребер и \(n-v\) v-ребер. Проанализируем, какие из них не вошли в гамильтонов цикл графа \(G(3,8,17)\). Выясняется, что «за бортом» остались \(2u\) u-ребер. Это ребра \(\{1+u,1+2u\}\), ..., \(\{2u,3u\}\) и \(\{1+v,1+u+v\}\), ..., \(\{u+v,2u+v\}\). А нельзя ли применить такой подход в общем случае? Оказывается, можно! Но с одним существенным дополнительным условием: если к изложенным выше ограничениям на \(u\) и \(v\) добавить условие \(2u\le v\), то граф \(G(u,v,3u+v)\) будет гамильтоновым. Причем гамильтонов цикл будет получаться удалением \(2u\) u-ребер, перечисленных выше. Остается добавить, что при сделанных ограничениях числа \(u+v\) и \(3u+v\) будут взаимно простыми.

Если же \(u\) и \(v\) отличаются менее чем в 2 раза, не годится не только наш метод удаления \(2u\) ребер (два указанных нами множества удаляемых ребер имеют в этом случае непустое пересечение), но и никакой другой: граф \(G(u,v,3u+v)\) не является в этом случае гамильтоновым. По этой причине задача о гамильтоновости графов \(G(u,v,n)\) была предложена в одном из конкурсов в рамках «Математического марафона» с дополнительным условием \(2u\le v\). Обойти это ограничение удалось участнику конкурса Олегу Полубасову. Он использовал те же идеи, что приведены выше, но гораздо более изощренную технику для отыскания значений \(n\), взаимно простых с \(u+v\), при которых граф будет гамильтонов. Познакомиться с этим решением можно в третьей главе книги «От задачи к исследованию».

Окончательно получаем: графы \(G(u,v,n)\) гамильтоновы для всех натуральных \(n\), начиная с некоторого, тогда и только тогда, когда числа \(u\) и \(v\) взаимно просты и имеют разную четность. В случае, когда взаимно простые \(u\) и \(v\) оба нечетны, гамильтоновыми, начиная с некоторого \(n\), будут все графы, имеющие четное число вершин.