Пересечения прямоугольников

[ewert]

Skeptic в сообщении #887436 писал(а):

Вот здесь.

Здесь просто небрежная формулировка: под "пересекаются" подразумевалось "имеют непустое пересечение" а под "всем им" -- "всем из этого множества". Естественно, никто на эту небрежность даже и внимания не обратил, все поняли всё правильно.

[Otta]

Skeptic

Цитата:

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

Есть набор прямоугольников. У любых трех из них пересечение непусто (=они имеют общую точку). Показать, что существует точка, которая принадлежит всем прямоугольникам набора.

Так лучше?

[Skeptic]

Спасибо. И доказательство просматривается.

[ewert]

Доказательство в любом случае не просто. Два наиболее стандартных способа -- это через теорему об отделимости и через теорему Радона. В любом случае понадобится индукция по количеству подмножеств в семействе. Теорема об отделимости -- с геометрической точки зрения интуитивно очевидна, однако формально отнюдь не тривиальна. Теорема Радона -- неочевидна и интуитивно в общем случае, однако в двумерном случае тривиальна до такой степени, что может даже не называться теоремой. В любом варианте непонятно, чем может облегчить доказательство то, что это -- прямоугольники.

[Skeptic]

Представим каждый прямоугольник из множества вершиной графа, а существование пересечения двух прямоугольников - ребром, соединяющим две вершины. Из условия пересечения трёх любых прямоугольников получим полносвязный граф, т.е. для каждого прямоугольника существует пересечение с остальными.
Можно ли считать это доказательством?

[kp9r4d]

Нет, как минимум потому что никак не используется выпуклость (а для невыпуклых множеств это неверно).

[Skeptic]

Прямоугольник - выпуклое множество точек.
Если не хватает выпуклости, то её можно добавить. На построении это никак не скажется, т.к. ребро - это не область пересечения, а существование пересечения со всеми необходимыми свойствами.

[kp9r4d]

Skeptic
Если заменить слово "прямоугольник" в вашем доказательстве на слово, например, "тройка точек" то ничего не изменится. Но это-то ладно, вообще вы снова путаете попарное пересечение с пересечением. Вы доказали лишь то, что если любая тройка прямоугольников имеет непустое пересечение, то и любая двойка прямоугольников имеет непустое пересечение, что не слишком уж содержательно.

[Skeptic]

kp9r4d, я ничего не путаю, вы отстали от дискуссии. Я использую это определение пересечения

Ф.Хаусдорф Теория множеств писал(а):

Пересечение множеств $A$ и $B$ - множество всех элементов, принадлежащих $A$ и $B$

. А вы какое?
Не надо проявлять инициативу, заменяя мои слова, и предъявляя мне претензии. Заменяйте прямоугольники на всё, что вам нравится, я за ваши действия не отвечаю.

[kp9r4d]

kp9r4d в сообщении #887676 писал(а):

А вы какое?

А я то же самое.

Skeptic в сообщении #887675 писал(а):

Не надо проявлять инициативу, заменив мои слова, и предъявляя мне претензии. Заменяйте прямоугольники на всё, что вам нравится, я за ваши действия не отвечаю.

Не надо передёргивать. Это стандартный аргумент, чтобы показать ошибку в доказательстве; очень простое рассуждение: если мы доказываем, что произведение двух чётных чисел - чётно, и при это нигде в своих рассуждениях не используем того, что мы работаем именно с чётными числам, а не с какими-нибудь другими, то те же самые рассуждения, слово в слово можно повторить и для двух нечётных чисел, не нарушая при этом логику, однако мы знаем, что произведение нечётных чисел - нечётно, а значит и само доказательство неверно.

[Skeptic]

Я работаю только с прямоугольниками.

[kp9r4d]

Но вы никак это не используйте.
Пусть есть множество $X=\{\{(0,0),(0,1),(1,1)\},\{(0,0),(0,1),(1,0)\},\{(0,0),(1,1),(1,0)\},\{(0,1),(1,1),(1,0)\}\}$ троек точек на плоскости. Любая тройка таких троек точек имеет непустое пересечение, однако пересечение всех четырёх троек - пусто. Однако я сейчас докажу, что оно непусто, вот так:
Представим каждую тройку точек из множества вершиной графа, а существование пересечения двух троек - ребром, соединяющим две вершины. Из условия пересечения трёх любых троек получим полносвязный граф, т.е. для каждой тройки существует пересечение с остальными.
Чем это (неверное) доказательство принципиально отличается от вашего?

[Skeptic]

kp9r4d
Я предложил идею доказательства. Нужно определить область применения, как в любой теореме: дано - требуется доказать. Сравните множество точек в прямоугольнике и приведённых вами троек. Найдите различия, этими различиями ограничьте свойства используемых множеств.

[kp9r4d]

Я ничего не понял.

[Otta]

Skeptic в сообщении #887709 писал(а):

Я предложил идею доказательства. Нужно определить область применения, как в любой теореме: дано - требуется доказать.

Ваше доказательство - Вам и определять.
Странный у Вас порядок: предложить рассуждение, которое якобы что-то доказывает, а потом требовать от окружающих, чтобы они уточнили, что именно. Это целиком Ваша забота и Ваша ответственность.
К стартовому посту рассуждение отношения не имеет, оно ничего не обосновывает. Почему, kp9r4d достаточно внятно изложил чуть выше: post887673.html#p887673