和倍集问题

石崇的BOSS

如果一个正整数的有限集合的所有元素之和是该集合所有元素的公倍数，则称之为和倍集。
例如集合{1,2,3}，元素之和为6，是1,2,3的公倍数。因此该集合是和倍集。
求证：正整数集N+的每个有限子集都是某个和倍集的子集。

石崇的BOSS

挖坟，求解答……

superacid

这个坟有点深。。。
只要考虑对任意n，包含元素{1,2,...,n}的集合
用数学归纳法，假设n=k成立，此时取出的集合是{1,2,...,k,x1,x2,...,xm}，那么就有1+2+...+k+x1+x2+...+xm是1,2,..,k,x1,x2,..,xm的倍数
那么当n=k+1时，令s=1+2+...+n=1+2+...+k+(k+1)
只要取出集合{1,2,...,k,k+1,2s,3s,...,ks,x1*s,x2*s,...,xm*s}
所有元素和等于s+2s+3s+...+ks+x1*s+x2*s+...+xm*s=(1+2+...+k+x1+x2+...+xm)*s
所有元素的最小公倍数等于[1,2,...,k,k+1,2s,3s,...,ks,x1*s,x2*s,..,xm*s]=[2s,3s,...,ks,x1*s,x2*s,..,xm*s]=[2,3,...,k,x1,x2,..,xm]*s
由于1+2+...+k+x1+x2+...+xm是1,2,..,k,x1,x2,..,xm的倍数，所以n=k+1时，上述集合满足条件
证明完毕

武杰610206738

楼主好可怜，三年前的坟都挖出来了····