Question

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

Answer 1

【答案】

【解析】

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

，.

其次證明：.

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

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

先給出一個引理.

引理在奇數個頂點的圖中，必有一個頂點的度數為偶數.

證明略.

回到原題.

（1）若存在，使得為奇數，不妨設.

則對每個，由題設在中的搭檔個數為奇數.

設對應的點分別為.

若為搭檔關系，則在對應的兩點之間連一條線.這些點構成的圖中每個頂點度數為奇數，由引理，這不可能.

（2）若對任意的，為偶數，設.

設為除1之外的搭檔構成的集合.則為奇數.從而為偶數.

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