December 21st, 2011

oak

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

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

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

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

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

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

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

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

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

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

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

scholar.google.com

«Гугол», похоже, отделил scholar.google.com от основного поиска. Теперь ни ссылки на него нет в основном поиске (ни даже в меню “More...”!), ни результата поиска по статьям среди результатов поиска по вебу. В общем, набираешь URL, копируешь строку поиска… Совершенно отдельный сервис.

Будем надеяться, что хоть совсем не прибьют.

Доб. Вру, иногда результаты все-таки показываются в основном поиске (под ними ссылки “Cited by” и “Related articles”).

Доб 2. 13 пользователей Гугола огорчены нововыведением «школяра». Эх, не видать нам его больше. За ссылку спасибо pamersiel.

Доб 3. http://googleblog.blogspot.com/2011/11/next-stage-in-our-redesign.html