第二十八讲代数：关于集合、数、式之二
12B1－008设集合Sn={1，2，…，n）．若X是Sn的子集，把X中所有数之和称为X的“容量”（规定空集容量为0）．若X的容量为奇（偶）数，则称X为Sn的奇（偶）子集．
（1）求证：Sn的奇子集与偶子集个数相等；
（2）求证：当n≥3时，Sn的所有奇子集容量之和，与所有偶子集容量之和相等．
（3）当n≥3时，求Sn所有奇子集的容量之和．
【题说】1992年全国联赛二试题2．
【证】设S为Sn的奇子集，令
则T是偶子集，S→T是奇子集的集到偶子集的一一对应，而且每个偶子集T，均恰有一个奇子集
与之对应，所以（1）的结论成立．
对任一i（1≤i≤n），含i的子集共2n-1个，用上面的对应方法可知在i≠1时，这2n-1个集中有一半是奇子集．在i=1时，由于n≥3，将上边的1换成3，同样可得其中有一半是奇子集．于是在计算奇子集容量之和时，元素i的贡献是2n-2?i．奇子集容量之和是
根据上面所说，这也是偶子集容量之和，两者相等．
B1－009用σ（S）表示非空整数集S中所有元素的和．设A=｛a1，a2，…，an｝是正整数集，且a1＜a2＜…＜a11．若对每个正整数n≤1500，存在A的子集S，使得σ（S）=n．试求满足上述要求的a10的最小值．
【题说】第二十一届（1992年）美国数学奥林匹克题3．
【解】令Sk=a1＋a2＋…＋ak（1≤k≤11）．
若ak＞Sk-1＋1，则不存在S
A，使
σ（S）=Sk-1＋1
所以，
Sk=Sk-1＋ak≤2Sk-1＋1 （1）
又由题设得 S1=a1=1．于是由（1）及归纳法易得
Sk≤2k－1（1≤k≤m） （2）
若S10＜750，则a11≤1500（否则750无法用σ（S）表出），S11=S10＋a11＜1500，所以S10≥750．
又S8≤28－1=255，于是
2a10≥a9＋a10=S10－S8≥495
所以，a10≥248．
另一方面，令
A={1，2，4，8，16，32，64，128，247，248，750}
当n≤255=27＋26＋…＋2＋20时，可找到S
｛1，2，4，…，128｝，使σ（S）=n．当n≤255＋247=502时，存在S
（1，2，4，…，128，247），使σ（S）=n；当n≤502＋248=750时，存在S
{1，2，4，…247，248}，使σ（S）=n；当n≤750＋750=1500时，存在S
A，使σ（S）=n．
于是a10的最小值为248．
页:
[1]