高二数学竞赛班讲义 第六讲 组合问题

《高二数学竞赛班讲义 第六讲 组合问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、高二数学竞赛班二试第六讲组合问题班级姓名一、知识要点：组合数学是一个既古老又年轻的离散数学分支，竞赛中的组合问题主要包括组合计数问题、组合极值问题、存在性问题、操作变换问题、组合几何问题以及图论中的问题，求解竞赛中的组合问题并不是需要复杂的数学知识，然而在趣味性命题的陈述下包含了高超的解题技巧，无论是从智力训练的角度，还是从竞赛准备的角度考虑，理解和钻研这些问题都是十分有意义的．在解决组合问题时，有时会用到以下几个原理．1、极端原理原理1设M是自然数集的一个非空子集，则M中必有最小数．原理2设M是实数集的一个有限的

2、非空子集，则M中必有最小数．2、抽屉原理把5个苹果放到4个抽屉中，必然有一个抽屉中至少有2个苹果，这是抽屉原理的通俗解释。一般地，我们将它表述为：把（mn＋1）个物体放入n个抽屉，其中必有一个抽屉中至少有（m＋1）个物体。使用抽屉原理解题，关键是构造抽屉。一般说来，数的奇偶性、剩余类、数的分组、染色、线段与平面图形的划分等，都可作为构造抽屉的依据。第一抽屉原理若将m个小球放入n个抽屉中，则必有一个抽屉内至少有个小球．第二抽屉原理若将m个小球放入n个抽屉中，则必有一个抽屉内至多有个小球．3、算两次原理所谓算两次原理（

3、又称富比尼原理）就是对同一个量，如果用两种不同的方法去计算，所得的结果应相等．二、经典例题例1．（2008年山西省预赛试题）设M20＝｛1，2，…，2008｝是前2008个正整数组成的集合，A＝｛，，…｝是M的一个30元子集，已知A中的元素两两互质，证明A中至少一半元素是质数．分析考查集合A中的合数a，设p是a的最小质因数，则p≤.又a≤2008，于是p≤45，再由A中的元素两两互质，可以证明A中16个元素中必有一个是质数，进而可以导出结论．证明先证明：A中16个元素中必有一个是质数．为此，任取16个元素，不妨设为

4、，，…，，若其中没有质数，则它们中至多一个为1，其余15个皆为合数．设，，…，都是合数，则每个数皆可分解成至少两个质因数的乘积，若是的最小质因数，则≤（i＝1，2，…，15）．由于A中的数两两互质，则，，…，互不相同，而将全体质数自小到大排列，第15个质数是47，所以，若是，，…，中的最大数，即有≥47，于是≥≥＞2008，即M，矛盾！因此，，，…，中必有质数，不妨设为质数，今从集合A中去掉，在剩下的29个元素中，再次进行同样的讨论，可知其中的16个元素中也必有一个是质数，设为.如此下去，可以连续进行15次，每次都

5、可从A中取到一个新的质数，因此A中至少有15个质数．说明本题利用极端原理，通过对合数的最小质因数的考查，获取集合A中元素的性质，进而完成了证明，这种方法也是数论中研究合数的一种重要策略．例2．已知A与B是集合｛1，2，3，…，100｝的两个子集，满足：A与B的元素个数相同，且A∩B为空集，若nA时总有2n+2B，则集合A∪B的元素个数最多为多少？分析该问题是组合构造，由条件“A与B的元素个数相同且若n∈A时总有2n+2∈B”知

6、A

7、＝

8、B

9、，且2n+2≤100，从而可知A中的元素不超过49个，为此需要进行分类考虑．

10、解首先证明

11、A∪B

12、≤66，只需要证明

13、A

14、≤33，由分析知需要证明：若A是｛1，2，3，…，49｝的任何一个34元子集，则必存在nA，使得2n+2A.证明如下：将｛1，2，3，…，49｝分成如下33个集合：｛1，4｝，｛3，8｝，｛5，12｝，…，20｛23，48｝，共12个；｛2，6｝，｛10，22｝，｛14，30｝，｛18，38｝，共4个；｛25｝，｛27｝，｛29｝，…，｛49｝，共13个；｛26｝，｛34｝，｛42｝，｛46｝，共4个．若A是｛1，2，3，…，49｝的任何一个34元的子集，则由抽屉原理可知

15、上述33个集合中至少有一个2元集合中的两个数均属于A，即存在n∈A，2n+2∈A.所以

16、A

17、≤33.事实上，如取A＝｛1，3，5，…，23，2，10，14，18，25，27，29，…，49，26，34，42，46｝，B＝｛2n+2

18、n∈A｝，则A，B满足题中要求，且

19、A∪B

20、＝66.所以集合A∪B的元素个数最多为66.说明将集合中的元素进行适当分会组，并结合抽屉原理使问题得以解决，这是解决类问题的常用手段.例3．(2007年浙江省预赛试题)设M＝｛1，2，…，65｝，AM为子集，若

21、A

22、＝33，且存在x，y∈A，x

23、＜y，x

24、y，则称A为“好集”，求最大的a∈M，使含a的任意33元子集为好集．分析首先要准确理解“好集”的含义，搞清楚“好集”中元素的构成规律，再来分析a的可能的取值．解令P＝｛21+i

25、i＝1，2，…，44｝—｛2（21+i）

26、i＝1，2，…，11｝，

27、p

28、＝33.显然对任意1≤i＜j≤44，不存在n≥3，使得21+j＝n(21+i)成立，故P是非好集．因