级联等幂集

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

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

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值大