2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: Пересечения прямоугольников
Сообщение14.07.2014, 15:46 
Заслуженный участник


11/05/08
32166
Skeptic в сообщении #887436 писал(а):
Вот здесь.

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение14.07.2014, 17:47 
Заслуженный участник


09/05/13
8904
∞⠀⠀⠀⠀
Skeptic
Цитата:
Подскажите как доказать, что если любые три прямоугольника из некоторого множества пересекаются, то существует точка, которая принадлежит всем им.

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

Так лучше?

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 11:19 


01/12/11

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 11:43 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 14:34 


01/12/11

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 14:41 
Заслуженный участник
Аватара пользователя


09/02/14

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 14:43 


01/12/11

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 14:48 
Заслуженный участник
Аватара пользователя


09/02/14

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 15:12 


01/12/11

1047
kp9r4d, я ничего не путаю, вы отстали от дискуссии. Я использую это определение пересечения
Ф.Хаусдорф Теория множеств писал(а):
Пересечение множеств $A$ и $B$ - множество всех элементов, принадлежащих $A$ и $B$
. А вы какое?
Не надо проявлять инициативу, заменяя мои слова, и предъявляя мне претензии. Заменяйте прямоугольники на всё, что вам нравится, я за ваши действия не отвечаю.

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 15:20 
Заслуженный участник
Аватара пользователя


09/02/14

1377
kp9r4d в сообщении #887676 писал(а):
А вы какое?

А я то же самое.
Skeptic в сообщении #887675 писал(а):
Не надо проявлять инициативу, заменив мои слова, и предъявляя мне претензии. Заменяйте прямоугольники на всё, что вам нравится, я за ваши действия не отвечаю.

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 15:35 


01/12/11

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 15:43 
Заслуженный участник
Аватара пользователя


09/02/14

1377
Но вы никак это не используйте.
Пусть есть множество $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)\}\}$ троек точек на плоскости. Любая тройка таких троек точек имеет непустое пересечение, однако пересечение всех четырёх троек - пусто. Однако я сейчас докажу, что оно непусто, вот так:
Представим каждую тройку точек из множества вершиной графа, а существование пересечения двух троек - ребром, соединяющим две вершины. Из условия пересечения трёх любых троек получим полносвязный граф, т.е. для каждой тройки существует пересечение с остальными.
Чем это (неверное) доказательство принципиально отличается от вашего?

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 17:06 


01/12/11

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 17:40 
Заслуженный участник
Аватара пользователя


09/02/14

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

 Профиль  
                  
 
 Re: Пересечения прямоугольников
Сообщение15.07.2014, 17:54 
Заслуженный участник


09/05/13
8904
∞⠀⠀⠀⠀
Skeptic в сообщении #887709 писал(а):
Я предложил идею доказательства. Нужно определить область применения, как в любой теореме: дано - требуется доказать.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3, 4

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Google Adsense [Bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group