2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Сколько отдаленных точек можно поместить в единичный куб?
Сообщение08.05.2019, 20:29 


11/07/16
801
Задача фольклорная, решение мне неизвестно. Пусть $n$ различных точек в единичном кубе
попарно удалены на расстояние строго больше единицы. Какое наибольшее значение может принять $n$?
Несложно разместить таким образом 6 точек. Пусть вершины куба обозначены
$A(0,0,0), B(0,1,0),C(1,1,0),D(1,0,0), A_1(0,0,1),B_1(0,1,1),C_1(1,1,1),D_1(1,0,1)$.
Четыре точки располагаем в сечении $ AA_1C_1C$, а середины ребер $BB_1$ и $ DD_1$ - еще две точки.
Оценка сверху на количество таких точек получается из оценок объемов. Понятно, что шары радиуса $1/2$
с центрами в этих точках не пересекаются. Понятно также, что по крайней мере $ 1/8$ часть такого шара
с объемом не менее $\frac {\pi(\frac 1 2)^3} {6}=\frac \pi {48}$ является подмножеством единичного куба.
Отсюда следует $n \le \lfloor \frac {48} \pi\rfloor = 15$. Задача привлекает тем, что непонятно, как исследовать
случаи $ n >6, n\le 15$ . Для высших размерностей задача еще сложнее.

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение08.05.2019, 21:49 
Заслуженный участник


23/07/08
10626
Crna Gora
Разобьём куб на $8$ маленьких кубиков со стороной $1/2$. Диаметр (максимальное расстояние между двумя точками) каждого маленького кубика равен $\frac{\sqrt{3}}2<1$. Значит, в каждом маленьком кубике можно разместить не более одной точки, а всего в единичном кубе — не более восьми.

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение08.05.2019, 22:31 
Заслуженный участник


20/08/14
11066
Россия, Москва
Восемь точно можно, например: 4 на нижней грани в углах, 4 на верхней грани в серединах рёбер, 2 нижние диагональные пары чуточку приподнять, 2 верхних диагональных пары чуть опустить. Верхние от нижних и так были достаточно далеко, а поднятие и спуск увеличивают расстояния в четвёрках.
Девятая никуда не влезает ...

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение08.05.2019, 23:03 


16/04/19
161
То есть сколько шаров помещается в куб $2\times2\times2$
Вроде это задача типа упаковки равных сфер.

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 00:04 


05/09/16
11468
Dmitriy40 в сообщении #1391830 писал(а):
4 на нижней грани в углах,
Markiyan Hirnyk в сообщении #1391788 писал(а):
попарно удалены на расстояние строго больше единицы.

:?:
Точки в соседних вершинах удалены на единицу, а не строго больше, так ведь?

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 00:33 
Заслуженный участник


23/07/08
10626
Crna Gora
Ну, поэтому Dmitriy40 чуточку сдвигает некоторые точки из углов так, чтобы расстояние стало строго больше $1$ (достаточно ясно описывает, как).

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 00:43 


05/09/16
11468
svv в сообщении #1391876 писал(а):
достаточно ясно описывает, как).

А... дотуда я не дочитал :facepalm:
Dmitriy40
Вопрос снимаю.

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 03:08 
Заслуженный участник


04/05/09
4582
Dmitriy40 в сообщении #1391830 писал(а):
4 на верхней грани в серединах рёбер
Слишком близко.

-- Ср май 08, 2019 19:17:51 --

7 точно помещаются.

-- Ср май 08, 2019 19:27:34 --

А 8 точно не помещаются.

-- Ср май 08, 2019 19:42:32 --

Допустим точек 8, тогда они должны находиться в угловых кубиках со стороной $1\over 2$ (см сообщение svv). Тогда ограничение можно усилить до угловых кубиков со стороной $1-{\sqrt 2\over 2}$, учитывая только точки у соседних вершин. Тогда ограничение можно ещё усилить, и так далее до угловых кубиков со стороной $0$.

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 09:05 


11/07/16
801
Уважаемые коллеги, кроме дельной оценки svv и толкового замечания wrest о том, что условие задачи "строго больше единицы", а не "больше или равно единицы", комментировать нечего. Я могу указать координаты точек: $P_1=A,P_2(1/8,1/8,1),P_3=C_1,P_4(7/8,7/8,0),P_5(1,0,1/2),P_6(0,1,1/2)$. Dmitriy40 и venco, пожалуйста, укажите и Вы эти координаты. Пробовал рассмотреть случай $n=7$, применяя математические системы. Таким образом образом можно рассмотреть условие, что расстояния больше или равны $1+10^{-200}$ (я утрирую), но тогда неясно, что с расстояниями, больше или равными $1+10^{-201}$. В ожидании конструктивного обсуждения.

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 09:36 


16/04/19
161

(Оффтоп)

есть коробка 2х2х2 и шары радиуса чуть больше 1
8 шаров точно не поместятся
чтобы поместить 7:
4 кладём вниз коробки (хотя бы 1 шар придётся чуть-чуть приподнять)
сверху вываливаем ещё 3, они сами скатятся куда надо, если потрести, кажется что влезут

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 10:18 


11/07/16
801
feedinglight
Цитата:
Вроде это задача типа упаковки равных сфер

Нет, это не так: радиусы сфер могут быть разными. Расстояния между центрами сфер должны быть строго больше единицы.

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


09/09/14
6328
Markiyan Hirnyk в сообщении #1391931 писал(а):
пожалуйста, укажите и Вы эти координаты
Ну для 7 точек просто:
    $\{0;0;0\}$
    $\{1;1;0\}$
    $\{0;1;\alpha\}$
    $\{1;0;\alpha\}$
    $\{\alpha;\alpha;1\}$
    $\{\beta;1;1\}$
    $\{1;\beta;1\}$,
где $\alpha =0.025$, $\beta=0.25$.

Надеюсь, ничего не напутал. Подобрал вручную за пару минут -- всего-то два параметра.

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 11:38 


11/07/16
801
grizzly Спасибо. Проверил с Мэйплом

Код:
seq(seq(VectorCalculus:-Norm(a-b), a = [`<,>`(0, 0, 0), `<,>`(1, 1, 0), `<,>`(0, 1, 0.25e-1), `<,>`(1, 0, 0.25e-1), `<,>`(0.25e-1, 0.25e-1, 1), `<,>`(.25, 1, 1), `<,>`(1, .25, 1)]), b = [`<,>`(0, 0, 0), `<,>`(1, 1, 0), `<,>`(0, 1, 0.25e-1), `<,>`(1, 0, 0.25e-1), `<,>`(0.25e-1, 0.25e-1, 1), `<,>`(.25, 1, 1), `<,>`(1, .25, 1)]);
    (1/2)                                                     
0, 2     , 1.000312451, 1.000312451, 1.000624805, 1.436140662,

                (1/2)                                           
  1.436140662, 2     , 0, 1.000312451, 1.000312451, 1.703305610,

  1.250000000, 1.250000000, 1.000312451, 1.000312451, 0.,

  1.414213562, 1.379084841, 1.006541107, 1.585283886,

  1.000312451, 1.000312451, 1.414213562, 0., 1.379084841,

  1.585283886, 1.006541107, 1.000624805, 1.703305610,

  1.379084841, 1.379084841, 0., 1.000624805, 1.000624805,

  1.436140662, 1.250000000, 1.006541107, 1.585283886,

  1.000624805, 0., 1.060660172, 1.436140662, 1.250000000,

  1.585283886, 1.006541107, 1.000624805, 1.060660172, 0.
plots:-pointplot3d([`<,>`(0, 0, 0), `<,>`(1, 1, 0), `<,>`(0, 1, 0.25e-1), `<,>`(1, 0, 0.25e-1), `<,>`(0.25e-1, 0.25e-1, 1), `<,>`(.25, 1, 1), `<,>`(1, .25, 1)], symbol = solidsphere, symbolsize = 20);

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


09/09/14
6328
А вообще задача очень интересная, если рассматривать её в более высоких размерностях. Предполагаю, что она не решена, поскольку обычно решают задачу с расстояниями не меньшими единицы (нестрогое неравенство). Там на размерности 3 всё простое заканчивается и дальше количество точек растёт быстрее количества вершин.

А в этой постановке я не знаю, можно ли выбрать больше, чем число вершин, или формула $2^n-1$ будет точной. Ну, или ни то ни другое :)

 Профиль  
                  
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 12:35 


11/07/16
801
grizzly
Цитата:
А в этой постановке я не знаю, можно ли выбрать больше, чем число вершин, или формула $2^n-1$ будет точной
Уже при $n=5$ ответ $2^n-1$ неверен: можно добавить центр пятимерного куби, т.к. длина главной диагонали куба равна $\sqrt 5=2.236067977...$.
Пока даже для трехмерного случая задача недорешена: не рассмотрен случай 8 точек, т.е. не показана его невозможность.

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

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



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

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


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

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