Question

【題目】已知 n 個四元集合 A1 ， A2 ，…， An ，每兩個有且只有一個公共元 ，并且有Card（A1 ∪ A2 ∪ …∪ An）=n .試求 n 的最大值.這里 Card A 為集合A中元素的個數 .

Answer 1

【答案】13

【解析】

考慮任一元.

如果每個 Ai 均含有a ， 則由條件知， 各 Ai 中的其他元素都不相同.

故，與已知條件相違.

因此， 必有一個 Ai 不含a .

不妨設 aA1 .若含 a 的集合大于或等于 5個， 那么， 由已知條件得知 A1與這 5個集合各有一個公共元（此元當然不等于a）， 而且這 5個元互不相同（若相同， 則這個公共元是2個含 a 的集合的公共元 ， 于是， 這兩個集合就有 2 個公共元， 又與已知條件相違）， 從而， Card A1≥5， 矛盾.所以 ， 含a的集合小于或等于 4 個.

另一方面， 因為，所以， 每個元恰好屬于 4個集合.

不妨設含有元 b 的集合為 A1 、A2 、A3 、A4.

由上述的結論可知.

如果 n >13， 那么， 存在元 c A1∪A2∪A3∪A4.設含 c 的集合為 A5， 則 A5不是.因而， 不含 b .而 A5與各有一個公共元（當然不是 b）， 這 4個公共元互不相同（理由同上）， 又都不是 c ， 從而，， 矛盾.

因此， 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.