等差数列子集和的等差性

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（1i1=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

yyy_fcz

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

xbtianlang

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

yyy_fcz

5# xbtianlang 呵呵，是我没转过弯来。