B1－008  設(shè)集合S_n={1，2，…，n）．若X是S_n的子集，把X中所有數(shù)之和稱為X的“容量”（規(guī)定空集容量為0）．若X的容量為奇（偶）數(shù)，則稱X為S_n的奇（偶）子集．

（1）求證：S_n的奇子集與偶子集個(gè)數(shù)相等；

（2）求證：當(dāng)n≥3時(shí)，S_n的所有奇子集容量之和，與所有偶子集容量之和相等．

（3）當(dāng)n≥3時(shí)，求S_n所有奇子集的容量之和．

【題說(shuō)】1992年全國(guó)聯(lián)賽二試題2．

【證】設(shè)S為S_n的奇子集，令

則T是偶子集，S→T是奇子集的集到偶子集的一一對(duì)應(yīng)，而且每個(gè)偶子集T，均恰有一個(gè)奇子集

與之對(duì)應(yīng)，所以（1）的結(jié)論成立．

對(duì)任一i（1≤i≤n），含i的子集共2^n-1個(gè)，用上面的對(duì)應(yīng)方法可知在i≠1時(shí)，這2^n-1個(gè)集中有一半是奇子集．在i=1時(shí)，由于n≥3，將上邊的1換成3，同樣可得其中有一半是奇子集．于是在計(jì)算奇子集容量之和時(shí)，元素i的貢獻(xiàn)是2^n-2?i．奇子集容量之和是

根據(jù)上面所說(shuō)，這也是偶子集容量之和，兩者相等．

B1－009  用σ（S）表示非空整數(shù)集S中所有元素的和．設(shè)A=｛a₁，a₂，…，a_n｝是正整數(shù)集，且a₁＜a₂＜…＜a₁₁．若對(duì)每個(gè)正整數(shù)n≤1500，存在A的子集S，使得σ（S）=n．試求滿足上述要求的a₁₀的最小值．

【題說(shuō)】第二十一屆（1992年）美國(guó)數(shù)學(xué)奧林匹克題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）

又由題設(shè)得 S₁=a₁=1．于是由（1）及歸納法易得

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

若S₁₀＜750，則a₁₁≤1500（否則750無(wú)法用σ（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}

當(dāng)n≤255=2⁷＋2⁶＋…＋2＋2⁰時(shí)，可找到S ｛1，2，4，…，128｝，使σ（S）=n．當(dāng)n≤255＋247=502時(shí)，存在S （1，2，4，…，128，247），使σ（S）=n；當(dāng)n≤502＋248=750時(shí)，存在S {1，2，4，…247，248}，使σ（S）=n；當(dāng)n≤750＋750=1500時(shí)，存在S A，使σ（S）=n．

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

<B