Минимум для сборки

[EtCetera]

venco

venco в сообщении #361485 писал(а):

другой короче

По-видимому, Вы правы. Мне вдруг привиделось, что радиус описанной вокруг правильного пятиугольника окружности равен его стороне, что, конечно же, неверно. А жаль, такая конфигурация, казалось бы, уже трепыхалась в руках... Впрочем, если удалить одну из вершин, то получившийся "недоикосаэдр" (вроде бы) начнет удовлетворять условиям задачи. Т.е. $n=11$ для $k=2$, $d=3$.

[ИСН]

Тоже нет.

[venco]

EtCetera в сообщении #361488 писал(а):

Впрочем, если удалить одну из вершин...

Придётся удалить по одной вершине из каждой пары противоположных, и останется только 6.

[venco]

ИСН в сообщении #360428 писал(а):

(1,1,0,0)
(1,0,1,0)
(1,0,0,1)
(0,1,1,0)
(0,1,0,1)
(0,0,1,1)
(-1,1,0,0)
...
ну, дальше понятно.

Между прочим, эта конфигурация позволяет расположить 25 точек с четырьмя расстояниями.

[EtCetera]

(Оффтоп)

ИСН в сообщении #361490 писал(а):

Тоже нет.

venco в сообщении #361492 писал(а):

EtCetera в сообщении #361488 писал(а):

Впрочем, если удалить одну из вершин...

Придётся удалить по одной вершине из каждой пары противоположных, и останется только 6.

Да-да-да. Можно считать экспериментально подтвержденным тот факт, что при приближении к 12 ночи "хорошие" конфигурации для данной задачи в моей голове превращаются в тыквы. Извиняюсь за икосаэдрический рецидив.

[ИСН]

Вспомнилась эта старая задача. Спрашивали про (23,3) - это удалось вложить в 6D (демикуб; точек даже больше, чем надо), а в 5D что-то никак. Ну и вообще: кто что думает?

[Dmitriy40]

Если нигде не ошибся, то вот вложение $(23,3)$ в 5D: $(0,0,0,0,0)$,$(0,0,0,1,1)$,$(0,1,1,1,-1)$,$(0,0,0,1,-1)$,$(0,0,1,0,1)$,$(0,0,1,0,-1)$,$(0,0,1,1,0)$,$(0,0,1,-1,0)$,$(0,1,0,0,1)$,$(0,1,0,0,-1)$,$(0,1,0,1,0)$,$(0,1,0,-1,0)$,$(0,1,1,0,0)$,$(0,1,1,1,1)$,$(0,1,-1,0,0)$,$(1,0,0,1,0)$,$(1,0,1,0,0)$,$(1,1,0,0,0)$,$(1,1,1,1,0)$,$(-1,0,0,1,0)$,$(-1,0,1,0,0)$,$(-1,1,0,0,0)$,$(-1,1,1,1,0)$.

[ИСН]

Юхууууу!!!

-- менее минуты назад --

Можно даже добавить точку (0,2,0,0,0).

[Dmitriy40]

Ещё несколько разных решений, не уверен что количество точек максимально:
$(3D,8,3): (0,0,0)$,$(0,0,1)$,$(1,1,0)$,$(0,1,0)$,$(0,1,1)$,$(1,0,0)$,$(1,0,1)$,$(1,1,1)$
$(3D,13,4): (0,0,0)$,$(0,0,2)$,$(1,1,0)$,$(0,2,0)$,$(0,1,1)$,$(0,2,2)$,$(1,0,1)$,$(1,1,2)$,$(1,2,1)$,$(-1,0,1)$,$(-1,1,0)$,$(-1,1,2)$,$(-1,2,1)$

$(4D,16,3): (0,0,0,1)$,$(0,0,0,-1)$,$(0,1,1,1)$,$(0,0,1,0)$,$(0,0,-1,0)$,$(0,1,0,0)$,$(0,1,1,-1)$,$(0,-1,0,0)$,$(1,0,0,0)$,$(1,0,1,1)$,$(1,0,1,-1)$,$(1,1,0,1)$,$(1,1,0,-1)$,$(1,1,1,0)$,$(1,1,-1,0)$,$(-1,0,0,0)$
$(4D,25,4): (0,0,0,0)$,$(0,0,1,1)$,$(0,0,1,-1)$,$(0,1,0,1)$,$(0,0,-1,1)$,$(0,0,-1,-1)$,$(0,1,0,-1)$,$(0,1,1,0)$,$(0,1,-1,0)$,$(0,-1,0,1)$,$(0,-1,0,-1)$,$(0,-1,1,0)$,$(0,-1,-1,0)$,$(1,0,0,1)$,$(1,0,0,-1)$,$(1,0,1,0)$,$(1,0,-1,0)$,$(1,1,0,0)$,$(1,-1,0,0)$,$(-1,0,0,1)$,$(-1,0,0,-1)$,$(-1,0,1,0)$,$(-1,0,-1,0)$,$(-1,1,0,0)$,$(-1,-1,0,0)$ (здесь первую точку программу почему-то не нашла, добавил руками, вроде подходит)

$(5D,36,4): (0,0,0,0,0)$,$(0,0,0,1,1)$,$(0,1,1,1,-1)$,$(0,0,0,-1,-1)$,$(0,0,0,1,-1)$,$(0,0,1,0,1)$,$(0,0,1,0,-1)$,$(0,0,1,1,0)$,$(0,0,1,-1,0)$,$(0,0,-1,0,-1)$,$(0,0,-1,1,0)$,$(0,1,0,0,1)$,$(0,1,0,0,-1)$,$(0,1,0,1,0)$,$(0,1,0,-1,0)$,$(0,1,1,0,0)$,$(0,1,-1,0,0)$,$(0,-1,0,0,-1)$,$(0,-1,0,1,0)$,$(0,-1,1,0,0)$,$(1,0,0,0,1)$,$(1,0,0,0,-1)$,$(1,0,0,1,0)$,$(1,0,0,-1,0)$,$(1,0,1,0,0)$,$(1,0,1,1,-1)$,$(1,0,-1,0,0)$,$(1,1,0,0,0)$,$(1,1,0,1,-1)$,$(1,1,1,0,-1)$,$(1,1,1,1,0)$,$(1,-1,0,0,0)$,$(-1,0,0,0,-1)$,$(-1,0,0,1,0)$,$(-1,0,1,0,0)$,$(-1,1,0,0,0)$

$(6D,32,3): (0,0,0,0,0,0)$,$(0,0,0,0,1,1)$,$(0,0,1,1,1,-1)$,$(0,0,0,0,1,-1)$,$(0,0,0,1,0,1)$,$(0,0,0,1,0,-1)$,$(0,0,0,1,1,0)$,$(0,0,0,1,-1,0)$,$(0,0,1,0,0,1)$,$(0,0,1,0,0,-1)$,$(0,0,1,0,1,0)$,$(0,0,1,0,-1,0)$,$(0,0,1,1,0,0)$,$(0,0,1,-1,0,0)$,$(0,1,0,0,0,-1)$,$(0,1,0,0,1,0)$,$(0,1,0,1,0,0)$,$(0,1,1,0,0,0)$,$(0,1,1,1,1,0)$,$(0,-1,0,0,1,0)$,$(0,-1,0,1,0,0)$,$(0,-1,1,0,0,0)$,$(1,0,0,0,0,-1)$,$(1,0,0,0,1,0)$,$(1,0,0,1,0,0)$,$(1,0,1,0,0,0)$,$(1,1,0,0,0,0)$,$(-1,0,0,0,0,-1)$,$(-1,0,0,0,1,0)$,$(-1,0,0,1,0,0)$,$(-1,0,1,0,0,0)$,$(-1,1,0,0,0,0)$

[Dmitriy40]

Наблюдая за найденными решениями, подумалось что их можно получать намного проще перебора. Для координат из множества $\{0, 1\}$ подходит расстояние Хэмминга. Для бОльших множеств аналогично, только считать не количество замен, а количество разных квадратов разностей для каждой замены.
Ну и плюс конечно кучу симметрий учесть.

С другой стороны, похоже некоторые решения не найдутся, например правильный пятиугольник $(2D,5,2)$, он ну явно не ложится в целочисленную сетку. Потому решения выше вполне могут быть не оптимальными.

[grizzly]

Dmitriy40 в сообщении #1249855 писал(а):

Ещё несколько разных решений, не уверен что количество точек максимально:
$(3D,8,3): $

Думаю, что максимум для 3D с тремя расстояниями будет достигаться на икосаэдре -- 12 точек.

А вообще интересная тема.

-- 23.09.2017, 01:28 --

У додекаэдра 20 вершин и 5 разных расстояний. Там тоже всё очень плотно -- скорее всего, по максимуму.
Интересно, что насчёт четырёх расстояний.

[Dmitriy40]

Про икосаэдр согласен.
Но, он вроде бы не влезает в целочисленную решётку (а как перебирать другие пока не придумал).
И, что хуже, не обобщается на высшие размерности, в 3D-то интересного не много.

[grizzly]

Dmitriy40 в сообщении #1249957 писал(а):

Но, он вроде бы не влезает в целочисленную решётку

Каждый вправе думать над задачей своими путями

Dmitriy40 в сообщении #1249957 писал(а):

а как перебирать другие пока не придумал

Можно попробовать по аналогии с икосаэдром добавить в больших размерностях к целочисленной решётке ($0, \pm 1$) значение золотого сечения -- $\pm \frac{1+\sqrt 5}{2}$. У додекаэдра добавляется ещё обратное: $\pm \frac{1-\sqrt 5}{2}$. Золотые сечения, когда возводятся в квадраты, хорошо сочетаются с целыми числами.

[Dmitriy40]

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

[grizzly]

Я на выходных выделил время и посмотрел литературу по этой теме. Оказалось, что:

Dmitriy40 в сообщении #1250031 писал(а):

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

Хуже того. Что-то определённое есть только для $\mathbb R^2$ для нескольких первых точек. Для $\mathbb R^3$ моя гипотеза о додекаэдре уже давно числится гипотезой без каких-либо заметных шансов перейти в другой разряд. О количестве точек в $\mathbb R^3$ с четырьмя расстояниями не удалось найти никаких гипотез. Для $\mathbb R^4$ уже в случае двух различных расстояний нет никакой определённости -- даже гипотезы никто особенно не рискуют светить. Вообще никаких конкретных результатов (известных на сегодняшний день рекордов) найти для $\mathbb R^4$ не удалось.

Всё это активно исследуется уже лет 70 (к чему существенно приложился Эрдёш с самого начала). Задача тесно связана с другими известными задачами (хроматические числа, граф единичных расстояний, гипотеза Борсука и многое другое из этой серии).

Немного информации есть в известной книге "Нерешённые пробелмы геометрии" (попробую оставить эту ссылку, см. п. F3 на стр. 152). Остальное гуглится начиная с ключевых слов "distinct distances problem" и дальше по найденным ссылкам.