Замкнутые самопересекающиеся ломаные

Александр Блинков, Александр Грибалко
«Квантик» №11, 2019

Рис. 1

В этой статье пойдёт речь о ломаных линиях на плоскости. Для того чтобы изобразить ломаную, достаточно выбрать несколько точек (не меньше трёх), занумеровать их в каком-нибудь порядке, после чего последовательно соединить отрезками точки с соседними номерами. Выбранные точки называются вершинами ломаной, а отрезки — её звеньями (на рисунке 1 — трёхзвенная ломаная с четырьмя вершинами).

Если хотя бы два звена ломаной пересекаются (в своих внутренних точках), её называют самопересекающейся (на рисунке 2 — четырёхзвенная самопересекающаяся ломаная).

И наконец, если первая и последняя вершины ломаной совпадают, её называют замкнутой. В такой ломаной количество вершин совпадает с количеством звеньев (на рисунке 3 изображена пятизвенная замкнутая ломаная).

Рис. 2 и 3

Нас будут интересовать замкнутые самопересекающиеся ломаные.

Начнём с задачи, предложенной А. Пешниным (её частные случаи были использованы на XXV турнире математических боёв имени А. П. Савина).

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

Рис. 4

Этот пример подсказывает, что аналогичным образом можно построить любую ломаную, удовлетворяющую условию, с нечётным количеством звеньев, большим трёх. Достаточно поставить на окружности требуемое количество вершин и последовательно соединить их через одну. Например, на рисунке 4, б — искомая ломаная с девятью звеньями.

Осталось разобраться с ломаными, у которых чётное количество звеньев, начиная с шести.

Искомой шестизвенной ломаной не существует, но доказывать это мы умеем только перебором всех случаев, который не очень интересен.

Для восьми звеньев существует красивый пример (рис. 5, а). Аналогично можно построить ломаную, удовлетворяющую условию, с любым чётным количеством звеньев, большим восьми. Как это делается, понятно из примеров для десяти и двенадцати звеньев, показанных на рисунках 5, б и 5, в. Сначала мы отмечаем на окружности точки, которых на две меньше, чем нужно, и соединяем их через одну. Так как точек чётное количество, получатся две замкнутые ломаные, все звенья которых пересекаются с другой ломаной в двух точках. После этого удаляем по одному звену в каждой ломаной и соединяем ломаные в одну, используя ещё две вершины, расположенные внутри окружности.

Рис. 5

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

Покажем, например, как построить двенадцатизвенную ломаную, удовлетворяющую условию. Изобразим две окружности, которые касаются друг друга внешним образом в некоторой точке. В одной из окружностей построим уже указанным способом пятизвенную ломаную, а в другой — семизвенную, причём точка касания должна быть их общей вершиной. А теперь эту точку «раздвоим» (рис. 6, результат раздвоения — вершины с номерами 1 и 6).

Рис. 6

Аналогично строятся все искомые ломаные, у которых количество звеньев чётное и больше восьми.

Возникает вопрос: почему мы начали с двух точек пересечения звеньев, а не с одной, что, казалось бы, более естественно?

Дело в том, что такой порядок более логичен, так как решение следующей задачи будет во многом опираться на решение рассмотренной.

Сразу заметим, что в этом случае звенья ломаной должны разбиваться на непересекающиеся пары, поэтому у искомых ломаных — чётное количество звеньев. Легко проверить, что замкнутая ломаная из четырёх звеньев условию не удовлетворяет.

Пример искомой ломаной из шести звеньев можно построить, исходя из следующих соображений: помимо того, что не могут пересекаться соседние звенья, не могут пересекаться и звенья, стоящие через одно. Действительно, в этом случае образуется треугольник (рис. 7, а), в который можно будет только «войти», если пересечь среднее звено, но нельзя будет «выйти». Поэтому надо пересекать первое звено с четвёртым, второе — с пятым, а третье — с шестым (рис. 7, б).

Рис. 7

Рис. 8

Пример искомой ломаной из восьми звеньев читателю предлагается построить самостоятельно (см. задачи в конце статьи). А вот пример десятизвенной ломаной можно получить, обратившись к задаче 1. Действительно, рассмотрим пример замкнутой пятизвенной ломаной, которая каждое своё звено пересекает два раза (рис. 4). «Сломаем» каждое звено между двумя точками пересечения и получим искомый пример (рис. 8). Аналогично, рассмотрев семизвенную ломаную из задачи 1, можно получить решение для ломаной с четырнадцатью звеньями; пример восьмизвенной ломаной из задачи 1 помогает получить решение для ломаной из шестнадцати звеньев, и т. д.

Этот приём не годится только для построения двенадцатизвенной ломаной, так как нет шестизвенной ломаной, которая каждое своё звено пересекает два раза. Но в этом случае можно использовать другую идею решения задачи 1: «раздвоение». Построим две ломаные из рис. 7, б с общей вершиной и «раздвоим» её (рис. 9, результат раздвоения — вершины с номерами 6 и 12). Понятно, что идея «раздвоения» вершин более универсальна. В том числе и потому, что позволяет комбинировать ломаные с разным количеством звеньев.

Рис. 9

Надеемся, что идеи и приёмы, описанные выше, помогут при решении других задач.

Художник Мария Усеинова