Разделы 
Дополнительно
Задача по математике - 3736
2019-06-16 
Дана горизонтальная полоса на плоскости, края которой - параллельные прямые, и $n$ прямых, пересекающих эту полосу. Каждые две из этих прямых пересекаются внутри полосы и никакие три из них не имеют общей точки. Рассмотрим все пути, начинающиеся на нижней кромке полосы, идущие по данным прямым и заканчивающиеся на верхней кромке полосы, обладающие таким свойством: идя по такому пути, мы все время поднимаемся вверх; дойдя до точки пересечения прямых, мы обязаны переходить на другую прямую (рис.). Докажите, что среди таких путей
а) есть не менее $n/2$ путей без общих точек;
б) есть путь, состоящий не менее чем из $n$ отрезков;
в) есть путь, проходящий не более чем по $\frac{n}{2} + 1$ прямым;
г) есть путь, проходящий по всем $n$ прямым.
Решение:
Пусть $A_1, A_2, \cdots, A_n$ - точки пересечения прямых с нижней кромкой полосы, занумерованные по порядку (слева направо), $B_1, B_2, \cdots, B_n$ - точки пересечения с верхней кромкой (также слева направо). Занумеруем пути, выходящие из точек $A_1, A_2, \cdots, A_n$ по порядку числами $1, 2, \cdots, n$. Из правил построения путей вытекают следующие свойства.
1° По каждому отрезку каждой прямой проходит ровно один путь.
2° Соседние пути - $k$-й и $(k + 1)$-й - соприкасаются вершинами, причем $k$-й всюду идет левее $(k + 1)$-го (для каждого $k = 1, 2, \cdots, n - 1$). Несоседние пути вообще не имеют общих точек.
3° $k$-й путь оканчивается в точке $B_k$. Теперь докажем все утверждения задачи.
а) Рассмотрим все пути с нечетными номерами. По свойству 1° они не могут иметь общих точек, а их число не меньше $\frac{n}{2}$.
б) Подсчитаем двумя способами общее количество отрезков на всех путях. Каждый из отрезков $A_iB_{n+1-i}$ одной из прямых разбивается точками пересечения с остальными прямыми на $n$ отрезков. Поэтому всего отрезков $n^2$. Ту же сумму $n^2$ согласно 1° мы должны получить, сложив количества отрезков во всех $n$ путях. Поэтому по крайней мере одно из слагаемых будет не меньше $n$.
Конечно, утверждение б) следует также из г).
в) Оценим количество отрезков в двух крайних путях - 1-ом и $n$-ом.
Эти пути ограничивают выпуклые множества, лежащие левее 1-го и правее $n$-го пути; первый путь лежит внутри угла $A_1PB_1$, а второй внутри угла $A_nPB_n$, где $P$ - точка пересечения прямых $A_1B_n$ и $A_nB_1$. Остальные прямые $A_2B_{n-1}, A_3B_{n-2}, \cdots, A_{n-1}B_2$ могут иметь общий отрезок только с одним из двух крайних путей (а именно с тем из них, который лежит по другую сторону от этой прямой, чем точка $P$). Итак, всего в двух крайних путях не больше чем $4 + (n - 2)$ отрезков, Поэтому
в одном из них не больше чем $\frac{n}{2} + 1$ отрезок.
г) Рассмотрим средний путь, т. е. путь о номером $m = \frac{n + 1}{2}$, если $n$ нечетно и $m = \frac{n}{2}$, если $n$ четно, и докажем, что он проходит по всем прямым (рис.). В самом деле, он
делит полосу на две области; каждый из отрезков $A_1B_n, A_2B_{n-1}, \cdots, A_nB_1$ начинается в одной из областей (может быть, на границе) и кончается в другой и, следовательно, имеет со средним путем общую точку, поэтому (по правилу построения путей) - и общий отрезок.
Дана горизонтальная полоса на плоскости, края которой - параллельные прямые, и $n$ прямых, пересекающих эту полосу. Каждые две из этих прямых пересекаются внутри полосы и никакие три из них не имеют общей точки. Рассмотрим все пути, начинающиеся на нижней кромке полосы, идущие по данным прямым и заканчивающиеся на верхней кромке полосы, обладающие таким свойством: идя по такому пути, мы все время поднимаемся вверх; дойдя до точки пересечения прямых, мы обязаны переходить на другую прямую (рис.). Докажите, что среди таких путей
а) есть не менее $n/2$ путей без общих точек;
б) есть путь, состоящий не менее чем из $n$ отрезков;
в) есть путь, проходящий не более чем по $\frac{n}{2} + 1$ прямым;
г) есть путь, проходящий по всем $n$ прямым.
Решение:
Пусть $A_1, A_2, \cdots, A_n$ - точки пересечения прямых с нижней кромкой полосы, занумерованные по порядку (слева направо), $B_1, B_2, \cdots, B_n$ - точки пересечения с верхней кромкой (также слева направо). Занумеруем пути, выходящие из точек $A_1, A_2, \cdots, A_n$ по порядку числами $1, 2, \cdots, n$. Из правил построения путей вытекают следующие свойства.
1° По каждому отрезку каждой прямой проходит ровно один путь.
2° Соседние пути - $k$-й и $(k + 1)$-й - соприкасаются вершинами, причем $k$-й всюду идет левее $(k + 1)$-го (для каждого $k = 1, 2, \cdots, n - 1$). Несоседние пути вообще не имеют общих точек.
3° $k$-й путь оканчивается в точке $B_k$. Теперь докажем все утверждения задачи.
а) Рассмотрим все пути с нечетными номерами. По свойству 1° они не могут иметь общих точек, а их число не меньше $\frac{n}{2}$.
б) Подсчитаем двумя способами общее количество отрезков на всех путях. Каждый из отрезков $A_iB_{n+1-i}$ одной из прямых разбивается точками пересечения с остальными прямыми на $n$ отрезков. Поэтому всего отрезков $n^2$. Ту же сумму $n^2$ согласно 1° мы должны получить, сложив количества отрезков во всех $n$ путях. Поэтому по крайней мере одно из слагаемых будет не меньше $n$.
Конечно, утверждение б) следует также из г).
в) Оценим количество отрезков в двух крайних путях - 1-ом и $n$-ом.
Эти пути ограничивают выпуклые множества, лежащие левее 1-го и правее $n$-го пути; первый путь лежит внутри угла $A_1PB_1$, а второй внутри угла $A_nPB_n$, где $P$ - точка пересечения прямых $A_1B_n$ и $A_nB_1$. Остальные прямые $A_2B_{n-1}, A_3B_{n-2}, \cdots, A_{n-1}B_2$ могут иметь общий отрезок только с одним из двух крайних путей (а именно с тем из них, который лежит по другую сторону от этой прямой, чем точка $P$). Итак, всего в двух крайних путях не больше чем $4 + (n - 2)$ отрезков, Поэтому
в одном из них не больше чем $\frac{n}{2} + 1$ отрезок.
г) Рассмотрим средний путь, т. е. путь о номером $m = \frac{n + 1}{2}$, если $n$ нечетно и $m = \frac{n}{2}$, если $n$ четно, и докажем, что он проходит по всем прямым (рис.). В самом деле, он
делит полосу на две области; каждый из отрезков $A_1B_n, A_2B_{n-1}, \cdots, A_nB_1$ начинается в одной из областей (может быть, на границе) и кончается в другой и, следовательно, имеет со средним путем общую точку, поэтому (по правилу построения путей) - и общий отрезок.
