当前位置：搜档网 › 抽屉原理和容斥原理

抽屉原理和容斥原理

I ．抽屉原则

10个苹果放入9个抽屉中，无论怎么放，一定有一个抽屉里放了2个或更多个苹果.这

个简单的事实就是抽屉原则.由德国数学家狄利克雷首先提出来的.因此，又称为狄利克雷原则.

将苹果换成信、鸽子或鞋，把抽屉换成信筒、鸽笼或鞋盒，这个原则又叫做信筒原则、

鸽笼原则或鞋盒原则.抽屉原则是离散数学中的一个重要原则，把它推广到一般情形就得到下面几种形式：原则一：把m 个元素分成n 类（m >n ），不论怎么分，至少有一类中有两个元素. 原则二：把m 个元素分成n 类（m >n ）

（1）当n |m 时，至少有一类中含有至少

n m

个元素；（2）当n |m 时，至少有一类中含有至少[n

]+1个元素.

其中n m 表示n 是m 的约数，n m 表示n 不是m 的约数，[

n m ]表示不超过n

的最大整数.

原则三：把1221+-+++n m m m 个元素分成n 类，则存在一个k ，使得第k 类至

少有k m 个元素. 原则四：把无穷多个元素分成有限类，则至少有一类包含无穷多个元素. 以上这些命题用反证法极易得到证明，这里从略.

一般来说，适合应用抽屉原则解决的数学问题具有如下特征：新给的元素具有任意性.

如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着. 问题的结论是存在性命题，题目中常含有“至少有……”、“一定有……”、“不少于……”、“存在……”、“必然有……”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果. 对一个具体的可以应用抽屉原则解决的数学问题还应搞清三个问题：（1）什么是“苹果”？

（2）什么是“抽屉”？（3）苹果、抽屉各多少？

用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定

的小范围内考虑问题，从而使问题变得简单明确. 用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律. 用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律. 用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”. Ⅱ. 容斥原则当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择.将整体分解为部分也就是将有限集X 表示成它的一组两两互异的非空真子集A 1，A 2，…A n 的并集，即

},,,{.2121n n A A A A A A X ==?集合叫做集合X 的一个覆盖.一个特殊情况

是，集族?中的任意两个集合都不相交，这时我们称集族?为集合X 的一个（完全）划分.如?为集合X 的划分，则对集合X 的计数可通过熟知的加法公式

||||||||||321n A A A A X ++++= ①

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

||||||||21n A A A X +++< ②

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

定理1 设则为有限集,),,2,1(n i A i =

∑∑

=≤<≤=-=-++-

i n

j i i n

i n j i i

i n

i A A A A

A 1

1||)

1(|||||| ③

证明：当,/,/,,12211

21B A A B A A B A A n ='='== 设时由加法公式有

||||||||)||(||)||(|||||||||||,||||||,|||||2121212

12122

11A A A A B B A B A B A A B A A A A A B A A B A -+=+-+-=++'+'=''==+'=+'

结论成立.

若n =k 时结论成立，则由

∑∑

∑=≤<≤=+=-+=+=+=+=+=-+-++-

=-+=-+=k

i k

j i k

i i k i k

i k j i i i i k

i k i k

i k i k i i k i A A A A A A A A A A A A A A A 1

1111

||||)

1(|||||

)(||||||

)(|||||||

∑

≤<≤+=+++-+-+

i i k i k

i k

k j k i k A A A A A A A 111

111|)(|)1(|)()(||

∑∑

+=+≤<≤+=-++-

=11

111

||)1(||||k i k j i i k i k

j i i

A A A A

知，

1+=k n 时结论成立.

由归纳原理知，对任意自然数n ，公式③成立. 公式③称为容斥公式，显然它是公式①的推广.

如果将i A 看成具有性质i P 的元素的集合，那么n A A A X 21=就是至少具有n

个性质n P P P ,,,21 之一的元素的集合. 因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目.

数学是一门非常迷人的学科，久远的历史，勃勃的生机使她发展成为一棵枝叶茂盛的参天大树，人们不禁要问：这根大树到底扎根于何处？为了回答这个问题，在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。

集合是一种基本数学语言、一种基本数学工具。它不仅是高中数学的第一课，而且是整个数学的基础。对集合的理解和掌握不能仅仅停留在高中数学起始课的水平上，而要随着数学学习的进程而不断深化，自觉使用集合语言(术语与符号)来表示各种数学名词，主动使用集合工具来表示各种数量关系。如用集合表示空间的线面及其关系，表示平面轨迹及其关系、表示方程(组)或不等式(组)的解、表示充要条件，描述排列组合，用集合的性质进行组合计数等。有限集元素的个数(容斥原理) 请看以下问题：

开运动会时，高一某班共有28名同学参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳比赛和田径比赛的有3人，同时参加游泳比赛和球类比赛的有3人，没有人同时参加三项比赛，

问同时参加田径比赛和球类比赛的有多少人？只参加游泳一项比赛的有多少人？

解决这个问题需要我们研究集合元素的个数问题(请读者参阅高中教材《数学》第一册(上)P23－P23阅读材料“集合元素的个数”。)

为此我们把有限集合A的元素个数记作card(A)

可以证明：

(1) card(A∪B)＝card(A)＋card(B)－card(A∩B)；

(2) card(A∪B∪C)=card(A)+card(B)+card(C)

-car d(A∩B)-card(A∩C)-card(B∩C)

+card(A∩B∩C)

如下图所示：

由图1－3－1，有

card(A∪B)=①+②+③=(①+②)+(②+③)-②＝

card(A)+card(B)-card(A∩B)

card(Cu(A∪B))=card(U)-card(A∪B)=card(U)-card(A)-card(B)+card(A∩B)

又由图1－3－2，有

card(A∪B∪C)=①+②+③+④+⑤+⑥+⑦＝

(①+④+⑤+⑦)+(②+⑤+⑥+⑦)+(③+④+⑥+⑦)-(⑤+⑦)-(⑥+⑦)-(④+⑦)+⑦＝

card(A)+card(B)+card(C)-card(A∩B)-card(A∩C)-card(B∩C)+card(A∩B∩C)

现在我们可以来回答刚才的问题了：

设A＝{参加游泳比赛的同学}，B＝{参加田径比赛的同学}，C＝{参加球类比赛的同学}

则card(A)=15，card(B)=8，card(C)=14，card(A∪B∪C)=28

且card(A∩B)=3，card(A∩C)=3，card(A∩B∩C)=0

由公式②得28＝15＋8＋14－3－3－card(B∩C)+0

即card(B∩C)=3

所以同时参加田径和球类比赛的共有3人，而只参加游泳比赛的人有15－3－3＝9(人)

例6．计算不超过120的合数的个数

分析1：用“筛法”找出不超过120的质数(素数)，计算它们的个数，从120中去掉质数，再去掉“1”，剩下的即是合数。

解法1：120以内：

① 既不是素数又不是合数的数有一个，即“1”；

② 素数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、

53、59、61、67、71、73、79、83、89、97、101、103、107、109、113、共30个。

所以不超过120的合数有120－1－30＝89(个)

(附：筛法：从小到大按顺序写出1－120的所有自然数：

先划掉1，保留2，然后划掉2的所有倍数4,6，…120等；保留3，再划掉所有3的倍数6,9…117、120等；保留5，再划掉5的所有倍数10,15，…120；保留7，再划掉7的所有倍数，…这样，上面数表中剩下的数就是120以内的所有素数，这种方法是最古老的寻找素数的方法，叫做“埃斯托拉‘筛法’”) 说明：当n 不很大时，计算1－n 中的合数的个数困难不大；但当n 很大时，利用筛法就很困难、很费时了，必须另觅他途。

[分析2]受解法1的启发，如果能找出1－n 中质数的个数m ，则n －1－m 就是不超过n 的合数的个数。由初等数论中定理：a 是大于1的整数。如果所有不大于√a 的质数都不能整除a ，那么a 是质数。因为120<121＝112，√120<11，所以不超过120的合数必是2或3或5或7的倍数，所以只要分别计算出不超过120的2、3、5、7的倍数，再利用“容斥原理”即可。

解法2：设S 1＝{a∣1≤3≤120,2∣a}；S 2＝{b∣1≤b≤120,3∣b}；S 3＝{c∣1≤3≤120,5∣c}；S 4={d∣1≤d≤120,7∣d}，则有：

card(S 1)＝[120/2]=60，card(S 2)＝[120/3]＝40，card(S 3)＝[120/5]＝24，card(S 4)＝[120/7]＝17；

([n]表示n 的整数部分，例如[2,4]＝2，…)

card(S 1∩S 2)＝[120/2×3]＝20，card(S 1∩S 3)＝[120/2×5]＝12， card(S 1∩S 4)＝[120/2×7]＝8，card(S 2∩S 3)＝[120/3×5]＝8， card(S 2∩S 4)＝[120/3×7]＝5，card(S 3∩S 4)[120/5×7]＝3，

card(S 1∩S 2∩S 3)[120/2×3×5]＝4，card(S 1∩S 2∩S 4)＝[120/2×3×7]＝2，

card(S 1∩S 3∩S 4)＝[120/2×5×7]＝1，card(S 2∩S 3∩S 4)＝[120/3×5×7]＝1，

card(S 1∩S 2∩S 3∩S 4)＝[120/2×3×5×7]＝0

∴card(S 1∪S 2∪S 3∪S 4)＝card(S 1)＋card(S 2)＋card(S 3)＋card(S 4)－card(S 1∩S 2)－card(S 1∩S 3)－card(S 1∩S 4)－card(S 2∩S 3)－card(S 2∩S 4)－card(S 3∩S 4)＋card(S 1∩S 2∩S 3)＋card(S 1∩S 2∩S 4)＋card(S 1∩S 3∩S 4)＋card(S 2∩S 3∩S 4)－card(S 1∩S 2∩S 3∩S 4)＝(60＋40＋24＋17)-(20+12+8+8+5+3)+(4+2+1+1)-0＝141-56＋8＝93 ∵2，3，5，7是质数 ∴93－4＝89

即不超过120的合数共有89个。四、有限集合子集的个数

问题：

(1) 集合{a}一共有几个子集？

(2) 集合{a，b}一共有几个子集？

(3) 集合{a,b,c}一共有几个子集？

(4) 集合{a,b,c,d}一共有几个子集？

(5) 猜想集合{a

1,a

…，a

}一共有几个子集？

(6) 利用上述猜想确定符合下列条件的集合M的个数：

{1,2}M{1,2，3,4，5,6，7,8，9,10}。

以上诸问题都牵涉到有限集合子集的个数问题。

有限集合{a}的子集有：φ，{a}；共两个

有限集合{a,b}的子集有：φ，{a}，{b}，{a,b}；共4＝22个；

有限集合{a,b,c}的子集有：φ；{a}，{b}，{c}；{a,b}，{a,c}，{b,c}；{a,b,c}；8＝23个；

有限集合{a,b,c,d}的子集有：φ；{a}，{b}，{c}，{d}；{a,b}，{a,c}，{a,d}，{b,c}，{b,d}，{c,d}；{a,b,c}，{a,b,d}，{a,c,d}，{b,c,d}； {a,b,c,d}；共16＝24个。这里，{a,b,c,d}的子集可以分成两部分，一部分不包括d，是{a,b,c}的子集；另一部分包括d，是{a,b,c}中每一个子集与{d}的并集。

循此思路，注意到2，4＝22，8＝23，16＝24的规律，可以猜想有限集合{a

1,a

…，

}的子集共有2n个，其中非空子集有2n－1个；真子集也有2n－1个，非空真子集有2n－1－1＝2n－2个。

利用上述猜想，问题(6)中集合M的个数应当有28＝256个。

例7．一个集合含有10个互不相同的两位数。试证，这个集合必有2个无公共元素的子集合，此两子集的各数之和相等。

分析：两位数共有10,11，……,99，计99－9＝90个，最大的10个两位数依次是90,91，……,99，其和为945，因此，由10个两位数组成的任意一个集

合中，其任一个子集中各元素之和都不会超过945，而它的非空子集却有210－1＝1023个，这是解决问题的突破口。

解：已知集合含有10个不同的两位数，因它含有10个元素，故必有210＝1024个子集，其中非空子集有1023个，每一个子集内各数之和都不超过90＋91＋…98＋99＝945<1023，根据抽屉原理，一定存在2个不同的子集，其元素之和相等。如此2个子集无公共元素，即交集为空集，则已符合题目要求；如果这2个子集有公共元素，则划去它们的公共元素即共有的数字，可得两个无公共元素的非空子集，其所含参数之和相等。

说明：此题构造了一个抽屉原理模型，分两步完成，计算子集中数字之和最多有945个“抽屉”，计算非空子集得1023个“苹果”，由此得出必有两个子集数字之和相等。第二步考察它们有无公共元素，如无公共元素，则已符合要求；如有公共元素，则去掉相同的数字，得出无公共元素并且非空的两个子集，满足条件。可见，有限元素子集个数公式起了关键作用。例8．设A ＝{1,2，3，…，n}，对X A ，设X 中各元素之和为N x ，求N x 的

总和

∑?A

X x

解：A 中共有n 个元素，其子集共有2n 个。A 中每一个元素在其非空子集中都出现了2n-1次，(为什么？因为A 的所有子集对其中任一个元素i 都可分为两类，一类是不含i 的，它们也都是{1,2，…，i-1,i+1,…n}的子集，共2n-1个；

另一类是含i 的，只要把i 加入到刚才的2n-1

个子集中的每一个中去)。因而求A 的所有子集中所有元素之和Nx 的总和时，A 中每一个元素都加了2n-1次，即出现了2n-1次，故得

∑?A

X x

＝1×2n-1＋2×2n-1＋…＋n……2n-1＝(1＋2＋…＋n)·2n-1＝

n(n+1)/2×2n-1＝n(n+1)×2n-2

说明：这里运用了整体处理的思想及公式1＋2＋…＋n ＝(1/2)n(n+1)，其理论依据是加法的交换律、结合律、乘法的意义等。得出集合中每一个元素都在总和中出现了2n-1次，是打开解题思路之门的钥匙孔。赛题精讲

例1设ABC 为一等边三角形，E 是三边上点的全体. 对于每一个把E 分成两个不相交子集

的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点？（第24届IMO 第4题）

【证明】如图I —3—2—1，在边BC 、CA 、AB 上分别取三点

P 、Q 、R ，使.3

,3,3AB

RB CA QA BC PC ===

显然 △ARQ ，△BPR ，△CQP 都是直角三角形. 它们的锐

角是30°及60°.

设E 1，E 2是E 的两个非空子集，且

==2121,E E E E E 由抽屉原则P 、Q 、R 中

至少有两点属于同一子集，不妨设P 、Q ∈E 1. 如果BC 边上除P 之外还有属于E 1的点，那么结论已明.

设BC 的点除P 之外全属于E 2，那么只要AB 上有异于B 的点S 属于E 2，设S 在BC 上的投影点为Ｓ′，则△SS ′B 为直角三角形. 再设AB 内的每一点均不属于E 2，即除B 之外全属于E 1，特别，R 、A ∈E 1，于是A 、Q 、R ∈E 1，且AQR 为一直角三角形. 从而命题得证.

【评述】此例通过分割图形构造抽屉. 在一个几何图形内有若干已知点，我们可以根据问题

的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决.

例2：在1，4，7，10，13，…，100中任选出20个数，其中至少有不同的两组数，其和都

等于104，试证明之. （第39届美国普特南数学竞赛题）

【证明】给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交

的集合.

{1}，{52}，{4，100}，{7，97}，…{49，55}. 且把它们分作是18个抽屉，从已知的34个数中任取20个数，即把前面两个抽屉

中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104.

【评述】此例是根据某两个数的和为104来构造抽屉. 一般地，与整数集有关的存在性问题

也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成抽屉. 例3 设 ,,,321a a a 是严格上升的自然数列：

<<<321a a a ，

求证：在这个数列中有无穷多个m a 可以表示为

q p m ya xa a +=，

这里q p ≠是两个正整数，而y x ,是两个适当的整数. （第17届IMO 第2题）【证明】对严格上升的自然数列 <<<321a a a ，取以1a 为模的剩余类，则可分为1a 类 {0}，{1}，{2}，…，{11-a }.

考虑无穷数列,,,32 a a 由抽屉原则，其中有无穷多项属于同一类，不妨设这一剩余类

是{r}，且记其中数值最小的那一项为q a ，显然1>q ，于是

,1r ua a q +=

其中的u 是某个正整数，其他的属于这一剩余类的任一项m a 可表示为

.1r a a q +=ν

由于,,u a a q m >>ν故所以有

.)(111q q m a a u ua a a a +-=-+=νν

令u x -=ν，这是一个正整数，再令1=y ，则上式成为

.1q m ya xa a -=

显然，这里的q p <=1.

例4：设n x x x ,,,21 为实数，满足12

232221=++++n x x x x ，求证：对于每一整数2≥k ，

存在不全为零的整数),,2,1(1||,,,,21n i k a a a a i n =-≤使得并且

)1(||2211--≤

+++n n n k n

k x a x a x a

【证明】由柯西不等式得 ))(111(|)||||(|2

232221222221n n x x x x x x x +++++++≤+++

即n x x x n ≤

+++||||||21 .

所以，当有时,10-≤≤k a i

||||||2211n n x a x a x a +++

)1(|)||||)(|1(21n k x x x k n -≤+++-≤

把区间))1(,0[n k -等分成12

-k 个小区间，每个小区间的长度为

)1(--n

k n

k ，由于

每个i a 能取k 个整数，因此n

n n k x a x a x a 共有||||||2211+++ 个正数，由抽屉原则

知必有二数会落在同一个小区间之内，设它们分别是

||||1

i n

i i i

i i x a x

a ∑∑=='''与，

因此有∑=--≤

''-'n

i n

i i i k n

k x a a 1

)1(|||)(|

① 很明显，我们有

.,,2,1,1||n i k a a i i =-≤''-'

现在取??

?<'-''≥''-'=)

0(,

)0(,

i i i i i i i x a a x a a a 如果如果

这里i =1,2,…,n ，于是①可表示为

∑=--≤

i n i i k n

k x a 1

)1(||

这里i a 为整数，适合.,,2,1,1||n i k a i =-≤

【评述】如上例所示，在证明存在某些有界量使相关的不等式成立时，可类似地把某区间

划分为若干小区间作为抽屉，借用抽屉原则来证明.

例5：一个国际社团的成员来自六个国家共有1978人，用1，2，…，1977，1978来编号，

试证明：该社团至少有一个成员的编号或者与他的两个同胞的编号之和相等，或者是其中一个同胞的编号的两倍. （第20届IMO 第6题）

【证明】可用反证法来证明与本题完全相当的下列问题：把整列1，2，…，1978按任一方

式分成六组，则至少有一组具有这样的性质：其中有一个数或等于四组中其他两数之和，或等于其中某一个数的两倍. 假设这六组中的每一组数都不具备上述性质，也就是说每一组数都具备下列性质，记作性质（P ）：同组中任何两数之差必不在此组中.

因为如果有b a ,连同b a -都在同一组中，那么由)(b a b a -+=可知，这组已具备题

目所要求的性质. 因1978÷6>329，所以由抽屉原则可以肯定有一个组A ，其中至少有380个正整数，现在从A 中任意取出330个数业，记其中最大的那个数为1a ，把1a 分别减去其余329个数而得到329个差，它们互不相等且均小于1978. 由性质（P ），它们不会再在组A 中，即应属于其余五组. 又因329÷5÷>65.再由抽屉原则可以肯定有一组B ，其中至少含有上述329个数中的66个数，从B 中任取66个数且记其中最大的那个数为b 1，再把b 1减去其余65个数，得出的差显然不再属于B ，当然也不会属于A. 假如其中的某一个数b b -1属于A ，由于1b 与b 分别可以写为

a a

b a a b -='-=111,

其中a a '与都属于A ，于是 a a a a a a b b '-=--'-=-)()(111

这就同A 具备性质（P ）的假设相违背，这就是说上述65个数必属其余四个数组. 由于65÷4>16，所以至少有一组，称为C ，至少会有上述65个整数中的17个，反复进行上述推理，最后可得一数组F ，其中至少会有两个数，大数与小数之差是一个小于1978的正整数，可是它不在A 、B 、C 、D 、E 、F 的任一组中，这显然是一个矛盾，这矛盾说明至少有一组数不具备性质（P ）.即题目的结论是正确的.

【评述】我们容易发现，如果把此题中1978改为任何一个不小于1957的正整数后其结论

仍是成立的. 上例的解答过程说明了对有些数学问题需要我们连续运用抽屉原则，而且每构造一次抽屉都把范围缩小一些.

例6：已知1与90之间的19个（不同的）正整数，两两的差中是否一定有三个相等？（匈

牙利数学竞赛题，1990年）

【证明】设这19个数为 .9011921≤<<<≤a a a

由于)()()(1217181819119a a a a a a a a -++-+-=- ，若右边的18个差中无三个相等，而只有两个相等，且取最小的，则 ,90)921(2119=+++?>- a a

这与89190119=-≤-a a 矛盾. 所以两两的差中定有三个相等. 抽屉原则实际上都是重叠原则，这里再介绍抽屉原则的几种变形：

平均量重叠原则：把一个量S 任意分成n 份，则其中至少有一份不大于n

，也至少有一份不少于

S . 面积的重叠原则：在平面上有n 个面积分别是A 1，A 2，…，A n 的图形，把这n 个图形按任何方式一一搬到某一个面积为A 的固定图形上去，

（1）如果A 1+A 2+…+A n >A ，则至少有两个图形有公共点；

（2）如果A 1+A 2+…+A n