2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Сколько отдаленных точек можно поместить в единичный куб?
Сообщение09.05.2019, 13:42 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Markiyan Hirnyk в сообщении #1391956 писал(а):
Уже при $n=5$ ответ $2^n-1$ неверен: можно добавить центр пятимерного куби
К чему добавить? :) Впрочем, согласен, после такого аргумента интуитивно кажется, что количество точек должно расти быстрее, чем число вершин.

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


20/08/14
11066
Россия, Москва
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 для увеличения расстояний по граням.

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


09/09/14
6328
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. Об этом уже говорили выше.

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


20/08/14
11066
Россия, Москва
Да, что-то я стормозил, с чего-то взял что при повороте квадрата по рёбрам он сохраняет расстояния между точками ... :facepalm:

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


04/05/09
4582
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$.

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


11/07/16
801
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.

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


08/11/11
5940
Про 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

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


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

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


08/11/11
5940
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$) и удовлетворяют условию задачи.

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


04/05/09
4582
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$
И так далее до нуля.

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


11/07/16
801
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$) и удовлетворяют условию задачи.

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

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


23/07/08
10626
Crna Gora
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), напоминающему шаг индукции.

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


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

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


23/07/08
10626
Crna Gora
Пусть $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}$.

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


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

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

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



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

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


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

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