?

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

( 45 comments — Leave a comment )
p_govorun
Dec. 21st, 2011 08:42 am (UTC)
В порядке оффтопика отмечу такой факт: под суровым взглядом Великого Нмого деревня -- безразмерная точка. :-)
fregimus
Dec. 21st, 2011 09:03 am (UTC)
Да!
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)
(no subject) - v_pychick - Dec. 21st, 2011 11:35 am (UTC) - Expand
(no subject) - v_pychick - Dec. 21st, 2011 12:30 pm (UTC) - Expand
(no subject) - fregimus - Dec. 21st, 2011 12:33 pm (UTC) - Expand
(no subject) - v_pychick - Dec. 21st, 2011 12:39 pm (UTC) - Expand
(no subject) - fregimus - Dec. 21st, 2011 12:43 pm (UTC) - Expand
(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)
Шестиконечной в общем случае. Вообще, всё придумано до нас (С): соты.
(no subject) - rapitosov - Dec. 21st, 2011 09:47 am (UTC) - Expand
(no subject) - varthan - Dec. 21st, 2011 11:03 am (UTC) - Expand
(no subject) - rapitosov - Dec. 21st, 2011 11:22 am (UTC) - Expand
(no subject) - jakobz - Dec. 21st, 2011 10:11 am (UTC) - Expand
(no subject) - ali_lj - Dec. 21st, 2011 12:35 pm (UTC) - Expand
(no subject) - jakobz - Dec. 21st, 2011 12:43 pm (UTC) - Expand
(no subject) - ali_lj - Dec. 21st, 2011 01:01 pm (UTC) - Expand
eugenebo
Dec. 21st, 2011 09:44 am (UTC)
На первый неглубокий взгляд -- а не задача ли это о максимально плотной упаковке? Каждая деревня -- это шар с радиусом в 1 св (ближе никто быть не может). А расстояние R между самыми далёкими деревнями задаёт сферический контейнер радиусом R/2 + 1*св, в который деревни нужно вписать. Сферический, очевидно, потому, что в задаче нет никакого выбранного вектора -- т.е. любое решение должно допускать поворот на любое число градусов. Вопрос, собственно, тогда сводится к минимальному размеру контейнера, в который N деревень ещё можно запихать.

Или я что-то упустил?
fregimus
Dec. 21st, 2011 10:11 am (UTC)
Деревни на плоскости находятся. Они не висят в небе, и нмого не ходят пить чай к друзьям в облака и под землю!

Можно и как задачу об упаковке рассматривать, конечно, да.
thedeemon
Dec. 21st, 2011 10:17 am (UTC)
(не подсматривая)

Мое предположение: ~1.902 св. Равносторонний пятиугольник с одной деревней в центре и пятью в углах.

Бонус: анимированные наглядные эксперименты:
http://stuff.thedeemon.com/lj/nmogo.html
fregimus
Dec. 21st, 2011 12:36 pm (UTC)
О, интересная симуляция, спасибо! Только вот доказать бы минимальность-то…
thedeemon
Dec. 21st, 2011 03:59 pm (UTC)
Доказать пока не берусь.
junipher_greene
Dec. 21st, 2011 11:58 am (UTC)
Пункт 2. Интервал [1; 2]. Шесть деревень расположены в вершинах и серединах сторон равностороннего треугольника с основанием 2 св.
junipher_greene
Dec. 21st, 2011 12:01 pm (UTC)
Пункт 2. Интервал [1; φ]. Шесть деревень раположены в вершинах и геометрическом центре равностороннего пятиугольника со стороной 1 св.
(no subject) - junipher_greene - Dec. 21st, 2011 12:02 pm (UTC) - Expand
(no subject) - fregimus - Dec. 21st, 2011 12:34 pm (UTC) - Expand
ihamsa.myopenid.com
Dec. 21st, 2011 01:22 pm (UTC)
Насколько я понимаю, общего решения (для задачи 3) не существует. Очень похожую (но не идентичную) задачу решали R.L. Graham и другие, см. напр. http://www.math.ucsd.edu/~ronspubs/98_01_circles.pdf. Возможно, оттуда можно вытащить решение задачи 2. T.е. доказать, что это вершины и центр правильного пятиугольника, других вариантов вроде нет.
3bl
Dec. 22nd, 2011 07:52 am (UTC)
Задача на уровне интуиции, конечно, достаточно проста. Гораздо сложнее с математическим доказательством минимальности.
Я - не готов. Но предлагаю всё же отталкиваться от чисто геометрических измышлизмов.
Очевидно, что минимальным углом между двумя CВ из одной деревни на соседей (а их, также очевидно, всегда более 1) является 60 град (по признаку равностороннего треугольника). Больше 60 - можно, но то увеличивает расстояние между двумя соседними деревнями (но не факт, что увеличивает между самыми удаленными), меньше - нельзя по условию минимального расстояния в 1СВ.
( 45 comments — Leave a comment )