设X是一个56元集合求最小的正整数n【精品文档】
六、设X是一个56元集合(求最小的正整数n,使得对X的任意15个子集,只要它们中任何7个的并的元素个数都不少于n,则这15个子集中一定存在3个,它们的交非空(
解 n的最小值为41(
首先证明n,41合乎条件(用反证法(假定存在X的15个子集,它们中任何7个的并不少于41个元素,而任何3个的交都为空集(因每个元素至多属于2个子集,不妨设每个元素恰好属于2个子集(否则在一些子集中添加一些元素,
256,,,上述条件仍然成立),由抽屉原理,必有一个子集,设为A,至少含有,1,,15,,
AAA,,,,8个元素,又设其它14个子集为(考察不含A的任何7个子集,1214
741C都对应X中的41个元素,所有不含A的7,子集组一共至少对应个元素(另14
aA,AAA,,,一方面,对于元素a,若,则中有2个含有a,于是a被计算1214
7777CC,aA,CC,AAA,,,了次;若,则中有一个含有a,于是a被计算了141212141413次,于是
7777741(56)()()CACCACC,,,,, 1414121413
7777,,,,56()()CCACC 14121312
7777,,,,56()8()CCCC, 14121312
196195,由此可得,矛盾(
n,41其次证明(
X,1,2,,56n,40用反证法(假定,设,令 ,,
Aiiiiiiiii,,,,,,,,,,7,14,21,28,35,42,49,1,2,,7, ,,i
Bjjjjjjjj,,,,,,,,,8,16,24,32,40,48,1,2,,8( ,,j
AiAAij,,,,,,8(1,2,,7),0(17)Bj,,7(1,2,,8)显然,,,iijj
BBij,,,,0(18)ABij,,,,,1(17,18),,于是,对其中任何3个ijij
子集,必有2个同时为,或者同时为,其交为空集( ABij
AAABBBst,,,,,,,(7),,对其中任何7个子集,有 iiijjj1212st
AAABBBiiijjj1212st
,,,,,,,,,AAABBBstiiijjj1212st
,,,,,,,,8787(7)(7)ststssss
2, ,,,,(3)4040s
n,41( 任何3个子集的交为空集,所以
综上所述,n的最小值为41(