Question

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

Answer 1

【答案】41

【解析】

構(gòu)造15個(gè)子集

，

.

則，，

，.

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

現(xiàn)分析其中任何七個(gè)子集的元素個(gè)數(shù).

任取其中七個(gè)子集，，…，及，，…，，其中，.則

.

故滿足題設(shè)的正整數(shù).

下面用反證法證明：滿足題設(shè).

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

分兩種情形討論.

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

由抽屜原理，知必有一個(gè)子集（不妨設(shè)為）中至少含有（表示不超過實(shí)數(shù)的最大整數(shù)）個(gè)元素.由，，…，組成的所有七元子集組，至少共對(duì)應(yīng)個(gè)元素.

另一方面，對(duì)任一元素，若，則，，…，中只有兩個(gè)子集含有，于是，被計(jì)算的次數(shù)為；若，則，，…，中只有一個(gè)子集含有，于是，被計(jì)算的次數(shù)為.

故

，即，矛盾.

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

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

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

綜上，滿足題設(shè)的最小正整數(shù).