高二数学竞赛班二试
第六讲 组合问题
班级 姓名
一、知识要点：
组合数学是一个既古老又年轻的离散数学分支，竞赛中的组合问题主要包括组合计数问题、组合极值问题、存在性问题、操作变换问题、组合几何问题以及图论中的问题，求解竞赛中的组合问题并不是需要复杂的数学知识，然而在趣味性命题的陈述下包含了高超的解题技巧，无论是从智力训练的角度，还是从竞赛准备的角度考虑，理解和钻研这些问题都是十分有意义的．
在解决组合问题时，有时会用到以下几个原理． 1、极端原理
原理 1 设M是自然数集的一个非空子集，则M中必有最小数． 原理 2 设M是实数集的一个有限的非空子集，则M中必有最小数． 2、抽屉原理
把5个苹果放到4个抽屉中，必然有一个抽屉中至少有2个苹果，这是抽屉原理的通俗解释。一般地，我们将它表述为：把（mn＋1）个物体放入n个抽屉，其中必有一个抽屉中至少有（m＋1）个物体。
使用抽屉原理解题，关键是构造抽屉。一般说来，数的奇偶性、剩余类、数的分组、染色、线段与平面图形的划分等，都可作为构造抽屉的依据。
第一抽屉原理 若将m个小球放入n个抽屉中，则必有一个抽屉 内至少有?小球．
第二抽屉原理 若将m个小球放入n个抽屉中，则必有一个抽屉内至多有?3、算两次原理
所谓算两次原理（又称富比尼原理）就是对同一个量，如果用两种不同的方法去计算，所得的结果应相等．
?m?1???1个n???m?个小球． ??n?二、经典例题
例 1．（2008年山西省预赛试题）设M＝｛1，2，…，2008｝是前2008个正整数组成的集合，A＝｛a1，a2，…a30｝是M的一个30元子集，已知A中的元素两两互质，证
1
明A中至少一半元素是质数．
分析 考查集合A中的合数a，设p是a的最小质因数，则p≤a.又a≤2008，于是p≤45，再由A中的元素两两互质，可以证明A中16个元素中必有一个是质数，进而可以导出结论．
证明 先证明：A中16个元素中必有一个是质数．
为此，任取16个元素，不妨设为a1，a2，…，a16，若其中没有质数，则它们中至多一个为1，其余15个皆为合数．设a1，a2，…，a15都是合数，则每个数皆可分解成至少两个质因数的乘积，若pi是ai的最小质因数，则pi≤
．由ai（i＝1，2，…，15）
于A中的数两两互质，则p1，p2，…，p15互不相同，而将全体质数自小到大排列，第15个质数是47，所以，若p1是p1，p2，…，p15中的最大数，即有p1≥47，于是a122≥p1≥47＞2008，即a1?M，矛盾！
因此，a1，a2，…，a15中必有质数，不妨设a1为质数，今从集合A中去掉a1，在剩下的29个元素中，再次进行同样的讨论，可知其中的16个元素中也必有一个是质数，设为a2.如此下去，可以连续进行15次，每次都可从A中取到一个新的质数， 因此A中至少有15个质数．
说明 本题利用极端原理，通过对合数的最小质因数的考查，获取集合A中元素的 性质，进而完成了证明，这种方法也是数论中研究合数的一种重要策略．
例 2．已知A与B是集合｛1，2，3，…，100｝的两个子集，满足：A与B的元素个数相同，且A∩B为空集，若n?A 时总有2n+2?B，则集合A∪B的元素个数最多为多少？
分析 该问题是组合构造，由条件“A与B的元素个数相同且若n∈A时总有2n+2∈B”知|A|＝|B|，且2n+2≤100，从而可知A中的元素不超过49个，为此需要进行分类考虑．
解 首先证明|A∪B|≤66，只需要证明|A|≤33，由分析知需要证明：若A是｛1，2，3，…，49｝的任何一个34元子集，则必存在n?A，使得2n+2?A.
证明如下：
将｛1，2，3，…，49｝分成如下33个集合：
｛1，4｝，｛3，8｝，｛5，12｝，…，｛23，48｝，共12个；｛2，6｝，｛10，22｝，｛14，30｝，｛18，38｝，共4个；｛25｝，｛27｝，｛29｝，…，｛49｝，共13个；｛26｝，｛34｝，｛42｝，｛46｝，共4个．
2
若A是｛1，2，3，…，49｝的任何一个34元的子集，则由抽屉原理可知上述33个集合中至少有一个2元集合中的两个数均属于A，即存在n∈A，2n+2∈A.
所以|A|≤33.
事实上，如取A＝｛1，3，5，…，23，2，10，14，18，25，27，29，…，49，26，34，42，46｝，B＝｛2n+2|n∈A｝，则A，B满足题中要求，且|A∪B|＝66.
所以集合A∪B的元素个数最多为66.
说明 将集合中的元素进行适当分会组，并结合抽屉原理使问题得以解决，这是解决类问题的常用手段.
例 3． (2007年浙江省预赛试题)设M＝｛1，2，…，65｝，A?M为子集，若|A|＝33，且存在x ，y∈A，x＜y，x | y，则称A为“好集”，求最大的a∈M，使含a的任意33元子集为好集．
分析 首先要准确理解“好集”的含义，搞清楚“好集”中元素的构成规律，再来分析a的可能的取值．
解 令P＝｛21 + i | i ＝1，2，…，44｝— ｛2（21 + i）| i ＝ 1，2，…，11｝，| p | ＝ 33.
显然对任意1≤i＜j≤44，不存在n≥3，使得21+j ＝ n (21 +i )成立，故P是非好集． 因此a≤21，下面证明：包含21的任意一个33元子集A一定为好集． 设A ＝｛a1，a2，…，a32，21｝．
若1，3，7，42，63中之一为集合A的元素，显然A为好集 现考虑1，3，7，42，63都不属于集合A．构造集合：
A1 ＝｛2，4，8，16，32，64｝， A2 ＝｛5，10，20，40｝，
A3 ＝｛6，12，24，48｝，A4＝｛9，18，36｝， A5 ＝｛11，22，44｝，A6＝｛13，26，52｝， A7 ＝｛14，28，56｝，A8＝｛15，30，60｝， A9 ＝｛17，34｝，A10＝｛19，38｝，
A11 ＝｛23，36｝，A12＝｛25，50｝，
3
A13 ＝｛27，54｝，A14＝｛29，58｝， A15 ＝｛31，62｝，
A' ＝｛33，35，37，…，61，65｝，
由上可见，A1，A2，…，A15每个集合中两个元素都是倍数关系，考虑最不利的情
''况，即A?A，也即A中16个元素全部选作A的元素，A中剩下16个元素必须从A1，
A2，…，A15这15个集合中选取，根据抽屉原理，至少有一个集合有两个元素被选，即
集合A中至少有两个元素存在倍数关系．
综上所述，包含21的任意一个33 元子集A一定为好集，即a的最大值为21． 说明 对于这一类型的集合问题，一般都需要通过适当的方式构造出符合某种要求的集合，抽屉原理是解决集合构造问题的常用工具．
例4．（2008年甘肃省预赛试题）一个20行若干列的0、1数阵满足：各列互不相同且任意两列同一行都取1的行数不超过2．求当列数最多时，数阵中1的个数的最小值．
分析 由题设，对于数阵中1的个数超过3的列，保留其中任意3个1，而将其余的都变成0，得到的新数阵仍然满足要求，于是可知当列数最多时，数阵中至多包含1的个数不超过3的所有的列.这样可得列数最大值，进而求得此时数阵中1的个数的最小值．
解 对于满足条件的列数最大的一个数阵，如果这个数阵中某一列1的个数超过3个，那么就保留其中任意3个1，其余的都改变成0，这样就会得到一个列数相同并有仍然满足要求的一个新数阵，如果这个新数阵中还有1的个数超过3的列，则重复上述过程，最后可以得到一个列数最多，且每列中1的个数最多为3的满足要求的数列，它的列数最
123多为1+C20+C20+C20.
另一方面，构造一个满足要求的数阵如下：它包括没有1的列以及所有互不相同的只有一个1的列，2个1的列和3个1的列，由上所说，可知这个数阵的列数是最多的，同时在满足要求的列数最多的所有数阵中所有数阵中，该数阵中的1是最少的，此数阵的列数
123123为1+C20+C20+C20，此数列中1的个数是C20+2C20+3C20＝20+380+3420＝3820
说明 本题中求数阵的列数的最大值的方法叫做局部整法，它是解决最值问题的一种行之有效的方法，尤其是离散变量最值问题常常需要用到这种方法．
例 5．（2008年浙江省预赛试题）将3k（k为正整数）个石子分成五堆，如果通过每
4
次从其中3堆中各取走一个石子，而最后取完，则称这样的分法是“和谐的”，试给出和谐分法的充分必要条件，并加以证明．
分析 从整体上看，就是从3k个石子中每次取3个，恰好k次取完，于是和谐的分法就是要求每堆石子的个数不超过k，再用数学归纳法证明，最多一堆石子的个数不超过k的分法是和谐的．
解 分析是和谐的充分必要条件是最多一堆石子的个数不超过k． 下面设五堆石子的个数分别为a、b、c、d、e（其中a≥b≥c≥d≥e）．
“必要性”的证明：若分法是和谐的，则把a所对应的石子取完至少要取a次，这a次每次都要取走3个石子，如果a＞k，则3a＞3k，即把a所对应的一堆取完时，需取走的石子多于五堆石子的总数，矛盾，因此最多一堆石子的个数不能超过k.
“充分性”的证明：（数学归纳法）
（1）当k ＝ 1时，满足a≤k的分法只能是1、1、1、0、0．显然这样的分法是和谐的．
（2）假设k≤n时，若a≤k的分法是和谐的．
当k ＝ n+1时，若a≤n+1，且分法a、b、c、d、e是不和谐的，则分法a－1、b－1、c－1、d、e也是不和谐的．由（2）及必要性的证明，可知
max｛a－1，b－1，c－1，d，e｝＞n． 因为a≥b≥c≥d≥e，所以 max｛a－1，b－1，c－1，d，e｝ ＝max｛a－1，d｝＞n．
若a－1≥d，则有a－1＞n．这与a≤n+1矛盾． 若a－1＜d，则有
n ＜ d ≤ c ≤b ≤ a ≤ n+1，
从而有a ＝ b ＝ c ＝ d ＝ n+1，于是有 3（n+1）＝ a + b + c + d + e ＝ 4 (n+1) + e， 这是不可能的．
因此，当a≤n+1时，分法a、b、c、d、e是和谐的
说明 本题充分性的证明采用的是数学归纳法，这是一种归纳构造，它是利用构造思想解决存在性问题的一种重要手段
5