?

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 08:52 am (UTC)
Построить-то по-всякому можно. А вот почему решение будет оптимальным…

Доб. Но это, конечно, одно из решений вопроса 1: Вы ограничили расстояние сверху диагональю пятиугольника, охватывающего эту звездочку. Только надо, конечно, подсчитать и показать, что условие минимального расстояния между деревнями выполнено.

Edited at 2011-12-21 09:12 am (UTC)
v_pychick
Dec. 21st, 2011 11:35 am (UTC)
Картинка, как я её вижу, такая.




кликабельно (1024х768 77kb)


За окружность деревни выносить не имеет смысла, т.к. это только увеличит расстояние между ними, внутрь занести тоже нельзя, т.к. не выполнится условие сурового взгляда. Вдоль окружности можно попробовать подвинуть точку (к примеру, А по стрелочке), но это сразу с уменьшением АГ увеличит АВ, что недопустимо).
v_pychick
Dec. 21st, 2011 12:30 pm (UTC)
сосбтвенно 1.9021130325903071442328786667588*СВ максимум в этом случае
fregimus
Dec. 21st, 2011 12:33 pm (UTC)
Не хватает только маленькой детали: доказательства минимальности.
v_pychick
Dec. 21st, 2011 12:39 pm (UTC)
а картинка выше не катит?
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. При таком движении центральная точка звездочки исчезает как и сама звездочка
(no subject) - thedeemon - Dec. 22nd, 2011 08:39 am (UTC) - Expand
(no subject) - thedeemon - Dec. 22nd, 2011 09:12 am (UTC) - Expand
(no subject) - v_pychick - Dec. 22nd, 2011 09:15 am (UTC) - Expand
(no subject) - v_pychick - Dec. 22nd, 2011 10:47 am (UTC) - Expand
(no subject) - thedeemon - Dec. 22nd, 2011 11:02 am (UTC) - Expand
(no subject) - v_pychick - Dec. 22nd, 2011 12:43 pm (UTC) - Expand
(no subject) - thedeemon - Dec. 22nd, 2011 12:56 pm (UTC) - Expand