Question

【題目】設為一個56元集合.求最小的正整數，使得對集合的任意15個子集，只要它們中間任何七個的并的元素個數均不少于，則這15個子集中一定存在三個集合，使得它們的交集非空.

Answer 1

【答案】41

【解析】

構造15個子集

，

.

則，，

，.

于是，這15個子集中任何三個中必有兩個是組，或者必有兩個是組，三者交集均為空集.

現分析其中任何七個子集的元素個數.

任取其中七個子集，，…，及，，…，，其中，.則

.

故滿足題設的正整數.

下面用反證法證明：滿足題設.

假設存在集合的某15個子集，，…，.盡管其中任何七個子集的并集不少于41個元素，但其中任何三個子集的交集均為空集，從而，每個元素至多屬于兩個子集.

分兩種情形討論.

（1）集合的每個元素均恰屬于，，…，中兩個子集.

由抽屜原理，知必有一個子集（不妨設為）中至少含有（表示不超過實數的最大整數）個元素.由，，…，組成的所有七元子集組，至少共對應個元素.

另一方面，對任一元素，若，則，，…，中只有兩個子集含有，于是，被計算的次數為；若，則，，…，中只有一個子集含有，于是，被計算的次數為.

故

，即，矛盾.

（2）集合可能存在一些元素至多屬于子集，，…，中一個子集.

在不含這些元素的子集中各找一個添入這些元素，直至集合的每個元素均恰含于子集，，…，中兩個子集.于是，改造過的子集，，…，中的任意三個的交仍然為空集.此時，該情形已化為（1），從而，也是矛盾的.

總之，對于集合的任意15個子集，只要它們中任何七個的并的元素個數均不少于41，則這15個子集中就一定存在三個交集非空的集合.

綜上，滿足題設的最小正整數.