2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.





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


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

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


18/05/15
69
Ну а если немного переформулировать задачу: ни для каких $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
4901
ihq.pl в сообщении #1269378 писал(а):
Ну а если немного переформулировать задачу: ни для каких $n+2$ точек не существует $n$ отрезков, отсекающих их друг от друга.
Почему Вы решили, что эта простая задача имеет что-то общее с задачей темы?
upd. :facepalm:

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


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

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

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


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

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


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

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

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

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

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


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


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

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


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

-- 27.11.2017, 09:51 --

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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