натуральные числа с равными суммами степеней.

[Руст]

1. Докажите, что для любого n, существует такие подмножества натуральных чисел А и В (все элементы различны и они не пересекаются), что при любом $0\le k\le n$ выполняются:

$$\sum_{a\in A}a^k=\sum_{b\in B}b^k, k\le n.$$

2. Каково минимальное количество элементов в A и B и каково минимальное возможное значение максимального элемента?
Ответ на последние вопросы я не знаю при $n>2$. Например для $n=2$ минимальное решение:

$2^0+3^0+7^0=1^0+5^0+6^0,$
$2+3+7=1+5+6$,
$2^2+3^2+7^2=1^2+5^2+6^2.$

[maxal]

Известное элегантное решение - $A$ и $B$ образуют разбиение множества $\{ 0, 1, 2, \dots, 2^{n+1}-1 \}$ в соответствие с последовательностью Туэ-Морса: $m\in A$, если в двоичной записи $m$ четное число единиц, в противном случае $m\in B$.
Например, для $n=2$ таким разбиением будет:
$A = \{ 0, 3, 5, 6 \}$
$B = \{ 1, 2, 4, 7 \}$

P.S. А вообще у этой задачи даже имя есть:
http://mathworld.wolfram.com/Prouhet-Ta ... oblem.html
http://en.wikipedia.org/wiki/Prouhet%E2 ... tt_problem

[Руст]

Я не знаю последовательность Туэ-Морса. Но решение вида $A=\{k\le 2^n|s_2(k-1)-odd\}, B=\{k\le 2^n|s_2(k-1)-even\}$, где $s_2(k)$ - сумма двоичных цифр числа k, это первое, что приходит в голову. Только оно не экономное. Есть квадратичные (по количеству членов) от n решения.
При $n\le 2$ количество членов ведет себя как $n+1$. Легко доказать, что количество членов больше n.

[Руст]

Похоже гипотеза о том, что минимальное количество членов равно $n+1$ верна.
Нашел следующий минимальный для $n=4$ пример (только ручкой на листе бумаги, соответственно не проверил что все соотношения выполняются, так как мне не приходилось считать степени):

$$1^k+7^k+9^k+16^k+20^k=2^k+4^k+13^k+15^k+21^k, k=0,1,2,3,4.$$

[juna]

Вот здесь я занимался похожим topic3687-30.html

[maxal]

Руст в сообщении #472535 писал(а):

Похоже гипотеза о том, что минимальное количество членов равно $n+1$ верна.

Это не гипотеза. Цитата с MathWorld по ссылке выше:
Solutions with n=m+1 are said to be "ideal" and are of interest because they are minimal solutions of the problem (Borwein and Ingalls 1994).

-- Mon Aug 01, 2011 03:39:44 --

Там же дан пример идеального решения для $k\leq 11$:
In 1999, S. Chen found the first ideal solution with m>=10,

$$0^k+11^k+24^k+65^k+90^k+129^k+173^k+212^k+237^k+278^k+291^k+302^k=$$

$$=3^k+5^k+30^k+57^k+104^k+116^k+186^k+198^k+245^k+272^k+297^k+299^k,$$

which is true for k=1, 2, ..., 11.

[Руст]

Да, и здесь все посчитали.
Я до конца не проверил у себя доказательство, но суть сводится к следующим:
1. Если множество А и В дают решение, то и сдвиг на любое число так же дают решение. Я сдвигал так, чтобы минимальное число равнялось 1.
2. Решение для 2n сводится к решению n с удвоением и сдвигом к 1 путем сведения к неоднородной системе. Поэтому, требуется индукцию проводит для неоднородных систем. При этом если получаются рациональные, то однородную систему путем нормировки всегда можно сделать целыми.
Нахождение идеального решения для $n=4$ у меня свелось к одному уравнению в целых числах:
$z(z+1)=(x+1)(y+1)(x+y)$. Решение $x=2,y=4,z=9$ привело к указанному решению без калькулятора.

[juna]

Руст в сообщении #472535 писал(а):

Похоже гипотеза о том, что минимальное количество членов равно $n+1$ верна.

В моей ссылке выше я указывал на связь с теоремой Жирара-Ньютона о суммах степеней корней. Ваша гипотеза - ее прямое следствие.
Действительно, вот имеем к примеру
$(t+3)^n+(t+4)^n+(t+12)^n+(t+16)^n+(t+20)^n=$ $(t+2)^n+(t+6)^n+(t+10)^n+(t+18)^n+(t+19)^n, n<5$, а значит имеем два уравнения:
$(x-3)(x-4)(x-12)(x-16)(x-20)=$ $x^5-55x^4+1100x^3-9680x^2+35904x-46080$
$(x-2)(x-6)(x-10)(x-18)(x-19)=$ $x^5-55x^4+1100x^3-9680x^2+35904x-41040$
Поскольку имеем $S_m+a_1S_{m-1}+a_2S_{m-2}+...+a_mm=0$, где $S_m=\sum_{k=1}^n{x_k^m}$ для $x^n+a_1x^{n-1}+...+a_n=0$, то если бы совпали $S_5$, это означало, что уравнения просто одинаковые - вплоть до свободного члена.

[Руст]

juna в сообщении #472630 писал(а):

Руст в сообщении #472535 писал(а):

Похоже гипотеза о том, что минимальное количество членов равно $n+1$ верна.

$(t+3)^n+(t+4)^n+(t+12)^n+(t+16)^n+(t+20)^n=$ $(t+2)^n+(t+6)^n+(t+10)^n+(t+18)^n+(t+19)^n, n<5$, а значит имеем два уравнения:

Чтобы найти такое соотношение надо вначале знать решение $t$ - сдвиг который может быть произвольным.
. Я искал решение исходя из того, что при соответствующем сдвиге члены A и B совпадут с точностью до знака. Тогда соотношения для четных степеней выполняются автоматический. Суммы нечетных степеней надо приравнять нулю. Соответственно вместо переменных А и В останутся только А можно перенести в одну сторону отрицательные у А и оно разобьется на A' и B' только по нечетным степеням. Решая при $n=4$ переходя к другим переменным решение сводится к вышеуказанному уравнению и легко находится решение.