Question

【題目】設(shè)的個子集滿足：（1）對任意的，恰有奇數(shù)個元素；（2）對任意的，都有.（3）若，則.試確定的最大值.

Answer 1

【答案】

【解析】

首先，下列個集合滿足條件（1），（2），（3）：

，.

其次證明：.

若不然，設(shè)的個子集同時滿足（1），（2），（3）.

稱滿足（3）的數(shù)對為“搭檔”，用表示集合的元素個數(shù).

先給出一個引理.

引理在奇數(shù)個頂點(diǎn)的圖中，必有一個頂點(diǎn)的度數(shù)為偶數(shù).

證明略.

回到原題.

（1）若存在，使得為奇數(shù)，不妨設(shè).

則對每個，由題設(shè)在中的搭檔個數(shù)為奇數(shù).

設(shè)對應(yīng)的點(diǎn)分別為.

若為搭檔關(guān)系，則在對應(yīng)的兩點(diǎn)之間連一條線.這些點(diǎn)構(gòu)成的圖中每個頂點(diǎn)度數(shù)為奇數(shù)，由引理，這不可能.

（2）若對任意的，為偶數(shù)，設(shè).

設(shè)為除1之外的搭檔構(gòu)成的集合.則為奇數(shù).從而為偶數(shù).

再考慮這個數(shù)，其中必有一個出現(xiàn)在偶數(shù)個中（否則，奇數(shù)個奇數(shù)的和為奇數(shù)，即出現(xiàn)的總次數(shù)為奇數(shù)，與為偶數(shù)矛盾）（設(shè)這個數(shù)為），則1與的公共搭檔數(shù)為偶數(shù)，即為偶數(shù)，與假設(shè)矛盾.