级联等幂集

mathe

最近看到CSDN上有人问一个关于“级联等幂集”的计算问题，我觉得可以作为擂台赛的题目:
http://topic.csdn.net/u/20080411 ... 9-71bf77ea4aaf.html
简单说，对于一个给定的整数k,k-级联等幂集是两个长度为k+1的正整数序列
$x_0,x_1,...,x_k$和$y_0,y_1,...,y_k$
使得对于任意非负整数m,$1<=m<=k$都有
$\sum_{t=0}^k x_t^m = \sum_{t=0}^k y_t^m$
而且这两个序列中总共2k+2个数都相互不相同

mathe

关于这个题目，我先给出一些我的数学方法的分析结果，如果大家有更多的分析结果，欢迎继续添加。

mathe

为方便起见，我们先定义一些记号。
对于n个数字$x_1,x_2,...,x_n$,我们定义函数
$s_k(x_1,x_2,...,x_n)=x_1^k+x_2^k+...+x_n^k=\sum_{t=1}^n x_t^k$
此外，我们再定义
$sigma_1{x_1,x_2,...,x_n}=\sum_{t=1}^n x_t$
$sigma_2{x_1,x_2,...,x_n} =\sum_{1<=t_1<t_2<=n} x_{t_1} x_{t_2}$
$sigma_3{x_1,x_2,...,x_n} =\sum_{1<=t_1<t_2<t_3<=n} x_{t_1} x_{t_2}x_{t_3}$
...
$sigma_k{x_1,x_2,...,x_n}=\sum_{1<=t_1<t_2<...<t_k<=n} \prod_{s=1}^k x_{t_s}$
...
$sigma_n{x_1,x_2,...,x_n}=\prod_{s=1}^n x_s$

mathe

下面为了简单起见，我们在不会出现歧异的情况下面，将采用$s_k$直接表示函数$s_k(x_1,x_2,...,x_n)$,同样
直接用$sigma_k$表示函数$sigma_k(x_1,x_2,...,x_n)$
也就是$sigma_1$就是n个数字中所有一个数字的和，
而$sigma_2$就是n个数中所有两个数字乘积的和，
...
而$sigma_k$就是n个数中所有$k$个数字乘积之和。
...
所以$sigma_1=s_1$
其次我们可以得出$sigma_2=1/2(s_1^2-s_2)$或者$s_2=sigma_1^2-2sigma_2$
更加一般的，数学中有结论:
$sigma_k$可以通过$s_1,s_2,...,s_k$的组合来表示出来，同样$s_k$可以用$sigma_1,sigma_2,...,sigma_k$的组合来表示出来。

mathe

所以对于级联等幂集，我们可以得到:
由定义我们知道，对于所有满足$1<=t<=k$的$t$都有
$s_t(x_0,x_1,...,x_k)=s_t(y_0,y_1,...,y_k)$
由4楼的结论我们可以得出,对于所有满足$1<=t<=k$的$t$都有
$sigma_t(x_0,x_1,...,x_k)=sigma_t(y_0,y_1,...,y_k)$
我们定义函数
$f(x)=(x-x_0)(x-x_1)...(x-x_k)$
$g(x)=(x-y_0)(x-y_1)...(y-y_k)$
这两个函数都是$k+1$次多项式
由韦达定理
$f(x)=x^{k+1)-sigma_1(x_0,x_1,...,x_k) x^k+....+(-1)^{k+1) sigma_{k+1}(x_0,x_1,...,x_k)=x^{k+1}+\sum_{s=1}^{k+1} (-1)^s sigma_s{x_0,x_1,...,x_k) x^{k+1-s}$
$g(x)=x^{k+1)-sigma_1(y_0,y_1,...,y_k) x^k+....+(-1)^{k+1) sigma_{k+1}(y_0,y_1,...,y_k)=x^{k+1}+\sum_{s=1}^{k+1} (-1)^s sigma_s{y_0,y_1,...,y_k) x^{k+1-s}$
所以
$f(x)-g(x)=sigma_{k+1}(x_0,x_1,...,x_k) -sigma_{k+1}(y_0,y_1,...,y_k)=C$
也就是函数$f(x)$和$g(x)$除了常数项以外所有系数都相同。
如果$f(x)$和$g(x)$的常系数也相同，那么这两个函数将完全相同，它们将由相同的根，
也就是$x_0,x_1,...,x_k$和$y_0,y_1,...,y_k$除了排列顺序不同将会完全相同，这个同题目初试条件要求不同，所有我们得到必须由$C!=0$
同样，如果$x_0,x_1,...,x_k$和$y_0,y_1,...,y_k$中如果有部分数据相同，那么我们去掉这些部分相同的数据，那么余下部分的数据构成两个长度不超过k的数列，它们k次以内幂之和都相同，同样根据上面分析过程，以它们为根的对应的多项式将完全相同，同样得到两个数列将完全相同。
所以我们得到
结论1）如果存在两个长度为$k+1$的序列对于所有满足$1<=t<=k$的整数t都有它们的t次幂之和相同，而且两个序列不完全相同，那么这两个序列必然没有任何相同的项。（但是同一个序列内部还是可以出现重复的数字）

无心人

这不是等幂和问题么？

什么时候起了小名了啊？

mathe

同样，由公式
$f(x)-g(x)=C$
我们分别将$x=y_0,x=y_1,...,x=y_k$代入上面等式，得到
$f(y_0)=f(y_1)=...=f(y_k)=C$
也就是
$(y_0-x_0)(y_0-x_1)...(y_0-x_k)$
$=(y_1-x_0)(y_1-x_1)...(y_1-x_k)$
$=...$
$=(y_k-x_0)(y_k-x_1)...(y_k-x_k)$
$=C$
也就是说存在常数$C$,它存在$k+1$种因子分解方式（因子可以出现负数），使得这些因子分解方式中所有因子按顺序排列以后，对应位置上元素的差值相同。
比如我们不妨设$x_0,x_1,...,x_k$已经排好序，也就是$x_0<x_1<...<x_k$
那么$C$的这$k+1$中因子分解中的任意一种 $(y_t-x_0)(y_t-x_1)...(y_t-x_k)$，其中最大两个因子的差值总是$(y_t-x_0)-(y_t-x_1)=x_1-x_0$,而第二大和第三大两个数之间的差值总是$x_2-x_1$,...,最小两个数之间差值总是$x_k-x_{k-1}$.

mathe

下面我们在来证明上面的条件不仅仅是必要的，还是充分的。
也就是说，如果对于一个合数$C$,它可以表示成至少$k+1$种因子分解方式，使得这些因子分解方式种所有因子排序以后，对应位置上元素的差值都相同，那么我们就可以找到两个不同的序列，对于所有的$t$满足$1<=t<=k$时,它们的t次幂之和相同。也就是
$C= c_{0,0} c_{0,1} c_{0,2} ... c_{0,k}$
$    = c_{1,0} c_{1,1} c_{1,2} ... c_{1,k}$
$   = ... $
$  = c_{k,0} c_{k,1} c_{k,2} ... c_{k,k}$
而且$c_{t,s+1}-c_{t,s}=u_s$, 记$U_s=u_0+u_1+...+u_s$
那么，记$v_t=c_{t,0}$上面因子分解结果我们可以改写成
$ C = v_0 (v_0+U_0) (v_0+U_1) ... (v_0+U_k)$
$    = v_1 (v_1 +U_0)(v_1+U_1) ... (v_1+U_k)$
$   = ... $
$   = v_k(v_k+U_0)(v_k+U_1)...(v_k+U_k)$
记函数
$h(x)=x(x+U_0)(x+U_1)....(x+U_k)$
那么我们知道k+1次方程$h(x)=0$有$k+1$个解$0,-U_0,-U_1,...,-U_k$
同样我们知道k+1次多项式$h(x)-C=0$有$k+1$个解$v_0,v_1,...,v_k$
由于这两个多项式方程除了常系数以外都相同，我们可以逆推前面的过程就知道这两个序列的$t$次幂之和相同。
唯一的问题时这里这些方程的根有可能是负整数。
不过我们可以发现，如果我们同时将两个方程的所有根都加上一个整常数，它们还是同样满足等幂和的特性。相当于我们将$h(x)$改为
$h(x)=(x-M)(x-M+U_0)(x-M+U_1)...(x-M+U_k)$
那么$h(x)$的解变成$M,M-U_0,M-U_1,...,M-U_k$
而$h(x)-C$的解变成$M+v0,M+v_1,...,M+v_k$
所以只要M取的充分大，所有这些解都会变成正整数。
所以我们知道这种方法来计算级联等幂集过程是充分而且必要的（唯一的例外是一个序列内部可能会出现重复的数据，也就是会出现部分多余的数据）。

mathe

原帖由 无心人 于 2008-4-13 09:35 发表


这不是等幂和问题么？

什么时候起了小名了啊？

这个我不清楚。不过我觉得通常等幂和问题对于$k+1$个数，不会要求1到k次幂之和都相同，而只会要求部分等幂和相同。
而从我后面的分析也可以知道,k是最大的可能。

无心人

看怎么出结果了
结果好的要数字序列长
k值大