Математикадан облыстық олимпиада, 2023 жыл, 9 сынып

Ұзын тар дәлізде бірнеше жол төселген(барлық жолдар дәлізге параллель және олардың еңдері дәліздің еңіне тең). Кез келген екі жолдың қиылысатыны белгілі болса, онда осы жолдардың барлығын еденге бір шегемен шегелеуге болатынын дәлелдеңіз.

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

Это частный случай теоремы Хелли.

Для тех , кто не знает что такое теорема Хелли, и кому лень гуглить:

Общая теорема Хелли. Если в пространстве $n$ измерений $(n=1, 2, 3)$ дано некоторое число ограниченных выпуклых фигур, каждые $n+1$ из которых имеют общую точку, то все эти фигуры имеют общую точку.

хорош

Давайте переформулируем задачу то есть соединим параллельные в одно тогда у нас самый левый конец и правое начало и есть наши гвозди так как каждый отрезок должен лежать за ними

не понял

что за набор слов

по индукции для $n=2,3,4$ и дальше легко

То есть нам надо доказать что у всех дорожек будет общая часть

База индукции : $2$ Очевидно подходит

Пусть $n$ будет кол-во дорожек . Доказываем что будет работать для $n+1$ дорожек .

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

Так как $n≥2$ , то можем представить пересечение $n$ дорожек как некий "прямоугольник".

Так как это пересечение дорожек , очевидно что как минимум у $1$ дорожки будет совпадать правая граница с "прямоугольником" . Назовем его $K$ дорожка . Аналогично с левой границей . Назовем его $L$ дорожка .

Теперь посмотрим на $n+1$ дорожку

Могут быть $3$ варианта .

$1)$Он в "прямоугольнике"

$2)$Он слева от "прямоугольника

$3)$Он справа он "прямоугольника"

$1$ Случай , очевидно задача решена

$2$ Случай , чтобы $n+1$ имел пересечение с $L$ дорожкой , $n+1$ дорожка в любом случай будет переступать границу $L$, соответственно и пересекает границу "прямоугольника" . Значит очевидно что будет общая часть всех дорожек , что нам и требовалось доказать.

$3$ Случай , аналогично с 2 случаем , но вместо $L$ будет $K$

Так как по условию задачи ширина ковра равна ширине коридора, что можно считать наши ковры отрезками, то рассмотрим отрезок с самым левым правым концом L1 = [a,b] и самым правым левым концом L2 = [c,d]. То что они пересекаются означает, в частности, что b$\geq$ с. Но тогда любой отрезок имеет правый конец не левее b и левый конец не правее с то есть содержит все точки из отрезка [с,b] (возможно, вырожденного в точку, но не пустого).

Предположим, что у нас есть n путей в коридоре. Мы докажем, что все эти дорожки можно прибить к полу одним гвоздем.

Во-первых, мы выбираем любые два пути, скажем, путь A и путь B. Поскольку мы знаем, что эти два пути пересекаются, должна быть точка, в которой они пересекаются. Назовем эту точку O.

Теперь мы размещаем гвоздь в точке O и прибиваем пути A и B к полу.

Затем мы идем по другому пути, скажем, по пути C, и мы знаем, что он пересекается с путями A и B. Поскольку пути A и B уже прибиты гвоздями, путь C может пересечься только в точке O. Поэтому мы также может закрепить путь C в точке O.

Мы можем повторить этот процесс для всех n путей, закрепив их в точке O, которая является точкой пересечения любых двух путей.

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

Пусть $[ a_i , b_i], i = 1, 2, ..., n$ – данные отрезки - дорожки. Предположим $ a = a_j = \max{a_1 , a_2, ..., a_n}$ ,

$b = b_j = \min{ b_1, b_2, ..., b_n}$

Если $a > b$, то отрезки $[a_i, b_i]$ и $[a_j, b_j]$ непересекаются – противоречие. Значит, $b \geq a$, и все отрезки содержат отрезок $[a, b]$