Question

設(shè)X是一個56元集合．求最小的正整數(shù)n，使得對X的任意15個子集，只要它們中任何7個的并的元素個數(shù)都不少于n，則這15個子集中一定存在3個，它們的交非空．  

Answer 1

解析：  n的最小值為41．

首先證明合乎條件．用反證法．假定存在X的15個子集，它們中任何7個的并不少于41個元素，而任何3個的交都為空集．因每個元素至多屬于2個子集，不妨設(shè)每個元素恰好屬于2個子集（否則在一些子集中添加一些元素，上述條件仍然成立），由抽屜原理，必有一個子集，設(shè)為A，至少含有＝8個元素，又設(shè)其它14個子集為．考察不含A的任何7個子集，都對應(yīng)X中的41個元素，所有不含A的7－子集組一共至少對應(yīng)個元素．另一方面，對于元素a，若，則中有2個含有a，于是a被計算了次；若，則中有一個含有a，于是a被計算了次，于是

，

由此可得，矛盾．

其次證明．

用反證法．假定，設(shè)，令

，

．

顯然，，，

于是,對其中任何3個子集，

必有2個同時為，或者同時為，其交為空集

對其中任何7個子集，有

              

任何3個子集的交為空集，所以n≥41.

綜上所述，n的最小值為41．