Question

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

Answer 1

解析：  n的最小值為41．

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

，

由此可得，矛盾．

其次證明．

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

，

．

顯然，，，

于是,對(duì)其中任何3個(gè)子集，

必有2個(gè)同時(shí)為，或者同時(shí)為，其交為空集

對(duì)其中任何7個(gè)子集，有

              

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

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