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