?

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

v_pychick
Dec. 21st, 2011 08:42 am (UTC)
возможно, я что-то не понял в задаче?
Почему бы аборигенам не построить деревни пяитиконечной звездочкой с лучами в 1св и одной деревней в центре?
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)
Я что-то очевидное упускаю? Ну, хорошее решение, но, может, как-то еще можно более компактно разложить? Доказать бы, что нет лучшего решения.
(no subject) - v_pychick - Dec. 21st, 2011 12:54 pm (UTC) - Expand
(no subject) - ihamsa.myopenid.com - Dec. 21st, 2011 01:26 pm (UTC) - Expand
(no subject) - v_pychick - Dec. 21st, 2011 01:34 pm (UTC) - Expand
(no subject) - thedeemon - Dec. 21st, 2011 03:40 pm (UTC) - Expand
(no subject) - v_pychick - Dec. 22nd, 2011 05:45 am (UTC) - Expand
(no subject) - thedeemon - Dec. 22nd, 2011 07:23 am (UTC) - Expand
(no subject) - v_pychick - Dec. 22nd, 2011 07:44 am (UTC) - Expand
(no subject) - thedeemon - Dec. 22nd, 2011 07:50 am (UTC) - Expand
(no subject) - v_pychick - Dec. 22nd, 2011 08:01 am (UTC) - Expand
(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
gdt
Dec. 21st, 2011 09:01 am (UTC)
да, интуитивно кажется, что решение должно быть "как можно больше" симметричным. но с первого взгляда не видно, как это можно доказать. может быть, это вообще не так.
varthan
Dec. 21st, 2011 09:26 am (UTC)
Шестиконечной в общем случае. Вообще, всё придумано до нас (С): соты.
rapitosov
Dec. 21st, 2011 09:47 am (UTC)
соты хороши для большого количества объектов, а шести объектов на полную соту не хватает, попробуйте с шестью стаканами
varthan
Dec. 21st, 2011 11:03 am (UTC)
Ну, яж говорю - в общем случае.

На самом деле лучшим решением будет прикопать Великого Нмого в зиндан удобного населению диаметра, украсив внутреннее пространство оного красивыми, непорченными деревнями пейзажами.
rapitosov
Dec. 21st, 2011 11:22 am (UTC)
какой вы практичный :)
jakobz
Dec. 21st, 2011 10:11 am (UTC)
В данном случае для шестиугольников максимальное расстояние получается равным двум. В случае пятиугольника с точкой в центре оно меньше.

ali_lj
Dec. 21st, 2011 12:35 pm (UTC)
В пятиугольнике расстояние до центра меньше 1 св.
jakobz
Dec. 21st, 2011 12:43 pm (UTC)
В пятиугольнике со стороной 1 - да, но такой не пройдет по условиям задачи. Надо пятиугольник с диаметром описанной окружности 1, сторона там будет децл побольше 1, а диагональ при этом будет меньше 2.
(no subject) - ali_lj - Dec. 21st, 2011 01:01 pm (UTC) - Expand