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

Берем самый левый ковер и прибиваем его самую правую часть

неверное решение

неверное решение

неверное решение

$Допустим, что для какого-то А ковра это верно и он самый крайний(определили такой ковер), так как у него самый правый конец и для этого А ковра верно по условии что он пересекается с любыми двумя другими коврами, значит пересекается со всеми остальными. Но если найдется ковер В который имеет конец левее от А он будет являться крайним, что противоречие, ведь А самый крайний и левый ковер. Тогда ковер А пересекается со всеми в каком-то точке где и будет забит гвоздь.$

Назовем дорожкой самой левой, если его правый конец левее всех, если пробить туда гвоздь (в самую правую часть), то он пройдет через все дорожки, тк если какой то дорожки там нет, то два случая :

1. Она не пересекает ее, сразу противоречие

2. Она находился под ней, то есть ее правая часть левее чем самой левой дорожки, тоже приводит к противоречию

Значит в любом случае в этой точке есть все дорожки

Допустим, что для какого-то А ковра это верно и он самый крайний(определили такой ковер), так как у него самый правый конец и для этого А ковра верно по условии что он пересекается с любыми двумя другими коврами, значит пересекается со всеми остальными. Но если найдется ковер В который имеет конец левее от А он будет являться крайним, что противоречие, ведь А самый крайний и левый ковер. Тогда ковер А пересекается со всеми в каком-то точке где и будет забит гвоздь.