B1－008  设集合S_n={1，2，…，n）．若X是S_n的子集，把X中所有数之和称为X的“容量”（规定空集容量为0）．若X的容量为奇（偶）数，则称X为S_n的奇（偶）子集．

（1）求证：S_n的奇子集与偶子集个数相等；

（2）求证：当n≥3时，S_n的所有奇子集容量之和，与所有偶子集容量之和相等．

（3）当n≥3时，求S_n所有奇子集的容量之和．

【题说】1992年全国联赛二试题2．

【证】设S为S_n的奇子集，令

则T是偶子集，S→T是奇子集的集到偶子集的一一对应，而且每个偶子集T，均恰有一个奇子集

与之对应，所以（1）的结论成立．

对任一i（1≤i≤n），含i的子集共2^n-1个，用上面的对应方法可知在i≠1时，这2^n-1个集中有一半是奇子集．在i=1时，由于n≥3，将上边的1换成3，同样可得其中有一半是奇子集．于是在计算奇子集容量之和时，元素i的贡献是2^n-2?i．奇子集容量之和是

根据上面所说，这也是偶子集容量之和，两者相等．

B1－009  用σ（S）表示非空整数集S中所有元素的和．设A=｛a₁，a₂，…，a_n｝是正整数集，且a₁＜a₂＜…＜a₁₁．若对每个正整数n≤1500，存在A的子集S，使得σ（S）=n．试求满足上述要求的a₁₀的最小值．

【题说】第二十一届（1992年）美国数学奥林匹克题3．

【解】令S_k=a₁＋a₂＋…＋a_k（1≤k≤11）．

若a_k＞S_k-1＋1，则不存在S A，使

σ（S）=S_k-1＋1

所以，

S_k=S_k-1＋a_k≤2S_k-1＋1                                 （1）

又由题设得 S₁=a₁=1．于是由（1）及归纳法易得

S_k≤2^k－1（1≤k≤m）                                （2）

若S₁₀＜750，则a₁₁≤1500（否则750无法用σ（S）表出），S₁₁=S₁₀＋a₁₁＜1500，所以S₁₀≥750．

又S₈≤2⁸－1=255，于是

2a₁₀≥a₉＋a₁₀=S₁₀－S₈≥495

所以，a₁₀≥248．

另一方面，令

A={1，2，4，8，16，32，64，128，247，248，750}

当n≤255=2⁷＋2⁶＋…＋2＋2⁰时，可找到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．

于是a₁₀的最小值为248．

<B