2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Попарные суммы
Сообщение09.03.2016, 01:58 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение09.03.2016, 08:30 
Заслуженный участник
Аватара пользователя


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

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

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

Вот пока всё :oops:

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение09.03.2016, 10:03 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
$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$, ну и дальше всё совсем просто.

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение09.03.2016, 11:20 
Заслуженный участник


18/01/12
933
Если числа не восстанавливаются при некотором $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).$

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение09.03.2016, 12:07 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
При попытке построить два различных набора из 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 --

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

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение11.03.2016, 16:48 


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

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение13.03.2016, 14:49 
Заслуженный участник


10/01/16
2315
Sirion в сообщении #1105794 писал(а):
Хочется как-то приспособить сюда симметрические многочлены.

:D

(Оффтоп)

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

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение16.03.2016, 16:36 


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

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение16.03.2016, 18:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение27.03.2016, 21:21 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение28.03.2016, 17:37 
Заслуженный участник


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

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


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

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

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

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение30.03.2016, 20:41 
Аватара пользователя


13/10/07
755
Роман/София, България

(Оффтоп)

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 :)

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение30.03.2016, 21:54 
Аватара пользователя


13/10/07
755
Роман/София, България
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.

 Профиль  
                  
 
 Re: Попарные суммы
Сообщение30.03.2016, 22:15 
Заслуженный участник


10/01/16
2315
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$

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

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



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

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


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

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