nbhkdz.com冰点文库

2012江苏省数学竞赛《提优教程》教案:第10讲 抽屉原理


第 10 讲

抽屉原理

抽屉原理又叫鸽笼原理、狄里克雷( P. G. Dirchlet,1805~1895,德国)原理、重叠原理、鞋 盒原理. 这一最简单的思维方式在解题过程中却可以演变出很多奇妙的变化和颇具匠心的运 用. 抽屉原理常常结合几何、整除、数列和染色等问题出现, 抽屉原理 I:把 n ? 1 件东西任意放入 n 只抽屉里,那

么至少有一个抽屉里有两件东西。 抽屉原理 II:把 m 件东西放入 n 个抽屉里,那么至少有一个抽屉里至少有 ?

?m? 件东西。 ?n? ?

抽屉原理 III:如果有无穷件东西,把它们放在有限多个抽屉里,那么至少有一个抽屉里含 无穷件东西。 应用抽屉原理解题,关键在于构造抽屉。构造抽屉的常见方法有:图形分割、区间划分、 整数分类(剩余类分类、表达式分类等) 、坐标分类、染色分类等等,下面举例说明。

A 类例题
例 1 如图,分别标有 1 到 8 的两组滚珠均匀放在内外两个圆环上,开 始时相对的滚珠所标数字都不相同, 当两个圆环按不同方向转动时, 必有某 一时刻,内外两环中至少有两对数字相同的滚珠相对. 分析 转动一周形成 7 个内外两环两对数字相同的时刻,以此构造抽屉。 证明 内外两个圆环转动可把一个看成是相对静止的,只有一个外环在转动.当外环转动 一周后,每个滚珠都会有一次内环上标有相同数字的滚珠相对的时刻,这样的时刻将出现 8 次. 但一开始没有标有相同数字的滚珠相对,所以外环转动一周的过程中最多出现 7 个时刻 内外标有相同数字的滚珠相对,故必有一个时刻内外两环中至少有两对数字相同的滚珠相对. 说明 转动一周内外两环两对的 8 个时刻排除显然不合题意的初始时刻是本题的突破口。 例 2 7 月份的天热得人都不想工作,只想呆在有空调的房间里.可小张却没有办法休

假,因为他是一个空调修理工,为了让更多人好好休息,他只能放弃自己的休息.在过去的 7 月份里,小张每天至少修理了一台空调.由于技术过硬,每一台空调都能在当天修理好.8 月 1 日结算的时候,大家发现小张在 7 月份一共修理了 56 台空调. 求证:存在连续的若干天(也可以是 1 天) ,在这些天里,小张恰好修理了 5 台空调.

分析 本题的难点在于将题中结论转化为抽屉原理的数学模型。 证明 我们来考察“连续的若干天”里小张修理的空调台数.设小张在第 i 天修理了 xi 台 空调,其中 i=1,2,?,31.则:x1<x1+x2<x1+x2+x3<?<x1+x2+?+x31=56. 另外:x1+5<x1+x2+5<x1+x2+x3+5<?<x1+x2+?+x31+5=61. 上面的两组数(共 62 个)均在 1 到 61 之间(包括这两个数) ,由抽屉原理,必有二个数是相 等的,且相等的两个数应该来自不同的组.从而 x1+x2+?+xq= x1+x2+?+xp+5.(q>p) 由此可见

xp+1+xp+2+?+xq=5.

即从第 p+1 天开始到第 q 天修理的空调正好是 5 台. 例 3 点 P 为 ABC 内任意一点,与点 A 、 B 、C 的连线分别交对边于 D 、 E 、 F .求

AP BP CP 、 、 中必有一个不大于 2,也必有一个不小于 2. PD PE PF AP BP CP 分析 由 S?PBC ? S?PCA ? S?PAB ? S?ABC 寻求关于 、 、 的关系式展开分析。 PD PE PF S PD 1 证明 利用 S?PBC ? S?PCA ? S?PAB ? S?ABC .以及 ?PBC ? ,??(其余两个 ? S?ABC AD 1 ? PA PD 1 1 1 1 类似)得: ? ? ? 1 .三个正数的和为 1,必有一个不小于 ,也必有 PA PB PC 3 1? 1? 1? PD PE PF 1 PA 1 1 ?2. 一个不大于 .不妨设 ? ,得 PA 3 3 PD 1? PD PC 1 1 ?2. ? ,得 PC 3 PF 1? PF AP BP CP 所以在 、 、 中必有一个不大于 2,也必有一个不小于 2. PD PE PF
证:在

情景再现
1.在边长为 1 的正方形内任意放入九个点,求证:存在三个点,以这三个点为顶点的三 角形的面积不超过

1 。 (1963 年北京市数学竞赛题) 8

2.质点沿直线方向往前跳,每跳一步前进 5 米,而前进方向上距离起点每隔 1 米都有

一个以此点为中心长为 2 ? 10 米的陷阱,证明该质点迟早要掉进某个陷阱里。 3.在坐标平面上任取 5 个整点(该点的横纵坐标都取整数) ,证明:其中一定存在两个 整点,它们的连线中点仍是整点。

?3

B 类例题
例 4. (1)对于任意的 5 个正整数,证明其中必有 3 个数的和能被 3 整除; (2)对于任意的 11 个正整数,证明其中一定有 6 个数,它们的和能被 6 整除。 分析 (1)可借助于 3 的同余类构造抽屉; (2)若仿造(1)借助于 6 的同余类构造抽屉 情形较为烦琐,不妨借助于(1)的结论从中构造出能满足被 2 整除的数.

{0},{1},{2} , 证明 (1) 任何自然数除以 3 的余数只能是 0、 1、 2, 不妨分别构造 3 个抽屉:
将这 5 个数按其余数放置到这 3 个抽屉中: ①若这 5 个正整数分布在这 3 个抽屉中,从 3 个抽屉中各取一个,其和必能被 3 整除; ②若这 5 个自然数分布在其中的 2 个抽屉中,则必有一个抽屉中含有至少 3 个数,取其 3 个,其和必能被 3 整除; ③若这 5 个自然数分布在其中的 1 个抽屉中,取其 3 个,其和必能被 3 整除。 (2)设 11 个整数为 a1 , a2 ,

, a11 ,因为 6 ? 2 ? 3 。

①先考虑被 3 整除的情形。由(1)知:在 11 个任意整数中,必存在: 3 | a1 ? a2 ? a3 , 不妨设 a1 ? a2 ? a3 ? b1 ; 同理, 剩下的 8 个任意整数中, 由 (1) 知, 必存在:3 | a4 ? a5 ? a6 , 不 妨 设 a4 ? a5 ? a6 ? b2; 同 理 , 其 余 的 5 个 任 意 整 数 中 , 有 : 3 | a7 ? a8 ? a9 , 设

a7 ? a8 ? a9 ? b3。
②再考虑 b1 , b2 , b3 中存在两数之和被 2 整除。依据抽屉原理, b1 , b2 , b3 这三个整数中,至少 有两个是同奇或同偶,这两个同奇(或同偶)的整数之和必为偶数. 不妨设 2 | b1 ? b2 ,则: 6 | b1 ? b2 ,即 6 | a1 ? a2 ? a3 ? a4 ? a5 ? a6 。 所以任意 11 个整数,其中必有 6 个数的和是 6 的倍数。 例 5.910 瓶红、蓝墨水,排成 130 行,每行 7 瓶。证明:不论怎样排列,红、蓝墨水瓶 的颜色次序必定出现下述两种情况之一种: 1.至少三行完全相同;

2.至少有两组(四行) ,每组的两行完全相同。 (北京市高中一年级数学竞赛 1990 年复赛试题) 分析 每行 7 个位置有 128 种不同放置方式,以此构造抽屉. 证明 910 瓶红、蓝墨水,排成 130 行,每行 7 瓶。每行中的 7 个位置中的每个位置都 有红、蓝两种可能,因而总计共有 2 ? 128 种不同的行式(当且仅当两行墨水瓶颜色及次序
7

完全相同时称为“行式”相同) 任取 130 行中的 129 行,依抽屉原理可知,必有两行(记为 A,B)“行式”相同。 在除 A、B 外的其余 128 行中若有一行 P 与 A(B)“行式”相同,则 P,A,B 满足“至少 有三行完全相同”;在其余(除 A,B 外)的 128 行中若没有与 A(B)行式相同者,则 128 行至多有 127 种不同的行式,依抽屉原理,必有两行(不妨记为 C、D)行式相同,这样便找 到了(A,B) 、 (C,D)两组(四行) ,每组两行完全相同。 说明 本题构造抽屉时用到分步计数原理, 2 ? 128 个“行式”是构造“抽屉”的关键。
7

例 6.将平面上每个点以红蓝两色之一着色,证明:存在这样的两个相似三角形,它们的 相似比为 1995,并且每一个三角形的三个顶点同色。 (1995 年全国高中数学联赛试题) 分析 构造相似比为 1995 的 9 点组。 证明 如图,作两个半径分别为 1 和 1995 的同心圆,在内圆上任取 9 个 点,必有 5 点同色,记为 A1,A2,A3,A4,A5。连半径 OAi 交大圆于 Bi ( i ? 1, 2,3, 4,5 ) ,对 B1,B2,B3,B4,B5,必有 3 点同色,记为 Bi , Bj , Bk ,
A5 A6 B6 B3 B4 A3 A2 A1 A4 A9 A8 B2 B1 B9 B8

A7 B7

则 ?Bi B j Bk 与 ?Ai Aj Ak 为三项点同色的相似三角形,相似比等于 1995,满 足题设条件。 评析 这里连续用了两次抽屉原理 (以染色作抽屉) 。 也可以一开始就 取位似比为 1995 的 9 个位似点组 ( Ai , Bi ) ( i ? 1, 2,

B5

C/

,9 ) ,对 4 个抽屉

B/ B A

C D

D/

(红,红) , (红,蓝) , (蓝,红) , (蓝,蓝)应用抽屉原理,得出必有 3 个位似点属于同一抽屉,从题目的证明过程中可以看出,相似比 1995 可

E

E/

以改换成另外一个任意的正整数、正实数。当然,不用同心圆也可证得,如在平面上取任三 点都不共线的 9 点,由抽屉原理必有 5 点同色,设为 A、B、C、D、E;以 A 为位似中心,以 1995 为相似比作 ABCDE 的相似形 AB'C'D'E',则 5 点 A,B',C',D',E'中必有 3 点同色,设为 B'D'E',则即为所求。

情景再现
4.有苹果、梨、桔子若干个,任意分成 9 堆,求证一定可以找到两堆,其苹果数、梨数、 桔子数分别求和都是偶数。 5.将平面上每个点以红蓝两色之一着色,证明:存在无数个内角为 30° ,60° ,90° 的相 似直角三角形,它们的相似比为 1995,并且每一个三角形的三个顶点同色。 6.有 17 位科学家,其中每一个人和其他所有人通信,他们通信中讨论三个问题,且每 两个科学家之间只讨论一个问题,求证至少有三个科学家相互之间讨论同一个问题。

C 类例题
例 7.给定一个由 10 个互不相等的两位十进制正整数组成的集合。求证:这个集合必有 两个无公共元素的子集合,各子集合中各数之和相等。 (第 14 届 IMO 试题) 分析 根据子集中各数之和构造抽屉. 解 10 个元素的集合就有 2
10

? 1024 个不同的构造子集的方法,也就是,它一共有 1024

个不同的子集,包括空集和全集在内。空集与全集显然不是考虑的对象,所以剩下 1022 个非 空真子集。 再看各个真子集中一切数字之和。用 N 表示,则 10 ? N ? 91 ? 92 ?

? 99 ? 855 。

这表明 N 至多只有 855 ? 9 ? 846 种不同的情况。由于非空真子集的个数是 1022,1022> 846,所以一定存在两个子集 A 与 B,使得 A 中各数之和=B 中各数之和。 若 A ? B ? ? ,则命题得证,若 A ? B ? C ? ? ,即 A 与 B 有公共元素,这时只要剔除 A 与 B 中的一切公有元素,得出两个不相交的子集 A1 与 B1,很显然 A1 中各元素之和=B1 中 各元素之和,因此 A1 与 B1 就是符合题目要求的子集。 例 8.设 S ? {1, 2,3,

, 280} 。求最小的自然数 n ,使得 S 的每个有 n 个元素的子集都含

有 5 个两两互素的数。 (1991 IMO32?3 ) 分析 本题一方面要确定 n 的下界,另一方面须构造符合题意的集合. 解 令 Ai ? {a | a ? S , i | a} , i ? 2,3,5, 7 。记 A ? A2 ? A3 ? A5 ? A7 ,利用容斥原理, 容易算出 | A |? 216 。 由于在 A 中任取 5 个数必有两个数在同一个 Ai
2 1--280内的素数 3 17 37 59 79 103 131 157 181 211 239 269 5 19 41 61 83 107 137 163 191 223 241 271 7 23 43 67 89 109 139 167 193 227 251 277 11 29 47 71 97 113 149 173 197 229 257 281

之中,从而它们不互素。所以 n ? 217 。 另一方面,令

13 31 53 73 101 127 151 179 199 233 263

B1 ? {1 和 S 中的一切素数 } ,

B2 ? {22 ,32 ,52 ,72 ,112 ,132 } ,
B3 ? {2 ?131,3 ? 89,5 ? 53,7 ? 37,11? 23,13 ?19} , B4 ? {2 ?127,3 ? 83,5 ? 47,7 ? 31,11?19,13 ?17} , B5 ? {2 ?113,3 ? 79,5 ? 43,7 ? 29,11?17} , B6 ? {2 ?109,3 ? 73,5 ? 41,7 ? 23,11?13} 。
易知 | B1 |? 60 。令 B ? B1 ? B2 ? B3 ? B4 ? B5 ? B6 ,则 | B |? 88 ,从而 | B |? 192 , 在 S 中任取 217 个数,由于 217 ? 192 ? 25 ,这 217 个数中必有 25 个数在 B 中,于是一定 存在 Bi , 使得至少有 [ 于是可得 n ? 217 。 说明 在这个解法中, 两次使用了抽屉原理, 其关键都是构造抽屉。 由于第一步要确定 n 的 下界,既要找出尽可能大的 n 的值,使得这 n 个数中的任意五个数中至少有两个不互素。故这 时必须构造 4 个“抽屉” ,满足: ①每个“抽屉”中任意两个数都不互素; ②每个“抽屉”中包含尽可能多的数。 在这些要求下构造出了集合 A2 , A3 , A5 , A7 ,从而得到 n ? 217 。 在确定 n ? 217 时,诸 Bi 的构造要求是: ① Bi 中的任意两个数互素; ② | Bi |? 5 。

25 ? 1 ] ? 1 ? 5 个数在其中, 这 5 个数显然是两两互素的。 所以 n ? 217 , 6

情景再现
7.9 条直线的每一条都把一个正方形分成两个梯形,而且它们的面积之比为 2∶ 3。证明: 这 9 条直线中至少有 3 条通过同一个点。 8.已知斐波那契数列:0,1,1,2,3,5,8,?试问:在前 100000002 项中,是否会 有某一项的末四位数字全是 0?(不指第一项)

习题 10
A
1.从集合 A ? {1, 2,

, 2n} 中任取 n ? 1 个数,证明:其中必有 2 个数互素。

2.任意给定 7 个整数,求证:其中必有两个数,其和或差可被 10 整除。 3.任给 7 个实数,求证:其中必有至少两个数(记为 x , y ) 满足 0 ?

x? y 3 。 ? 1 ? xy 3

4 .某厂生产一种直径为 10mm 的圆形零件,由加工水平可知零件直径之差不会超过

0.5mm ,并且其直径不小于 10mm ,现在要挑出两个零件,使它们的直径之差小于 0.01mm ,
若任意抽取,问至少要抽取多少件? 5. 求证: 在凸 n(n ? 7) 边形中, 至少存在两个内角 ? , ? , 使得 | cos ? ? cos ? |?

1 。 2(n ? 6)
, n )的

6.我们称点 (

x1 ? x2 ? n

? xn y1 ? y2 ? , n

? yn

) 为 n 个点 ( xi , yi ) ( i ? 1, 2,

重心。求证:平面上任意 13 个整点中,必有某 4 个点的重心为整点。

习题
B
7.从正整数集 {1, 2,3, 中的一个可以整除另一个。 8.从前 39 个正整数中任意取出 8 个数,证明:取出的数中一定有两个数,这两个数中大 数不超过小数的 1.5 倍。 9.已知整数 a1 , a2 ,

,99,100} 中,任意选出 51 个数。求证:其中一定有两个数,它们

, a10 。证明存在一个非零数列 x1 , x2 ,

, x10 使得对 xi ?{?1,0,1} 和

x1a1 ? x2 a2 ?

? x10 a10 能被 1001 整除。
2

10.两两不等高的 n ? 1 个人,随便排成一列,求证:可以从总挑选 n ? 1 个人向前一步出 列,使他们的身高从左到右是递增或递减的。

习题

C
11.某运动队的队员编号物重复地取自正整数 1 到 100。如果其中任一队员的编号都不是 另两队员编号之和,也不是另一队员编号的 2 倍,问这个运动队最多有几人? 12.我们称非空集合 A1 , A2 , (1) A 1 ? A2 ?

, An 为集合 A 的一个 n 划分,如果:

(2) Ai ? Aj ? ? , 1 ? i ? j ? n 。 ? An ? A ;

求最小的正整数 m ,使得对 A ? {1, 2,

, m} 的任意一个 13 划分 A1 , A2 ,
9 b。 8

, A13 ,一定存在某

个集合 Ai (1 ? i ? 13) ,在 Ai 中有两个元素 a , b 满足 b ? a ?

本节“情景再现”解答: 1.证明:根据题意,构造的“抽屉”中至少要有 3 点,且以这三个点为顶点的三角 形的面积不超过
A1 A2 A3 A4

1 。如图,四等分正方形,得到 4 个矩形。在正方形内任意放入九个点, 8

则一定存在一个矩形,其内至少存在 [

9 ?1 ] ? 1 ? 3 个点,设三点为 A、B、C,具体考 4
h , 则 △ABC

C A B A/

察其所在的矩形(如图) ,过三点分别作矩形长边的平行线,过 A 的平行线交 BC 于 A' 点 , 设 A 点 到 矩 形 长 边 的 距 离 为 的 面 积

S?ABC ? S?AA/ C ? S?AA/ B ?

1 1 1 1 ? 1 ? h ? ? 1 ? ( ? h) ? 。 2 2 4 8

2.证明:若该质点跳了 m 步后掉进了第 l 个陷阱里,则本题等价于:存在正整数 m, l , 使得 | l ? m 5 |? 10?3 。 把区间 [0,1) 分成 1000 等分,每一等分都是左闭右开的小区间,它们的长都是10 。 考虑 1001 个实数 k 5 ? [k 5] , k ? 1, 2,
?3

,1001 ,由于 k 5 ? [k 5] ?[0,1) ,则这 1001

个实数都在区间 [0,1) 内。 由抽屉原理, 必有两个实数设为 i 5 ? [i 5] 和 j 5 ? [ j 5] 都在同 一小区间内(不妨设 i? j ) 。 于 是 有 | (i 5 ? [i 5]) ?( j 5 ? [ j 5]) |? 10?3 , 即

| ( i? j ) 5 ? (i [

5 ?] j [

3 i 设 m? ? 5 ? ]?) |, 10

j l ? [i 5] ? [ j 5] , 则 有 ,

| l ? m 5 |? 10?3 。从而当质点跳了 m 步后掉进了第 l 个陷阱里。
3 . 解 : 由 中 点 坐 标 公 式 知 , 坐 标 平 面 两 点 ( x1 , y1 ) 、 ( x2 , y2 ) 的 中 点 坐 标 是

(

x1 ? x2 y1 ? y2 x ? x2 y1 ? y2 , ) 。欲使 1 , 都是整数,当且仅当 x1 与 x2 , y1 与 y2 的奇偶性相 2 2 2 2

同。 坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有如下四种: (奇数、 奇数) , (偶数,偶数) , (奇数,偶数) , (偶数,奇数)以此构造四个“抽屉”,则在坐标平面上任取五 个整点,那么至少有两个整点,属于同一个“抽屉”因此它们连线的中点就必是整点。 4.证明:因为每一堆里的每一种水果数或为奇数或为偶数(两个抽屉) ,而 9=2×4+1, 故对于苹果,9 堆中必有 5 堆的奇偶性相同;这 5 堆对于梨数来说,由于 5=2×2+1,故必有 3 堆的奇偶性相同;这 3 堆对于桔子数也必有 2 堆的奇偶性相同。于是,就找到这样的两堆, 它们的苹果数、梨数,桔子数的奇偶性都分别相同,从而其和数分别都是偶数。 5.任取 a∈ R+,以 a 为边作等边三角形,则必有两点同色,记为 A,B 同红色,以 AB 为直径作一圆,再作圆内接正六边形 AC1C2BC3C4(如图) , 当 Ci 中有红点时 △ACiB 即为所求;当 Ci 中无红点即 Ci 全为蓝色时, Rt△C1C2C3 即为所求。再由 a 的任意性知,这样的三角形有无数个。 6. 科学家对应一个点, 两科学家之间讨论的问题对应两点间连线的颜色, 本题转化为染色问题:完全十七边形 K17 用红黄蓝三色染其边,必存在同色三角形。 由 A1 出发有 16 条边, 用三色染, 必有六条同色 (设为红色) , 不妨认为 A1 A2, A1 A3, ….. A1 A7 为红色; 若 A2,A3,….. A7 之间有红色连线,则存在红色三角形,否则六点 A2,A3,….. A7 两两连线得 K6,用黄蓝两色染边,必存在同色三角形。 7.证明:设正方形为 ABCD,E、F 分别是 AB,CD 的中点。设直线 l 把正方形 ABCD 分成两个梯形 ABGH 和 CDHG,并且与 EF 相交于 P(如图) 。 梯形 ABGH 的面积∶ 梯形 CDHG 的面积=2∶ 3 , EP 是梯形 ABGH 的中 位线,PF 是梯形 CDHG 的中位线,由于梯形的面积=中位线×梯形的高,并
B G C l A H D

C4

C3

A

B

C1

C2

E

2k

P

Q 3k

F

且两个梯形的高相等(AB=CD) ,所以梯形 ABGH 的面积∶ 梯形 CDHG 的面 积=EP∶ PF,也就是 EP∶ PF=2∶ 3 。这说明,直线 L 通过 EF 上一个固定的点 P,这个点把 EF 分成长度为 2∶ 3 的两部分。这样的点在 EF 上还有一个,如图上的 Q 点(FQ∶ QE=2∶ 3) 。 同样地,如果直线 l 与 AB、CD 相交,并且把正方形分成两个梯形面积之比是 2∶ 3,那 么这条直线必定通过 AD、BC 中点连线上的两个类似的点(五等分点) 。 这样,在正方形内就有 4 个固定的点,凡是把正方形面积分成两个面积为 2∶ 3 的梯形的

直线,一定通过这 4 点中的某一个。根据抽屉原理,必有一个点,至少有 [ 线通过此点。

9 ?1 ] ? 1 ? 3 条直 4

8.注意到斐波那契数列是严格递增的,故满足要求的项至少是五位以上的数. 再注意到斐波那契数列的特点是每一项等于前面两项的和,而 100000002=10 ? 2 ,我
8

们可以以相邻两项的末四位数字所成的有序对为抽屉,而末四位数字组成的数一共有 10 个 (不足四位前面补 0) ,抽屉的个数正好是 10 ?10 ? 10 .现有 10 ? 1 个数对,至少有两个
4 4 8 8

4

4 数对,它们的末四位完全相同.设为 ? ai , ai ?1 ? , a j , a j ?1 , ( i ? j )即有: 10 a j ? ai ,

?

?

?

?

且 10

4

?a

j ?1

? ai ?1 ? .

4 于是 10 ? a j ?1 ? ai ?1 ? a j ? ai ? ,

??

? ?

??

而 a j ?1 ? ai ?1 ? a j ? ai ? a j ?1 ? a j ? ? ai ?1 ? ai ? ? a j ?1 ? ai ?1 就是说 a j ?1 和 ai ?1 的末四位相同,从而数对 ? ai ?1 , ai ? 、 a j ?1 , a j 的末四位相同. (事实上我们 得到了两个连续三个数, ? ai ?1 , ai , ai ?1 ? 和 a j ?1 , a j , a j ?1 对应末四位全部相同. ) 依次类推,我们可以得到 ? a1 , a2 ,

?

? ?

? ?

?

?

?

?

?

, ai?1 ? 和 ? a j ?i ?1 , a j ?i ? 2 ,

, a j ?1 ? 的对应末四位全部相

同,从而 a j ?i ?1 与 a1 (即 0)的末四位相同,所以 a j ?i ?1 的末四位全为 0. “习题 10”解答: 1.构造 n 个抽屉: {1, 2} 、 {3, 4} 、??、 {2n ? 1, 2n} ,则 n ? 1 个数中必有两个数属于 同一个抽屉,即此两数互素 2.∵任意整数除以 10 的余数,只能是 0,1,2,3,4,5,6,7,8,9 这十个数中的一 个。 ∴不妨从余数角度出发,考虑构造合适的抽屉。 (由题目分析,要求我们构造六个抽屉, 并且抽屉中的余数和或差只能是 0) 由这 10 个余数,构造 6 个抽屉: {0} , {5} , {1,9} , {2,8} , {3, 7} , {4, 6} 则任意 7 个不同整数除以 10 后所得余数(即 7 个元素) ,任意放入这 6 个抽屉,其中必 有一个抽屉包含有其中 2 个不同整数除以 10 后所得的 2 个余数。 ①若这两个余数同属于抽屉{0}或抽屉{5},则此二余数差是 0,即这两个余数对应的整数

之差可以被 10 整除。 ②若这两个余数同属于 {1,9} , {2,8} , {3, 7} , {4, 6} 这四个抽屉中的任意一个,则这两 个余数和是 10,即这两个余数所对应整数之和是 10 的倍数。 可见,任意 7 个不同的整数中,必有两个数的和或差是 10 的倍数。 3.记 7 个数为 tan ?1 、 tan ? 2 、??、 tan ?7 ,其中 ?1 , ?2 ,

, ?7 ? ( ?

? ?

(?

? ?

, ) 等分成 6 个区间:( ? , ? ] 、( ? , ? ] 、(? , 0] 、(0, ] 、( , ] 、( , ) , 2 2 6 6 6 3 3 2 2 3 3 6

?

?

?

?

?

?

? ?

, ) ,将区间 2 2

? ?

则 7 个 角 必 有 两 个 属 于 同 一 区 间 , 不 妨 设 | ? i ? ? j |?

?

6

,设

?i ? ? j , 则

0? t a? n i (? ? j ? )

?

x? y 3 x , y 满足 0 ? t ,即存在两个数 an 。 ? 6 1 ? xy 3
,10.5 时,

4.首先指出取 51 件是不行的。当零件的直径成等差数列: 10,10.01,10.02, 每两件的直径之差都不小于 0.01mm 。

再证取 52 件时成立。将区间 [10,10.5] 作 51 等分,则 52 个零件中必有两件的直径属于同

10.5 ? 10 0.5 ? ? 0.01 ,所以最少要取 52 件。 51 50 2 2 5.首先证明凸多边形至多有 5 个内角小于 ? 。用反证法,若有 6 个内角小于 ? ,则 3 3 2 其内角和 S ? 6 ? ? ? (n ? 6)? ? (n ? 2)? ,这与 S ? (n ? 2)? 矛盾。 3 2 1 于是,凸 n 边形至少有 n ? 5 个内角在区间 [ ? , ? ) 内,它们的余弦值在 ( ?1, ? ] 内。 3 2
一等分区间,有直径之差 ? 将区间 ( ?1, ? ] 平均分成 n ? 6 个小区间,每个小区间的长为

1 2

1 。于是 n ? 5 个角 2(n ? 6)

的余弦值分布在 n ? 6 个小区间内,至少有两个角的余弦值在同一个小区间内,设为 cos ? 、

cos ? ,因此 | cos ? ? cos ? |?

1 。 2(n ? 6)

6.按照坐标的奇偶性构造 4 个抽屉: (奇数、奇数) , (偶数,偶数) , (奇数,偶数) , (偶 数,奇数) ,由抽屉原理必有一个抽屉里至少有 [ 点。 7. 证明: 因为任何一个正整数都能表示成一个奇数与 2 的方幂的积, 并且表示方法唯一, 所以我们可把 1 ~ 100 的正整数分成如下 50 个抽屉(因为 1 ~ 100 中共有 50 个奇数) :

13 ? 1 ] ? 1 ? 4 个点,这 4 点的重心显然是整 4

(1) {1,1? 2,1? 22 ,1? 23 ,1? 24 ,1? 25 ,1? 26 } ; (2) {3,3 ? 2,3 ? 22 ,3 ? 23 ,3 ? 24 ,3 ? 25 } ; (3) {5,5 ? 2,5 ? 22 ,5 ? 23 ,5 ? 24 } ; (4) {7,7 ? 2,7 ? 22 ,7 ? 23 } ; (5) {9,9 ? 2,9 ? 22 ,9 ? 23 } ; ?? (25) {49, 49 ? 2} ; (26) {51} ; ?? (50) {99} 。

1 ~ 100 中的每一个数都在其中的 1 个抽屉内。 这就构造了 50 个抽屉, 从中任取 51 个数,
据抽屉原理,其中必定至少有两个数属于同一个抽屉,即属于 (1) ~ (25) 号中的某一个抽屉, 显然在这 25 个抽屉中的任何同一个抽屉内的两个数,一个是另一个的倍数。 8.证明:把前 39 个正整数分成下面 7 组: 1; 2,3; 4,5,6; 7,8,9,10; 11,12,13,14,15,16; 17,18,19,20,21,22,23,24,25; ① ② ③ ④ ⑤ ⑥

26,27,28,29,30,31,32,33,34,35,36,37,38,39; ⑦ 因为从前 39 个自然数中任意取出 8 个数,所以至少有两个数取自上面第② 组到第⑦ 组中 的某同一组,这两个数中大数就不超过小数的 1.5 倍。 评析: 本题可以改造为如下一系列题目: ①从前 16 个自然数中任取 6 个自然数; ②从前 25 个自然数中任取 7 个自然数;

③从前 60 个自然数中任取 9 个自然数; ④从前 91 个自然数中任取 10 个自然数; ?? 这些都可以得到同一个结论:其中存在 2 个数,它们相互的比值在 [ , ] ]内。如果我们 改变区间 [

2 3 3 2

q p , ] ( p ? q )端点的值,则又可以构造出一系列的新题目来。 p q

9.考虑形如 x1a1 ? x2 a2 ?

? x10 a10 ( xi ?{0,1} )的数,这样的数共有 210 ? 1024 个。

这 1024 个数除以 1001 余数只有 1001 种,于是必有两个不同的数除以 1001 所得的余数相同,
/ / 设 这 两 个 数 为 y / ? x1 a1 ? x2 a2 ? / // ? x10 a10 和 y // ? x1// a1 ? x2 a2 ? // ? x10 a10 , 其 中

/ 1 ,0 ,1 } y / ? y // 能被 1001 整除。令 xi/ ? xi// ? xi ,则 xi ?{? xi/ , xi / ? { 0 , 。则它们的差 1}

,且 xi

不全为零,于是数列 x1 , x2 ,

, x10 为所求。

10 .将人的身高依次记为 a1 , a2 ,

, an2 ?1 ??①,对此数列的每一项 ai 有一组正整数

( xi , yi ) 作为它的坐标,其中 xi 是以 ai 为首项的最长的递增子数列的项数, yi 是以 ai 为首项
的最长的递减子数列的项数。 下面只需证明存在 s ,使 xs ? n ? 1 或 ys ? n ? 1 。若不然,则对一切 i 均有 xi ? n 且

yi ? n ,从而数列①最多有 n2 个不同的下标,得出数列①中有两个项坐标相同,记 ai 与 a j 的
坐标相同: xi ? x j , yi ? y j ( i ? j ) 。但 当 ai ? a j 时,以 a j 为首项的递增数列前面,至少还可以添上 ai ,从而 xi ? x j ? 1 这与

xi ? x j 矛盾;
当 ai ? a j 时,以 a j 为首项的递减数列前面,至少还可以添上 ai ,从而 yi ? y j ? 1这与

yi ? y j 矛盾。
这些矛盾表明, 反设对一切 i 均有 xi ? n 且 yi ? n 是不行的, 故必存在 s , 使 xs ? n ? 1 或

ys ? n ? 1 。
11.首先全体奇数 1、3、5、??、99 共 50 个都可以成为队员的编号。下面证明不可以

再 增 加 了 。 若 运 动 队 有 51 个 队 员 , 从 小 到 大 记 为 a1 , a2 ,

, a51 ? ? ① , 作 差

??②,这样就得到 101 个数,由于①②中的数都不超过 100 a5 1 ? a , ?1 a 1 a5? 1 a, 2 , a 5 50 的范围,由抽屉原理知,必有两数相等,注意到①中的数互不相等,②中的数也互不相等, 故只能是①中的某个数 ai 与②中的某个数 a51 ? a j 相等,即 ai ? a51 ? a j , ai ? a j ? a51 ,这 说明编号 a51 等于另两队员编号之和( i ? j 时) ,或另一队员编号的 2 倍( i ? j 时) ,这与条 件矛盾,故最多 50 名队员。 12.先证 m ? 117 。若不然,则 m ? 117 ,令 Ai ? {a | a ? i (mod13), a ?S } ,则对一切

a, b ? Ai



i ? 1, 2,

?b ? a ? 117 ,13 ) 均 有 ? ? b ? a ? 13 ? 104 , 从 而 ? a ? b ? 13

a a ?b 13 13 9 9 ? 1? ? 1? ? 1? ? ,这与 b ? a ? b 矛盾,故 m ? 117 。 b b b 104 8 8
再证 m ? 117 时满足条件。因为此时最大的 14 个数 104、105、??、117 分布在 13 个 集 合 中 , 由 抽 屉 原 理 知 , 必 有 两 个 数 a , b ( a ? b ) 属 于 同 一 集 合 Ai , 则

104 ? b ? a ? 117 ?

9 9 ? 104 ? b 。综上所述:最小的 m ? 117 。 8 8

w。w-w*k&s%5¥u


2012江苏省数学竞赛《提优教程》教案:第10讲 抽屉原理

2012江苏省数学竞赛《提优教程》教案:第10讲 抽屉原理_学科竞赛_高中教育_教育专区。第 10 讲 抽屉原理 抽屉原理又叫鸽笼原理、狄里克雷( P. G. Dirchlet,180...

2012江苏省数学竞赛《提优教程》教案:第10讲_覆盖

2012江苏省数学竞赛《提优教程》教案:第10讲_覆盖 隐藏>> 第10 讲 覆盖本节主要内容是图形覆盖与嵌入. 一、图形覆盖的定义: 平面闭图形指的是由平面上一条简...

2012江苏省数学竞赛《提优教程》教案:第11讲 极端原理

2012江苏省数学竞赛《提优教程》教案:第11讲 极端原理_学科竞赛_高中教育_教育专区。第十一讲 极端原理 考虑极端情况,是解决数学问题的非常重要的思考方式。在具体...

2012江苏省数学竞赛《提优教程》教案:第05讲 子集

2012江苏省数学竞赛《提优教程》教案:第05讲 子集_学科竞赛_高中教育_教育专区...由抽屉原理,得集合 S 的子集中至少有两个子集的和相等。若这两个子集有公共...

2012江苏省数学竞赛《提优教程》教案:第11讲 极端原理

10页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,...2012江苏省数学竞赛《提优教程》教案:第11讲 极端原理 隐藏>> 第十一讲 极端...

2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖

2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖_学科竞赛_高中教育_教育专区...的图形 G 所覆盖. 原则 3 (重叠原理) n 个平面图形的面积分别为 S1,S2,?...

2012江苏省数学竞赛《提优教程》教案:第11讲_三角问题选讲

2012江苏省数学竞赛《提优教程》教案:第11讲_三角问题选讲_学科竞赛_高中教育_...10 . 2 2 2 2 例 7 设△ABC 内有一点 P,满足∠PAB=∠PBC=∠PCA=θ...

2012江苏省数学竞赛《提优教程》教案:第36讲__同_余

2012江苏省数学竞赛《提优教程》教案:第36讲__同_余_学科竞赛_高中教育_教育...8,4,2,6(mod10). 这种现象在数学 上称为“模同期现象”.一般地,我们有如...

2012江苏省数学竞赛《提优教程》教案:第80讲_存在性问题(新)

2012江苏省数学竞赛《提优教程》教案:第80讲_存在性问题(新)_学科竞赛_高中教育...说明 解决有关染色问题抽屉原理是经常使用的. 例 4 在坐标平面上,纵、横坐标...