Попарные суммы

[DeBill]

Не даны $n$ чисел. Но зато даны все их $\frac{n\cdot (n-1)}{2}$ попарные суммы.
Для каких $n$ по набору этих попарных сумм набор исходных чисел восстанавливаются однозначно?
(Среди чисел могут быть одинаковые. Среди сумм могут быть одинаковые. Числа - любые.)

[gris]

$n=2.$ По сумме двух чисел восстановить их невозможно.

$n=3.$ Такая задача обычно предлагается младшим школьникам, не знакомым ещё с методами Гаусса. Самые смышлёные складывают все три суммы и делят на два. Потом из результата вычитают попарности. Числа восстанавливаются. Три неизвестных, три линейных уравнения. Однозначно.

$n>3.$ А вот тут уже начинается. Указано ли для попарных сумм для каких именно пар (Предположим, что изначально все числа как-то выстроены) они посчитаны?
Если указано, то одно решение получается просто. Вопрос об однозначности.
А если не указано, тогда надо перемешивать сами пары. Будет $n^2!$ систем. Ну меньше, если учитывать аддитивность. Среди это обилия систем одна будет отвечать истинному положению дел и иметь решение. А другие?

Вот пока всё

[worm2]

$n=4$ — восстановить в общем случае невозможно. Например, $\{2, 6, 8, 10\}$ и $\{3, 5, 7, 11\}$ дают одинаковый набор сумм $\{8, 10, 12, 14, 16, 18\}$.

$n=5$ восстанавливается однозначно. Сумма всех сумм даёт учетверённую сумму исходных чисел $4S$, откуда находим $S$. Отсортируем по возрастанию как неизвестные числа $x_1$, $x_2$, ..., $x_5$, так и известные суммы $s_1$, ..., $s_{10}$.
Очевидно, $s_1=x_1+x_2$, $s_{10}=x_4+x_5$, откуда $x_3=S-s_1-s_{10}$. Далее, $s_2=x_1+x_3$, откуда находим $x_1$, ну и дальше всё совсем просто.

[hippie]

Если числа не восстанавливаются при некотором $n,$ то они не восстанавливаются и при $2n.$

В частности, если $n$ — степень двойки, то в общем случае числа не восстанавливаются.
Например, при $n=8,$ наборы $(-1,\ -1,\ -1,\ 0,\ 1,\ 2,\ 2,\ 2)$ и $(-2,\ 0,\ 0,\ 0,\ 1,\ 1,\ 1,\ 3)$ дают одинаковые наборы попарных сумм: $(-2,\ -2,\ -2,\ -1,\ -1,\ -1,\ 0,\ 0,\ 0,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 2,\ 2,\ 2,\ 3,\ 3,\ 3,\ 4,\ 4,\ 4).$

[worm2]

При попытке построить два различных набора из 6 чисел, дающих одинаковый набор сумм, кажется, натолкнулся на противоречие. Пусть $\mathbf{x}$ и $\mathbf{x'}$ — разные наборы, дающие один набор сумм $\mathbf{s}$. Как и в предыдущем сообщении, я всё сортирую по возрастанию, а сумму $\mathbf{s}$ обозначаю через $S$. Из незыблемости соотношений
$s_1=x_1+x_2$, $s_2=x_1+x_3$, $s_{15}=x_5+x_6$, $s_{14}=x_4+x_6$ следует вот что:
1) Если $x'_1=x_1$, то $x'_2=x_2$, $x'_3=x_3$. Если затем положить $x'_5\ne x_5$, то это приведёт к изменению суммы $S$, являющейся инвариантом. Равенство же $x'_5=x_5$ влечёт совпадение всего набора. Значит, $x'_1\ne x_1$.
2) Пусть $e=x'_1-x_1>0$. Тогда $x'_2=x_2-e$, $x'_3=x_3-e$. Опять же из инвариантности $S$ с неизбежностью следует: $x'_4=x_4+e$, $x'_5=x_5+e$, $x'_6=x_6-e$.
3) Из предыдущего пункта видно, что в наборе остаются неизменными следующие суммы: $x_1+x_2$, $x_1+x_3$, $x_1+x_6$, $x_2+x_4$, $x_2+x_5$, $x_3+x_4$, $x_3+x_5$, $x_4+x_6$, $x_5+x_6$. Меняются же:
$x'_1+x'_4=x_1+x_4+2e$,
$x'_2+x'_3=x_2+x_3-2e$,
$x'_1+x'_5=x_1+x_5+2e$,
$x'_2+x'_6=x_2+x_6-2e$,
$x'_3+x'_6=x_3+x_6-2e$,
$x'_4+x'_5=x_4+x_5+2e$.
Эти 6 сумм нужно сопоставить между собой, в том смысле, что каждая сумма в левой части, если убрать штрихи, равна какой-то другой сумме в правой части.
4) Снова вспоминаем про упорядочение по возрастанию. Получается, что $s_3$ равно одной из сумм: $x_1+x_4$, либо $x_2+x_3$. Отсюда следует, что либо первая, либо вторая сумма из шести выписанных равна $s_3$. Что даёт нам либо $x_1+x_4=x_2+x_3-2e$, либо $x_2+x_3=x_1+x_4+2e$, но оба равенства эквивалентны, а значит оба и верны. Аналогично: $x_3+x_6=x_4+x_5+2e$, а значит, 3-я сумма сопоставляется с 4-й: $x_1+x_5=x_2+x_6-2e$.
5) Выписываем рядом три получившихся равенства и, вычитая одно из другого, получаем: $x_5-x_4=x_6-x_3$. Вспоминая о возрастании, заключаем, что (тут была ошибка, исправил) $x_3=x_4$, $x_5=x_6$. Аналогично, $x_1=x_2$. Но тогда изменённый набор не будет отсортирован по возрастанию. Противоречие.

Выходит, набор из $n=6$ чисел восстанавливается однозначно.

-- Ср мар 09, 2016 14:25:23 --

Неточность в терминологии: где я пишу о "возрастании", имеется в виду "неубывание". Но исправлять не стал, т.к. как-то тяжеловесно звучит.

[Sirion]

Хочется как-то приспособить сюда симметрические многочлены. Хочется, но пока не получается.

[DeBill]

Sirion в сообщении #1105794 писал(а):

Хочется как-то приспособить сюда симметрические многочлены.

(Оффтоп)

Меня разоблачили...
Задачка постулирована (?) специально для нашего болгарского друга
ins- - чтобы он проникся идеей, и технику освоил

[Sirion]

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

[provincialka]

О! Как раз на днях давала эту задачку студентам. В теме о "порядках" и их диаграммах Хассе. Но только для $n=4$ и $n=5$

[maxal]

Задача похожа на Turnpike problem, где даны не попарные суммы, а попарные разности.

[DeBill]

maxal
С разностями, видимо, все сложнее. А с суммами - ответ уже, фактически, был дан в посте hippie, а идея решения - у Sirion: надо состряпать многочлен, корни которого есть попарные суммы корней другого многочлена. Тогда получается задача: по первому восстановить другой....

[worm2]

Ну дык идею написать-то легко, а уже для $N=4$ зубодробительная задача получается, а нужно её ещё обобщить на произвольное $N$.
Как-то тяжеловато плыть в соляной кислоте с отрубленными ногами
Если только кто-то глубоко изучал тему симметрических многочленов и знает хитрые тропы...

-- Ср мар 30, 2016 12:29:11 --

Также, вероятно, тут бы помогло знание теории Галуа, но это не про меня, например.

[ins-]

(Оффтоп)

DeBill, thank you for remembering me. I understood the basic idea for symmetric polynomials, but was travelling yesterday for some health checks and met some friends. It is the reason for seeing the problem too late. The last problem I posted - for expression's value also can be solved with using polynomials. Not symmetric, but polynomials. If you are interested you can see it http://artofproblemsolving.com/communit ... 46p6091691 It is a link to another site, because I cannot directly upload a picture. The problem posted by you is interesting. Are you the creator? I suppose you think my level is higher than it is in the reality :)

[ins-]

I have a question: "what does 'любые' mean?" Any real or any integer numbers? I found something interesting https://en.wikipedia.org/wiki/Partition_(number_theory) the part "Generation" might deal with polynomials.

[DeBill]

ins- в сообщении #1110603 писал(а):

"what does 'любые' means?" Any real or any integer numbers?

Any real.

ins- в сообщении #1110579 писал(а):

Are you the creator?

Not. It seems, this problem from IMO (?). I discussed it with my pupils some years ago; as I remember, we used not standard symmetrical polynomials, but sums $\sigma_1 =x_1 +...+ x_n, \sigma _2 = x_1^2 + ... + x_n^2, ...,\sigma _n = x_1^n + ...+ x_n^n$