Условие
Какое наибольшее число точек самопересечения может иметь замкнутая 14-звенная
ломаная, проходящая по линиям клетчатой бумаги так, что ни на какой линии не
лежит более одного звена ломаной?
Решение
Покажем сначала, что любая замкнутая 14-звенная
ломаная имеет 7 горизонтальных и 7 вертикальных звеньев. Действительно, из
каждой вершины ломаной выходят одно вертикальное и одно горизонтальное звено.
По всем 14 вершинам мы насчитаем, таким образом, 14 горизонтальных и 14
вертикальных звеньев. Но при таком подсчёте каждое звено мы учли дважды.
Значит, имеется 7 горизонтальных и 7 вертикальных звеньев.
Занумеруем теперь горизонтальные звенья нашей ломаной ``сверху вниз'' и
выясним, сколько точек самопересечения может лежать на каждом звене. На
первом и седьмом звеньях вовсе нет точек самопересечения, так как выше
первого и ниже седьмого звена нет вершин ломаной. Ясно, кроме того, что на
втором и шестом звеньях может быть не больше двух, а на третьем и пятом
звеньях — не больше четырёх точек самопересечения — по числу вершин
ломаной, лежащих сверху (соответственно, снизу) от этих звеньев. На четвёртом
звене может быть не более шести точек самопересечения. Покажем, что на
четвёртом звене может лежать
на самом деле только пять точек
самопересечения, Действительно, если бы их было шесть, то при этом каждая
вершина ломаной, лежащая выше четвёртого звена, оказалась бы соединённой с
одной из вершин, лежащих ниже этого звена, и обратно. Таким образом, вершины,
принадлежащие четвёртому звену, не с чем было бы соединять. Мы показали, что
наша ломаная не может иметь больше, чем
2 + 4 + 5 + 4 + 2 = 17 точек
самопересечения. Пример ломаной, у которой число точек самопересечения равно
17, показан на рис. 65.
Источники и прецеденты использования
