Математикадан облыстық олимпиада, 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 это неравенство нарушается, что приводит к противоречию. Следовательно, предположение о том, что такой дорожки не существует, неверно.

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

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