?

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

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