集合的方法

1 第二章 集合 第三节 集合的方法

（分类原则，极端原理，容斥原理与抽屉原理）

一、基本知识和方法 当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择. 集合的划分反映了集合与子集之间的关系，这既是一类数学问题，也是数学中的解题策略——分类思想的基础. 1. 覆盖与划分——分类讨论的根据 将整体分解为部分，也就是将有限集A表示成它的一组两两互异的非空真子集123,,,nAAAA的并集，即12nAAAA，其中iAA，(1,2,)iAin,则集合12{,,,}nAAA叫做集合A的一个覆盖. 一个特殊情况是，集合中的任意两个集合都不相交，这时我们称集合为集合A的一个（完全）划分.即是集合A的一个覆盖，且()ijAAij. 如为集合A的划分，则对集合A的计数可通过熟知的加法公式 123||||||||||nAAAAA ①

进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事. 我们可以考虑通过对任意的集族中的子集的计数来计算||A，当集族中至少存在两个集合的交非空时，我们称这个覆盖为集合A的不完全划分. 对于集合A的不完全划分，显然有

12||||||||nAAAA ②

因为在计算iA时出现了对某些元素的重复计数，为了计算||A，就得将②式右边重复计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的工作. 2. 容斥原理 完成上述工作的准则就是容斥原理，是十九世纪英国数学家西尔维斯提出的，容 2

斥原理有两个公式. （1）容斥公式 用A表示集合A的元素个数，则 ABABAB，

CBACBCABACBACBA，

此结论可以推广到n个集合的情况。 定理1 设则为有限集,),,2,1(niA

i

ninjiininjiiiniAAAAA11111||)1(|||||| ③ 容斥公式常用来计算至少具有某几个性质之一的元素的数目. （2）筛法公式 与容斥公式讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性质的元素的个数，即||21nAAA. 为此，我们先引入下面的引理. 引理1 设A关于全集I的补集为A，则.||||||IAA

引理2 ,11iniiniAA,11iniiniAA 利用两个引理改写公式③便得： 定理2 设),,2,1(niAi为有限集I的子集，

则||||||||111iniiniiniAIAA ninjiininjiiAAAAI111||)1(|||||| ④

3.极端原理 最小数原理一：设P是自然数集的一个非空子集，则P中必有最小数. 最小数原理二：设P是实数集的一个有限非空子集，则P中必有最小数. 上述的最小数原理又称为极端原理. 3

4.抽屉原理 我们考虑这么一个事实：任意给出3个自然数，那么其中一定有两个数之和能被2整除.我们把“奇数”和“偶数”各看成一个抽屉，把3个自然数按奇、偶性分别放入各自的抽屉，可知必有一个抽屉放入2个自然数，取这两个自然数，要么同是奇数，要么同是偶数，它们的和一定是偶数，故能被2整除.这个事实就可以抽象为抽屉原理. 抽屉原则常见的形式如下： （1） 把(1)nkk个物体，按照任意方式全部放入n个抽屉中，一定存在一个抽屉中至少有两个物体. （2） 把(1)mnkk个物体，按照任意方式全部放入n个抽屉中，一定存在一个抽屉中至少有1m个物体. （3） 把12+++(1)nmmmkk个物体，按照任意方式全部放入n个抽屉中，那么存在一个抽屉中至少放了1+1m个物体，或在第二个抽屉中至少放了

2+1m个物体，或在第n个抽屉中至少放了+1nm个物体.

（4） 把m个物体，按照任意方式全部放入n个抽屉中，有两种情况： 当n整除m时，一定存在一个抽屉中至少放入了mn个物体；

当n整除m时，一定存在一个抽屉中至少放入了1mn个物体. 一般来说，适合应用抽屉原理解决的数学问题具有如下特征：新给的元素具有任意性.如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着. 问题的结论是存在性命题，题目中常含有“至少有„„”、“一定有„„”、“不少于„„”、“存在„„”、“必然有„„”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果. 抽屉原理的解题思路： （1）认真领会题意，分析条件和要得到的结论，确定把什么条件看成是“抽屉”，把什么条件看成是“物体”。 （2）设计抽屉，设计好抽屉是解决这类数学问题的关键，抽屉的设计涉及很多数学知识，要抓住主要的基本关系进行分类，设计抽屉的性质和个数。 4

（3）应用抽屉原理得到必要的结论，再综合其它数学知识，解决具体问题。 下面再介绍抽屉原理的几种变形： 平均量重叠原理：把一个量S任意分成n份，则其中至少有一份不大于nS，也至少有一份不少于nS. 面积的重叠原理：在平面上有n个面积分别是12,,nAAA的图形，把这n个图形按任何方式一一搬到某一个面积为A的固定图形上去， （1）如果12nAAAA，则至少有两个图形有公共点； （2）如果12nAAAA，则固定图形中至少有一个点未被盖住. 二、典型例题 第一节 分类原则 有些数学问题涉及的对象较为复杂，统一解决有困难，于是就将这些对象分成“不重不漏”的若干类，然后逐类解决。分类的原则是：每次分类必须不重不漏，其理论根据就是集合的分划。 分类原则 设所研究的对象的全体形成集合M，12,,nAAA是M的一组非空子

集，且（1）()ijAAij，（2）MAUini1，那么这组子集叫做研究对象的全体的一个n—分类。其中每一个子集叫做所研究对象的一个类。 解题中的分类讨论是根据解题的需要自然进行的，有时还要进行多级分类。 例1 对任意Nkn,，令.321nnnnkS求S被2除所得的余数。 分析 因为)3(mod0)3(nm，)3(mod1)13(nm，)3(mod1)23(2rm，)3(mod2)23(12rm，所以对n按奇偶性分类是自然的。

解析：（1）当n为奇数时，设Nlln,12. 对于Nm，若3不能整除m，则 )3(mod)3(mod1)3(mod11)1(21222mmmmmlll； 若m|3，则)3(mod012mml. 5

于是，当n为奇数时对Nm总有).3(modmmn 从而).3(mod)654()321(321kS 当33tk或23tk时就有).)(3(mod0NtS 当13tk时就有

).)(3(mod1)]1()2()3[()654()321(321NtkkkkkS

（2）当n为偶数时对Nm由（1）知 3不能整除m)3(mod1nm，).3(mod0|3nmm 于是).3(mod)011()011(321kS 当33tk时（1+1+0）共有t+1组，故).3(mod22)011)(1(ttS 当23tk时（1+1+0）共有t组，且)3(mod1)1(nnkk，故)3(mod22112ttS； 当13tk时（1+1+0）共有t组，且，故有).3(mod12tS 综合（1）（2）可知，

当n为正奇数时有))(3(mod13,12333,0NttkttkS或；

当n为正偶数时有))(3(mod7939292,695919,1998949,0NttttktttktttkS或或，或或或或. 评注：这是一个二级划分的例子。首先按n的奇偶分成两大类，然后又将每一类对k按模3的剩余类分成三个小类。 分类实际上就是给研究对象增加限制条件，从而使解决问题的难度降低。如 例2 求集合B,C,使得}10,,2,1{CB,并且C的元素乘积等于B的元素和。 分析：这实际上是求特殊条件下集合方程的解。注意到集合B的元素和551021，而12054321，故知集合C至多有4个元素，这样我们可按|C|的可能值分成4类来讨论。 解析：因为12055102154321，所以集合C至多有4个元素。下 6

面对|C|分4种情况讨论如下： （1）C由一个元素构成。因为C的元素乘积不超过10，B的元素和至少为55—10=45.故此情况不成立； （2）C由两个元素构成，设为)(,yxyx，则yxxy55即 56)1)(1(yx，解得.7,6yx故}.10,9,8,5,4,3,2,1{},7,6{BC （3）C由三个元素构成，设为zyx，则zyxxyz55； 若3x，则zyxxyz5560543，无解！ 验证：若1x，则10,4zy，此时}.9,8,7,6,5,3,2{},10,4,1{BC 若2x，则107)12)(12(532zyzyyz为质数，无解！ （4）C由4个元素构成，设为tzyx，则必有1x，否则 551205432xyzt。这时 .2,54tzytzyyzt 如（3），3y无解，故只有.2y 这时105)12)(12(522tztzzt 解得.7,3tz从而}.10,9,8,6,5,4{},7,3,2,1{BC 综上，B,C有3组解。 练习： 1.对任意的0,0ba，求}},1,1min{max{22baba的值。

提示：可设0ba，令3222111bababa，拟分如下三种情况讨论：

（1）321ba，（2）0213ba，（3）0213ba 结论是：3222}},1,1min{max{baba（321ba） 2.证明：任何一个三角形可以被分割成三个多边形（包括三角形），其中之一为