Question

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

Answer 1

解：n的最小值為41．
首先證明n=41合乎條件．用反證法．假定存在X的15個子集，它們中任何7個的并不少于41個元素，而任何3個的交都為空集．因每個元素至多屬于2個子集，不妨設每個元素恰好屬于2個子集（否則在一些子集中添加一些元素，上述條件仍然成立），由抽屜原理，必有一個子集，設為A，至少含有=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，利用交集與并集求得結果，兩者結合完成結論．
點評：此題考查反證法，充分考慮所證命題的反面的全面性，證明過程中與抽屜原理有機結合解決問題．