Минимально удаленные аборигены

[fregimus]

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

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

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

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

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

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

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

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

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

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

Comments

[p_govorun.livejournal.com]

В порядке оффтопика отмечу такой факт: под суровым взглядом Великого Нмого деревня -- безразмерная точка. :-)

[fregimus.livejournal.com]

Да!

[v-pychick.livejournal.com]

возможно, я что-то не понял в задаче?
Почему бы аборигенам не построить деревни пяитиконечной звездочкой с лучами в 1св и одной деревней в центре?

[fregimus.livejournal.com]

Построить-то по-всякому можно. А вот почему решение будет оптимальным…

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

[v-pychick.livejournal.com]

Картинка, как я её вижу, такая.



(http://www.pychick.ru/lj/1/DSC09263s.JPG)

За окружность деревни выносить не имеет смысла, т.к. это только увеличит расстояние между ними, внутрь занести тоже нельзя, т.к. не выполнится условие сурового взгляда. Вдоль окружности можно попробовать подвинуть точку (к примеру, А по стрелочке), но это сразу с уменьшением АГ увеличит АВ, что недопустимо).

[v-pychick.livejournal.com]

сосбтвенно 1.9021130325903071442328786667588*СВ максимум в этом случае

[fregimus.livejournal.com]

Не хватает только маленькой детали: доказательства минимальности.

[v-pychick.livejournal.com]

а картинка выше не катит?

[fregimus.livejournal.com]

Я что-то очевидное упускаю? Ну, хорошее решение, но, может, как-то еще можно более компактно разложить? Доказать бы, что нет лучшего решения.

[v-pychick.livejournal.com]

ну вроде как картинка намекает на доказательство от обратного. Предположим, что расположение на картинке не оптимально. Попробуем найти более оптимальное, перемещая точки.

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

Других вариантов я не вижу. Следовательно, данное расположение оптимально.

[ihamsa.myopenid.com (from livejournal.com)]

Положим, двигая одну точку, уменьшить расстояние нельзя; ну а может быть можно подвинуть сразу несколько точек?

[v-pychick.livejournal.com]

любое взаимное расположение точек достигается перемещением любых точек АБВВГ относительно Е (Е берем за начало координат и если двигается она, сдвигаем их тоже). Так вот подвинуть КУДА? внутрь круга? нельзя, станут ближе СВ. Наружу? нельзя - новое взаимное расстояние между точками на "противоположных" лучах звезды станет больше.

[thedeemon.livejournal.com]

А давайте эту задачу на 4 точках посомтрим. Берем равносторонний треугольник и точку в центре. Двигать вершину внутрь аналогичной окружности нельзя, двигать наружу или вдоль окружности как бы тоже плохо - увеличиваем максимальное расстояние. Оптимальная фигура? Нет, квадрат лучше.

[v-pychick.livejournal.com]

задача на 6-ти точках, а не на 4-х.

[thedeemon.livejournal.com]

Рассуждения-то теже. Я просто показываю, что найдя локальный минимум, мы еще не доказали, что он же и глобальный.

[v-pychick.livejournal.com]

Не считая того, что в случае 4-х точек нет понятия "противоположный луч".

[thedeemon.livejournal.com]

Почему? В чем разница?

[v-pychick.livejournal.com]

потому что при движении вдоль окружности в случае 6 точек у вас запас хода луча всего 12 градусов, а 4-х - 60. При таком движении центральная точка звездочки исчезает как и сама звездочка

[thedeemon.livejournal.com]

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

[thedeemon.livejournal.com]

Реально разница есть, если рассматривать не локальное движение точки А, а геометрические места, куда она вообше может переместиться на плоскости. В случае 4 точек для А есть более "подходящие" места:

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

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

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

Впрочем, не уверен, годится ли это доказательство, ибо это только движение одной точки. Глобальность минимума по-прежнему не очевидна.

[v-pychick.livejournal.com]

вообще смешивать случаи разного количества точек нельзя.

[v-pychick.livejournal.com]

для шести точек вполне очевидна.
вы согласны с тем, что минимум достигается в фигуре "звездочка"?

[thedeemon.livejournal.com]

Лучшей конфигурации мне не известно, и скорее всего это действительно минимум. Но у меня нет доказательства несуществования лучшей конфигурации.

[v-pychick.livejournal.com]

да почему же, я не понимаю...
давайте приведем факты, полученные уже нами и вытекающие из условия задачи..

1. три любые точки из шести не должны находиться на одной прямой (т.к. это автоматически означает расстояние 2СВ, что явно хуже достигнутого результата).
2. максимальный угол в любом треугольнике образованном любыми тремя точками не должен превышать 144 градусов.
3. Все точки должны принадлежать кругу с радиусом СВ.
4. расстояние между двумя любыми точками не меньше СВ.
5. Расстояние между двумя любыми точками не больше 1.9021130325903071442328786667588*СВ

условиям 3 и 4 соответствуют две фигуры - пятиугольник (не обязательно равносторонний) с точкой в центре (наша звездочка) и равносторонний шестиугольник. Шестиугольник убирается условием 5. Условие 2 делает пятиугольник равносторонним.

[thedeemon.livejournal.com]

А пункт 3 откуда следует?

[gdt.livejournal.com]

да, интуитивно кажется, что решение должно быть "как можно больше" симметричным. но с первого взгляда не видно, как это можно доказать. может быть, это вообще не так.

[varthan.livejournal.com]

Шестиконечной в общем случае. Вообще, всё придумано до нас (С): соты.

[rapitosov.livejournal.com]

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

[varthan.livejournal.com]

Ну, яж говорю - в общем случае.

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

[rapitosov.livejournal.com]

какой вы практичный :)

[jakobz.livejournal.com]

В данном случае для шестиугольников максимальное расстояние получается равным двум. В случае пятиугольника с точкой в центре оно меньше.

[ali-lj.livejournal.com]

В пятиугольнике расстояние до центра меньше 1 св.

[jakobz.livejournal.com]

В пятиугольнике со стороной 1 - да, но такой не пройдет по условиям задачи. Надо пятиугольник с диаметром описанной окружности 1, сторона там будет децл побольше 1, а диагональ при этом будет меньше 2.

[ali-lj.livejournal.com]

Ага, точно. Для описанной с R = 1 св похоже на правду :)

[eugenebo.livejournal.com]

На первый неглубокий взгляд -- а не задача ли это о максимально плотной упаковке? Каждая деревня -- это шар с радиусом в 1 св (ближе никто быть не может). А расстояние R между самыми далёкими деревнями задаёт сферический контейнер радиусом R/2 + 1*св, в который деревни нужно вписать. Сферический, очевидно, потому, что в задаче нет никакого выбранного вектора -- т.е. любое решение должно допускать поворот на любое число градусов. Вопрос, собственно, тогда сводится к минимальному размеру контейнера, в который N деревень ещё можно запихать.

Или я что-то упустил?

[fregimus.livejournal.com]

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

Можно и как задачу об упаковке рассматривать, конечно, да.

[thedeemon.livejournal.com]

(не подсматривая)

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

Бонус: анимированные наглядные эксперименты:
http://stuff.thedeemon.com/lj/nmogo.html

[fregimus.livejournal.com]

О, интересная симуляция, спасибо! Только вот доказать бы минимальность-то…

[thedeemon.livejournal.com]

Доказать пока не берусь.

[junipher-greene.livejournal.com]

Пункт 2. Интервал [1; 2]. Шесть деревень расположены в вершинах и серединах сторон равностороннего треугольника с основанием 2 св.

[junipher-greene.livejournal.com]

Пункт 2. Интервал [1; φ]. Шесть деревень раположены в вершинах и геометрическом центре равностороннего пятиугольника со стороной 1 св.

[junipher-greene.livejournal.com]

И то, и другое про пункт 1, конечно.

[fregimus.livejournal.com]

Неверно: от центра до вершины < 1.

[ihamsa.myopenid.com (from livejournal.com)]

Насколько я понимаю, общего решения (для задачи 3) не существует. Очень похожую (но не идентичную) задачу решали R.L. Graham и другие, см. напр. http://www.math.ucsd.edu/~ronspubs/98_01_circles.pdf. Возможно, оттуда можно вытащить решение задачи 2. T.е. доказать, что это вершины и центр правильного пятиугольника, других вариантов вроде нет.

[3bl.livejournal.com]

Задача на уровне интуиции, конечно, достаточно проста. Гораздо сложнее с математическим доказательством минимальности.
Я - не готов. Но предлагаю всё же отталкиваться от чисто геометрических измышлизмов.
Очевидно, что минимальным углом между двумя CВ из одной деревни на соседей (а их, также очевидно, всегда более 1) является 60 град (по признаку равностороннего треугольника). Больше 60 - можно, но то увеличивает расстояние между двумя соседними деревнями (но не факт, что увеличивает между самыми удаленными), меньше - нельзя по условию минимального расстояния в 1СВ.