Question

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

Answer 1

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

   另一方面，因?yàn)?IMG height=19 src='http://thumb.zyjl.cn/pic1/img/20090722/20090722103547004.gif' width=39>＋＋＋…＋＝4n,所以每個(gè)元恰好屬于4個(gè)集.不妨設(shè)含有元b的集合為，，，，則由上述的結(jié)論可知，（）＝3×4＋1＝13.如果n＞13,那么存在元c.

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

   n≤13是可能的，例如，不難驗(yàn)證，如下13個(gè)集：｛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.