2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Минимум для сборки
Сообщение12.10.2010, 23:36 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение12.10.2010, 23:50 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Тоже нет.

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение13.10.2010, 00:08 
Заслуженный участник


04/05/09
4589
EtCetera в сообщении #361488 писал(а):
Впрочем, если удалить одну из вершин...
Придётся удалить по одной вершине из каждой пары противоположных, и останется только 6.

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение13.10.2010, 03:59 
Заслуженный участник


04/05/09
4589
ИСН в сообщении #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 точек с четырьмя расстояниями.

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение13.10.2010, 23:51 
Заслуженный участник


28/04/09
1933

(Оффтоп)

ИСН в сообщении #361490 писал(а):
Тоже нет.
venco в сообщении #361492 писал(а):
EtCetera в сообщении #361488 писал(а):
Впрочем, если удалить одну из вершин...
Придётся удалить по одной вершине из каждой пары противоположных, и останется только 6.
Да-да-да. Можно считать экспериментально подтвержденным тот факт, что при приближении к 12 ночи "хорошие" конфигурации для данной задачи в моей голове превращаются в тыквы. Извиняюсь за икосаэдрический рецидив.

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение22.09.2017, 00:15 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение22.09.2017, 09:58 
Заслуженный участник


20/08/14
11867
Россия, Москва
Если нигде не ошибся, то вот вложение $(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)$.

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение22.09.2017, 10:14 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Юхууууу!!!

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

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

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение22.09.2017, 22:02 
Заслуженный участник


20/08/14
11867
Россия, Москва
Ещё несколько разных решений, не уверен что количество точек максимально:
$(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)$

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение22.09.2017, 23:52 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение23.09.2017, 01:10 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Dmitriy40 в сообщении #1249855 писал(а):
Ещё несколько разных решений, не уверен что количество точек максимально:
$(3D,8,3): $
Думаю, что максимум для 3D с тремя расстояниями будет достигаться на икосаэдре -- 12 точек.

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

-- 23.09.2017, 01:28 --

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

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение23.09.2017, 11:56 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение23.09.2017, 13:02 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение23.09.2017, 15:49 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Минимум для сборки
Сообщение25.09.2017, 12:18 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 41 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group