Надо доказать, что рассматриваемое число самопересечений не может быть больше указанных значений, и привести примеры ломаных, для которых эти значения достигаются.
Ясно, что два звена ломаной пересекаются не более чем в одной точке и что смежные звенья не пересекаются (т. е. не имеют общих точек, кроме общей вершины). Всего замкнутая $n$-звенная ломаная имеет $\dfrac{n(n-1)}{2}$ пар звеньев, в том числе $n$ пар смежных звеньев. Таким образом, число точек самопересечения не превосходит
$$
\dfrac{n(n-1)}{2}-n=\dfrac{n(n-3)}{2}.
$$
Если $n$ нечётно, то $n$-звенная ломаная с таким числом самопересечений существует: достаточно в правильном $n$-угольнике провести все $n$ диагоналей, наименее удалённых от центра (см. рисунок 1 для $n=5$ и $n=7$). Эти звенья составляют замкнутую $n$-звенную ломаную, все несмежные звенья которой пересекаются (в разных точках). Задача а) решена.
Рис. 1
Пусть теперь $n$ чётно. Занумеруем вершины данной $n$-звенной ломаной подряд, начиная с любой, и обозначим через $A$ множество вершин с чётными номерами и через $B$ множество вершин с нечётными номерами. Любое звено ломаной идёт из некоторой точки множества $A$ в некоторую точку множества $B$. Пусть $l$ — прямая, содержащая некоторое звено. Если это звено пересекает все несмежные с ним звенья, то все вершины с чётными номерами лежат по одну сторону от $l$ (мы не принимаем, конечно, во внимание вершин рассматриваемого звена, которые лежат на $l$). Значит, множества $A$ и $B$ лежат по разные стороны от прямой $l$ и при этом имеют с ней по одной общей точке. Таких прямых существует не более двух. Этот факт представляется мне очевидным, но для любителей строгих рассуждений я приведу его доказательство (см. рис. 2).
Рис. 2
Пусть есть три такие прямые. Точнее, пусть $A_1$, $A_2$, $A_3\in A$ и $B_1$, $B_2$, $B_3\in B$ — такие точки, что множества $A$ и $B$ лежат по разные стороны от каждой из прямых $A_1B_1$, $A_2B_2$, $A_3B_3$. Так как точки $A_2$, $B_2$ лежат по разные стороны от прямой $A_1B_1$, а точки $A_1$, $B_1$, лежат по разные стороны от прямой $A_2B_2$, то пересекаются отрезки$A_1B_1$ и $A_2B_2$; пусть $C$ — точка пересечения. Точка $A_3$ лежит по ту жё сторону от прямой $A_1B_1$, что точка $A_2$, и лежит по ту же сторону от прямой $A_2B_2$, что точкa $A_1$; значит, она содержится в угле $A_1CA_2$. По аналогичным причинам точка $B_3$ лежит в угле $B_1CB_2$. Значит, прямая $A_3B_3$ не пересекает хотя бы один из отрезков $CA_1$, $CA_2$ и не пересекает хотя бы один из отрезков $CB_1$, $CB_2$. Пусть она не пересекает $CA_i$ и $CB_j$ (на рисунке это $CA_2$ и $CB_1$); тогда точки $A_i$ и $B_j$ лежат от неё по одну сторону, что противоречит предположению.
Итак, имеется не более двух звеньев, которые пересекают все несмежные с ними звенья. Значит, по крайней мере $n-2$ звеньев не пересекают хотя бы одно из несмежных с ними звеньев; следовательно, имеется по крайней мере $\dfrac{n-2}{2}$ пар непересекающихся несмежных звеньев и общее число точек самопересечения не превосходит
$$
\frac{n(n-3)}{2}-\frac{n-2}{2}=\frac{n(n-4)}{2}+1.
$$
Остаётся при любом чётном $n$ построить $n$-звенную ломаную с $\dfrac{n(n-4)}{2}+1$ самопересечениями.
Проведём в правильном $n$-угольнике все диагонали, ближайшие к его центру, но не проходящие через центр. (При чётном $\dfrac{n}{2}$ они образуют замкнутую ломаную, при нечётном $\dfrac{n}{2}$ — две замкнутые ломаные, симметричные друг другу относительно центра.) Каждая из этих диагоналей пересекает все несмежные с ней диагонали, кроме одной — параллельной ей; это даёт $\dfrac{n(n-4)}{2}$ пересечений. Сотрём две параллельные диагонали, а их концы соединим крест-накрест. (См. рисунок 3 для $n=6$ и $n=12$. Тонкие сплошные линии — это ближайшие к центру не проходящие через центр диагонали правильного $n$-угольника. Пунктирные линии — выбрасываемые диагонали. Жирные сплошные линии — диагонали, которыми они заменяются. Сплошные тонкие и жирные линии составляют нашу ломаную.) Число пересечений увеличится на 1, причём, как легко проверить, $n$ проведённых отрезков образуют замкнутую ломаную. Задача б) решена.
Рис. 3
Приведём ещё несколько зaдач, по форме похожих на разобранную задачу. Прежде всего, можно расширить класс рассматриваемых ломаных, разрешив ломаной распадаться на несколько замкнутых ломаных. Чтобы придать зaдаче более естественную форму, мы сформулируем её так.
На плоскости фиксированы $n$ точек, никакие три из которых не лежат на одной прямой. Некоторые из этих точек соединены отрезками, причём каждая точка соединена ровно с двумя другими. Каково наибольшее возможное число точек пересечения этих отрезков (общие концы не считаются точками пересечения)?
В этой задаче ответ не совпадает с предыдущим ответом. Например, на рисунке 4 показана ситуация, в которой $n=8$, а число точек пересечения равно 18. В то же время число точек самопересечения 8-звенной замкнутой ломаной, по доказанному, не превосходит 17.
Рис. 4
Различные задачи можно поставить в связи с самопересечениями пространственных ломаных. Вообще-то ясно, что у $n$-звенной замкнутой пространственной ломаной число точек самопересечения не может быть больше, чем максимальное число точек самопересечения в плоском случае: спроектировав ломаную на подходящую плоскость, мы получим $n$-звенную плоскую ломаную, у которой самопересечений не меньше, чем до проектирования. С другой стороны, если даны три звена нашей ломаной, любые два из которых пересекаются или имеют общий конец, то эти три звена лежат в одной плоскости. Это наблюдение позволяет доказать без труда, что $n$-звенная ломаная с предельным числом самопересечений обязательно является плоской. Ввиду этого возникают два содержательных пространственных аналога нашей задачи.
1. Каково наибольшее возможное число точек самопересечения $n$-звенной замкнутой пространственной ломаной, про которую дополнительно известно, что:
она не является плоской,
никакие три её звена не лежат в одной плоскости?
Задача б) интересна тем, что в её решении (во всяком случае, известном мне) более простым является случай чётного $n$, а не нечётного, как для плоской ломаной.
Впрочем, резонно возразить, что для пространственной ломаной самопересечения вообще являются противоестественными. Зато для неё естественны заузливания (я не привожу никаких определений, их можно найти, например, в «Кванте» №3 за 1981 г.). В качестве простого упражнения читатель может доказать такое утверждение.
Замкнутая пространственая ломаная, имеющая менее 6 звеньев, не может быть заузлена; замкнутая 6-звенная ломаная может быть заузлена.
Однако заузленная 6-звенная ломаная может быть только «трилистником» (см. рис. 5, а). Следующий по сложности узел — «восьмёрка» (см. рис. 5, б).
Рис. 5
2. Каково наименьшее число звеньев заузленной пространственной ломаной типа восьмёрки?
Вообще интересно связать минимальное число звеньев ломаной, принадлежащей данному типу узлов, с другими инвариантами этого типа узлов (см. «Квант» №3 за 1981 г. и №7 за 1975 г.). Об этом можно сказать слишком много, и поэтому я не скажу больше ничего.
