Question

【題目】設(shè).求最大的整數(shù)，使得集合S有k個(gè)互不相同的非空子集，具有性質(zhì)：對這k個(gè)子集中任意兩個(gè)不同子集，若它們的交非空，則它們交集中的最小元素與這兩個(gè)子集中的最大元素均不相同.

Answer 1

【答案】

【解析】

對有限非空實(shí)數(shù)集A，用與分別表示集合A的最小元素與最大元素.

考慮集合S的所有包含1且至少有兩個(gè)元素的子集.

注意到，，

故.

于是，這樣的子集一共個(gè).

顯然滿足要求.

接下來證明：當(dāng)時(shí)，不存在滿足要求的k個(gè)子集.

用數(shù)學(xué)歸納法證明：對整數(shù)，在集合的任意個(gè)不同非空子集中，存在兩個(gè)子集，滿足，且. ①

顯然，只需對的情形證明上述結(jié)論.

當(dāng)時(shí)，將的全部七個(gè)非空子集分成三組，

第一組：｛3｝，｛1，3｝，｛2，3｝；

第二組：｛2｝，｛1，2｝；

第三組：｛1｝，｛1，2，3｝.

由抽屜原理，知任意四個(gè)非空子集必有兩個(gè)在同一組中， 取同組中的兩個(gè)子集分別記為，在排在前面的記為，則滿足結(jié)論①.

假設(shè)結(jié)論在時(shí)成立.考慮時(shí)的情形.

若中至少有個(gè)子集不含，對其中的個(gè)子集用歸納假設(shè)，知存在兩個(gè)子集滿足結(jié)論①.

若至多有-1個(gè)子集不含，則至少有+1個(gè)子集含，將其中+1個(gè)子集均去掉，得到｛1，2，…，n｝的+1個(gè)子集.

由于｛1，2，…，n｝的全體子集可分為組，每組兩個(gè)子集互補(bǔ)，故由抽屜原理，知在上述+1個(gè)子集中一定有兩個(gè)屬于同一組，即互為補(bǔ)集.

因此，相應(yīng)地有兩個(gè)子集滿足，這兩個(gè)集合顯然滿足結(jié)論①.

于是，時(shí)結(jié)論成立.

綜上，.