作业帮 > 数学 > 作业

设A是不大于40的8个自然数的集合,求证:必有A的两个相异子集,使这两个子集的元素和相等!

来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/11/18 14:17:42
设A是不大于40的8个自然数的集合,求证:必有A的两个相异子集,使这两个子集的元素和相等!
相异子集就是两个子集不相等。
设A是不大于40的8个自然数的集合,求证:必有A的两个相异子集,使这两个子集的元素和相等!
A一共有256个子集 ,除了其本身和空集外还有254个子集,下面讨论这254个子集
这254子集最小含一个元素,最多含7个元素
若是全部元素小于40
子集的元素和至少是1,子集的元素和最多是39+38+37+36+35+34+33=252
也就是说子集和最多有252中可能,但现有254个子集,
由抽屉原理知必然存在两个不同子集的元素和相等.
若A含有40,
若A最小元素至少为7,子集的元素和至少是7,子集的元素和最多是259 ,最多253种和,
由抽屉原理可证明必然存在两个不同子集的元素和相等.
若A最小元素为k,其中1≤k≤6 若A还有含有40-k,那么两个子集A1={k,40-k},A2={40} ,元素和相等,得证
若A不含有40-k,那么子集的元素和最多是40+39+38+37+36+35+34+33-(40-k)=252+k
子集的元素和从k到252+k也最多是253种和,由抽屉原理可证