高中数学竞赛专题精讲23抽屉原理(含答案)

《高中数学竞赛专题精讲23抽屉原理(含答案)》由会员分享，可在线阅读，更多相关《高中数学竞赛专题精讲23抽屉原理(含答案)（11页珍藏版）》请在金锄头文库上搜索。

1、23 抽屉原理 在数学问题中有一类与“存在性”有关的问题，例如：“13个人中至少有两个人出生 在相同月份”； “某校 400 名学生中，一定存在两名学生，他们在同一天过生日”；“2003 个人任意分成200 个小组，一定存在一组，其成员数不少于11”；“把 0 ， 1 内的全部有 理数放到100 个集合中， 一定存在一个集合，它里面有无限多个有理数”。这类存在性问题 中，“存在”的含义是“至少有一个”。在解决这类问题时，只要求指明存在，一般并不需 要指出哪一个， 也不需要确定通过什么方式把这个存在的东西找出来。这类问题相对来说涉 及到的运算较少，依据的理论也不复杂，我们把这些理论称之为“抽屉原

2、理”。 “抽屉原理”最先是由19 世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问 题的， 所以又称“迪里赫莱原理”，也有称“鸽巢原理”的。这个原理可以简单地叙述为“把 10 个苹果，任意分放在9 个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。 这个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常常得到一些令人惊异 的结果。 抽屉原理是国际国内各级各类数学竞赛中的重要内容，本讲就来学习它的有关知识 及其应用。 （一）抽屉原理的基本形式 定理 1、如果把n+1 个元素分成n 个集合，那么不管怎么分，都存在一个集合，其中至 少有两个元素。 证明：（用反证法）若不存

3、在至少有两个元素的集合，则每个集合至多1 个元素，从而 n 个集合至多有n 个元素，此与共有n+1 个元素矛盾，故命题成立。 在定理 1 的叙述中， 可以把“元素”改为“物件”，把“集合”改成“抽屉”，抽屉原 理正是由此得名。 同样，可以把“元素”改成“鸽子”，把“分成n 个集合”改成“飞进n 个鸽笼中”。 “鸽笼原理”由此得名。 例题讲解 1 已知在边长为1 的等边三角形内（包括边界）有任意五个点（图1）。证明：至少有 两个点之间的距离不大于 2从 1-100 的自然数中， 任意取出51 个数，证明其中一定有两个数，它们中的一个是另一 个的整数倍。 3从前 25 个自然数中任意取出7 个数，

4、证明：取出的数中一定有两个数，这两个数中大 数不超过小数的1.5 倍。 4已给一个由10 个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个 无公共元素的子集合，各子集合中各数之和相等。 5在坐标平面上任取五个整点（该点的横纵坐标都取整数），证明：其中一定存在两个整 点，它们的连线中点仍是整点。 6在任意给出的100 个整数中，都可以找出若干个数来（可以是一个数），它们的和可被 100 整除。 7 17 名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目， 而且任意两名科学家通信时只讨论一个题目，证明： 其中至少有三名科学家，他们相互通信 时讨论的是同一个题目。

5、 课后练习 1幼儿园买来了不少白兔、 熊猫、长颈鹿塑料玩具， 每个小朋友任意选择两件， 那么不管怎样挑选， 在任意七个小朋友中总有两个彼此选的玩具都相同，试说明 道理. 2正方体各面上涂上红色或蓝色的油漆（每面只涂一种色），证明正方体一定 有三个面颜色相同 . 3把 1 到 10 的自然数摆成一个圆圈， 证明一定存在在个相邻的数，它们的和数 大于 17. 4有红袜 2 双，白袜 3 双，黑袜 4 双，黄袜 5 双，蓝袜 6 双（每双袜子包装在 一起）若取出 9 双，证明其中必有黑袜或黄袜2 双. 5在边长为 1 的正方形内，任意给定13 个点，试证：其中必有4 个点，以此 4 点 为顶点的四边

6、开面积不超过（假定四点在一直线上构成面积为零的四边形）. 6在一条笔直的马路旁种树，从起点起，每隔一米种一棵树，如果把三块“爱 护树木”的小牌分别挂在三棵树上，那么不管怎样挂， 至少有两棵挂牌的树之间 的距离是偶数（以米为单位），这是为什么？ 课后练习答案 1. 解 从三种玩具中挑选两件，搭配方式只能是下面六种： （兔、兔），（兔、熊猫），（兔、长颈鹿）， （熊猫、熊猫）， （熊猫、长颈鹿）， （长颈鹿、长颈鹿） 把每种搭配方式看作一个抽屉，把7 个小朋友看作物体，那么根据原则1，至少有 两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式， 选的玩具相同 . 原则 2 如果

7、把 mn+k(k1)个物体放进n 个抽屉，则至少有一个抽屉至多放进m+1 个物体 . 证明同原则相仿 .若每个抽屉至多放进m个物体 , 那么 n 个抽屉至多放进mn 个物体 , 与题设不符，故不可能. 原则 1 可看作原则 2 的物例（ m=1 ） 2. 证明把两种颜色当作两个抽屉，把正方体六个面当作物体，那么6=22+2，根据 原则二，至少有三个面涂上相同的颜色. 3. 证明 如图 12-1，设 a1，a2，a3， a9，a10分别代表不超过10 的十个自然数， 它们围成一个圈，三个相邻的数的组成是（a1，a2，a3），（a2，a3，a4），（a3，a4， a5），, （a9，a10，a1）

8、,（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 个物体， 或在

9、第二个抽屉里至少放入m2+1 个物体，或在第 n 个抽屉 里至少放入 mn+1 个物体 . 证明假定第一个抽屉放入物体的数不超过m1个，第二个抽屉放入物体的数不超过m2 个，第n 个抽屉放入物体的个数不超过mn，那么放入所有抽屉的物体总数不 超过 m1+m2+mn个，与题设矛盾 . 4. 证明 除可能取出红袜、白袜3 双外. 还至少从其它三种颜色的袜子里取出4 双， 根据原理 3，必在黑袜或黄袜、蓝袜里取2 双. 上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题，不错，这正是 抽屉原则的主要作用. 需要说明的是，运用抽屉原则只是肯定了“存在”、“总有”、 “至少有”，却不能确切地指出

10、哪个抽屉里存在多少. 制造抽屉是运用原则的一大关键 首先要指出的是，对于同一问题，常可依据情况，从不同角度设计抽屉，从而导致 不同的制造抽屉的方式. 5. 证明如图 12-2 把正方形分成四个相同的小正方形. 因 13=34+1，根据原则2，总有 4 点落在同一个小正方形内（或边界上），以此4 点为顶点的四边形的面积不超过小正方形的面积，也就不超过整个正方形面积的. 事实上，由于解决问题的核心在于将正方形分割成四个面积相等的部分，所以还可 以把正方形按图12-3（此处无图）所示的形式分割. 合理地制造抽屉必须建立在充分考虑问题自身特点的基础上. 6. 解如图 12-4（设挂牌的三棵树依次为A、

11、B、C.AB=a，BC=b ，若 a、b 中有一为偶 数，命题得证 . 否则 a、b 均为奇数，则AC=a+b为偶数，命题得证 . 下面我们换一个角度考虑： 给每棵树上编上号， 于是两棵树之间的距离就是号码差， 由于树的号码只能为奇数和偶数两类，那么挂牌的三棵树号码至少有两个同为奇数 或偶数，它们的差必为偶数，问题得证. 后一证明十分巧妙， 通过编号码， 将两树间距离转化为号码差. 这种转化的思想方法 是一种非常重要的数学方法 例题答案： 1分析： 5 个点的分布是任意的。如果要证明“在边长为1 的等边三角形内（包括边 界）有 5 个点，那么这 5 个点中一定有距离不大于的两点”， 则顺次连接

12、三角形三边中点， 即三角形的三条中位线，可以分原等边三角形为4 个全等的边长为的小等边三角形，则5 个点中必有2 点位于同一个小等边三角形中（包括边界），其距离便不大于。 以上结论要由定理“三角形内（包括边界） 任意两点间的距离不大于其最大边长”来保 证，下面我们就来证明这个定理。 如图 2，设 BC是ABC的最大边， P， M是ABC内（包括边界）任意两点，连接PM ， 过 P分别作 AB 、BC边的平行线，过M作 AC边的平行线，设各平行线交点为P、Q、N，那么 PQN= C，QNP= A 因为 BC AB ，所以 AC，则 QNP PQN ，而 QMP QNP PQN （三角形的外 角大

13、于不相邻的内角），所以PQ PM 。显然BC PQ ，故 BC PM 。 由此我们可以推知，边长为的等边三角形内（包括边界）两点间的距离不大于。 说明： （1）这里是用等分三角形的方法来构造“抽屉”。类似地，还可以利用等分线段、等 分正方形的方法来构造“抽屉”。例如“任取n+1个正数 ai， 满足 0ai1 （i=1,2, ,n+1）， 试证明：这n+1 个数中必存在两个数，其差的绝对值小于”。又如：“在边长为1 的正方 形内任意放置五个点，求证：其中必有两点，这两点之间的距离不大于。 （2）例 1 中，如果把条件（包括边界）去掉，则结论可以修改为：至少有两个点之间 的距离小于，请读者试证之，

14、并比较证明的差别。 （3）用同样的方法可证明以下结论： i ） 在边长为1 的等边三角形中有n 2+1 个点，这 n2+1 个点中一定有距离不大于 的两点。 ii ）在边长为1 的等边三角形内有n 2+1 个点，这 n 2+1 个点中一定有距离小于 的两点。 （4）将（ 3）中两个命题中的等边三角形换成正方形，相应的结论中的换成，命 题仍然成立。 （5）读者还可以考虑相反的问题：一般地，“至少需要多少个点，才能够使得边长 为 1 的正三角形内（包括边界）有两点其距离不超过”。 2分析：本题似乎茫无头绪，从何入手？其关键何在？其实就在“两个数”，其中一个是 另一个的整数倍。我们要构造“抽屉”，使

15、得每个抽屉里任取两个数，都有一个是另一个的 整数倍， 这只有把公比是正整数的整个等比数列都放进去同一个抽屉才行，这里用得到一个 自然数分类的基本知识：任何一个正整数都可以表示成一个奇数与2 的方幂的积，即若 m N+,KN+ ，nN,则 m=(2k- 1)2 n， 并且这种表示方式是唯一的， 如 1=12，2=121， 3=32， 证明：因为任何一个正整数都能表示成一个奇数乘2 的方幂， 并且这种表示方法是唯一 的，所以我们可把1-100 的正整数分成如下50 个抽屉（因为1-100 中共有 50 个奇数）： （1）1 ，12，12 2，123，124，125，126； （2）3 ，32，32

16、 2，323，324，325 ； （3）5 ，52，52 2，523，524； （4）7 ，72，72 2，723； （5）9 ，92，92 2，923； （6）11 ，112，112 2 ，112 3； （25）49 ，492； （26）51 ； （50）99 。 这样， 1-100 的正整数就无重复，无遗漏地放进这50 个抽屉内了。从这100 个数中任 取 51 个数，也即从这50 个抽屉内任取51 个数，根据抽屉原则，其中必定至少有两个数属 于同一个抽屉，即属于（1）- （25）号中的某一个抽屉，显然，在这25 个抽屉中的任何同 一个抽屉内的两个数中，一个是另一个的整数倍。 说明： （1）从上面的证明中可以看出，本题能够推广到一般情形：从1-2n 的自然数中，任意 取出 n+1 个数， 则其中必有两个数，它们中的一个是另一个的整数倍。想一想，为什么？因 为 1-2n 中共含 1，3， 2n-1 这 n 个奇数，因此可以制造n 个抽屉，而n+1n，由抽屉 原则，结论就是必然的了。给n以具体值，就可以构