Областная олимпиада по математике, 2023 год, 11 класс

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

Комментарий/решение

Предположим, что у нас есть n путей в коридоре, и каждый путь пересекается как минимум с половиной оставшихся путей. Докажем, что существует путь, пересекающийся со всеми остальными путями.

Для доказательства воспользуемся индукцией. Сначала докажем базовый случай, когда n=2. В этом случае оба пути пересекаются друг с другом, а значит, существует путь, пересекающийся с оставшимся.

Теперь предположим, что утверждение верно для n-1 путей. То есть существует путь, который пересекается со всеми оставшимися n-2 путями.

Теперь мы добавим еще один путь в коридор. Этот новый путь пересекается по крайней мере с половиной оставшихся n-1 путей, то есть (n-1)/2 путей. Поскольку мы знаем, что существует путь, который пересекается со всеми оставшимися n-2 путями, есть две возможности:

Новый путь пересекается с этим путем. В этом случае мы нашли путь, который пересекается со всеми оставшимися n-1 путями, и все готово.

Новый путь не пересекается с путем, который пересекается со всеми оставшимися n-2 путями. В этом случае новый путь пересекается как минимум с (n-1)/2 - 1 = (n-3)/2 из оставшихся n-2 путей. Поскольку (n-3)/2 меньше или равно (n-2)/2, новый путь по-прежнему пересекается как минимум с половиной оставшихся путей. Следовательно, мы можем применить предположение индукции к оставшимся n-1 путям, и мы найдем путь, который пересекается со всеми оставшимися путями, включая новый путь.

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

Представим фиксированный горизонтальный коридор.

И по этому коридору расположены дорожки, у которых есть границы. Пусть это будет левая граница и правая относительно коридора .

$X_{r};X_{l}$—правая граница и левая граница дорожки $X$ соответственно. Возьмём дорожку, у которого правая граница самая левая из всех дорожек в коридоре(Назовем это $L$ дорожкой), и возьмём дорожку, у которого левая граница самая правая(Пусть это $K$ дорожка)

Если они пересекаются, то задача уже решена т.к. каждая правая граница расположена правее чем $L_{r}$, и так же каждая левая граница левее чем $K_{l}$, от чего хотя бы $1$ граница каждой дорожки лежит между $K_{l}$ и $L_{r}$.

$K=K_{l}K_{r}, K_{l}L_{r} \in K_{l}K_{r}$ т.к. $K$ и $L$ пересекаются, это значит что один пересек границу другого. Значит дорожка $K$ содержит хотя бы одну границу каждой дорожки, что равносильно, что $K$ пересекается со всеми дорожками.

Тогда пусть $K;L$ не пересекаются

$1)$Если нет дорожки, которая пересекает обоих дорожек, то каждый из них пересекается хотя бы чем с $\dfrac{n-1}{2}$ , из чего в сумме они пересекаются с $n-1$ дорожками, считая $K$ и $L$ в коридоре хотя бы $n+1$ кол-во дорожек, что приводит к противоречию, и такого не может быть по условию.

$2)$Если есть такая дорожка $R$, которая пересекает сразу $K$ и $L$, то эта дорожка содержит промежуток между $K_{l}$ и $L_{r}$, где есть хотя бы $1$ граница каждой дорожки, из чего $R$ пересекается со всеми дорожками