Question

【題目】若A1，A2，…，Am為集合A＝{1，2，…，n}（n≥2且n∈N*）的子集，且滿足兩個條件：

①A1∪A2∪…∪Am＝A；

②對任意的{x，y}A，至少存在一個i∈{1，2，3，…，m}，使Ai∩{x，y}＝{x}或{y}．則稱集合組A1，A2，…，Am具有性質P．

如圖，作n行m列數表，定義數表中的第k行第l列的數為akl．

a11	a12	…	a1m
a21	a22	…	a2m
…	…	…	…
an1	an2	…	anm

（1）當n＝4時，判斷下列兩個集合組是否具有性質P，如果是請畫出所對應的表格，如果不是請說明理由；

集合組1：A1＝{1，3}，A2＝{2，3}，A3＝{4}；

集合組2：A1＝{2，3，4}，A2＝{2，3}，A3＝{1，4}．

（2）當n＝7時，若集合組A1，A2，A3具有性質P，請先畫出所對應的7行3列的一個數表，再依此表格分別寫出集合A1，A2，A3；

（3）當n＝100時，集合組A1，A2，…，At是具有性質P且所含集合個數最小的集合組，求t的值及|A1|+|A2|+…|At|的最小值．（其中|Ai|表示集合Ai所含元素的個數）

Answer 1

【答案】（1）集合組1具有性質P，集合組2不具有性質P，理由見解析；（2）圖見解析，A1＝{3，4，5，7}，A2＝{2，4，6，7}，A3＝{1，5，6，7}；（3）304

【解析】

（1）根據題意檢驗兩個集合組是否滿足性質即可；

（2）一共7行對應1,2,3,4,5,6,7，七個數，其中每列的1或0代表這個集合里面有或者無對應的數，要求每行必須有1，任意兩個數至少有一列只出現一個；

（3）條件①可知數表M中任意一行不全為0，由條件②可得數表M中任意兩行不完全相同，結合排列組合知識求解.

（1）集合組1具有性質P．

所對應的數表為：

1	0	0
0	1	0
1	1	0
0	0	1

集合組2不具有性質P．

因為存在{2，3}{1，2，3，4}，有{2，3}∩A1＝{2，3}，{2，3}∩A2＝{2，3}，{2，3}∩A3＝，

與對任意的{x，y}A，都至少存在一個i∈{1，2，3}，有Ai∩{x，y}＝{x}或{y}矛盾，

所以集合組A1＝{2，3，4}，A2＝{2，3}，A3＝{1，4}不具有性質P．…

（2）

A1＝{3，4，5，7}，A2＝{2，4，6，7}，A3＝{1，5，6，7}．

（注：表格中的7行可以交換得到不同的表格，它們所對應的集合組也不同）

（3）設A1，A2，…，At所對應的數表為數表M，

因為集合組A1，A2，…，At為具有性質P的集合組，所以集合組A1，A2，…，At滿足條件①和②，

由條件①：A1∪A2∪…∪At＝A，可得對任意x∈A，都存在i∈{1，2，3，…，t}有x∈Ai，

所以axi＝1，即第x行不全為0，所以由條件①可知數表M中任意一行不全為0.

由條件②知，對任意的{x，y}A，都至少存在一個i∈{1，2，3，…，t}，使Ai∩{x，y}＝{x}或{y}，所以axi，ayi一定是一個1一個0，即第x行與第y行的第i列的兩個數一定不同．

所以由條件②可得數表M中任意兩行不完全相同．

因為由0，1所構成的t元有序數組共有2t個，去掉全是0的t元有序數組，共有2t﹣1個，又因數表M中任意兩行都不完全相同，所以100≤2t﹣1，所以t≥7．

又t＝7時，由0，1所構成的7元有序數組共有128個，去掉全是0的數組，共127個，選擇其中的100個數組構造100行7列數表，則數表對應的集合組滿足條件①②，即具有性質P．所以t＝7．

因為|A1|+|A2|+…+|At|等于表格中數字1的個數，

所以，要使|A1|+|A2|+…+|At|取得最小值，只需使表中1的個數盡可能少，

而t＝7時，在數表M中，1的個數為1的行最多7行；1的個數為2的行最多C72＝21行；1的個數為3的行最多C73＝35行；1的個數為4的行最多C74＝35行；

因為上述共有98行，所以還有2行各有5個1，

所以此時表格中最少有7+2×21+3×35+4×35+5×2＝304個1．所以|A1|+|A2|+…+|At|的最小值為304．