2024中国数学奥林匹克(第二十一届全国中学生数学冬令营)试题及解(10)

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个

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库2024中国数学奥林匹克(第二十一届全国中学生数学冬令营)试题及解(10)在线全文阅读。