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

[Markiyan Hirnyk]

В плоскости задано $n$ попарно непересекающихся замкнутых отрезков и $n+2$ различные точки вне этих отрезков ($n$ - натуральное число). Доказать, что среди заданных точек можно выбрать две точки, которые "видят одна другую", т. е. соединяющий их отрезок не пересекает заданных отрезков и остальных точек.

[Dan B-Yallay]

Индукцией.

Допустим, у нас нет отрезков вообще: $n=0$ ;
Тогда имеем две точки, которые в отсутствие отрезков "свободно видят друг друга".

Берём $n=1$. Без ограничения общности можно рассмотреть предыдущие 2 точки, к которым добавим отрезок и еще одну точку.
Чтобы разделить предыдущие точки, необходимо провести отрезок между ними. Тогда у третьей точки есть два возможных расположения:
$\bullet$ на линии, являющейся продолжением отрезка;
$\bullet$ по какую-либо сторому от линии
Очевидно, что в обоих случаях третья точка будет видна как минимум одной из предыдущих точек.

Думаю, продолжение достаточно прозрачное.

[Markiyan Hirnyk]

1. Насколько мне известно, $0$ не является натуральным числом в России.
2. Пожалуйста, подробно изложите "достаточно прозрачное" продолжение доказательства. Эта задача понравилась М. Концевичу https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D1%86%D0%B5%D0%B2%D0%B8%D1%87,_%D0%9C%D0%B0%D0%BA%D1%81%D0%B8%D0%BC_%D0%9B%D1%8C%D0%B2%D0%BE%D0%B2%D0%B8%D1%87.

[Dan B-Yallay]

Markiyan Hirnyk в сообщении #1163374 писал(а):

1. Насколько мне известно, $0$ не является натуральным числом в России.

Прошу прощения, пишу не из России.

Markiyan Hirnyk в сообщении #1163374 писал(а):

2. Пожалуйста, подробно изложите "достаточно прозрачное" продолжение доказательства. Эта задача понравилась М. Концевичу.

Я не могу проследить связи между детальным описанием решения задачи и тем отрадным фактом, что она понравилась М. Концевичу.
Но попробую изложить (если не ошибся с "прозрачностью")

-- Ср окт 26, 2016 14:41:39 --

Далее по индукции.
Допустим, что для некоторого $k \geqslant 1$ показано, что $k+2$ точки нельзя разделить $k$ отрезками, поэтому при любом расположении имеем ровно 2 точки $a$ и $b$ "видящие друг друга".

Добавим отрезок $I_{k+1}$, разделяющий $a, \ b$ и новую $(k+2)+1$-ю точку $c$.

Если она невидима никакой другой точкой, тогда yбираем отрезок $I_{k+1}$ и точку $a$ и получаем $k+2$ точки, разделенные $k$ отрезками. Противоречие.

[grizzly]

Dan B-Yallay в сообщении #1163375 писал(а):

Добавим отрезок $I_{k+1}$, разделяющий $a, \ b$ и новую $(k+2)+1$-ю точку $c$.

Если она невидима никакой другой точкой, тогда yбираем отрезок $I_{k+1}$ и точку $a$ и получаем $k+2$ точки, разделенные $k$ отрезками. Противоречие.

Как по мне, так достаточно одного слова "очевидно" (действительно ведь очевидно) или же должно быть столько слов, чтобы было понятно, почему нельзя слово "отрезок" заменить на слово "прямая" (или "луч" или ещё что-то похитрее) с тем же дословным доказательством.
Я, конечно, усложняю, но прецеденты были.

[Dan B-Yallay]

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

Как по мне, так достаточно одного слова "очевидно"

Дык я пробовал в первом сообщении -- не понравилось.
Потребовали именно много слов. :)

[maxal]

Dan B-Yallay в сообщении #1163375 писал(а):

Допустим, что для некоторого $k \geqslant 1$ показано, что $k+2$ точки нельзя разделить $k$ отрезками, поэтому при любом расположении имеем ровно 2 точки $a$ и $b$ "видящие друг друга".

Почему "ровно"? Должно быть "найдутся" (таких пар может быть несколько). Это подпорчивает получение противоречия в вашем доказательстве.
Кроме того, странно, что вы начинаете с некоторого доказанного случая $k$ отрезков и $k+2$ точек и добавляете туда новые. Логичнее начинать с доказуемого случая $k+1$ отрезка и $k+3$ точек и удалять оттуда точки/отрезки сводя задачу к доказанной.

[Skeptic]

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

[grizzly]

Skeptic
Ваше замечание имеет сейчас номер 888. Это примечательно.

[wrest]

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

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

Вопрос-то другой -- можно ли расположить $n+2$ точки так, чтобы не нашлось ни одной пары видящих друг друга.

[Dan B-Yallay]

maxal
С замечаниями согласен, "разматывать" надо в обратную сторону. Но с наскоку не получается так что надо думать.

[DeBill]

Будем усугубляТь ситуацию: вырастим отрезки (в обе стороны) по максимуму. Сначала - первый отрезок - пока он не уткнется в другой (либо дойдет до бесконечности), затем - второй, и т.д.
Лемма. Полученная система лучей-отрезков делит плоскость ($=$ сферу) на $n+1$ выпуклую часть.
Тогда все легко: точек - больше...
Д-во леммы. Пусть получилось $k$ лучей и $s$ больших отрезков (и $m$ прямых). У них $k+2s+1$ вершин (включая бесконечноудаленную). Посчитаем ребра: изначально их было $n$; каждая вершина, попавшая на луч-отрезок-прямую, добавляет одно ребро, итого ребер $n+k +2s$, потому граней Г $=2+P - B =n+1$

[grizzly]

DeBill в сообщении #1163640 писал(а):

делит ... на $n+1$ выпуклую часть.

здесь нужно утверждать "делит ... на не более чем ...". Контрпример -- два отрезка, лежащие на одной прямой.

DeBill в сообщении #1163640 писал(а):

Сначала - первый отрезок - пока он не уткнется в другой (либо дойдет до бесконечности), затем - второй, и т.д.

Здесь нужно оговаривать отдельно поведение при касании (отрезок при продолжении попадает в вершину другого отрезка). Это не должно испортить рассуждения, я думаю, если правильно оговорить (если оговорить неправильно, могут появиться невыпуклые области, например).

DeBill в сообщении #1163640 писал(а):

У них $k+2s+1$ вершин (включая бесконечноудаленную).

с учётом кратности совпадающих вершин, кроме бесконечноудалённой. Так кажется?

Но хочется верить, что всё это поправимо и ничего другого нет.

[DeBill]

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

"делит ... на не более чем ...". Контрпример -- два отрезка, лежащие на одной прямой.

Да, придется...

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

отрезок при продолжении попадает в вершину другого отрезка)

Ну и хрен с ним: один из них - продолжим дале.

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

с учётом кратности совпадающих вершин,

А вот это неприятно. Лучше - как выше, избечь их тупым продолжением одного.
Или так: можно заменить каждый отрезок чуть большим интервалом - с сохранением непересекаемости их, и гипотетическом препятствиением дружбе точек. Тогда полученная система будет устойчива к малым возмущениям. "Пошевелим" ее - и избавимся от всех нетипичных ситуевин.

[grizzly]

DeBill в сообщении #1163943 писал(а):

Ну и хрен с ним: один из них - продолжим дале.

Их может несколько сходиться, результат картинки будет сколько-то зависеть от порядка в котором мы будем продолжать. Ну его. Следующее предложение выглядит намного лучше:

DeBill в сообщении #1163943 писал(а):

Или так: можно заменить каждый отрезок чуть большим интервалом - с сохранением непересекаемости их, и гипотетическом препятствиением дружбе точек. Тогда полученная система будет устойчива к малым возмущениям. "Пошевелим" ее - и избавимся от всех нетипичных ситуевин.

Да, это убеждает.

А что с переходом в $\mathbb R^3$? Там ведь всё аналогично, если резать недоплоскостями -- и тоже $n+1$? А рассуждение с формулой Эйлера там применимо? (я просто не соображу, к чему её применить).

-- 28.10.2016, 23:43 --

А, ну да, в любом случае не нужно там будить Эйлера; просто считать.