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