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

[ins-]

I tried the problem, but cannot find the relation between the power sums and the partitions. If it is a subject of some advanced math theory I have no chances (I have no dedicated math education - math is a hobby for me). In case there is some trick without advanced theory - it is not obvious for me. It seems I'm not the only one that cannot solve the problem. If it is not solved for some time - you might post a solution to it. It might be a good occasion for some of the users to see something interesting.

[Iam]

Например,
$ \mathrm a=(a_i) $,
$a(x)=\sum_{i=0}^n x^{a_i}$, где: $a_i $– $i$-е число в наборе, -- производящая функция набора ($n=a(1) $).
$P_a(x)=(a^2(x)-a(x^2))/2$ -- производящая функция набора сумм пар чисел из $\mathrm a$.
Пусть $P_a(x)= P_b(x) $, тогда
$a^2(x)-b^2(x)=a(x^2)-b(x^2) \Rightarrow (x-x_1) \dots (x-x_k) (x-x’_1) \dots (x-x’_k)= (x-\sqrt{x_1})(x+\sqrt{x_1})\dots (x-\sqrt{x_k}) (x+\sqrt{x_k}), $
где: $x_i, x’_i $– соответственно корни многочленов $a(x)-b(x)$ и $a(x)+b(x) $.
Положив для примера $x_i=1, i=1,\dots, k$, получим
$a(x)=[(x+1)^k+(x-1)^k]/2, b(x)=[(x+1)^k-(x-1)^k]/2$.
При этом $n=a(1)=b(1)=2^n$. Решение для таких n ранее получено by hippie.

[DeBill]

Iam
Замечательная идея!
Но что же Вы не закончили?
Пусть $\varphi (x) = a(x) - b(x), \psi (x) =a(x) + b(x) $,
тогда $\varphi (x^2)$ делится на $\varphi (x)$, причем частное и есть $\psi (x)$. Но тогда: если $x$ - корень полинома $\varphi$, то и $x^2$ - тоже корень. Значит, все корни $\varphi$ распадаются на цепочки$\varepsilon _1, \varepsilon _2, ... , \varepsilon _m,$, где каждый следующий - квадрат предыдущего, а квадрат последнего равен первому. Многочлен $\alpha (x)$ с такими корнями дает частное
$\frac{\alpha (x^2)}{\alpha (x)}$, равное $\beta (x) = (x+\varepsilon _1)\cdot (x+ \varepsilon _2) \cdot ...\cdot (x+ \varepsilon _m)$. Заметим, что $\alpha (1) \ne 0,$ (кроме как в тривиальном случае $\alpha (x) =x-1$), а $\beta (1) = (1+\varepsilon _1)\cdot (1+ \varepsilon _2) \cdot ...\cdot (1+ \varepsilon _m) =1 $ (домножим и разделим на $1 - \varepsilon _1$ - все сократится) (а в тривиальном случае $\beta (x) = x +1$, так что $\beta (1) = 2$). Осталось вспомнить, что $a(1) = b(1) = n,$ так что $\varphi (1) =0, \psi (1) = 2n$. Значит, $\varphi$ есть произведение многочленов типа $\alpha$, описанных выше (причем тривиальный обязательно присутствует - и, мобыть, не один раз). Значит, $2n = \psi (1)$ равно произведению кучи единичек и нескольких двоек! Уфф...
Но это еще не конец . Потому как решение проведено для наборов из НАТУРАЛЬНЫХ чисел. Но, дальше, как обычно:
Для целых: сдвигом превратим числа набора в натуральные
Для рациональных: домножением на общий знаменатель сделаем их целыми
Для вещественных: будем считать $\mathbb{R}$ линейным пространством над полем $\mathbb{Q}$. Рассмотрим линейную оболочку чисел из обеих (о?) наборов, и выберем в этом подпространстве базис. Разложим числа наборов по этому базису. Коль для наборов была неединственность, то и для каких-то координат - тоже. Ан оне вже рациональны... Большая победа!
Спасибо, Iam, решение с Вашей идеей - гораздо лучше того, что я умел - чисто технического, нудного и противного

[Iam]

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

[worm2]

DeBill, присоединяюсь к благодарности за красивую задачу и доказательство.
Iam, Ваша идея гениальна.
Кажется, можно ещё упростить.
$\psi(x)=\frac{\varphi(x^2)}{\varphi(x)}$. Пусть $\varphi(x)=(x-1)^pQ(x)$, где $Q(x)$ не делится на $x-1$. Тогда $\psi(x)=(x+1)^p\frac{Q(x^2)}{Q(x)}$, причём $Q(1)\ne 0$ и $2n=\psi(1)=2^p$.

[DeBill]

worm2
Вах!! Стало совсем коротко!

[Alexander Evnin]

Решение данной задачи имеется в статье
К. Кохась. Наборы кратных сумм // Задачи Санкт-Петербургской олимпиады школьников по математике 2003 г.

[grizzly]

А здесь -- захватывающий исторический обзор по теме набора сумм.