Question

【题目】设的个子集满足：（1）对任意的，恰有奇数个元素；（2）对任意的，都有.（3）若，则.试确定的最大值.

Answer 1

【答案】

【解析】

首先，下列个集合满足条件（1），（2），（3）：

，.

其次证明：.

若不然，设的个子集同时满足（1），（2），（3）.

称满足（3）的数对为“搭档”，用表示集合的元素个数.

先给出一个引理.

引理在奇数个顶点的图中，必有一个顶点的度数为偶数.

证明略.

回到原题.

（1）若存在，使得为奇数，不妨设.

则对每个，由题设在中的搭档个数为奇数.

设对应的点分别为.

若为搭档关系，则在对应的两点之间连一条线.这些点构成的图中每个顶点度数为奇数，由引理，这不可能.

（2）若对任意的，为偶数，设.

设为除1之外的搭档构成的集合.则为奇数.从而为偶数.

再考虑这个数，其中必有一个出现在偶数个中（否则，奇数个奇数的和为奇数，即出现的总次数为奇数，与为偶数矛盾）（设这个数为），则1与的公共搭档数为偶数，即为偶数，与假设矛盾.