Processing math: 80%

Областная олимпиада по математике, 2023 год, 9 класс


В длинном узком коридоре постелено несколько дорожек(все дорожки параллельны коридору и можно считать, что ширина каждой дорожки равна ширине коридора). Докажите, что можно одним гвоздём прибить все эти дорожки к полу, если известно, что любые две дорожки пересекаются.
посмотреть в олимпиаде

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

  0
2 года 1 месяца назад #

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

  2
1 года 8 месяца назад #

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

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

  1
1 года 8 месяца назад #

хорош

пред. Правка 2   0
2 года 1 месяца назад #

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

  1
2 года 1 месяца назад #

не понял

пред. Правка 2   0
2 года 1 месяца назад #

  1
1 года 4 месяца назад #

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

  8
2 года назад #

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

пред. Правка 2   4
2 года назад #

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  0
2 года назад #

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

  0
2 года назад #

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

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

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

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

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

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

  0
1 года 2 месяца назад #

Пусть [ai,bi],i=1,2,...,n – данные отрезки - дорожки. Предположим a=aj=max ,

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]