Задача по комбинаторной геометрии

[Markiyan Hirnyk]

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

[ihq.pl]

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

[grizzly]

ihq.pl в сообщении #1269378 писал(а):

Ну а если немного переформулировать задачу: ни для каких $n+2$ точек не существует $n$ отрезков, отсекающих их друг от друга.

Почему Вы решили, что эта простая задача имеет что-то общее с задачей темы?
upd.

[ihq.pl]

grizzly в сообщении #1269401 писал(а):

Почему Вы решили, что эта простая задача имеет что-то общее с задачей темы?

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

[grizzly]

ihq.pl в сообщении #1269408 писал(а):

А в чем разница?

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

[ihq.pl]

grizzly в сообщении #1269419 писал(а):

(Мне лень это формулировать очень аккуратно, надеюсь, понятно, что имеется в виду известное утверждение о многочлене одной переменной.) Не кажется ли Вам, что п.(б) доказать намного проще?.

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

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

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

[grizzly]

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

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

[grizzly]

ihq.pl в сообщении #1269448 писал(а):

То есть, заданы как набор точек, так и набор отрезков. Утверждение, что не существует такого набора отрезков, отсекающих все точки друг от друга, автоматом влечет за собой то, что и заданный набор отрезков тоже их не отсекает. Что именно не так?

Мои извинения. Всё верно, это я чего-то вчера не того наговорил. То ли невнимателен был, то ли забыл задачу, неважно.

ihq.pl в сообщении #1269378 писал(а):

Понятно, что найдется такая точка и такой отрезок, который отсекает её от всех остальных.

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

-- 27.11.2017, 09:51 --

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

[ihq.pl]

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

[grizzly]

ihq.pl в сообщении #1293602 писал(а):

Теперь рассмотрел, и вижу, что как-то там всё не просто:)

Хорошо, что разобрались. А то я в качестве аргумента привёл не совсем удачный рисунок -- нужно было отрезки к центру внахлёст пустить.