Симметричные множества точек

[вздымщик Цыпа]

stef в сообщении #893699 писал(а):

Цитата:

Для плокости все точки должны лежать на окружности? И подойдут правильные многоугольники (их вершины), а так же многоугольники с чередованием сторон, то есть как бы удвоенный с небольшим поворотом многоугольник.

Да, всё верно. Ждём доказательства)

Ну есть наметки доказательства для плоскости, только даже они долгие и нудные.

Возможных расстояний конечное число и поэтому среди них можно выбрать максимальное.
Точек, отстоящих от данной на это максимальное расстояние, не больше двух.
Если их хотя бы три, то выбрав из них среднюю (углы при данной точке
там должны быть все острые и понятно, которая средняя) и рассмотрев еще две
максимально отстоящие от нее, убеждаемся, что всяко появляются расстояния больше
максимального. Таким образом, либо все точки распадаются на пары максимально
отстоящих друг от друга, либо выстраиваются в замкнутые цепочки с максимальным
попарным расстоянием. Если есть две пары точек таких, что расстояния внутри
пар максимальные, то отрезки, соединяющие точки в парах, должны пересекаться,
иначе будут расстояния больше максимального.

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

Точки через одну в этой цепочке будем называть соседними.
Среди соседних точек есть две, расстояние между которыми минимально. Значит и для
других должны быть точки на таком же расстоянии. Кандидаты на них могут быть только
среди соседей, иначе возникнут расстояния меньше минимального.
Размечая пары точек на этом расстоянии из-за нечетности их количества приходим к тому,
что у одной из точек оба соседа на минимальном расстоянии,
а значит и у всех должно быть так же.

Таким образом, каждая точка является вершиной трех одинаковых равнобедренных
треугольников с двумя сторонами максимальной длины и одной минимальной.
Эти треугольники расположены так, что на все три описанная окружность одна.
Ну а значит и на все остальные тоже она же и звезда не помятая.

Случай, когда точки разбиты на пары, максимально отстоящие, слегка сложнее, но тоже
не должен представлять особых трудностей, кроме той, что шлепать по клавиатуре
уже поднадоело.

Вообще, сомневаюсь, что можно тут состряпать что-то более изящное, поскольку
всяко надо плясать от максимального расстояния. Счетных наборов точек с похожими
свойствами полно разных. От вершин всяческих замощений, до точек с рациональными
координатами, а пожалуй единственное, что существенно отличает конечные наборы чисел
от бесконечных — это наличие максимального и минимального.

[Toucan]

stef в сообщении #893699 писал(а):

Цитата:

И равенство множеств понимается именно с точностью до кратности элементов?

stef, замечание за неправильное цитирование: в заголовке цитаты отсутствует ссылка на цитируемое сообщение.

Для того чтобы процитировать фрагмент сообщения, выделите его мышкой и нажмите кнопку "Вставка" в цитируемом сообщении.

[stef]

вздымщик Цыпа в сообщении #894684 писал(а):

Ну есть наметки доказательства для плоскости, только даже они долгие и нудные.

Да, это серьёзная работа. В вашем втором случае нужно обосновать принципиально новый нюанс -- все отрезки пересекаются в одной точке. Но рассмотрением ещё какого-то третьего расстояния, наверное, можно и с этим справиться. А вот по поводу

вздымщик Цыпа в сообщении #894684 писал(а):

Вообще, сомневаюсь, что можно тут состряпать что-то более изящное

я поспорю. На то задача и олимпиадная . Поскольку решение вроде бы верно, завтра выложу идею, заметно ускоряющую ход доказательства.

[вздымщик Цыпа]

stef в сообщении #894731 писал(а):

В вашем втором случае нужно обосновать принципиально новый нюанс -- все отрезки пересекаются в одной точке.

Необязательно. При нечетном количестве пар так может не быть.

stef в сообщении #894731 писал(а):

я поспорю.

Ну да, доказательство того, что все точки на одной сфере, оказалось вообще устным. Радиус такой сферы $R = \dfrac 1 n \sqrt{\sum_{j>i} \rho(A_i,A_j)^2}$ при любой размерности пространства. Т.е. иногда бывает и побольше, но такая точно есть.

Другое дело, что начальной задачи классификации всех м-симметричных наборов точек это не решает. Мало ли что можно на сферу накидать. Во всяком случае, есть еще кое-то, что в теме не перечислено. Как установить полный список и доказать, что нет ничего сверх него, не очень понятно.

К тому же, нет уверенности, что среди всех

$$\{\sigma | \forall j \ \rho(A_i, A_j) = \rho(A_k, A_{\sigma(j)})\} $$

обязательно найдется такая, что

$$\forall j, l\ \rho(A_j, A_l) = \rho(A_{\sigma(j)}, A_{\sigma(l)})$$

. По всем примерам, это вроде как так, но доказать это не видно как. А без этого даже свести разговор к движениям и их транзитивности не выйдет.

[Aritaborian]

stef в сообщении #894731 писал(а):

завтра выложу идею, заметно ускоряющую ход доказательства.

Неделя уж прошла ;-)

[вздымщик Цыпа]

Что-то ТС куда-то завеялся. Видимо, на его помощь расчитывать не приходится.

Кстати, вот это:

вздымщик Цыпа в сообщении #896634 писал(а):

среди всех

$$\{\sigma | \forall j \ \rho(A_i, A_j) = \rho(A_k, A_{\sigma(j)})\} $$

обязательно найдется такая, что

$$\forall j, l\ \rho(A_j, A_l) = \rho(A_{\sigma(j)}, A_{\sigma(l)})$$

оказалось неверным.

Пример из восьми точек у меня есть. Очевидно, он без труда размещается в $\mathbb R^7$.
Возможно, его удастся запихать в пространство и с более низкой рзмерностью, только возиться надо.

Так что, перейти к чему-то такому, вроде «берем всякие конечные подгруппы $O(m)$ и орбитами прозвольных точек $\mathbb R^m$ исчерпываются все возможные варианты», в общем случае не выйдет.

[вздымщик Цыпа]

Задачкой вроде бы заинтересовались, а потом интерес угас. Я тоже о ней позабыл, но вот при уборке наткнулся на бумажку с рисунком

вздымщик Цыпа в сообщении #897353 писал(а):

Пример из восьми точек у меня есть. Очевидно, он без труда размещается в $\mathbb R^7$.
Возможно, его удастся запихать в пространство и с более низкой рзмерностью, только возиться надо.

Оказалось, примерчик легко вкладывается в $\mathbb R^3$.

$$ \begin{aligned} A_1 &= (3, 10, 4)\\ A_2 &= (10, 5, 0)\\ A_3 &= (10, - 5, 0)\\ A_4 &= (3, - 10, 4)\\ A_5 &= (- 3, - 10, - 4)\\ A_6 &= (- 10, - 5, 0)\\ A_7 &= (- 10, 5, 0)\\ A_8 &= (- 3, 10, - 4)\\ \end{aligned} $$

Условиям задачи он удовлетворяет. Для проверки можно воспользоваться программкой (maxima):

(Оффтоп)

x:2; y:1; p:3; q:4; pq:5;

r1 : [ p*y,  pq*x, q*y];
r2 : [pq*x,  pq*y,   0];
r3 : [pq*x, -pq*y,   0];
r4 : [ p*y, -pq*x, q*y];

r5 : -r1; r6 : -r2; r7 : -r3; r8 : -r4;

d(x,y) := (x[1] - y[1])^2 + (x[2] - y[2])^2 + (x[3] - y[3])^2$

check(x,a,b,c,d) := is((x - a)^2 + (x - b)^2 + (x - c)^2 + (x - d)^2 = 0)$

check(90,  d(r1,r2), d(r3,r4), d(r5,r6), d(r7,r8));
check(100, d(r1,r8), d(r2,r3), d(r4,r5), d(r6,r7));
check(210, d(r1,r7), d(r2,r8), d(r3,r5), d(r4,r6));
check(290, d(r1,r3), d(r2,r4), d(r5,r7), d(r6,r8));
check(400, d(r1,r4), d(r2,r7), d(r3,r6), d(r5,r8));
check(410, d(r1,r6), d(r2,r5), d(r3,r8), d(r4,r7));
check(500, d(r1,r5), d(r2,r6), d(r3,r7), d(r4,r8));

Очевидно, не существует движения, переводящего $A_2$ в $A_4$, т.к. будь оно, непременно должно было бы перевести $A_1$ в $A_3$, а $A_3$ в $A_5$, но $\rho(A_1, A_3) \ne \rho(A_3, A_5)$.

Если никому не интересно, то про подробности, как это было получено (ну не угадал же в самом деле), и про примерчик из семи точек с еще более бедной группой движений ничего писать не буду.

[Aritaborian]

Интересно.

[patzer2097]

вздымщик Цыпа, а почему в условиях задачи

вздымщик Цыпа в сообщении #896634 писал(а):

все точки на одной сфере,

не напишете?

[вздымщик Цыпа]

patzer2097 в сообщении #907494 писал(а):

вздымщик Цыпа, а почему в условиях задачи

вздымщик Цыпа в сообщении #896634 писал(а):

все точки на одной сфере,

не напишете?

Пусть $r_i = A_i - \dfrac 1 n \sum\limits_j A_j$.

$\sum\limits_i r_i = 0$

$S_i &= \sum\limits_j |A_i - A_j|^2 =\sum\limits_j |r_i - r_j|^2 = n r_i^2 - 2\sum\limits_j(r_i, r_j) + \sum\limits_j r_j^2 = $
$=n r_i^2 - 2(r_i, \sum\limits_j r_j) + \sum\limits_j r_j^2 = n r_i^2 + \sum\limits_j r_j^2$

По условию задачи все $S_i$ равны.

$0 = S_i - S_k = n(r_i^2 - r_k^2)$

т.е. все $|r_i|$ равны. Пусть $|r_i| = R$.

$S_i = 2nR^2$

С висячим индексом выглядит некрасиво. Сложим их все.

$\sum\limits_i S_i = 2n^2R^2$

Выбросим нулевые слагаемые и половину оставшихся.

$\sum\limits_{i>j} |A_i - A_j|^2 = n^2R^2$

Aritaborian в сообщении #907486 писал(а):

Интересно.

Завтра.

[patzer2097]

вздымщик Цыпа, я пока не понимаю Вашего доказательства. Если $A_i$ - это точки, то как мы их складываем и вычитаем? А главное, не очень понятно, как Ваше утверждение про сферу следует из полученного Вами факта.

[вздымщик Цыпа]

patzer2097 в сообщении #907521 писал(а):

Если $A_i$ - это точки, то как мы их складываем и вычитаем?

Конечно же Вы правы. Определенная неряшливость тут есть. Но она поправима. Выбираем произвольную точку $O$ и устанавливаем соответствие $A \leftrightarrow \overrightarrow{OA}$ и тогда можно брать линейные комбинации точек, но только такие, сумма коэффициентов которых равна $1$, с получением точек. Также можно тогда точки вычитать с получением векторов. Для аккуратности тут надо было ввести промежуточные векторные переменные, но я поленился.

patzer2097 в сообщении #907521 писал(а):

А главное, не очень понятно, как Ваше утверждение про сферу следует из полученного Вами факта.

Все $|r_i|$ равны между собой, а это расстояния от $A_i$ до некоторой точки, которая фигурирует в определении $r_i$

————————————————

Aritaborian в сообщении #907486 писал(а):

Интересно.

Для начала перестанем думать о расстояниях и размерностях и начнем красить ребра полных графов во всякие цвета. Одинаково покрашенные ребра будут соответствовать одинаковым расстояниям между точками. Наборам точек из условия задачи будут соответствовать графы из вершин которых выходят равное количество ребер каждого цвета.

В свою очередь, каждому такому графу с $n$ вершинами будет соответствовать как минимум набор точек в ${\mathbb R}^{n-1}$. Ограничение на существование симплексов с заданым набором длин ребер — это всего лишь неравенства (неравенство треугольника и более сложные неравенства больших размерностей), и мы всегда можем выбрать эти расстояния такие, чтоб симплекс мало отличался от правильного и заведомо существовал.

Движению набора точек будет соответствовать автоморфизм графа, сохраняющий цвет ребер.

Попробуем ракрасить какой-нибудь граф так, чтоб у него были два таких цвета, что ребра покрашенные в них
были у вершин по одному и были две вершины такие, чтоб ребра этих цветов вели в пары точек, соединенных
ребрами разных цветов. Ну т.е., чтоб не существовало автоморфизма, переводящего одну вершину в другую.

Понятно, что так можно покрасить только граф с четным количеством вершин.
Простым перебором убеждаемся, что для двух-, четырех- и шестивершинных графов это невозможно.
Легко строим пример для восьми.

$$\begin{matrix} 0&a&c&f&g&e&d&b\\ a&0&b&c&e&g&f&d\\ c&b&0&a&d&f&g&e\\ f&c&a&0&b&d&e&g\\ g&e&d&b&0&a&c&f\\ e&g&f&d&a&0&b&c\\ d&f&g&e&c&b&0&a\\ b&d&e&g&f&c&a&0\\ \end{matrix}$$

$c(A_2, A_1) = a, c(A_2, A_3) = b, c(A_1, A_3) = c$
$c(A_4, A_3) = a, c(A_4, A_5) = b, c(A_3, A_5) = d$

А как эту штуку запихал в ${\mathbb R}^3$, напишу чуть позже.

[вздымщик Цыпа]

Теперь будем считать, что $a,\dots,f$ — это квадраты расстояний между точками.

Будем разглядывать матрицу Кэли — Менгера и ее миноры. Илюстрации в коде maxima.

M: matrix(
  [0, a, c, f, g, e, d, b, 1],
  [a, 0, b, c, e, g, f, d, 1],
  [c, b, 0, a, d, f, g, e, 1],
  [f, c, a, 0, b, d, e, g, 1],
  [g, e, d, b, 0, a, c, f, 1],
  [e, g, f, d, a, 0, b, c, 1],
  [d, f, g, e, c, b, 0, a, 1],
  [b, d, e, g, f, c, a, 0, 1],
  [1, 1, 1, 1, 1, 1, 1, 1, 0]
);

Чтобы конструкция была трехмерная, надо чтоб все пятиточечные поднаборы имели нулевой 4-объем.
Считаем пару из них.

/* 1 3 5 7 + 2 */
Y1: expand(determinant(submatrix(4, 6, 8, M, 4, 6, 8)));

/* 1 3 5 7 + 4 */
Y2: expand(determinant(submatrix(2, 6, 8, M, 2, 6, 8)));

Эти многочлены не факторизуются, но факторизуется их разность: $(d - c) (e - a) (f - b) (g - d - c)$.
(постоянный множитель игнорируем). Расстояния мы хотим сохранить различными. Значит необходимо $d = g - c$.

После подстановки факторизуется Y1: $c (f - e + b - a)^2 (g - c)$
Делаем подстановки $e = h - a$, $f = h - b$ и продолжаем:

/* 1 2 5 6 + 3 */
Y3: expand(determinant(submatrix(4, 7, 8, M, 4, 7, 8)));

/* 1 2 5 6 + 4 */
Y4: expand(determinant(submatrix(3, 7, 8, M, 3, 7, 8)));

factor(Y4 - Y3);

Получаем $(g - 2 c) (h - 2 a) (h - 2 b) (h - g)$. Следовательно, $h = g$. Итого у нас остается четыре
свободные переменные $a, b, c, g$. Причем $a+b+c+d+e+f+g = 4g$, т.е. $g$ — квадрат диаметра описанной сферы.

Значит, $A_iA_jA_{i+4}A_{j+4}$ — это все прямоугольники с одинаковыми диагоналями, проходящими через центр описанной сферы.

Дальнейшие манипуляции с минорами ничего интересного не дают. Заходим с другого конца:

Пусть $r_i$ — радиус-вектор $A_i$, проведенный из центра. $r_{i+4} = -r_i$.

$$ \begin{aligned} (r_1,r_2) &= (r_3,r_4) \\ (r_1,r_3) &= (r_2,r_4) \\ (r_1, r_2 - r_3) &= (r_3 - r_2, r_4) \\ (r_1 + r_4, r_2 - r_3) &= 0 \\ (r_4 - r_5, r_2 - r_3) &= 0 \\ \end{aligned} $$

Т.е. прямые $A_4A_5$ и $A_2A_3$ ортогональны и пространства для фантазии не осталось совсем.
Строим, проверяем, наслаждаемся