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

Пусть на прямой расположены D_1,D_2...D_n дорожек . Каждая дорожка пересекается хотя бы с половиной остальных дорожек, то есть с минимумом других дорожек.

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

Обозначим S_i как множество дорожек, с которыми пересекается D_i. Из условия задачи для каждой D_i выполняется неравенство:

$$|S_i| \geq \left\lceil \frac{n-1}{2} \right\rceil.$$

Предположим, что такой дорожки, которая пересекается со всеми остальными, не существует. Тогда для каждой дорожки D_i найдется хотя бы одна дорожка, с которой она не пересекается. То есть для каждой i существует D_j, такой что D_j \notin S_i.

Теперь рассмотрим сумму:

$$\sum_{i=1}^{n} |S_i|.$$

Каждую дорожку D_i пересекает хотя бы с $$\left\lceil \frac{n-1}{2}\right\rceil.$$ другими, то есть:

$$\sum_{i=1}^{n} |S_i| \geq n \cdot \left\lceil \frac{n-1}{2} \right\rceil.$$

С другой стороны, если для каждой D_i существует хотя бы одна дорожка, с которой она не пересекается, то каждая пара D_i и D_j может быть посчитана максимум один раз. Это означает, что общее количество пересечений не может превышать $$\frac{n(n-1)}{2}.$$ , то есть:

$$\sum_{i=1}^{n} |S_i| \leq \frac{n(n-1)}{2}.$$

Таким образом, получаем неравенство:

$$n \cdot \left\lceil \frac{n-1}{2} \right\rceil \leq \frac{n(n-1)}{2}.$$

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

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

Ответ: да такая дорожка существует