2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Задача по комбинаторной геометрии
Сообщение26.10.2016, 22:23 


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

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


11/12/05
9952
Индукцией.

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

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

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

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


11/07/16
801
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.

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


11/12/05
9952
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$ отрезками. Противоречие.

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


09/09/14
6328
Dan B-Yallay в сообщении #1163375 писал(а):
Добавим отрезок $I_{k+1}$, разделяющий $a, \ b$ и новую $(k+2)+1$-ю точку $c$.

Если она невидима никакой другой точкой, тогда yбираем отрезок $I_{k+1}$ и точку $a$ и получаем $k+2$ точки, разделенные $k$ отрезками. Противоречие.
Как по мне, так достаточно одного слова "очевидно" (действительно ведь очевидно) или же должно быть столько слов, чтобы было понятно, почему нельзя слово "отрезок" заменить на слово "прямая" (или "луч" или ещё что-то похитрее) с тем же дословным доказательством.
Я, конечно, усложняю, но прецеденты были.

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


11/12/05
9952
grizzly в сообщении #1163388 писал(а):
Как по мне, так достаточно одного слова "очевидно"
Дык я пробовал в первом сообщении -- не понравилось.
Потребовали именно много слов. :)

 Профиль  
                  
 
 Re: Задача по комбинаторной геометрии
Сообщение27.10.2016, 06:28 
Модератор
Аватара пользователя


11/01/06
5654
Dan B-Yallay в сообщении #1163375 писал(а):
Допустим, что для некоторого $k \geqslant 1$ показано, что $k+2$ точки нельзя разделить $k$ отрезками, поэтому при любом расположении имеем ровно 2 точки $a$ и $b$ "видящие друг друга".

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

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


01/12/11

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

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


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

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


05/09/16
11453
Skeptic в сообщении #1163426 писал(а):

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

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

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


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

 Профиль  
                  
 
 Re: Задача по комбинаторной геометрии
Сообщение27.10.2016, 23:48 
Заслуженный участник


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

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


09/09/14
6328
DeBill в сообщении #1163640 писал(а):
делит ... на $n+1$ выпуклую часть.
здесь нужно утверждать "делит ... на не более чем ...". Контрпример -- два отрезка, лежащие на одной прямой.
DeBill в сообщении #1163640 писал(а):
Сначала - первый отрезок - пока он не уткнется в другой (либо дойдет до бесконечности), затем - второй, и т.д.
Здесь нужно оговаривать отдельно поведение при касании (отрезок при продолжении попадает в вершину другого отрезка). Это не должно испортить рассуждения, я думаю, если правильно оговорить (если оговорить неправильно, могут появиться невыпуклые области, например).
DeBill в сообщении #1163640 писал(а):
У них $k+2s+1$ вершин (включая бесконечноудаленную).
с учётом кратности совпадающих вершин, кроме бесконечноудалённой. Так кажется?

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

 Профиль  
                  
 
 Re: Задача по комбинаторной геометрии
Сообщение28.10.2016, 22:55 
Заслуженный участник


10/01/16
2315
grizzly в сообщении #1163678 писал(а):
"делит ... на не более чем ...". Контрпример -- два отрезка, лежащие на одной прямой.

Да, придется...
grizzly в сообщении #1163678 писал(а):
отрезок при продолжении попадает в вершину другого отрезка)

Ну и хрен с ним: один из них - продолжим дале.
grizzly в сообщении #1163678 писал(а):
с учётом кратности совпадающих вершин,

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

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


09/09/14
6328
DeBill в сообщении #1163943 писал(а):
Ну и хрен с ним: один из них - продолжим дале.
Их может несколько сходиться, результат картинки будет сколько-то зависеть от порядка в котором мы будем продолжать. Ну его. Следующее предложение выглядит намного лучше:
DeBill в сообщении #1163943 писал(а):
Или так: можно заменить каждый отрезок чуть большим интервалом - с сохранением непересекаемости их, и гипотетическом препятствиением дружбе точек. Тогда полученная система будет устойчива к малым возмущениям. "Пошевелим" ее - и избавимся от всех нетипичных ситуевин.
Да, это убеждает.

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

-- 28.10.2016, 23:43 --

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

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

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



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

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


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

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