Question

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

Answer 1

【答案】13

【解析】

考慮任一元.

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

故，與已知條件相違.

因此， 必有一個(gè) Ai 不含a .

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

另一方面， 因?yàn)?/span>，所以， 每個(gè)元恰好屬于 4個(gè)集合.

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

由上述的結(jié)論可知.

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

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