当前位置:首页 >> 数学 >>

高中数学竞赛讲座:抽屉原理


抽屉原理
抽屉原理又叫重叠原则或鸽原则,抽屉原则有如下几种情形。 抽屉原则I 把 n ? 1 件东西任意放入 n 只抽屉里,那么至少有一个抽屉里有两件东西。 抽屉原则II 把 m 件东西放入 n 个抽屉里,那么至少有一个抽屉里至少有 ? ? 件东西。 ?n ? 抽屉原则III 如果有无穷件东西,把它们放在有限多个抽屉里,那么至少有一个抽屉里含 无穷件东西。 利用抽屉原则

解题时,其关键是如何利用题中已知条件构造出与题设密切相关的“抽 屉” ,下面通过例子说明抽屉原则的应用。 例 1.在边长为 1 的正方形内任意放置 5 个点,试证:其中必有两个点,它们之间的距离 不大于
2 2 ?m ?

。 证明:将边长为 1 的正方形划分成如图所示的四个边长为 正方形,则每个小正方形中任意两点间的距离不大于
2 2
1 2

的小

,据抽

屉原理:5 个点放入四个正方形中,其中至少有一个正方形中至 少有 2 个点,则这两个点间的距离不大于
2 2


1 2

例 2.证明:边长为 1 的的正三角形内任意放置 5 个点,其中必有两点,其距离不超过



证明:将边长为 1 的正三角形的各边中点连结起来,得到四个小正三角形,则每个小正三 角形中任意两点间的距离不大于
1 2

,据抽屉原理:5 个点放入 4 个小正三角形中,其中至
1 2

少有一个小正三角形中至少有 2 个点,则这两个点间的距离不超过



例 3.在边长为 1 的正方形中有任意九个点。试证:在以这些为顶点的各个三角形中,至 少有一个三角形,其面积不大于
1 8


1 4 ? 4 的小长方

证明:将边长为 1 的正方形划分为如图所示的 4 个

形, 个点放入 4 个小长方形中, 9 则必有一个长方形中放入了至少 3 个点,设为 A , B , C ,则三角形 ABC 的面积不大于过 A 作边的平行线交 BC 于 A ? ,则:
S ? ABC ? S ? A A ? B ? S ? A A ? C ?
1 2 ?1? 1 4 ? 1 8 1 8

,证明如下:



例 4.求证:任给五个整数,必能从中选出三个,使得它们的和能被 3 整除。 证明:因为任意一个整数被 3 除的余数只能是 0,1,2,若任给的 5 个整数被 3 除的余数

中 0,1,2 都出现,则余数为 0,1,2 的三个整数之和能被 3 整除;若 5 个数被 3 除的余 数只出现 0,1,2 中的两个,则据抽屉原理知:必有 3 个整数的余数相同,而余数相同的 3 个数之和能被 3 整除。故任给五个整数,必能从中选出三个,使得它们的和能被 3 整除。 例 5.求证:在 1, 4 , 7 ,10 , ? ,97 ,100 中任选 20 个不同的整数,其中必有二整数之和为 104。 证明:将 1, 4 , 7 ,10 , ? ,97 ,100 这 34 个自然数分成如下 18 个集合:

?1?, ?4 ,100 ?, ?7 ,97 ?, ? , ?49 ,55 ?, ?52 ? ,从 1, 4 , 7 ,10 , ? ,97 ,100 中任选 20 个数,即从上述 18
个集合中选 20 个数,则必有一个集合中选了 2 个数,而这两个数的和为 104。 n 例 6. a 1 , a 2 , ? , a n 是自然数 1, 2 ,3 , ? , n 随意打乱次序重新排列而成的一串数, 是奇数。 设 证明: ( a 1 ? 1)( a 2 ? 1) ? ( a n ? n ) 总是偶数。 证明:因 n 为奇数,设 n ? 2 k ? 1 ,则 1, 2 ,3 , ? , n 中共有 k ? 1 个奇数,从而 1, 2 ,3 , ? , n ,
a 1 , a 2 , ? , a n 中共 2( k ? 1 )= 2 k ? 2 ? n ? 1 个奇数,这 n ? 1 个奇数放入 n 个括号中,则

必有一个括号中的两个数均为奇数,从而这两个数之差为偶数,所以 ( a 1 ? 1)( a 2 ? 1) ? ( a n ? n ) 总是偶数。 例 7.求证:对于任给的 1987 个自然数 a 1 , a 2 , ? , a 1987 ,从中总可以找到若干个数,使它 们的和能被 1987 整除。 证明:构造如下 1987 个和: a 1 , a 1 ? 2 , a 1 ? a 2 ? a 3 , ? , a 1 ? a 2 ? ? ? a 1987 ,若其中有一 个和能被 1987 整除, 则结论成立。 否则上述 1987 个和除以 1987 的余数只能为 1, 2 , ? ,1986 , 则其中必有两个和的余数相同,设为 a 1 ? a 2 ? ? ? a i , a 1 ? a 2 ? ? ? a j ( i ? j ) , 则 ( a 1 ? a 2 ? ? ? a j ) ? ( a 1 ? a 2 ? ? ? a i ) ? ( a i ? 1 ? a i ? 2 ? ? ? a j ) 能被 1987 整除。 例 8.在任意一次集会中,其中必有两个人,他们认识的人一样多,试证明之。 证明:设参加集会的共有 n 个人,制造如下抽屉: 认识的人的人数为 0 的人属于集合 A 0 ;认识的人的人数为 1 的人属于集合 A1 ; 认识的人的人数为 2 的人属于集合 A 2 ,?;认识的人的人数为 n ? 1 的人属于集合 A n ?1 这里得到 n 个集合,可以证明 A 0 , A n ?1 中至少有一个集合为空集。若 A 0 中有一个元素, 则其余 n ? 1 个人最多认识 n ? 2 个人, 所以 A n ?1 为空集; 同理可证: A n ?1 中有一个元素, 若 则 A 0 为空集。 所以上述 n 个集合, 其实至多只有 n ? 1 个集合。n 个人放入 n ? 1 个集合中, 其中必有一个集合中有两个人,结论得证。 例 9.证明:在全世界所有人中任选六个人,其中一定有三个人,他们之间或者互相认识, 或者互相不认识。 证明: 6 个人中任一个人记为 A , 从 则其余 5 个同 A 或者认识, 或者不认识, 据抽屉原理: 其中必有三个人同 A 认识,或者不认识; 若有三个人同 A 认识,则这三个人或者互不认识,则结论成立。或者有两个人相互认识, 则这两个人同 A 三人互相认识。 若有三个人同 A 不认识, 则这三个人或者互相认识, 则结论成立, 或者有两个人互不认识, 则这两个人同 A 三人互不认识。结论成立。 例 10.平面上有 1987 个点,任取三个点都有两点的距离小于 1。求证:存在半径为 1 的 圆,它至少盖住 994 个点。 证明:在所给的 1987 个点中任选一点,记为 A ,以 A 为圆心作一个半径为 1 的圆,若其 余的 1986 个点都在圆 A 内,则结论成立;否则,在圆 A 外的点中任一点,记为 B ,以 B

为圆心作一个半径为 1 的圆, 则除去 A , B 之外的其余 1985 个点必在圆 A 或圆 B 内, 否则, 至少存在一点 C 在圆 A 或圆 B 的外部,则 A , B , C 三点任两点间的距离均大于 1,与条件 矛盾,所以除去 A , B 之外的其余 1985 个点必在圆 A 或圆 B 内。据抽屉原理:必有一个圆 内至少有 ?
? 1985 ? 1 ? ? ? 1 ? 993 个点,加上圆心共 994 个点。知结论成立。 2 ? ?

例 11.十七个科学家,其中每一个和其他所有的人都通信。在他们的通信中,只讨论三个 题目,而且每两个科学家之间只讨论一个题目。求证:至少有三个科学家相互之间在讨论 同一个题目。 证 明 : 在 17 位 科 学 家 中 任 选 一 位 , 记 为 A , 则 A 至 少 与 其 余 16 位 科 学 家 中 的
? 16 ? 1 ? ? 3 ? ? 1 ? 6 位科学家讨论同一题目,记为题目 1,若这 6 位科学家中有两位科学家在 ? ?

讨论题目 1,则结论成立;若这 6 位科学家都不讨论题目 1,则他们只能讨论另外两题目, 据抽屉原理:他们中至少有 3 位科学家在讨论同一题目。从而知:结论成立。 例 12. 一个国际社团的成员来自六个国家, 共有 1978 人, 1, 2 , ? ,1978 来编号。 用 试证明: 该社团至少有一个成员的编号与他的两个同胞的编号之和相等,或是其一个同胞编号的二 倍。 证明:证明:用反证法,即设每个国家成员编号 k 1 , k 2 , ? k m 中不存在 k i ? k j ? k k 我们将 用抽屉原理引出矛盾。 六个国家共有成员 1978 人, 1978=6 ? 329 ? 4 , 而 所以总有一个国家 A1 的成员至少有 330 人,设他们编号数为 a 1 , a 2 , ? a 330 , 且 a 1 ? a 2 ? ? ? a 330 作 329 个差
a 2 ? a 1 , a 3 ? a 1 , ? , a 330 ? a 1

(1)

由反证法假定,它们不能是 A1 国成员的编号数(若 a i ? a 1 ? a 是 A1 国成员的编号,则
a i ? a 1 ? a ,与反证法假定矛盾) ,所以这 329 个差数是另外五国成员的编号,由于

329=5 ? 65 ? 4 ,因此有一个国家(记为 A 2 )至少有 66 个成员的编号数落在差数(1)的 范围, 记这 66 个编号当选为 b1 , b 2 , ? b 66 , b1 ? b 2 ? ? ? b 66 由反证法假设又知道 5 个差为 数
b 2 ? b1 , b 3 ? b1 , ? , b 66 ? b1

(2)

不可能是 A 2 国成员的编号数, 也不可能是 A1 国的, 因为若某 b i ? b1 ? a ( A 1 国成员编号) , 则 ( a m ? a 1 ) ? ( a n ? a 1 ) ? a , 故 a m ? a n ? a ,与反证假定型矛盾。于是(2)的数只能是 另四国成员编号,由于
65 ? 4 ? 16 ? 1

所以有某国 A 3 的确良 17 位成员的编号数落在(2)中,记这些编
C 1 , C 2 , ? , C 17 , C 1 ? C 2 ? ? ? C 17 ,作 6 个差数 C 2 ? C 1 , C 3 ? C 1 , ? , C 17 ? C 1

(3)

则它们不是 A 3 ,也不是 A 2 、 A1 国的成员的编号数,故必是另三个国家的。由于
16 ? 3 ? 5 ? 1 ,因些有某国 A 4 的 6 位成员的编数落在(3)中,记这 6 个编号数为

d 1 ? d 2 ? d 3 ? ? ? d 6 ,作五个差数, d 2 ? d 1 , d 3 ? d 1 ? d 6 ? d 1

(4)

同样道理知它们只能是其余两个国家成员的编号数,因些有 A 5 国的 3 个成员编号数落在 (4) 这 3 个编号记为 e 1 ? e 2 ? e 3 。 中, 又作差 e 2 ? e 1 , e 3 ? e 1 , 它不是 A1 , A 2 , A 3 , A 4 , A 5 国 的 成 员 编 号 数 , 所 以 f 1 ? e 3 ? e1 是 第 六 国 A 6 成 员 的 编 号 , 此 时 f 2 ? f 1 不 能 是
A 6 , A 5 , ? , A1 的成员编号,但 0 ? f 2 ? f 1 ? 1978 总是某成员编号,这就矛盾了。可见原

命题成立。 例 13.在 100 个连续自然数 1, 2 , ? ,100 中,任取 51 个数,试证明在这 51 个数中,一定有 两个数,其中一个是另一个的倍数。 证明:任意一个自然数都能表示成为 ( 2 m ? 1) ? 2 ( m 为自然数, t 为非负整数)的形式。 将前 100 个自然数分为如下 50 个集合:
t

A1 ? 1 ? 2 ,1 ? 2 ,1 ? 2 ,1 ? 2 ,1 ? 2 ,1 ? 2 ,1 ? 2
0 1 2 3 4 5

A2

? ? ?3 ? 2

6

0

,3 ? 2 ,3 ? 2 ,3 ? 2 ,3 ? 2 ,3 ? 2
1 2 3 4

5

?A

?

3

? ?5 ? 2 , 5 ? 2 , 5 ? 2 , 5 ? 2 , 5 ? 2
0 1 2 3

4

?

? A 49 ? ?97 ? , A 50 ? ?99 ? ,其中前 100 个自然数中的每个自然数都属于其中一个集合, 而且只属于一个集合。据抽屉原理:从中选 51 个数,必有两个数是取自同一个集合,在 同一个集合中,较大的数必是较小数的倍数。 例 14.设 M 是由 1985 个不同的自然数组成的集合, M 中的元素的素因子均不超 26,求 证:存在 a , b , c , d ? M ,使得 abcd 是某个自然数的四次方。 证明:不超过 26 的质数共 9 个:2 ,3 ,5 , 7 ,11 ,13 ,17 ,19 , 23 ,所以这 1985 个正整数可表示为:
?1

2

?3

?2

? ? ? 23
9

?9

的形式, ? 1 ? 0 , ? 2 ? 0 , ? , ? 9 ? 0 ,考虑 (? 1 , ? 2 , ? , ? 9 ) 的奇偶

? ? 性 类型 ,共 有 2 ? 512 种 类型。在 1985 全 正整 数中 可找 出一 对 (? 1? , ? 2 , ? , ? 9 ) 、 ? ? (? 1??, ? 2? , ? , ? 9? ) 有相同奇偶性,即 ? i? 与 ? i?? 奇偶性相同, i ? 1, 2 , ? , 9 。然后在剩下的 ? ? ? ? 1985 ? 2 个数中又可以找出两个,他们的指数 (? 1? , ? 2 , ? , ? 9 ) 、(? 1??, ? 2? , ? , ? 9? ) 也有相同 ? ? 的奇偶性。如此下去,由于 1985 ? 2 ? 513 ? 512 ,故可得 513 对 (? 1? , ? 2 , ? , ? 9 ) 、

? ? (? 1??, ? 2? , ? , ? 9? ) , 且 有 ? i? ? ? i?? ? 2 ? i ( i ? 1, 2 , ? , 9 ) 最 后 , 在 上 述 的 513 个 , ? ? ? ? ( ? 1 , ? 2 , ? , ? 9 ) 中,又必有两个 ( ? 1? , ? 2 , ? , ? 9 ) 、 ( ? 1??, ? 2? , ? , ? 9?) 奇偶性相同,所以

? i? ? ? i?? ? 2 ? i , i ? 1, 2 , ? ,9 ,设 ? i? ? ? i?? ? 2 ? i? , ? i ? ? i ? 2 ? i?? , i ? 1, 2 , ? ,9 ,则
? i? ? ? i?? ? ? i ? ? i ? 4 ? i , i ? 1, 2 , ? ,9 。此时所求四个数为:

, 2 ? 3 ? ? ? 23 , 2 ? 3 ? ? ? 23 , 2 ? 3 ? ? ? 23 。 例 15.平面上有两个定点 A 和 B 及任意四点 P1 , P2 , P3 , P4 ,求证:这四点中一定有两点
2 ?3 ? ? ? 23
2

? ?1

? ?2

? ?9

? ? 1?

? ? 2?

? ? 9?

?1

?

?9

?1

?

2

?9

Pi , P j ( i , j ? 1, 2 ,3 , 4 , i ? j )使得 | sin ? AP i B ? sin ? AP j B |?

1 3



证明:显然: 0 ? ? AP i B ? ? ,? 0 ? sin ? AP i B ? 1 ( i ? 1, 2 ,3 , 4 ) ,即在 [ 0 ,1] 内有四个 实 数 sin ? AP 1 B , sin ? AP 2 B , sin ? AP 3 B , sin ? AP 4 B , 把 [ 0 ,1] 分 成 三 个 子 区 间
? 1 ? ?1 2 ? ? 2 ? ? 0 , 3 ? , ? 3 , 3 ? , ? 3 ,1 ? ,由抽屉原理知: sin ? AP 1 B , sin ? AP 2 B , sin ? AP 3 B , sin ? AP 4 B 中 ? ? ? ? ? ?

必有两个数在同一区间中,不妨设为 sin ? AP i B , sin ? AP j B ( i ? j , i , j ? 1, 2 ,3 , 4 ) ,则:
| sin ? AP i B ? sin ? AP j B |? 1 3

,命题得证。
x? y 1 ? xy ? 3 3

例 16.任给 7 个实数,证明其中必有两个数,记为 x , y ,满足 0 ? 证明:设 7 个实数为 x 1 , x 2 , ? , x 7 ,令 x i ? tg ? i ? i ? ( ? 个子区间,每个子区间的长度为
(?

? ?
, 2 2

) ,将区间 ( ?

? ?
, 2 2

) 分为 6

?
6

,即为:
?
6 ], [

?
2

,?

?
3

], [ ?

?
3

,?

?
6

], [ ?

?
6

, 0 ], [ 0 ,

? ?
, 6 3

], [

? ?
, 3 2

), 据抽屉原理知: 必有两个角 ? , ? 落

在同一区间中,即其差在 0 与

?
6

之间, ,由于这两个角的正切对应着 7 个实数中, 2 个实
?
6

数 x , y ,则由 x ? tg ? , y ? tg ? 0 ? ? ? ? ? 即: 0 ?
x? y 1 ? xy ? 3 3

,得 0 ?

tg ? ? tg ? 1 ? tg ? tg ?

?

3 3





练习
1.假设空间中有六个点,其中任意三点不共线,任意四点不共面,在每两点之间连结直 线段后,将每一条线段或者染上红色,或者染上蓝色。求证:不论怎样染色,一定存在一 个三角形,它的三边有相同的颜色。 2.任给无理数 ? 和正整数 Q ,一定可以找到一个有理数
m n

(其中 0 ? m ? Q ) ,使得

|? ?

n m

|?

1 mQ



3.设 a 1 , a 2 , ? , a n ? 1 是自然数,并且 1 ? a 1 ? a 2 ? ? ? a n ? 1 ? 2 n ,则总能找到这样两个 数 a i 与 a j (1 ? i ? j ? n ? 1) ,使得 a i | a j 。 4.设 a 1 , a 2 , ? , a n , ? 是任意一个具有性质 a k ? a k ? 1 ( k ? 1) 的正整数的无穷序列,求证: 这个序列中有无穷多个 a m 可以表示为 a m ? xa 且p?q。 5.设自然数 n 有下面的性质:从 1, 2 , ? , n 中任取 50 个不同的数,这 50 个数中必有两个 数之差等于 7,这样的 n 的最大的一个值是多少? 6.任何十个不同的两位数的集合必能选出两个不相交的子集,使每个子集内的各数之和 相等。 7.设 S ? ?1, 2 ,3 , ? , 280 ? ,求最小自然数 n 使得 S 的每个有 n 个元素的子集含有 5 个两两 互素的数(IMO(32) ) 8 . 设 x 1 , x 2 , ? , x 100 都 是 整 数 , 则 这 些 整 数 中 必 有 一 些 相 邻 的 项 , 如
x i , x i ?1 , ? , x i ? k (1 ? i ? i ? k ? 100 ) ,使它们的和被 100 整除。
p

? ya q ,其中 p , q , x , y 是适当的正整数,

9.能否在 n 行 n 列的方格表的空格上分别填上 1, 2 , 3 三个数,使得每行每列及每条对角线 上各数字之和各不相同。
? 1 中,求证至少有一个数被 n 整除,其中 n 为大于 1 10.在 2 ? 1, 2 ? 1, 2 ? 1, ? , 2 的奇数。 11.一个象棋大师有 11 个星期用来准备参加比赛,代决定每天至少下一盘棋,但为了使 自己不太累,他决定在任一星期内不下多于 12 盘棋,试证:存在一些连续的日子,代在 这些日子里恰好下了 21 盘棋。 12.在不超过 91 的自然数中任取 10 整数,证明这 10 个数中一定有两个数的比值在区间
1 2 3 n ?1

?2 3? ? 3 , 2 ? 内。 ? ?

13.任给 7 个实数,证明其中必有两个数,记为 x , y ,满足 0 ?

x? y 1 ? xy

?

3 3

14 . 求 证 : 存 在 不 全 为 0 的 整 数 a , b , c , 且 每 个 数 的 绝 对 值 均 小 于 1000000 , 使
| a ? b 2 ? c 3 |? 10
? 11


b1 , b 2 , b 3 是 a 1 , a 2 , a 3 这三个数任意调换次序得到

例 15.设 a 1 , a 2 , a 3 为任意三个整数,

的一个排列,试证: a 1 ? b1 , a 2 ? b 2 , a 3 ? b 3 中至少有一个是偶数。


相关文章:
高中数学竞赛讲义-抽屉原理
高中数学竞赛讲义-抽屉原理_学科竞赛_高中教育_教育专区。数学教育网---数学试题-数学教案-数学课件-数学论文-竞赛试题-中高考试题信息 http://www.qyjzs.cn ...
浅谈抽屉原理在高中数学竞赛中的运用
浅谈抽屉原理在高中数学竞赛中的运用 浅谈抽屉原理在高中数学竞赛中的运用 抽屉...高中数学竞赛讲义-抽屉原... 7页 免费 高中数学竞赛讲座:抽屉... 6页 免费...
1002_高中数学竞赛系列讲座——抽屉原理
1002_高中数学竞赛系列讲座——抽屉原理_高二数学_数学_高中教育_教育专区。一套很有用的数学竞赛丛书,老师学生皆宜http://www.cenre.com/teacher/special/onespecia...
初一数学竞赛系列讲座(14)抽屉原理
初一数学竞赛系列讲座(14) 抽屉原理 一、知识要点 (1)抽屉原理 1 把 n+1 个东西,任意地分放到 n 个抽屉里,那么必有一个抽屉里有 2 个东西. (2)抽屉...
抽屉原理与高中数学竞赛
摘 要 本论文首先讨论了抽屉原理的一般含义和它的两种推广形式;其次给出了抽屉...高中数学竞赛讲座:抽屉... 6页 免费 抽屉原理——初一数学竞... 暂无评价 ...
高中竞赛专题:抽屉原理
高中竞赛专题:抽屉原理_理学_高等教育_教育专区。数学竞赛竞赛讲座 10 --抽屉原则 --抽屉原则大家知道,两个抽屉要放置三只苹果,那么一定有两只苹果放在同一个抽屉...
高中数学竞赛讲义-抽屉原理
高中数学竞赛讲义-抽屉原理_高三数学_数学_高中教育_教育专区。奥赛数学讲义 ...高中数学竞赛讲座 10抽屉... 暂无评价 8页 免费 抽屉原理在数学竞赛中的.....
中学数学竞赛 抽屉原理讲义
中学数学竞赛 抽屉原理讲义_数学_自然科学_专业资料。主要是增对高中数学联赛的 ...高中数学竞赛讲座:抽屉... 6页 免费 抽屉原理在数学竞赛中的... 9页 1下载...
竞赛讲座(抽屉原理)
1002_高中数学竞赛系列讲座... 11页 免费 初一数学竞赛系列讲座(14)... 暂无...竞赛讲座(抽屉原理) 竞赛讲座(抽屉原理) 一、 知识要点 1、 抽屉原理 1 、把...
北京数学竞赛培训第13讲 抽屉原理
北京数学竞赛培训第13讲 抽屉原理_数学_高中教育_教育专区。第 13 讲 抽屉原理...抽屉原理在数学竞赛中的... 9页 1下载券 高中数学竞赛讲座:抽屉... 6页 免...
更多相关标签: