2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Задача по комбинаторной геометрии
Сообщение26.11.2017, 21:36 


11/07/16
410
ihq.pl
Из неравенства (в ваших обозначениях) $N>n$не следует, что найдется пара точек, которые видят друг друга: несколько из $N$ соединяющих точки отрезков могут пересекаться с одним и тем же самым отрезком из $n$ заданных .

 Профиль  
                  
 
 Re: Задача по комбинаторной геометрии
Сообщение26.11.2017, 22:16 


18/05/15
80
Ну а если немного переформулировать задачу: ни для каких $n+2$ точек не существует $n$ отрезков, отсекающих их друг от друга. В предыдущем моем посте доказано, что отрезков, которые отсекали бы точки друг от друга попарно, не существует. Попробуем построить отрезки, которые этому условию не удовлетворяют. Понятно, что найдется такая точка и такой отрезок, который отсекает её от всех остальных. Проводим его, и задача сводится к поиску $n-1$ отрезков, отсекающих друг от друга $n+1$ оставшиеся точки. То есть, задача та же, только теперь для $n-1$. Поступаем таким же образом. И т.д. На шаге $k$ имеем $k$ отрезков и $n+2-k$ точек, которые видят друг друга. Если $k=n$, остаются 2 точки, которые видят друг друга. Очевидно, что это критический из возможных случаев в том смысле, что другие построения привели бы к тому, что видящих друг друга точек оказалось бы больше, чем две.

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


09/09/14
5462
ihq.pl в сообщении #1269378 писал(а):
Ну а если немного переформулировать задачу: ни для каких $n+2$ точек не существует $n$ отрезков, отсекающих их друг от друга.
Почему Вы решили, что эта простая задача имеет что-то общее с задачей темы?
upd. :facepalm:

 Профиль  
                  
 
 Re: Задача по комбинаторной геометрии
Сообщение26.11.2017, 23:52 


18/05/15
80
grizzly в сообщении #1269401 писал(а):
Почему Вы решили, что эта простая задача имеет что-то общее с задачей темы?

Так показалось. А в чем разница?

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


09/09/14
5462
ihq.pl в сообщении #1269408 писал(а):
А в чем разница?
В расстановке кванторов. Попытайтесь найти разницу между следующими утверждениями: (а) для любого набора $n$ точек на плоскости, найдётся функция-многочлен степени $n-1$, график которой проходит через эти точки и (б) для любой функции-многочлена степени $n-1$ найдётся $n$ точек, принадлежащих её графику.
(Мне лень это формулировать очень аккуратно, надеюсь, понятно, что имеется в виду известное утверждение о многочлене одной переменной.) Не кажется ли Вам, что п.(б) доказать намного проще? Вот и здесь так же.
udp. :facepalm:

 Профиль  
                  
 
 Re: Задача по комбинаторной геометрии
Сообщение27.11.2017, 01:48 


18/05/15
80
grizzly в сообщении #1269419 писал(а):
(Мне лень это формулировать очень аккуратно, надеюсь, понятно, что имеется в виду известное утверждение о многочлене одной переменной.) Не кажется ли Вам, что п.(б) доказать намного проще?.

Нет, вообще не понятно, что имеется в виду, если честно. (а) и (б) очевидно совершенно разные задачи. Ну хотя бы потому что в случае полинома одной переменной (а) не верно. А вот, неравносильность задачи ТС и моей мне лично в глаза прямо так сходу не бросается. Смотрим еще раз на задачу ТС:

В плоскости задано $n$ попарно непересекающихся замкнутых отрезков и $n+2$ различные точки вне этих отрезков...

То есть, заданы как набор точек, так и набор отрезков. Утверждение, что не существует такого набора отрезков, отсекающих все точки друг от друга, автоматом влечет за собой то, что и заданный набор отрезков тоже их не отсекает. Что именно не так? Заметьте, я ничего не утверждаю. Скорее всего, в ваших словах есть смысл. Но я его не вижу. Я собственно и спросил сразу, где ошибка в рассуждениях. ТС, например, не сказал, что это две разные задачи. А ведь в первой моей постановке тоже задавались сначала точки на плоскости, а не отрезки. Он указал на ошибку в доказательстве, которую я затем исправил. В общем, я по-прежнему не вижу разницы. А увидеть, особенно после вашего замечания, стало еще интересней. Ну может не дано? - этот вариант тоже не исключаю:))

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


09/09/14
5462
ihq.pl
Может это я чего-то не понимаю? Но мне интересна только такая часть задачи: для любого заданного набора из $n$ отрезков нельзя разместить $n+2$ точки так, чтобы ни одна точка не видела другую. То есть, набор отрезков задан (произвольным образом), а точки можем расставлять как угодно.
Почему Вы считаете, что Ваша формулировка эквивалентна, я не пойму.


Решение в Вашей формулировке действительно тривиально: отсекаем отрезком одну точку и используем индукцию. Для начала только нужно все точки очертить каким-то внешним периметром, который потом удаляется. (upd. 27.11)
:facepalm:

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


09/09/14
5462
ihq.pl в сообщении #1269448 писал(а):
То есть, заданы как набор точек, так и набор отрезков. Утверждение, что не существует такого набора отрезков, отсекающих все точки друг от друга, автоматом влечет за собой то, что и заданный набор отрезков тоже их не отсекает. Что именно не так?
Мои извинения. Всё верно, это я чего-то вчера не того наговорил. То ли невнимателен был, то ли забыл задачу, неважно.
ihq.pl в сообщении #1269378 писал(а):
Понятно, что найдется такая точка и такой отрезок, который отсекает её от всех остальных.
Вот это место непонятно. Лучше так: понятно, что найдётся такая точка и такой набор отрезков, который отсекает её от всех остальных точек. Вы доказали только невозможность попарно отрезать. А что если для каждой точки некоторое подмножество отрезков является отрезающим? (и один и тот же отрезок может участвовать в разных наборах)

-- 27.11.2017, 09:51 --

Вот набор из 6 отрезков и 6 точек, в котором каждая точка отделена от других набором отрезков. Вы не показали, что такое невозможно при разнице 2 между количеством точек и количеством отрезков.
Изображение

 Профиль  
                  
 
 Re: Задача по комбинаторной геометрии
Сообщение21.02.2018, 16:42 


18/05/15
80
grizzly извиняюсь за поздний ответ. Наверно, слишком поздний, все поди уже и думать забыли про задачу.. Вы правы. Я как следует не разобрался в задаче. Теперь рассмотрел, и вижу, что как-то там всё не просто:))

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


09/09/14
5462
ihq.pl в сообщении #1293602 писал(а):
Теперь рассмотрел, и вижу, что как-то там всё не просто:)
Хорошо, что разобрались. А то я в качестве аргумента привёл не совсем удачный рисунок -- нужно было отрезки к центру внахлёст пустить.

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

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



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

Сейчас этот форум просматривают: TR63


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

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