高中数学奥赛辅导 第七讲 抽屉原则、容斥原理

数学奥赛辅导 第七讲

抽屉原则、容斥原理

知识、方法、技能

I．抽屉原则 10个苹果放入9个抽屉中，无论怎么放，一定有一个抽屉里放了2个或更多个苹果.这个简单的事实就是抽屉原则.由德国数学家狄利克雷首先提出来的.因此，又称为狄利克雷原则. 将苹果换成信、鸽子或鞋，把抽屉换成信筒、鸽笼或鞋盒，这个原则又叫做信筒原则、鸽笼原则或鞋盒原则.抽屉原则是离散数学中的一个重要原则，把它推广到一般情形就得到下面几种形式： 原则一：把m个元素分成n类（m>n），不论怎么分，至少有一类中有两个元素. 原则二：把m个元素分成n类（m>n）

m

个元素； nm

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

n

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

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

mm

]表示不超过的最大nn

整数.

原则三：把m1 m2 m2 n 1个元素分成n类，则存在一个k，使得第k类至少

有mk个元素.

原则四：把无穷多个元素分成有限类，则至少有一类包含无穷多个元素.

以上这些命题用反证法极易得到证明，这里从略. 一般来说，适合应用抽屉原则解决的数学问题具有如下特征：新给的元素具有任意性.如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着. 问题的结论是存在性命题，题目中常含有“至少有 ”、“一定有 ”、“不少于 ”、“存在 ”、“必然有 ”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果. 对一个具体的可以应用抽屉原则解决的数学问题还应搞清三个问题： （1）什么是“苹果”？ （2）什么是“抽屉”？ （3）苹果、抽屉各多少？ 用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确. 用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.

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

X A1 A2 An.集合 {A1,A2, ,An}叫做集合X的一个覆盖.一个特殊情况是，

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

|X| |A1| |A2| |A3| |An| ①

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

|X| |A1| |A2| |An| ②

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

定理1 设Ai(i 1,2, ,n)为有限集,则 | Ai|

i 1n

|A|

i

i 1

n

|Ai Aj| ( 1)

n 1

| Ai| ③

i 1

n

1 i j n

A1/B,A2 A2/B,由加法公式有 证明：当n 1时,设A1 A2 B,A1

| |B| |A2|,|A1 | |B| |A1|,|A2

B||A1 A2| |A1 A2

| B| |A1 | |A2

(|A1| |B|) (|A2| |B|) |B| |A1| |A2| |A1 A2|

结论成立.

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

| Ai| | Ai| |Ak 1| |( Ai) Ak 1|

i 1

i 1k

i 1

k 1kk

| Ai| |Ak 1| | (Ai Ai 1)|

i 1k

i 1

k

k 1

|Ai|

i 1

1 i j k

|Ai Aj| ( 1)

| Ai| |Ak 1| Ai

i 1

i 1

k

k

k

k

Ak 1|

k 1i 1

1 i i k

|(Ai Ak 1) (Aj Ak 1)| ( 1)| (Ai Ak 1)|

i 1

|A|

i

|Ai Aj| ( 1)| Ai|知，

i 1

k

k 1

1 i j k 1

n k 1时结论成立.

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

如果将Ai看成具有性质Pi的元素的集合，那么X A1 A2 An就是至少具有n

个性质P1,P2, ,Pn之一的元素的集合. 因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目. 2．筛法公式 与容斥公式讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性质的元素的个数，即|A1 A2 An|. 为此，我们先引入下面的引理.

引理1 设A关于全集I的补集为A，则

|A| |A| |I|.

引理2 Ai Ai, Ai Ai,

i 1

i 1

i 1

i 1

n

n

n

n

引理简单证略. 利用二引理改写公式③便是

定理2 设Ai(i 1,2, ,n)为有限集I的子集，则| Ai| | Ai| |I| | Ai|

i 1

i 1

i 1

n

n

n

|I|

|A

i 1

n

i

|

1 i j n

|Ai Aj| ( 1)| Ai| ④

i 1

n

n

赛题精讲

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

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

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

P、Q、R，使PC

BCCAAB

,QA ,RB .显然 333

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

角是30°及60°.

设E1，E2是E的两个非空子集，且

E E1 E2,E1 E2 由抽屉原则P、Q、R中

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

设BC的点除P之外全属于E2，那么只要AB上有异于B的点S属于E2，设S在BC上的投影点为Ｓ′，则△SS′B为直角三角形. 再设AB内的每一点均不属于E2，即除B之外全属于E1，特别，R、A∈E1，于是A、Q、R∈E1，且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 设a1,a2,a3, 是严格上升的自然数列：

a1 a2 a3 ，

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

am xap yaq，

这里p q是两个正整数，而x,y是两个适当的整数. （第17届IMO第2题） 【证明】对严格上升的自然数列a1 a2 a3 ，取以a1为模的剩余类，则可分为a1类

{0}，{1}，{2}， ，{a1 1}.

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

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

aq ua1 r,

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

aq a1 r.

由于am aq,故 u,所以有

am a1 aq ua1 ( u)a1 aq.

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

am xa1 yaq.

显然，这里的p 1 q.

2222

例4：设x1,x2, ,xn为实数，满足x1 x2 x3 xn 1，求证：对于每一整数k 2，

存在不全为零的整数a1,a2, ,an,使得|ai| k 1(i 1,2, ,n)并且

|a1x1 a2x2 anxn|

(k 1).

kn 1

【证明】由柯西不等式得

222

(|x1| |x2| |xn|)2 (12 12 12)(x12 x2 x3 xn)