等差数列子集和的等差性

yyy_fcz

设1~n共n个自然数，从中任取k个数求和，共得到m个不同的和，从小到大排列为S1~Sm。求证S1~Sm也为等差数列，公差为1。

hujunhua

S₁=1+2+...+k=k(k+1)/2
S_m=n+(n-1)+...+(n-k+1)=nk-k(k-1)/2
m=S_m-S₁+1=k(n-k)+1

假定S_i1（1<i<m）为Range(n)的一个k元子集，并且∑S_i1=S_i中，那么
1）存在x∈S_i1，x-1不属于S_i1
       否则，若任意x∈S_i1→x-1∈S_i1，那么就可以一直递减到1∈S_i1，从而得出S_i=S₁
2）存在y∈S_i1，y+1不属于S_i1
       否则，若任意y∈S_i1→y+1∈S_i1，那么就可以一直递增到n∈S_i1，从而得出S_i=S_m
由1）知，将x换成x-1所得集合亦Range(n)的一个k元子集，即存在S_i-1=S_i-1
由2）知，将y换成y+1所得集合亦Range(n)的一个k元子集，即存在S_i+1=S_i+1
故S₁，S₂，..., S_m是一段连续自然数。

xbtianlang

当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操作，所得的组合和必然连续，证毕!

yyy_fcz

3# xbtianlang
这样会遗漏许多组合吧，取n=10，k=3，（1，5，8）这个组合就会被漏掉，需证明该组合的和包含在上述算法得到的和中。

xbtianlang

所有组合的和都在{1,2,3}-{8,9,10}的和之间，怎么可能漏掉呢？你要证明的是和的集合，重复自然淘汰，哪来的遗漏啊。

yyy_fcz

5# xbtianlang

呵呵，是我没转过弯来。