当前位置:首页 >> 学科竞赛 >>

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


数学奥赛辅导
知识、方法、技能

第七讲

抽屉原则、容斥原理
I.抽屉原则 10 个苹果放入 9 个抽屉中,无论怎么放,一定有一个抽屉里放了 2 个或更多个苹果.这 个简单的事实就是抽屉原则.由德国数学家狄利克雷首先提出来的.因此,又称为狄利克雷原 则. 将苹果换成信、鸽子或鞋,把抽屉换成信筒、鸽笼或鞋盒,这个原则又叫

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

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

m m ]表示不超过 的最大 n n

用抽屉原则解题的基本思想是根据问题的自身特点和本质,弄清对哪些元素进行分类, 找出分类的规律. 用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”. Ⅱ. 容斥原则 当我们试图对某些对象的数目从整体上计数碰到困难时,考虑将整体分解为部分,通过 对每个部分的计数来实现对整体的计数是一种明智的选择 .将整体分解为部分也就是将有限 集 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 |? ?| Ai | ?
i ?1 i ?1

n

n

1?i ? j ? n

?

| Ai ? A j | ? ? ? (?1) n?1 | ? Ai |
i ?1

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 ?1 k i ?1

k ?1

k

k

?| ? Ai | ? | Ak ?1 | ? | ? ( Ai ? Ai ?1 ) |
i ?1 k i ?1

k

? ? | Ai | ?
i ?1

1?i ? j ? k

?

| Ai ? A j | ? ? ? (?1) k ?1 | ? Ai | ? | Ak ?1 | ?? Ai ?
i ?1 i ?1
k

k

k

Ak ?1 | ?
k ?1 i ?1

1?i ?i ? k

?

| ( Ai ? Ak ?1 ) ? ( A j ? Ak ?1 ) | ? ? ? (?1) k | ? ( Ai ? Ak ?1 ) |
i ?1

? ? | Ai | ?

1?i ? j ? k ?1

?

| Ai ? A j | ? ? ? (?1) k | ? Ai | 知,
i ?1

k ?1

n ? k ? 1 时结论成立.
由归纳原理知,对任意自然数 n,公式③成立. 公式③称为容斥公式,显然它是公式①的推广. 如果将 Ai 看成具有性质 Pi 的元素的集合,那么 X ? A1 ? A2 ? ? ? An 就是至少具有 n 个性质 P 1, P 2 ,?, P n 之一的元素的集合. 因此,容斥公式常用来计算至少具有某几个性质之 一的元素的数目. 2.筛法公式 与容斥公式讨论的计数问题相反,有时需要计算不具有某几个性质中的任何一个性质的 元素的个数,即 | A1 ? A2 ? ?? An | . 为此,我们先引入下面的引理. 引理 1 设 A 关于全集 I 的补集为 A ,则

| A | ? | A |?| I | .
引理 2

i ?1

? Ai ? ? Ai , ? Ai ? ? Ai ,
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 | ?? | Ai | ?
i ?1

n

1?i ? j ? n

?

| Ai ? A j | ? ? ? (?1) n | ? Ai |
i ?1

n



赛题精讲
例 1 设 ABC 为一等边三角形, E 是三边上点的全体. 对于每一个把 E 分成两个不相交子集的 划分,问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点?(第 24 届 IMO 第 4 题) 【证明】如图 I—3—2—1,在边 BC、CA、AB 上分别取三点 P、Q、R,使 PC ?

BC CA AB , QA ? , RB ? . 显然 3 3 3

△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 上 的投影点为S′,则△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 ? ?,

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

am ? xa p ? 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 是某个正整数,其他的属于这一剩余类的任一项 a m 可表示为

aq ? ?a1 ? r.
由于 am ? aq , 故? ? u, 所以有

am ? ?a1 ? aq ? ua1 ? (? ? u)a1 ? aq .
令 x ? ? ? u ,这是一个正整数,再令 y ? 1 ,则上式成为

am ? xa1 ? yaq .
显然,这里的 p ? 1 ? q .
2 2 2 2 例 4:设 x1 , x2 ,?, xn 为实数,满足 x1 ? x2 ? x3 ? ? ? xn ? 1 ,求证:对于每一整数 k ? 2 ,

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

| a1 x1 ? a2 x2 ? ? ? an xn |?
【证明】由柯西不等式得

(k ? 1) n . k n ?1

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

即 | x1 | ? | x2 | ??? | xn |? 所以,当 0 ? ai ? k ? 1 时, 有

n.

a1 | x1 | ?a2 | x2 | ?? ? an | xn |

? (k ? 1)(| x1 | ? | x2 | ? ? ? | xn |) ? (k ? 1) n .
把区间 [0, (k ? 1) n ) 等分成 k ? 1 个小区间,每个小区间的长度为
2

(k ? 1) n ,由于 k n ?1

每个 a i 能取 k 个整数,因此 a1 | x1 | ?a2 | x2 | ?? ? an | xn | 共有k n 个正数,由抽屉原则知 必有二数会落在同一个小区间之内,设它们分别是

? ai? | xi | 与? ai?? | xi | ,
i ?1 i ?1

n

n

因此有 |

? (a? ? a??) | x
i ?1 i i

n

i

||?

(k ? 1) n k n ?1



很明显,我们有

| ai? ? ai?? |? k ? 1, i ? 1,2,?, n.
现在取 ai ? ?

?ai? ? ai??, ?ai?? ? ai? ,

(如果xi ? 0) (如果xi ? 0)

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

| ? ai xi |?
i ?1

n

(k ? 1) n . k n ?1

这里 a i 为整数,适合 | ai |? k ? 1, i ? 1,2,?, n. 【评述】如上例所示,在证明存在某些有界量使相关的不等式成立时,可类似地把某区间划 分为若干小区间作为抽屉,借用抽屉原则来证明. 例 5:一个国际社团的成员来自六个国家共有 1978 人,用 1,2,?,1977,1978 来编号, 试证明:该社团至少有一个成员的编号或者与他的两个同胞的编号之和相等,或者是其 中一个同胞的编号的两倍. (第 20 届 IMO 第 6 题) 【证明】可用反证法来证明与本题完全相当的下列问题:把整列 1,2,?,1978 按任一方

式分成六组, 则至少有一组具有这样的性质: 其中有一个数或等于四组中其他两数之和, 或等于其中某一个数的两倍. 假设这六组中的每一组数都不具备上述性质,也就是说每一组数都具备下列性质,记作 性质(P) : 同组中任何两数之差必不在此组中. 因为如果有 a , b 连同 a ? b 都在同一组中,那么由 a ? b ? (a ? b) 可知,这组已具备题目 所要求的性质. 因 1978÷6>329,所以由抽屉原则可以肯定有一个组 A,其中至少有 380 个正整数,现 在从 A 中任意取出 330 个数业,记其中最大的那个数为 a1 ,把 a1 分别减去其余 329 个数而 得到 329 个差,它们互不相等且均小于 1978. 由性质(P) ,它们不会再在组 A 中,即应属于 其余五组. 又因 329÷5÷>65.再由抽屉原则可以肯定有一组 B,其中至少含有上述 329 个数 中的 66 个数,从 B 中任取 66 个数且记其中最大的那个数为 b1,再把 b1 减去其余 65 个数, 得出的差显然不再属于 B,当然也不会属于 A. 假如其中的某一个数 b1 ? b 属于 A,由于 b1 与 b 分别可以写为

b1 ? a1 ? a?, b ? a1 ? a
其中 a与a? 都属于 A,于是 b1 ? b ? (a1 ? a?) ? (a1 ? a) ? a ? a? 这就同 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 个数为

1 ? a1 ? a2 ? ? ? a19 ? 90.
由于 a19 ? a1 ? (a19 ? a18 ) ? (a18 ? a17 ) ? ? ? (a2 ? a1 ) , 若右边的 18 个差中无三个相等,而只有两个相等,且取最小的,则

a19 ? a1 ? 2 ? (1 ? 2 ? ? ? 9) ? 90,

这与 a19 ? a1 ? 90 ? 1 ? 89矛盾.

所以两两的差中定有三个相等.

抽屉原则实际上都是重叠原则,这里再介绍抽屉原则的几种变形: 平均量重叠原则:把一个量 S 任意分成 n 份,则其中至少有一份不大于 份不少于

S ,也至少有一 n

S . n

面积的重叠原则:在平面上有 n 个面积分别是 A1,A2,?,An 的图形,把这 n 个图形 按任何方式一一搬到某一个面积为 A 的固定图形上去, (1)如果 A1+A2+?+An>A,则至少有两个图形有公共点; (2)如果 A1+A2+?+An<A,则固定图形中至少有一个点未被盖住. 例 7:在一个面积为 20×25 的长方形内任意放进 120 个面积为 1×1 的正方形,证明:在这 个长方形内一定还可以放下一个直径为 1 的圆,它和这 120 个正方形的任何一个都不相 重叠. (第 1 届全俄数学奥林匹克试题) 【证明】要使直径为 1 的圆完全放在一个矩形里,它的圆心应与矩形任何一条边的距离不小 于

1 1 ,这可从 20×25 的长方形 ABCD 的每一边剪去一个宽为 的长条,则余下的长方 2 2

形 A′B′C′D′的面积为 19×24=456[如图 I—3—2—2(a)].这样,任意放进长方形 ABCD 内的直径为 1 的圆心都在长方形 A′B′C′D′中,此外,圆心应与任何一个正 方形的边界的距离也大于 (b)所得图形的面积是

1 1 ,即在任何一个小正方形以外加上 的框[如图 I—3—2—2 2 2

1? 4?

1 ? ? ? ? 3? . 2 4 4

用这样的 120 个图形互不相交地去覆盖长方形 A′B′C′D′,它们的总面积等于

120 ? (3 ?

?
4

).

但是

120 ? (3 ?

?
4

). ? 120 ?

12 ? 3.2 ? 30 ? 15.2 ? 456 . 4

这说明用这样的 120 图形不能覆盖一个面积为 456 的长方形, 从而可以在长方形 ABCD 内放置一个直径为 1 的圆,它不与所有的小正方形中的任何一个重叠. 例 8:设 n 与 k 是正整数, n ? 3,

n ? k ? n 平面上有 n 个点,其中任意三点不共线,如果其 2

中每个点都至少和其他 k 个点用线段连接, 则连接的线段中至少有三条围成一个三角形. (波兰数学竞赛题,1968 年) 【证明】因为 n ? 3, k ?

2 所以 k ? 2 .这表明:n 个点中必有两个点 a 与 b,它们之间连一段 n

线段,余下的点构成的集合记作 X.X 中用线段与 a 连接的所有点的集合记作 A,而与 b 连接的所有点的集合记作 B. 显然 A∪B 是 X 的子集,因此,|A∪B|≤|X|=n-2. 另一方 面,由已知条件, | A |? k ? 1, | B |? k ? 1 ,则由容斥公式,

n ? 2 ?| A ? B |?| A | ? | B | ? | A ? B |? 2k ? 2? | A ? B |
即 | A ? B |? 2k ? n ? 0 . 这就证明了 A ? B ? ? ,也就是说 A ? B 中必有一点 c,它与 a,b 构成一个△abc.


相关文章:
数学奥赛辅导 第七讲 抽屉原则、容斥原理
数学奥赛辅导 第七讲 抽屉原则容斥原理数学奥赛辅导 第七讲 抽屉原则容斥原理隐藏>> 数学奥赛辅导知识、方法、技能 第七讲 抽屉原则容斥原理 I.抽屉原则 10...
数学奥赛辅导_第七讲_抽屉原则、容斥原理
第七讲 抽屉原则 6页 免费 抽屉原理(一) 12页 免费 高中数学奥赛辅导教材第...Ⅱ. 容斥原则 当我们试图对某些对象的数目从整体上计数碰到困难时,考虑将整体...
高中数学奥赛辅导系列-抽屉原理
数学奥赛辅导 第七讲 抽屉... 9页 10财富值 高中数学奥赛辅导系列:集... ...抽屉原则有时也被称为鸽巢原理, 它是德国数学家狄利克雷首先明确的提出来并用...
高中数学竞赛 容斥原理
高二数学竞赛培训 第一讲... 5页 4下载券 初中数学竞赛专题辅导讲... 18页...容斥原理 13页 免费 高中数学竞赛讲座:抽屉... 6页 免费高​中​数​学...
抽屉原理与容斥原理 竞赛用
抽屉原理容斥原理 竞赛用_初三数学_数学_初中教育_教育专区。抽屉原理容斥原理一、抽屉原理的定义 (1)定义 一般情况下, 把 n+1 或多于 n+1 个苹果放到 ...
数学奥赛辅导第九讲
数学奥赛辅导第六讲 数学奥赛辅导第七讲 数学奥赛辅导...2.利用容斥原理 利用容斥原理 例如: 设元素 a ...3.利用抽屉原则 利用抽屉原则 由于抽世原则的结论...
2015国考行测暑期每日一练数学运算:容斥原理和抽屉原理精讲
2015国考行测暑期每日一练数学运算:容斥原理抽屉原理精讲_公务员考试_资格考试/认证_教育专区。公务员考试,国家公务员考试,2015年国家公务员考试备考辅导资料公职...
第十二讲 容斥与抽屉
第七讲抽屉原则容斥原理 暂无评价 9页 20财富值 数学奥赛辅导_第七讲_抽屉...容斥原理(五年级) 2页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出...
行测数学运算:容斥原理和抽屉原理精讲
行测数学运算:容斥原理抽屉原理精讲_公务员考试_资格考试/认证_教育专区。官方网站:www.offcn.com 给人改变未来的力量 强烈推荐! !! 中公教育.公务员考试第一品...
更多相关标签:
抽屉原理与容斥原理 | 信息学奥赛辅导 | 数学奥赛辅导丛书 | 生物奥赛辅导 | 高考奥赛对接辅导 | 高中数学奥赛辅导总结 | 信息学奥赛辅导资料 | 高中奥赛辅导方案 |