Сколько отдаленных точек можно поместить в единичный куб?

[Markiyan Hirnyk]

Задача фольклорная, решение мне неизвестно. Пусть $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$ . Для высших размерностей задача еще сложнее.

[svv]

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

[Dmitriy40]

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

[feedinglight]

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

[wrest]

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

4 на нижней грани в углах,

Markiyan Hirnyk в сообщении #1391788 писал(а):

попарно удалены на расстояние строго больше единицы.

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

[svv]

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

[wrest]

svv в сообщении #1391876 писал(а):

достаточно ясно описывает, как).

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

[venco]

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$.

[Markiyan Hirnyk]

Уважаемые коллеги, кроме дельной оценки 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}$. В ожидании конструктивного обсуждения.

[feedinglight]

(Оффтоп)

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

[Markiyan Hirnyk]

feedinglight

Цитата:

Вроде это задача типа упаковки равных сфер

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

[grizzly]

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$.

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

[Markiyan Hirnyk]

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);

[grizzly]

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

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

[Markiyan Hirnyk]

grizzly

Цитата:

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

Уже при $n=5$ ответ $2^n-1$ неверен: можно добавить центр пятимерного куби, т.к. длина главной диагонали куба равна $\sqrt 5=2.236067977...$.
Пока даже для трехмерного случая задача недорешена: не рассмотрен случай 8 точек, т.е. не показана его невозможность.