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

[grizzly]

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

Уже при $n=5$ ответ $2^n-1$ неверен: можно добавить центр пятимерного куби

К чему добавить? :) Впрочем, согласен, после такого аргумента интуитивно кажется, что количество точек должно расти быстрее, чем число вершин.

[Dmitriy40]

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

Dmitriy40 и venco, пожалуйста, укажите и Вы эти координаты.

Да пожалуйста: $\{(0;0;0),(1;1;0),(0.5;0;1),(0.5;1;1),(1;0;0.1),(0;1;0.1),(0;0.5;0.9),(1;0.5;0.9)\}$, последние 4 точки немного смещены по Z для увеличения расстояний по граням.

[grizzly]

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

Да пожалуйста: $\{(0;0;0),(1;1;0),(0.5;0;1),(0.5;1;1),(1;0;0.1),(0;1;0.1),(0;0.5;0.9),(1;0.5;0.9)\}$,

Между третьей и седьмой точками, например, расстояние меньше 1. Об этом уже говорили выше.

[Dmitriy40]

Да, что-то я стормозил, с чего-то взял что при повороте квадрата по рёбрам он сохраняет расстояния между точками ...

[venco]

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

Dmitriy40 и venco, пожалуйста, укажите и Вы эти координаты.

У меня другая конфигурация:
$(0,0,0)$
$(1,a,a)$
$(a,1,a)$
$(a,a,1)$
$(b,1,1)$
$(1,b,1)$
$(1,1,b)$
$a=0.033$
$b=0.29$

-- Чт май 09, 2019 09:00:06 --

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

Пока даже для трехмерного случая задача недорешена: не рассмотрен случай 8 точек, т.е. не показана его невозможность.

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

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

[Markiyan Hirnyk]

venco Мне непонятно Ваше предложение. Первое неясное место

Цитата:

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

Какое ограничение? Что значит усилить? Пожалуйста, изложите его подробнее.

Цитата:

У меня другая конфигурация

Да, проверка подтверждает:

restart; with(VectorCalculus): seq(seq(Norm(VectorCalculus:-`+`(a, VectorCalculus:-`-`(b))), a = [`<,>`(0, 0, 0), `<,>`(1, 0.33e-1, 0.33e-1), `<,>`(0.33e-1, 1, 0.33e-1), `<,>`(0.33e-1, 0.33e-1, 1), `<,>`(.29, 1, 1), `<,>`(1, .29, 1), `<,>`(1, 1, .29)]), b = [`<,>`(0, 0, 0), `<,>`(1, 0.33e-1, 0.33e-1), `<,>`(0.33e-1, 1, 0.33e-1), `<,>`(0.33e-1, 0.33e-1, 1), `<,>`(.29, 1, 1), `<,>`(1, .29, 1), `<,>`(1, 1, .29)]);
0, 1.001088408, 1.001088408, 1.001088408, 1.443641230, 1.443641230, 1.443641230, 1.001088408, 0., 1.367544515, 1.367544515, 1.540869235, 1.000568838, 1.000568838, 1.001088408, 1.367544515, 0., 1.367544515, 1.000568838, 1.540869235, 1.000568838, 1.001088408, 1.367544515, 1.367544515, 0., 1.000568838, 1.000568838, 1.540869235, 1.443641230, 1.540869235, 1.000568838, 1.000568838, 0., 1.004091629, 1.004091629, 1.443641230, 1.000568838, 1.540869235, 1.000568838, 1.004091629, 0., 1.004091629, 1.443641230, 1.000568838, 1.000568838, 1.540869235, 1.004091629, 1.004091629, 0.

[g______d]

Про 8 шаров: внизу страницы 267 по ссылке и далее

https://www.cambridge.org/core/services ... a_cube.pdf

(там рассматривается случай $\ge 1$, но доказывается его единственность для 8 шаров, из чего следует, что $>1$ для 8 шаров не бывает).

Upd: у venco такое же рассуждение, как там.

-- Чт, 09 май 2019 10:58:26 --

Другие ссылки можно найти, например, здесь (последний абзац).

http://mathworld.wolfram.com/SpherePacking.html

[Markiyan Hirnyk]

g______d Как было указано выше, задача отличается от задачи об укладке шаров: радиусы могут быть разными, важно, что расстояния между центрами шаров строго больше единицы. Пожалуйста, читайте сообщения потока. Все же спасибо за интерес и участие в обсуждении.

[g______d]

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

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

А что мешает все радиусы считать равными $1/2$? В изначальной задаче вообще никаких шаров нет, есть только точки. По-моему, задача равносильна задаче упаковки не-касающихся шаров диаметра $1$ в куб со стороной $2$.

update: эта равносильность отмечалась и в предыдущих постах (например, feedinglight)

-- Чт, 09 май 2019 12:08:19 --

Ну то есть пусть $n$ точек удовлетворяют условию задачи. Тогда замкнутые шары радиуса $1/2$ с центрами в этих точках не пересекаются и находятся в кубе со стороной $2$ с тем же центром, что и исходный куб.

В другую стороны: пусть есть $n$ непересекающихся замкнутых шаров радиуса $1/2$ в кубе со стороной $2$. Тогда центр каждого из шаров отдалён не менее чем на $1/2$ от каждой грани куба. Следовательно, все центры находятся в кубе со стороной $1$ (с тем же центром, что и куб со стороной $2$) и удовлетворяют условию задачи.

[venco]

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

venco Мне непонятно Ваше предложение. Первое неясное место

Цитата:

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

Какое ограничение? Что значит усилить? Пожалуйста, изложите его подробнее.

У меня нет русской клавиатуры, тяжело набирать.
Пусть возможное положение точек ограничено при-угловыми кубиками со стороной $b$ (на первой итерации - $1\over 2$). Посмотрим, где может находиться одна точка, чтобы точке у соседней вершины осталось хоть какое-то место:
$(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2>1$
$(x_1-x_2)^2>1-(y_1-y_2)^2-(z_1-z_2)^2>1-b^2-b^2$
$x_1<x_2-\sqrt{1-2b^2}<1-\sqrt{1-2b^2}$
Получится, что выбранная точка должна быть ещё и в угловом кубе со стороной $b_1=1-\sqrt{1-2b^2}\approx 0.29$
Продолжая, получим ещё более строгое ограничение $b_2=1-\sqrt{1-2b_1^2}\approx 0.09$
И так далее до нуля.

[Markiyan Hirnyk]

g______d Пожалуйста, обоснуйте Ваши утверждения. Из того, что куда-то невозможно вложить четыре шара радиуса $1/2$ не следует, что там нет четырех точек, с попарными расстояниями строго больше единицы. Простой пример - крестообразное множество $\{(x,y,z): |x| \le 1/8, -2\le y,y \le 2\, -1/4 \le z, z \le 1/4\}\cup \{(x,y,z): |y|\le 1/8, -2\le x,x \le 2\, -1/4 \le z, z \le 1/4\}$.

-- 09.05.2019, 21:25 --

venco

Цитата:

Пусть возможное положение точек ограничено при-угловыми кубиками со стороной $b$ (

Извините, не понимаю. Что такое "приугловой кубик"? Сколько их? А если это не так?

-- 09.05.2019, 21:25 --

venco

Цитата:

Пусть возможное положение точек ограничено при-угловыми кубиками со стороной $b$ (

Извините, не понимаю. Что такое "приугловой кубик"? Сколько их? А если это не так?

-- 09.05.2019, 21:29 --

g______d

Цитата:

Ну то есть пусть $n$ точек удовлетворяют условию задачи. Тогда замкнутые шары радиуса $1/2$ с центрами в этих точках не пересекаются и находятся в кубе со стороной $2$ с тем же центром, что и исходный куб.

В другую стороны: пусть есть $n$ непересекающихся замкнутых шаров радиуса $1/2$ в кубе со стороной $2$. Тогда центр каждого из шаров отдалён не менее чем на $1/2$ от каждой грани куба. Следовательно, все центры находятся в кубе со стороной $1$ (с тем же центром, что и куб со стороной $2$) и удовлетворяют условию задачи.

Понял и согласен. Спасибо. Извините, но я человек дотошный.

[svv]

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

Что такое "приугловой кубик"?

Приугловой кубик — это куб, являющийся собственным подмножеством единичного куба и имеющий с ним общую вершину.
Рассматриваются только приугловые кубики со стороной, не превосходящей $\frac 1 2$.

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

Сколько их?

Приугловых кубиков бесконечно много. Но различных приугловых кубиков с заданной стороной $b \in (0,1)$ всего $8$, по числу вершин единичного куба.

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

А если это не так?

Пусть утверждение $P(b)$ означает: каждому из 8 приугловых кубиков со стороной $b$ принадлежит ровно одна из восьми точек, которые надо разместить. Схема доказательства следующая:
1) Мы доказываем, что истинно $P(\frac 1 2)$.
2) Мы доказываем, что из $P(b)$, где $b\in(0,\frac 1 2]$, следует $P(f(b))$, где $f(b)$ — некоторая функция $b$, такая, что $0<f(b)<b$.
3) Мы доказываем, что последовательность $b, f(b), f(f(b)),...$ стремится к нулю.
Ваш вопрос "а если это не так?" относился к этапу 2), напоминающему шаг индукции.

[Markiyan Hirnyk]

svv Спасибо. Мне непонятно неравенство $(x_1-x_2)^2>1-(y_1-y_2)^2-(z_1-z_2)^2>1-b^2-b^2$ и последующее.

[svv]

Пусть $P(b)$ выполнено. Возьмём две смежных вершины единичного куба, для определённости $(0,0,0)$ и $(0,0,1)$, и рассмотрим соответствующие им приугловые кубики со стороной $b$.
Пусть координаты точек (тех, что надо разместить) в этих двух приугловых кубиках равны соответственно $(x_1, y_1, z_1)$ и $(x_2, y_2, z_2)$. Утверждение $P(b)$ означает, в частности:
$\bullet$ $0\leqslant x_1\leqslant b;\;\; 0\leqslant x_2\leqslant b$, и отсюда $(x_2-x_1)^2 \leqslant b^2$;
$\bullet$ $0\leqslant y_1\leqslant b;\;\; 0\leqslant y_2\leqslant b$, и отсюда $(y_2-y_1)^2 \leqslant b^2$;
$\bullet$ $$0\leqslant z_1\leqslant b;\;\;1-b\leqslant z_2 \leqslant 1$

Сложим неравенства:
$(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2>1$ (по предположению, точки размещены с соблюдением условия)
$b^2\geqslant(x_2-x_1)^2$
$b^2\geqslant(y_2-y_1)^2$
Получим:
$(z_2-z_1)^2>1-2b^2$
Так как $z_2\geqslant z_1$, то
$z_2-z_1>\sqrt{1-2b^2}$
Сложим последнее неравенство с
$1\geqslant z_2$
Получим
$z_1< 1-\sqrt{1-2b^2}$

Повторим то же рассуждение для приугловых кубиков при вершинах $(0,0,0)$ и $(1,0,0)$. Получим аналогично $x_1< 1-\sqrt{1-2b^2}$.
Повторим то же рассуждение для приугловых кубиков при вершинах $(0,0,0)$ и $(0,1,0)$. Получим аналогично $y_1< 1-\sqrt{1-2b^2}$.
Итак, $(x_1,y_1,z_1)$ принадлежит приугловому кубику при вершине $(0,0,0)$ со стороной $1-\sqrt{1-2b^2}$.

Повторяя то же рассуждение для других пар приугловых кубиков (соответствующих другим смежным вершинам), докажем $P(f(b))$, где $f(b)=1-\sqrt{1-2b^2}$.

[Markiyan Hirnyk]

svv
Спасибо, понял. Теперь для аналогичной оценки $x_1$ надо рассмотреть точки в кубиках при $(0,0,0)$ и $(1,0,0)$ и затем так же доказать для $y_1$. Остроумное и неочевидное (хотя, возможно, известное) рассуждение. А как с большими размерностями, скажем, 4?