试题

设X是一个56元集合．求最小的正整数n，使得对X的任意15个子集，只要它们中任何7个的并的元素个数都不少于n，则这15个子集中一定存在3个，它们的交非空．

解：n的最小值为41．
首先证明n=41合乎条件．用反证法．假定存在X的15个子集，它们中任何7个的并不少于41个元素，而任何3个的交都为空集．因每个元素至多属于2个子集，不妨设每个元素恰好属于2个子集（否则在一些子集中添加一些元素，上述条件仍然成立），由抽屉原理，必有一个子集，设为A，至少含有[

2×56

15

]+1=8个元素，又设其它14个子集为A₁，A₂，A₁₄．考察不含A的任何7个子集，都对应X中的41个元素，所有不含A的7-子集组一共至少对应41C₁₄⁷个元素．另一方面，对于元素a，若a·A，则A₁，A₂，A₁₄中有2个含有a，于是a被计算了C₁₄⁷-C₁₂⁷次；若a∈A，则A₁，A₂，A₁₄中有一个含有a，于是a被计算了C₁₄⁷-C₁₃⁷次，于是
41C₁₄⁷≤（56-|A|）（C₁₄⁷-C₁₂⁷）+|A|（C₁₄⁷-C₁₃⁷），
=56（C₁₄⁷-C₁₂⁷）-|A|（C₁₃⁷-C₁₂⁷），
≤56（C₁₄⁷-C₁₂⁷）-8（C₁₃⁷-C₁₂⁷），
由此可得196≤195，矛盾．
其次证明n≥41．
用反证法．假定n≤40，设X=1，2，56，
令A_i={i，i+7，i+14，i+21，i+28，i+35，i+42，i+49，·i=1，2，…，7}，B_j={j，j+8，j+16，j+24，j+32，j+40，j+48，j=1，2，…，8}．
显然，|A_i|=8（i=1，2，…，7），|A_i∩A_j|=0（1≤i＜j≤7），|B_j|=7（j=1，2，…，8），
|B_i∩B_j|=0（1≤i＜j≤8），|A_i∩B_j|=1（1≤i≤7，1≤j≤8），
于是，对于其中任何3个子集，必有2个同时为A_i，或者同时为|B_j|，其交集为空集．
对其中任何7个子集A_i1，A_i2，…A_is，B_j1，B_j2，…B_jt（s+t=7），
有|A_i1∪A_i2∪…A_is∪B_j1∪B_j2∪…∪B_jt|，
=|A_i1|+|A_i2|+…+|A_is|+|B_j1|+|B_j2|+…+|B_jt|-st，
=8s+7t-st，
=8s+7（7-s）-s（7-s），
=（s-3）²+40≥40，
任何3个子集的交集为空集，所以n≥41．
综上所述，n的最小值为41．
解：n的最小值为41．
首先证明n=41合乎条件．用反证法．假定存在X的15个子集，它们中任何7个的并不少于41个元素，而任何3个的交都为空集．因每个元素至多属于2个子集，不妨设每个元素恰好属于2个子集（否则在一些子集中添加一些元素，上述条件仍然成立），由抽屉原理，必有一个子集，设为A，至少含有[

2×56

15

]+1=8个元素，又设其它14个子集为A₁，A₂，A₁₄．考察不含A的任何7个子集，都对应X中的41个元素，所有不含A的7-子集组一共至少对应41C₁₄⁷个元素．另一方面，对于元素a，若a·A，则A₁，A₂，A₁₄中有2个含有a，于是a被计算了C₁₄⁷-C₁₂⁷次；若a∈A，则A₁，A₂，A₁₄中有一个含有a，于是a被计算了C₁₄⁷-C₁₃⁷次，于是
41C₁₄⁷≤（56-|A|）（C₁₄⁷-C₁₂⁷）+|A|（C₁₄⁷-C₁₃⁷），
=56（C₁₄⁷-C₁₂⁷）-|A|（C₁₃⁷-C₁₂⁷），
≤56（C₁₄⁷-C₁₂⁷）-8（C₁₃⁷-C₁₂⁷），
由此可得196≤195，矛盾．
其次证明n≥41．
用反证法．假定n≤40，设X=1，2，56，
令A_i={i，i+7，i+14，i+21，i+28，i+35，i+42，i+49，·i=1，2，…，7}，B_j={j，j+8，j+16，j+24，j+32，j+40，j+48，j=1，2，…，8}．
显然，|A_i|=8（i=1，2，…，7），|A_i∩A_j|=0（1≤i＜j≤7），|B_j|=7（j=1，2，…，8），
|B_i∩B_j|=0（1≤i＜j≤8），|A_i∩B_j|=1（1≤i≤7，1≤j≤8），
于是，对于其中任何3个子集，必有2个同时为A_i，或者同时为|B_j|，其交集为空集．
对其中任何7个子集A_i1，A_i2，…A_is，B_j1，B_j2，…B_jt（s+t=7），
有|A_i1∪A_i2∪…A_is∪B_j1∪B_j2∪…∪B_jt|，
=|A_i1|+|A_i2|+…+|A_is|+|B_j1|+|B_j2|+…+|B_jt|-st，
=8s+7t-st，
=8s+7（7-s）-s（7-s），
=（s-3）²+40≥40，
任何3个子集的交集为空集，所以n≥41．
综上所述，n的最小值为41．