2006中国数学奥林匹克(第二十一届全国中学生数学冬令营)试题及解答
六、设X是一个56元集合．求最小的正整数n，使得对X的任意15个子集，只要它们中任何7个的并的元素个数都不少于n，则这15个子集中一定存在3个，它们的交非空．
解 n的最小值为41．
首先证明n 41合乎条件．用反证法．假定存在X的15个子集，它们中任何7个的并不少于41个元素，而任何3个的交都为空集．因每个元素至多属于2个子集，不妨设每个元素恰好属于2个子集（否则在一些子集中添加一些元素，上述条件仍然成立），由抽屉原理，必有一个子集，设为A，至少含有
2 56
115
＝8个元素，又设其它14个子集为A1,A2, ,A14．考察不含A的任何7个子集，
7
都对应X中的41个元素，所有不含A的7－子集组一共至少对应41C14个元素．另
一方面，对于元素a，若a A，则A1,A2, ,A14中有2个含有a，于是a被计算
77
C12次；,A了C14若a A，则A1,A2, 41
77
C13中有一个含有a，于是a被计算了C14
次，于是
41C14 (56 A)(C14 C12) A(C14 C13)
56(C14 C12) A(C13 C12)
56(C14 C12) 8(C13 C12)
7
7
7
7
77777
7777
，
由此可得196 195，矛盾．
其次证明n 41．
用反证法．假定n 40，设X 1,2, ,56 ，令
Ai i,i 7,i 14,i 21,i 28,i 35,i 42,i 49 ,
i 1,2, ,7，
Bj j,j 8,j 16,j 24,j 32,j 40,j 48 ,j 1,2, ,8．
显然，Ai 8(i 1,2 ，,,7),Ai Aj 0(1 i j 7)Bj 7(j 1,2, ,8)，
Bi Bj 0(1 i j 8)，Ai Bj 1(1 i 7,1 j 8)，于是，对其中任何
3个
