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

高中数学奥林匹克竞赛讲座:10抽屉原则


高考资源网(ks5u.com)

您身边的高考专家

竞赛讲座 10 --抽屉原则 --抽屉原则
大家知道,两个抽屉要放置三只苹果,那么一定有两只苹果放在同一个抽屉里, 更一般地说,只要被放置的苹果数比抽屉数目大,就一定会有两只或更多只的苹果放 进同一个抽屉,可不要小看这一简单事实,它包含着一个重要而又十分基本的原则 ——抽屉原则. 1. 抽屉原则有几种最常见的形式

原则 1 如果把 n+k(k≥1)个物体放进 n 只抽屉里,则至少有一只抽屉要放进两个或更 多个物体: 原则本身十分浅显,为了加深对它的认识,我们还是运用反证法给予证明;如果每个 抽屉至多只能放进一个物体,那么物体的总数至多是 n,而不是题设的 n+k(k≥1), 这不可能. 原则虽简单.巧妙地运用原则却可十分便利地解决一些看上去相当复杂,甚至感到无 从下手的总是,比如说,我们可以断言在我国至少有两个人出生的时间相差不超过 4 秒钟,这是个惊人的结论,该是经过很多人的艰苦劳动,统计所得的吧!不,只须我 们稍动手算一下: 不妨假设人的寿命不超过 4 万天(约 110 岁,超过这个年龄数的人为数甚少),则

10 亿人口安排在 8 亿 6 千 4 百万个"抽屉"里,根据原则 1,即知结论成立. 下面我们再举一个例子: 例 1 幼儿园买来了不少白兔,熊猫,长颈鹿塑料玩具,每个小朋友任意选择两件, 那么不管怎样挑选, 在任意七个小朋友中总有两个彼此选的玩具都相同, 试说明道理. 解 从三种玩具中挑选两件,搭配方式只能是下面六种: (兔,兔),(兔,熊猫),(兔,长颈鹿),(熊猫,熊猫),(熊猫,长颈鹿), (长颈鹿,长颈鹿) 把每种搭配方式看作一个抽屉,把 7 个小朋友看作物体,那么根据原则 1,至少有两 个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的 玩具相同.

www.ks5u.com

-1-

版权所有@高考资源网

高考资源网(ks5u.com)

您身边的高考专家

原则 2 如果把 mn+k(k≥1)个物体放进 n 个抽屉,则至少有 一个抽屉至多放进 m+1 个物体.证明同原则相仿.若每个抽屉 至多放进 m 个物体,那么 n 个抽屉至多放进 mn 个物体,与题 设不符,故不可能. 原则 1 可看作原则 2 的物例(m=1) 例 2 正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三 个面颜色相同. 证明把两种颜色当作两个抽屉,把正方体六个面当作物体,那么 6=2×2+2,根据原则 二,至少有三个面涂上相同的颜色. 例 3 把 1 到 10 的自然数摆成一个圆圈,证明一定存在在个相邻的数,它们的和数大 于 17. 证明 如图 12-1,设 a1,a2,a3,…,a9,a10 分别代表不超过 10 的十个自然数,它们 (a (a 围成一个圈,三个相邻的数的组成是(a1,a2,a3), 2,a3,a4), 3,a4,a5),…, (a9,a10,a1),(a10,a1,a2)共十组.现把它们看作十个抽屉,每个抽屉的物体数是 a1+a2+a3,a2+a3+a4,a3+a4+a5,…a9+a10+a1,a10+a1+a2,由于 (a1+a2+a3)+(a2+a3+a4)+…+(a9+a10+a1)+(a10+a1+a2) =3(a1+a2+…+a9+a10) =3×(1+2+…+9+10)

根据原则 2,至少有一个括号内的三数和不少于 17,即至少有三个相邻的数的和不小于 17. 原则 1,原则 2 可归结到期更一般形式: 原则 3 把 m1+m2+…+mn+k(k≥1)个物体放入 n 个抽屉里,那么或在第一个抽屉里至少放 入 m1+1 个物体,或在第二个抽屉里至少放入 m2+1 个物体,……,或在第 n 个抽屉里 至少放入 mn+1 个物体. 证明假定第一个抽屉放入物体的数不超过 m1 个,第二个抽屉放入物体的数不超过 m2 个,……,第 n 个抽屉放入物体的个数不超过 mn,那么放入所有抽屉的物体总数不超 过 m1+m2+…+mn 个,与题设矛盾. 例 4 有红袜 2 双,白袜 3 双,黑袜 4 双,黄袜 5 双,蓝袜 6 双(每双袜子包装在一起) 若取出 9 双,证明其中必有黑袜或黄袜 2 双.

www.ks5u.com

-2-

版权所有@高考资源网

高考资源网(ks5u.com)

您身边的高考专家

证明 除可能取出红袜,白袜 3 双外.还至少从其它三种颜色的袜子里取出 4 双,根据 原理 3,必在黑袜或黄袜,蓝袜里取 2 双. 上面数例论证的似乎都是"存在","总有","至少有"的问题,不错,这正是抽 屉原则的主要作用.需要说明的是,运用抽屉原则只是肯定了"存在","总有", "至少有",却不能确切地指出哪个抽屉里存在多少. 2. 制造抽屉是运用原则的一大关键

首先要指出的是,对于同一问题,常可依据情况,从不同角度设计抽屉,从而导致不 同的制造抽屉的方式. 例 5 在边长为 1 的正方形内,任意给定 13 个点,试证:其中必有 4 个点,以此 4 点

为顶点的四边开面积不超过

(假定四点在一直线上构成面积为零的四边形).

证明如图 12-2 把正方形分成四个相同的小正方形. 因 13=3×4+1,根据原则 2,总有 4 点落在同一个小正方形内(或边界上),以此 4

点为顶点的四边形的面积不超过小正方形的面积,也就不超过整个正方形面积的

.

事实上,由于解决问题的核心在于将正方形分割成四个面积相等的部分,所以还可以 把正方形按图 12-3(此处无图)所示的形式分割. 合理地制造抽屉必须建立在充分考虑问题自身特点的基础上. 例 6 在一条笔直的马路旁种树,从起点起,每隔一米种一棵树,如果把三块"爱护树 木"的小牌分别挂在三棵树上,那么不管怎样挂,至少有两棵挂牌的树之间的距离是 偶数(以米为单位),这是为什么?

www.ks5u.com

-3-

版权所有@高考资源网

高考资源网(ks5u.com)

您身边的高考专家

解如图 12-4(设挂牌的三棵树依次为 A,B,C.AB=a,BC=b,若 a,b 中有一为偶数, 命题得证.否则 a,b 均为奇数,则 AC=a+b 为偶数,命题得证. 下面我们换一个角度考虑:给每棵树上编上号,于是两棵树之间的距离就是号码差, 由于树的号码只能为奇数和偶数两类,那么挂牌的三棵树号码至少有两个同为奇数或 偶数,它们的差必为偶数,问题得证. 后一证明十分巧妙,通过编号码,将两树间距离转化为号码差.这种转化的思想方法 是一种非常重要的数学方法

例 7 从自然数 1,2,3,…99,100 这 100 个数中随意取出 51 个数来,求证:其中一 定有两个数,,它们中的一个是另一个的倍数. 分析设法制造抽屉: (1)不超过 50 个; (2)每个抽屉的里的数(除仅有的一个外), 其中一个数是另一个数的倍数,一个自然数的想法是从数的质因数表示形式入手. 解设第一个抽屉里放进数:1,1×2,1×2 ,1×2 ,1×2 ,1×2 ,1×2 ; 第二个抽屉时放进数:3,3×2,3×2 ,3×2 ,3×2 ,3×2 ; 第三个抽屉里放进数:5,5×2,5×2 ,5×2 ,5×2 ; ……………… 第二十五个抽屉里放进数:49,49×2; 第二十六个抽屉里放进数:51. ……………… 第五十个抽屉里放进数:99. 那么随意取出 51 个数中,必有两个数同属一个抽屉,其中一个数是另一个数的倍数.
2 3 4 2 3 4 5 2 3 4 5 6

www.ks5u.com

-4-

版权所有@高考资源网

高考资源网(ks5u.com)

您身边的高考专家

制造抽屉并非总是一帆风顺的,有时要边制造边调整,改进. 例 8 任意给定 7 个不同的自然数,求证其中必有两个整数,其和或差是 10 的倍数. 分析注意到这些数队以 10 的余数即个位数字,以 0,1,…,9 为标准制造 10 个抽屉, 标以[0],[1],…,[9].若有两数落入同一抽屉,其差是 10 的倍数,只是仅有 7 个 自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4], [3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是 10 的倍 数. 3. 较复杂的问题须反复地运用抽屉原则,将复杂问题转化为简单问题.

例 9 以(x,y,z)表示三元有序整数组,其中 x,y,z 为整数,试证:在任意七个 三元整数组中,至少有两个三元数组,它们的 x,y,z 元中有两对都是奇数或都是偶 数. 分析 设七个三元素组为 A1(x1,y1,z1),A2(x2,y2,z2),…,A7(x7,y7,z7). 现在逐步探索,从 x 元开始,由抽屉原则,x1,x2,…,x7 这七个数中,必定有四个 数具有相同的奇偶性,不妨设这四个数是 x1,x2,x3,x4 且为偶数,接着集中考虑 A1, A2,A3,A4 这四组数的 y 元,若比如 y1,y2,y3,y4 中有两个是偶数,则问题已证,否 则至多有一个是偶数,比如 y4 是偶数,这时我们再来集中考虑 A1,A2,A3 的 z 元.在 z1,z2,z3 中,由抽屉原则必有两个数具有相同的奇偶性,如 z1,z2,这时无论它们是 奇数,还是偶数,问题都已得到证明. 下面介绍一个著名问题. 例 10 任选 6 人,试证其中必有 3 人,他们互相认识或都不认识. 分析 用 A,B,C,D,E,F 表示这 6 个人,首先以 A 为中心考虑,他与另外五个人 B, C,D,E,F 只有两种可能的关系:认识或不认识,那么由抽屉原则,他必定与其中某 三人认识或不认识,现不妨设 A 认识 B,C,D 三人,当 B,C,D 三人都互不认识时, 问题得证;当 B,C,D 三人中有两人认识,如 B,C 认识时,则 A,B,C 互相认识, 问题也得证. 本例和上例都采用了舍去保留,化繁为简,逐步缩小考虑范围的方法. 例 11a,b,c,d 为四个任意给定的整数,求证:以下六个差数 b-a,c-a,d-a,c-b,d-b,d-c 的乘积一定可以被 12 整除. 证明 把这 6 个差数的乘积记为 p,我们必须且只须证明:3 与 4 都可以整除 p,以下 分两步进行. 第一步,把 a,b,c,d 按以 3 为除数的余数来分类,这样的类只有三个,故知 a,b, c,d 中至少有 2 个除以 3 的余数相同,例如,不妨设为 a,b,这时 3 可整除 b-a,从 而 3 可整除 p.
www.ks5u.com -5版权所有@高考资源网

高考资源网(ks5u.com)

您身边的高考专家

第二步,再把 a,b,c,d 按以 4 为除数的余数来分类,这种类至多只有四个,如果 a, b,c,d 中有二数除以 4 的余数相同,那么与第一步类似,我们立即可作出 4 可整除 p 的结论. 设 a,b,c,d 四数除以 4 的余数不同,由此推知,a,b,c,d 之中必有二个奇数(不 妨设为 a,b),也必有二个偶数(设为 c,d),这时 b-a 为偶数,d-c 也是偶数,故 4 可整除(b-a)(d-c),自然也可得出 4 可整除 p. 如果能进一步灵活运用原则,不仅制造抽屉,还根据问题的特征,制造出放进抽屉的 物体,则更可收到意想不到的效果. 例 12 求证:从任意 n 个自然数 a1,a2,…,an 中可以找到若干个数,使它们的和是 n 的倍数. 分析以 0,1,…,n-1 即被 n 除的余数分类制造抽屉的合理的,但把什么样的数作为 抽屉里的物体呢?扣住"和",构造下列和数: S1=a1, S2=a1+a2, S=a1+a2+a3, ………… Sn=a1+a2+…+an, 其中任意两个和数之差仍为和数,若他们之中有一是 n 的倍数,问题得证,否则至少 有两个数被 n 除余数相同,则它们的差即它们中若干数(包括 1 个)的和是 n 的倍数, 问题同样得证. 例子 3(北京 1990 年高一竞赛)910 瓶红,蓝墨水,排成 130 行,每行 7 瓶,证明: 不论怎样排列,红蓝墨水瓶的颜色次序必定出现下述两种情况之一种: (1)至少有三行完全相同; (2)至少有两组(四行)每组的两行完全相同. 解 910 瓶红,蓝墨水排成 130 行,每行 7 瓶,对一行来说,每个位置上有红蓝两种可 7 对每一种不同排法设为一种"行式", 能,因此,一行的红,蓝墨水排法有 2 =128 种, 共有 128 种行式. 现有 130 行,在其中任取 129 行,依抽屉原则知,必有两行 A,B 行式相同. 除 A,B 外余下 128 行,若有一行 P 与 A 行式相同,知满足(1)至少有三行 A,B,P 完全相同,若在这 128 行中设直一行 5A 行或相同,那么这 128 行至多有 127 种行式,
www.ks5u.com -6版权所有@高考资源网

高考资源网(ks5u.com)

您身边的高考专家

依抽屉原则,必有两行 C,D 具有相同行式,这样便找到了(A,B),(C,D)两组 (四行),且两组两行完全相同. 练习十二 1. 一个篮球运动员在 15 分钟内将球投进篮圈 20 次,证明总有某一分钟他至少投 进两次. 2. 有黑,白,黄筷子各 8 只,不用眼睛看,任意地取出筷子来,使得至少有两双 筷子不同色,那么至少要取出多少只筷子才能做到? 3. 证明:在 1,2,3,…,10 这十个数中任取六个数,那么这六个数中总可以找 到两个数,其中一个是另一个的倍数. 4. 证明:任意 502 个整数中,必有两个整数的和或差是 998 的倍数.

5. 任意写一个由数字 1,2,3 组成的 30 位数,从这 30 位数任意截取相邻三位, 可得一个三位数,证明:在从各个不同位置上截得的三位数中至少有两个相等. 6. 证明:把任意 10 个自然数用适当的运算符号连接起来,运算的结果总能被 1890 整除. 7. 七条直线两两相交,所得的角中至少有一个角小于 26°.

8. 用 2 种颜色涂 3 行 9 列共 27 个小方格,证明:不论如何涂色,其中必至少有两 列,它们的涂色方式相同. 9. 10. 用 2 种颜色涂 5×5 共 25 个小方格,证明:必有一个四角同色的矩形出现. 求证存在形如 11…11 的一个数,此数是 1987 的倍数.

练习十二 1.15 分钟里在每一分钟看作一个抽屉,20 次投篮看作 20 个物体,根据原理一即得. 2.至少要取11只筷子.因为11只筷子中必有一双筷子同色,不妨设它是黄色,则 黑色或白色的筷子至少有3只,其中必有一双同色,即黑色或白色,故取11只筷子 足以保证成功.但少于11只不行,如取10只筷子,闵可能出现8只黄色,黑白各 一只,不合要求. 3.将10个数分成5组:(1,7),(2,6),(3,9),(4,8),(5, 10).任取六个数必有两个落入同一组,而同组二数中一数是另一数的倍数.

www.ks5u.com

-7-

版权所有@高考资源网

高考资源网(ks5u.com)

您身边的高考专家

4.每个整数被998除,余数必是0,1,2,…,997中的一个.把这998 个余数制造为(0),(1,997),(2,996),…,(497,501), (498),(499),(500)共501个抽屉,把502个整数按被998 除的余数大小分别放入上述抽屉,必有两数进入同一抽屉.若余数相同,那么它们的 差是998的倍数,否则和为998的倍数. 5.从各种位置上截得的三位数有28个,但由1,2,3组成的不同三位数有3× 3×3=27个,故有两个截得的三位数相同. 6.1890=2×3×5×7×9.将10个数记为x1,x2,…,x9,x10.1 0个数中至少有两个被9除余数相同,设为x1,x2则x1-x2可被9整除.同样剩 下8个数中有两个数的差可被7整除,记为x3-x4,剩下6个数中有两个数的差可 被5整除, 记为x5-x6, 剩下4个数中有两个数的差可被3整除, 记为x7-x8. 剩 下两数x9,x10,若有一数为偶数,则x9,x10可被2整除,否则x9-x10可被 2整除.故乘积(x1-x2)(x3-x4)(x5-x6)(x7-x8)x9x10与 (x1-x2)(x3-x4)(x5-x6)(x7-x8)(x9-x10)二者之一必可 被1890整除. 7.任选一点P,过P点分别作各线的平行线,则它们把一周角分成14个彼此相邻 的角,其中至少有一个角小于26°. 8.用两种颜色涂1×3的小方格共有8种方法.现有9列,由抽屉原则,必有两列 涂法一样. 9.设两种颜色为红,蓝,考察第一行的涂色.必有三格同色,不妨设为红色,且在 左边三列.现考察左边三列,若下面四行中某一行有两格同为红色,则出现四角同红 色矩形,否则每行仅可能一格染红色,从而四行中必有二行左边三列中有两列同染蓝 色,从而得到四角同为蓝色的矩形.

共1987个数,其中必有一个是1987的倍数, 10.考虑1,11,… 否则必有两数被1987除余数相同,其差

是1987的倍数.但10 与1987没有 除1外的因数,故 是1987倍数导致矛盾.

i

www.ks5u.com

-8-

版权所有@高考资源网


相关文章:
数学奥林匹克专题讲座 第13讲 抽屉原理
数学奥林匹克专题讲座 第 13 讲 抽屉原理把 5 个苹果放到 4 个抽屉中,必然有一个抽屉中至少有 2 个苹果,这是抽屉原理 的通俗解释。一般地,我们将它表述为:...
高中数学竞赛讲义-抽屉原理
高中数学竞赛讲义-抽屉原理_学科竞赛_高中教育_教育专区。数学教育网---数学试题...4.已给一个由 10 个互不相等的两位十进制正整数组成的集合。求证:这个集合必...
高中数学奥赛辅导 第七讲 抽屉原则、容斥原理
第七讲 抽屉原则、容斥原理_学科竞赛_高中教育_教育...如 10 个苹果放入 9 个抽屉,可以随意地一个抽屉...(第 1 届全俄数学奥林匹克试题) 【证明】要使...
奥林匹克数学·抽屉原则训练第一讲
奥林匹克数学·抽屉原则训练第一讲_学科竞赛_小学...10.用红、黄两种颜色将 2×5 的矩形的小方格随意...数学奥林匹克竞赛讲座 1... 287人阅读 5页 免费...
初中数学竞赛:抽屉原则
初中数学竞赛:抽屉原则 【知识精读】 1, 4 个苹果放进 3 个抽屉, 有一种...高中数学竞赛讲座 10抽屉... 34人阅读 8页 免费 初中数学竞赛精品标准教.....
全国高中数学竞赛讲义-抽屉原理练习题
全国高中数学竞赛讲义-抽屉原理练习题_学科竞赛_高中教育_教育专区。§23 抽屉...3.证明 如图 12-1,设 a1,a2,a3,?,a9,a10 分别代表不超过 10 的十个...
第七讲抽屉原则
又称鸽巢原理 ,最早由德国数学家狄利克雷提出,并...【解析】 由于任取 10 个数中有两个数在同一个...竞赛讲座-抽屉原则 8页 免费 第七讲 抽屉原理 暂无...
高中数学竞赛培训 抽屉原理 Word版 含答案
高中数学竞赛培训 抽屉原理 Word版 含答案_学科竞赛_高中教育_教育专区。高中数学竞赛培训 Word版 含答案 抽屉原理 把八个苹果任意地放进七个抽屉里, 不论怎样放...
2012江苏省数学竞赛《提优教程》教案:第10讲 抽屉原理
2012江苏省数学竞赛《提优教程》教案:第10抽屉原理_学科竞赛_高中教育_教育专区。第 10抽屉原理 抽屉原理又叫鸽笼原理、狄里克雷( P. G. Dirchlet,18...
小学奥数系列:20简单抽屉原则
小学奥数系列:20简单抽屉原则_学科竞赛_小学教育_...3.一次智力竞赛,试卷上出了 10 道选择题,评分标准...数学教师带领 30 名学生做游戏,师生每人都各自在一...
更多相关标签: