Задача

Артёмка, 599 просмотров

Дано n-мерное пространство. Какое максимальное количество точек можно расставить в этом пространстве так, чтобы для каждой точки расстояние от нее до начала координат было не больше, чем расстояние от этой точки до любой другой из расставленных точек? Интересны даже частные случаи для разных n > 1.

Примечание:
Отрадофф,
сочувствую школьникам и их поколению.

Примечание:
> Вы не первый задаетесь этим вопросом :)
Да, следовало этого ожидать. И так как в ближайшее время общего решения или хотя бы намека на таковое не предвидится, упростим(?) задачу. Пусть расстояние между точками считается не по Евклиду, а как сумма модулей разностей соответствующих координат. Если и такая задача не решается просто, тогда ну ее на фиг.

Примечание:
zexo,
ого, как-то сомнительно, хочу доказательство.

Примечание:
> Оптимальное при n=3 будет иметь 22 точки и получаться отражениями следующего заполнения одной стороны октаэдра ...
У меня туго с пространственным воображением (особенно с такой метрикой), поэтому проверю такую расстановку (а заодно и посчитаю площади для 24 точек), когда будет время спокойно посидеть (то есть хрен знает когда).
Для пространств большей мерности я думал, что задачу можно будет свести к задаче (или задачам) линейного программирования, но, видимо, это тоже будет непросто, так что не судьба.
Ладно, посмотрим, кто что еще сможет предложить.

> Еще можно вместо суммы модулей координат смотреть максимум модулей координат.
Тоже думал об этом. Оставлю на потом.

Примечание:
Андрей Тимофеев,
в четырехмерном пространстве таких точек только 24. Стоит прочитать ответы людей, отвечавших перед Вами.
Ну и ответы сами по себе без доказательства не так уж и ценны.

Ответы:

Rentier

n = 1 => две точки (по разные стороны от начала оси)
n = 2 => шесть точек, равномерно распределенных на окружности с центром в начале координат. Расстояние между двумя ближайшими точками равно расстоянию до начала координат.
n = 3 => двенадцать, кажется. Вершины икосаэдра. http://www.pravmn.narod.ru/icos.htm

alarmeria

Вы не первый задаетесь этим вопросом :)

перезагрузка

Ну если верить Rentier, то зависимость напоминает n*(n+1)
1 - 2
2 - 6
3 - 12
4 - 20 ..?
5 - 30 ..?
......

alarmeria

лучше, конечно, читать английский вариант: http://en.wikipedia.org/wiki/Kissing_number_problem

Evgeny Adishchev

Для задачи из дополнения №2, похоже, ответом будут вершины, середины ребер и сторон всех порядков в правильном октаэдре (фигуры, заданной уравнением ||x||=1)

alarmeria

Нет. Уже при n=3 середины сторон законфликтуют с серединами ребер.
Но и вершины+середины ребер (6+12=18) -- не оптимальное заполнение уже при n=3.
Оптимальное при n=3 будет иметь 22 точки и получаться отражениями следующего заполнения одной стороны октаэдра:

alarmeria

Причем в указанном ответе для n=3 доказать нвозможность 24 точек легко, считая площади 1/2-окрестностей этих точек, а вот невозможность 23 доказывать так же фигово, как и невозможность 13 в классической задаче (из-за которой еще Ньютон с Грегори препирался).

alarmeria

Нет. Для n=4 ответа здесь уже не появится. (По крайней мере, от меня.)

alarmeria

Упс... писал второпях и написал неправду. То, что выше нарисовано для n=3, подойдет только если манхэттенское расстояние между точками считать на сфере (то есть на поверхности октаэдра), а не в объемлющем трехмерном пространстве.

Я по долгу службы держал в руках полную версию, поверьте на слово, МОЖНО и не только это...

В случае с одномерным пространством (прямая)
данному условию удовлетворяют 2 точки с условием что одна имеет координаты (-∞...0), а вторая (0...+∞)

15 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.