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

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

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

Имхо условие сформулировано непонятно. Если по фактам то оно говорит вот о чем: дана прямая(длинный узкий корридор) и на ней расположены отрезки(дорожки), притом каждый отрезок пересекается не менее чем с половиной из оставшихся

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

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

$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$ пересекается со всеми дорожками