?

Log in

No account? Create an account

Previous Entry | Next Entry

Задолжал сложную эстафетную задачу Ушастому. Отдаю долг.

Mos maiorum народа нмого запрещает им строить деревни ближе, чем на дистанции одного сурового взгляда Великого Нмого (назовем для простоты это расстояние 1 св). Тем не менее, аборигены стараются располагать свои деревни так, чтобы расстояние между ними было поменьше — и торговля процветает, и к знакомым чайку попить недалеко идти.

На острове Нмала находится 6 деревень нмого, и, как говорят, расположены они так, что расстояние между двумя самыми удаленными друг от друга деревнями минимально возможное (назовем оптимальным и такое расположение, и расстояние между самыми удаленными друг от друга деревнями в оптимальном расположении).

1. (Частичное неконструктивное решение.) Найти и обосновать верхнюю и нижнюю границу оптимального расстояния (доказать, что оно находится в интервале [pq]). Тривиальным ответом на этот вопрос будет, например, интервал [1; 5], т. к. самые дальние деревни не могут быть ближе, чем 1 св по построению, а 5 соответствует деревням, расположенным на одной линии. Но это очень слабое решение, а чем более стягивается интервал, тем менее тривиальным делается доказательство.

2*. (Конструктивное решение.) Найти расположение деревень на острове Нмала и доказать, что расстояние между самыми удаленными деревнями минимальное из возможных.

3****. Решить вопросы 1 и 2 для общего случая N > 6 деревень. (Доб. Насколько я знаю, общего решения не известно, но попытаться стоит!)

Деревни, само собой, следует полагать безразмерными точками.

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

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

Доб. Все деревни находятся в одной плоскости. Евклидовой, предупреждая дальнейшие сомнения.

Tags:

Comments

fregimus
Dec. 21st, 2011 12:43 pm (UTC)
Я что-то очевидное упускаю? Ну, хорошее решение, но, может, как-то еще можно более компактно разложить? Доказать бы, что нет лучшего решения.
v_pychick
Dec. 21st, 2011 12:54 pm (UTC)
ну вроде как картинка намекает на доказательство от обратного. Предположим, что расположение на картинке не оптимально. Попробуем найти более оптимальное, перемещая точки.

1. Перемещаем Е. Переместить её, не нарушая условия, что точки находятся друг к другу не ближе, чем СВ, мы можем только за круг, на расстояние не менее 1 СВ от любой другой точки. Что дает расстояние явно большее до точки на противоположной стороне круга, чем 1.9 СВ. Не подходит.
2. Перемещаем любую другую кроме Е, возьмем А, они равнозначны (фактически эти перемещения - попытки привести взаимное расположение точек в любую другую фигуру, кроме "звездочки"). Двигать в круг нельзя, т.к. нарушим условие "расстояние до Е больше или равно СВ". Наружу - нельзя, увеличим АВ и АГ. Вдоль окружности: уменьшая АГ увеличиваем АВ и наоборот, не подходит.

Других вариантов я не вижу. Следовательно, данное расположение оптимально.
ihamsa.myopenid.com
Dec. 21st, 2011 01:26 pm (UTC)
Положим, двигая одну точку, уменьшить расстояние нельзя; ну а может быть можно подвинуть сразу несколько точек?
v_pychick
Dec. 21st, 2011 01:34 pm (UTC)
любое взаимное расположение точек достигается перемещением любых точек АБВВГ относительно Е (Е берем за начало координат и если двигается она, сдвигаем их тоже). Так вот подвинуть КУДА? внутрь круга? нельзя, станут ближе СВ. Наружу? нельзя - новое взаимное расстояние между точками на "противоположных" лучах звезды станет больше.
thedeemon
Dec. 21st, 2011 03:40 pm (UTC)
А давайте эту задачу на 4 точках посомтрим. Берем равносторонний треугольник и точку в центре. Двигать вершину внутрь аналогичной окружности нельзя, двигать наружу или вдоль окружности как бы тоже плохо - увеличиваем максимальное расстояние. Оптимальная фигура? Нет, квадрат лучше.

v_pychick
Dec. 22nd, 2011 05:45 am (UTC)
задача на 6-ти точках, а не на 4-х.
thedeemon
Dec. 22nd, 2011 07:23 am (UTC)
Рассуждения-то теже. Я просто показываю, что найдя локальный минимум, мы еще не доказали, что он же и глобальный.
v_pychick
Dec. 22nd, 2011 07:44 am (UTC)
Не считая того, что в случае 4-х точек нет понятия "противоположный луч".
thedeemon
Dec. 22nd, 2011 07:50 am (UTC)
Почему? В чем разница?
v_pychick
Dec. 22nd, 2011 08:01 am (UTC)
потому что при движении вдоль окружности в случае 6 точек у вас запас хода луча всего 12 градусов, а 4-х - 60. При таком движении центральная точка звездочки исчезает как и сама звездочка
thedeemon
Dec. 22nd, 2011 08:39 am (UTC)

Исчезает только в последней точке движения, и на всем интервале (включая последнюю точку) сохраняется условие увеличения расстояния до "противоположного луча". Все еще не вижу принципиальной разницы.
thedeemon
Dec. 22nd, 2011 09:12 am (UTC)
Реально разница есть, если рассматривать не локальное движение точки А, а геометрические места, куда она вообше может переместиться на плоскости. В случае 4 точек для А есть более "подходящие" места:

(за пределами красных зон, где слишком близки другие точки, но внутри пересечения зеленых, где максимальное расстояние не увеличивается)

А в случае 6 точек таких мест нет:

Синим криво обведена граница мест, где максимальное расстояние не увеличивается, она целиком в красной зоне.

Впрочем, не уверен, годится ли это доказательство, ибо это только движение одной точки. Глобальность минимума по-прежнему не очевидна.
v_pychick
Dec. 22nd, 2011 09:15 am (UTC)
вообще смешивать случаи разного количества точек нельзя.
v_pychick
Dec. 22nd, 2011 10:47 am (UTC)
для шести точек вполне очевидна.
вы согласны с тем, что минимум достигается в фигуре "звездочка"?
thedeemon
Dec. 22nd, 2011 11:02 am (UTC)
Лучшей конфигурации мне не известно, и скорее всего это действительно минимум. Но у меня нет доказательства несуществования лучшей конфигурации.
(no subject) - v_pychick - Dec. 22nd, 2011 12:43 pm (UTC) - Expand
(no subject) - thedeemon - Dec. 22nd, 2011 12:56 pm (UTC) - Expand