Дана горизонтальная полоса на плоскости, края которой — параллельные прямые, и $n$ прямых, пересекающих эту полосу. Каждые две из этих $n$ прямых пересекаются внутри полосы и никакие три не проходят через одну точку. Рассмотрим все пути, начинающиеся на нижней кромке полосы, идущие по данным прямым, и заканчивающиеся на верхней кромке, обладающие таким свойством: идя по такому пути, мы всё время поднимаемся вверх; дойдя до точки пересечения прямых, мы обязаны перейти на другую прямую. Докажите, что среди таких путей
есть путь, состоящий не менее чем из $n$ отрезков;
есть путь, проходящий не более чем по $\dfrac{n}{2}+1$ прямым;
есть путь, проходящий по всем $n$ прямым.
А. В. Карзанов
Всесоюзная математическая олимпиада школьников (1975 год, 8–9 классы)
Обозначим точки пересечения прямых с нижней кромкой полосы по порядку (слева направо) через $A_1$, $A_2$, $\ldots$, $A_n$ (рис. 7). Точки пересечения тех же прямых с верхней кромкой полосы обозначим соответственно через $B_1$, $B_2$, $\ldots$, $B_n$.
Рис. 7
Перечислим некоторые свойства путей, о которых говорится в условии.
1°. По каждому отрезку каждой прямой проходит ровно один путь. Действительно, правила, сформулированные в условии, позволяют единственным способом продолжить путь вверх и вниз до краёв полосы.
2°. Существует $n$ различных путей: из каждой точки $A_1$, $\ldots$, $A_n$ выходит свой путь. Занумеруем их по порядку: 1‑й, 2‑й, $\ldots$, $n$‑й.
3°. Путь, начинающийся в точке $A_k$, заканчивается в точке $B_k$. В самом деле, согласно правилам, каждый путь в точке пересечения прямых переходит на другую прямую, поэтому (рис. 8) пути не могут пересекать друг друга, а лишь соприкасаются вершинами. Таким образом, $k$‑й путь делит полосу на две области — левую, в которой расположены все пути с номерами $i\lt k$, и правую, в которой расположены пути с номерами $i\gt k$. Поэтому $k$‑й путь окончится в $B_k$ (рис. 9).
Рис. 8Рис. 9
Перейдём к доказательству отдельных утверждений задачи.
а) Посчитаем двумя способами общее количество отрезков во всех путях вместе. С одной стороны, каждая прямая разбита на $n$ отрезков, поскольку она пересечена $n-1$ другими прямыми; следовательно, общее число отрезков равно $n^{2}$. С другой стороны, ту же сумму $n^2$ мы должны получить, сложив количества отрезков во всех $n$ путях (мы используем здесь 1° и 2°). Отсюда следует, что хотя бы в одном из путей не менее $n$ отрезков.
б) Оценим количество отрезков в двух крайних путях: 1‑м и $n$‑м. Эти пути, очевидно, ограничивают выпуклые множества: первый — множество точек, лежащих левее всех прямых, последний — множество точек, лежащих правее всех прямых (рис. 10). Ясно, что первый путь лежит слева от ломаной $A_1PB_1$, последний — справа от ломаной $A_nPB_n$, где $P$ — точка пересечения $(A_1B_n)$ и $(A_nB_1)$, и лишь начальные и конечные отрезки того и другого пути лежат на прямых $A_1B_1$ и $A_nB_n$. Что же касается каждой из остальных $n-2$ прямых $A_2B_{n-1}$, $A_3B_{n-2}$, $\ldots$, $A_{n-1}B_2$, то они могут иметь общий отрезок только с одним из крайних путей (если прямая проходит слева от точки $P$, то она не может иметь общий отрезок с правым крайним путём, и наоборот). Из выпуклости крайнего пути вытекает, что каждая из этих $(n-2)$ прямых имеет с ним не более одного отрезка. Таким образом, количество отрезков в двух крайних путях не больше $4+(n-2)$. Отсюда следует, что хотя бы в одном из этих путей не более $2+\dfrac{n-2}2=1+\dfrac n2$ отрезков.
Рис. 10
в) Пусть $m=\dfrac{n+1}2$, если $n$ нечётно (тогда $m$ — средний номер между 1 и $n$), и $m=\dfrac n2$, если $n$ чётно. Докажем, что $m$‑й путь проходит по всем $n$ прямым. Выше (3°) мы говорили, что $m$‑й путь делит полосу на две области, начинается в точке $A_m$ и заканчивается в точке $B_m$. Каждая из $n$ прямых $A_1B_n$, $A_2B_{n-1}$, $\ldots$, $A_mB_{n+1-m}$, $\ldots$, $A_nB_1$, как нетрудно видеть, начинается в одной области (быть может, на её границе), а заканчивается — в другой. Следовательно, она имеет с $m$‑м путём общую точку. Но по правилу «перехода» она должна тогда иметь с этим путём и общий отрезок. Итак, $m$‑й путь имеет общий отрезок с каждой прямой.
Любопытным, но, видимо, очень трудным вопросом, связанным с этой задачей, является отыскание возможного числа отрезков в максимальном (по числу отрезков) пути. Можно убедиться (попробуйте!), что для $n=3$ максимальный путь всегда состоит из 3 отрезков, для $n=4$ он может состоять из 5 или 6 отрезков, для $n=5$ — из 6, 7 или 8. Интересно было бы найти те границы $c_n$ и $C_n$, между которыми заключена длина максимального пути для $n$ прямых (или хотя бы получить для $c_n$ и $C_n$ хорошие оценки и выяснить порядок роста $c_n$ и $C_n$ при $n\to\infty$).
