Question

已知n個四元集合，每兩個有且只有一個公共元，并且有Card()＝n，試求n的最大值.這里CardA為集合A中元素的個數(shù).

Answer 1

解析：考慮任一元a,如果每個均含有a,則由條件知,各中的其他元素都不相同,故()＝3n＋1＞n,與已知條件相違.因此必有一個不含a,不妨設(shè)a.若含a的集合不少于5個，那么，由已知條件得知，與這5個集合各有一個公共元（此元當(dāng)然不等于a）,而且這5個元互不相同（若有相同的，則這個公共元是兩個含a的集合的公共元，于是這兩個集合就有兩個公共元，又與已知條件相違），從而≥5，矛盾，所以含a的集合不多于4個.

   另一方面，因為＋＋＋…＋＝4n,所以每個元恰好屬于4個集.不妨設(shè)含有元b的集合為，，，，則由上述的結(jié)論可知，（）＝3×4＋1＝13.如果n＞13,那么存在元c.

   設(shè)含c的集合為,則不是，，，，因而不含b.而與，，， 各有一個公共元（當(dāng)然不是b）,這4個公共元互不相同（理由同上），又都不是c,從而≥5，因此n≤13.

   n≤13是可能的，例如，不難驗證，如下13個集：｛0，1，2，3｝，｛0，4，5，6｝，｛0，7，8，9｝，｛0，10，11，12｝，｛10，1，4，7｝，｛10，2，5，8｝，｛10，3，6，9｝，｛11，1，5，9｝，｛11，2，6，7｝，｛11，3，4，8｝，｛12，1，6，8｝，｛12，2，4，9｝，｛12，3，5，7｝符合要求.故n的最大值為13.