Made in China :)

[grizzly]

Продолжим поиски неразгаданного интересного в среде MSE. Предлагаю оценить сложность китайских олимпиад

Дано $n+1$ различных точек на плоскости $A_0,A_1,\ldots,A_n$ и $m$ -- минимум среди попарных расстояний между этими точками.
Пусть $|AB|$ обозначает расстояние между точками $A$ и $B$. Какое наименьшее значение может принимать следующее выражение:

$$ \dfrac{|A_0A_1|\cdot|A_0A_2|\dots|A_0A_n|}{m^n}. $$

Для $n\le 6$ ответ очевиден. А дальше?

[Sender]

grizzly в сообщении #1054497 писал(а):

Дано $n$ различных точек на плоскости $A_0,A_1,\ldots,A_n$

Воочию вижу $n+1$ точку.

[grizzly]

Sender в сообщении #1054503 писал(а):

Воочию вижу $n+1$ точку.

Спасибо! Пересказал своими словами
Сейчас поправлю всё в исходном сообщении.

[Sender]

Предлагаю следующую переформулировку:
Дано $n+1$ различных точек на плоскости $A_0,A_1,\ldots,A_n$, попарные расстояния между которыми не меньше $1$.
Пусть $|AB|$ обозначает расстояние между точками $A$ и $B$. Какое наименьшее значение может принимать выражение $|A_0A_1|\cdot|A_0A_2|\cdot\ldots\cdot|A_0A_n|$?

-- Пт сен 18, 2015 12:18:10 --

Кстати, для $n=7$ я пока вижу только $\sqrt{3}$. Кто меньше?

[grizzly]

Sender в сообщении #1054514 писал(а):

Кстати, для $n=7$ я пока вижу только $\sqrt{3}$. Кто меньше?

Да, так хочется предположить, что решение всегда будет иметь вид концентрических правильных шестиугольников, повёрнутых через раз на $\pi /6$. Для $n$ не кратных 6 шестиугольник верхнего уровня будет просто недозаполнен.

[amon]

grizzly в сообщении #1054540 писал(а):

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

Боюсь, что нет. На моем птичьем языке это называется зонами Бриллюэна гексагональной решетки, а они такие:

[12d3]

Предлагаю попробовать доказать или опровергнуть следующее утверждение (мне оно кажется правдоподобным): Считаем положение точки $A_0$ фиксированным.
Пусть $X_n$ - множество расстановок точек $A_1,...,A_n$, дающих глобальный минимум целевой функции, $P(x), x \in X_n$ - множество точек расстановки $x$. Тогда $\forall x \in X_{n+1} \,\,\exists y \in X_n : P(y) \subset P(x)$.

[amon]

Вместо того, что бы делом заняться, эта задачка крутится. Координаты узлов на плоскости (комплексной) можно параметризовать двумя целыми числами и записать в виде $Z_{mn}=m+n\tilde{z}$, где $\tilde{z}=e^{i\pi/3}$. Тогда $\left\lvert Z_{mn}\right\rvert^2=m^2+n^2+mn$ дадут квадраты радиусов соответствующих "зон Бриллюэна", а "вырождение" по $mn$ - число узлов с данным радиусом. Дальше Диофантовы уравнения пошли, я в них не силен. Минимум получится при полном заполнении нижних зон. Все, пошел своим делом заниматься.

[grizzly]

amon в сообщении #1054544 писал(а):

это называется зонами Бриллюэна гексагональной решетки, а они такие:

Жутко интересно. Я не знал об этом ранее. Очевидно, Вы правы -- моего пространственного воображения почти хватило на 3 шестиугольника, а если бы хватило чуть больше, чем на "почти", я бы догадался, что следующий -- 4 круг -- вмещает 12 точек. Замечательно!

По поводу зон Бриллюэна. Я пока не разобрался полностью, но на Вашем рисунке или что-то немного не так, или это не совсем наш случай. Обратите внимание на самую внешнюю из заштрихованных областей. Расстояние от её точек до вершин чёрной звезды Давида меньше 1. На самом деле я на Вашем рисунке вижу 3 нужных нам концентрических шестиугольника -- белый, звезда Давида и следующий с вертикальной штриховкой, а нужных точек следующего цикла не вижу (если я правильно представляю себе, что это будет 12 точек на следующей концентрической окружности -- они располагаются на пересечении сторон первого и третьего концентрических шестиугольников).

Поправьте меня, пожалуйста, если я ошибаюсь (но только когда освободитесь).

-- 18.09.2015, 16:12 --

12d3
Прошу извинить, я по уши залез в пространственное воображение и теперь не могу вернуться в мир формул, чтобы разобрать полторы строчки. Не могли бы Вы на словах расшифровать Ваше утверждение? Спасибо заранее.

[amon]

grizzly в сообщении #1054569 писал(а):

это не совсем наш случай.

Скорее всего, не наш. По-моему, решеток типа нашей в природе нет, а есть шестиугольная без узла в центре. Рисунок этот я спер из презентации по физике, и там, скорее всего, рассматривалась решетка графена (без узла в центре). Но ниже, пользуясь сакральным знанием о решетках Браве, я, вроде, свел задачу от картинок к уравнениям в целых числах (правда, уравнения не выписал, и решить их не могу ;)

[12d3]

grizzly в сообщении #1054569 писал(а):

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

Утверждается, что оптимальная конфигурация из $n+1$ точек получается из некоторой оптимальной конфигурации для $n$ точек просто дорисовыванием одной точки на минимально возможном расстоянии от центра. Получится такой конструктивный метод. То бишь, если у нас вначале есть только точка $A_0$, то в процессе к ней на радиусе 1 дорисуются 6 точек, потом еще 6 точек в углах шестиугольника, и т.д., вы итоге выйдет, что наши точки образуют гексагональную решетку с шагом 1. Собственно, это и описал amon.

[grizzly]

12d3 в сообщении #1054577 писал(а):

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

А ну да, это она и есть. Тогда нужно попытаться найти способ напрямую использовать свойства оптимальности этих решёток / диаграмм Вороного.

[Sender]

Нарисовал картинку покрупнее.
Поскольку узлы гексагональной решётки имеют координаты $(\frac{i}{2},\frac{j\sqrt{3}}{2})$, радиусы окружностей будут иметь вид $\frac{\sqrt{i^2+3j^2}}{2}$, где $i,j\in \mathbb{Z}$.

[Munin]

Подпись:
Атом молибдена. Коперник, тушь, XVI век.

[amon]

Исключительно, приоритет застолбить ;) (Что бы потом, когда кто-нибудь действительно задачу решит, кричать: "Я - раньше! Я -первый!")

Имеется гексагональная решетка. Ее можно построить так. Рассмотрим комплексную плоскость. Пусть первый узел находится в начале координат. Все остальные узлы получатся складыванием чисел $m$ (вещественное целое число) и $ne^{i\pi/3}$ ($n$ - тоже вещественное целое). Тогда комплексные числа, соответствующие узлам, имеют вид $Z_{mn}=m+n\tilde{z}$, где $\tilde{z}=e^{i\pi/3}$. Квадрат радиуса окружности получается как $R^2=Z_{mn}Z_{mn}^*=m^2+n^2+mn$, то есть тоже целое (здесь я почему-то не согласуюсь с Sender'ом). Остается сосчитать, какие бывают $R^2$ы, и сколько на каждом таком кружке узлов (не меньше шести, но бывает и больше). На компьютере это делается мгновенно, посему мой мозг, привыкший за последние годы к тому, что если задача сведена к компьютерной, то она решена, дальше думать отказался.

-- 18.09.2015, 23:31 --

Sender в сообщении #1054731 писал(а):

узлы гексагональной решётки имеют координаты $(\frac{i}{2},\frac{j\sqrt{3}}{2})$

Вы в этом уверены? По-моему, можно нарисовать эту решетку как две вложенные прямоугольные $(i,2j)$ сдвинутые на мой $\tilde{z}=e^{i\pi/3}$, но не одну. Или я чего-то не понял.