等差数列子集和的等差性
设1~n共n个自然数，从中任取k个数求和，共得到m个不同的和，从小到大排列为S1~Sm。求证S1~Sm也为等差数列，公差为1。 S1=1+2+...+k=k(k+1)/2Sm=n+(n-1)+...+(n-k+1)=nk-k(k-1)/2
m=Sm-S1+1=k(n-k)+1
假定Si1（1<i<m）为Range(n)的一个k元子集，并且∑Si1=Si中，那么
1）存在x∈Si1，x-1不属于Si1
否则，若任意x∈Si1→x-1∈Si1，那么就可以一直递减到1∈Si1，从而得出Si=S1
2）存在y∈Si1，y+1不属于Si1
否则，若任意y∈Si1→y+1∈Si1，那么就可以一直递增到n∈Si1，从而得出Si=Sm
由1）知，将x换成x-1所得集合亦Range(n)的一个k元子集，即存在Si-1=Si-1
由2）知，将y换成y+1所得集合亦Range(n)的一个k元子集，即存在Si+1=Si+1
故S1，S2，..., Sm是一段连续自然数。 当k=n时，m=1不需考虑；
假设k<n，对1+2+…+k 做一系列的+1操作，便可得到从k(k+1)/2到nk-k(k-1)/2的所有数。
方法如下：
k个数的组合初值为{1,2,…,k},对最大数k逐步+1，直至{1,2,…,k-1,n}；
然后对第二大的k-1逐步+1，直至{1,2,…,k-2,n-1,n}；
再其次是第三大的k-2,同样操作，一直进行到第k大的1逐步+1，直至{n-k+1,n-k+2,…,n-1,n}；
每次都是+1操作，所得的组合和必然连续，证毕! 3# xbtianlang
这样会遗漏许多组合吧，取n=10，k=3，（1，5，8）这个组合就会被漏掉，需证明该组合的和包含在上述算法得到的和中。 所有组合的和都在{1,2,3}-{8,9,10}的和之间，怎么可能漏掉呢？你要证明的是和的集合，重复自然淘汰，哪来的遗漏啊。 5# xbtianlang
呵呵，是我没转过弯来。
页:
[1]