数学竞赛中的抽屉原理

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 数学竞赛中的抽屉原理 【摘 要】虽然抽屉原理的叙述 比较简单，但是其被广泛的应用，其延 伸出了很多中题目。在这类题型中，最 重要的下手点就是构造抽屉，在是构造 抽屉的几种方法，这是灵活应用抽屉原 理的关键 中国论文网 /5/view-5330769.htm 【关键词】数学竞赛；抽屉原理； 题型 一、引言 本文以抽屉原理为研究对象，对 其理论、竞赛题目等内容进行分析和总 结。 二、抽屉原理概述 抽屉原理在国内外都被广泛的应 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 用，我国被记录的最早运用这个理论的 是在晏子春秋中有一个“二桃杀三 士”的故事，讲的是晏子采用借“ 桃”杀 人的办法，不费吹灰之力，杀了得罪他 的三个齐国勇士的故事。抽屉原理形成 理论是由 19 世纪德国数学家狄利克雷 完成成，所以抽屉原理又被称为狄利克 雷原来，建立成理论后，以后逐渐地应 用到引数论、集合论、组合论等数学分 支中，逐步的成为各级数学竞赛常见的 题目。抽屉原理被首次应用是在 1947 年，由匈牙利数学家把这一原理引用到 当时的数学竞赛中。当时匈牙利全国数 学竞赛中有这样一道题目，即：“证明： 任何 6 个人中，一定可以找到 3 个互相 认识的人，或者 3 个互不认识的人。 ”这 道题是数学竞赛中的经典题目，这道题 目从表面看起来，是相互矛盾的，也是 不符合常识的。但如果你懂得抽屉原理， 要证明这个问题是十分简单的。由于这 是一道非常创新的题目，在很短的时间 内，被全世界广泛的流传，随着也使得 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 更多的人知道了这一原理。通过这道题 目，使得抽屉原理被广泛的流传。由于 这个试题的形式新颖，解法巧妙，很快 就在全世界广泛流传，使不少人知道了 这一原理。在我国身边，最长见的如招 生考试、招聘、工作分配等等，都可以 看到抽屉原理的作用。在我国古代文献 中，有不少成功地运用抽屉原理来分析 问题的例子。我国古代科学家虽然很早 就会用抽屉原理来分析具体问题，但是 在古代文献中并未发现关于抽屉原理的 概括性文字，没有人将它抽象为一条普 遍的原理。最后还不得不将这一原理冠 以数百年后西方学者狄里克雷的名字。 三、抽屉原理在数学竞赛中的题 目分析及总结 在上文中，对抽屉原理在数学竞 赛中和生活中的应用进行说明，可见抽 屉原理在生活中被广泛的应用。抽屉原 理在数学竞赛题目分析与解答。例题 1：“证明：任何 6 个人中，一定可以找 到 3 个互相认识的人，或者 3 个互不认 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 识的人。 ”分析：看到这道题目，首先要 把用编号 1、编号 2、编号 3、编号 4、 编号 5、编号 6 代表 6 个人，从中随便 找一个，例如编号 1 吧，把其余 5 个人 放到与“编号 1 认识” 和“与编号 1 不认 识”两个“抽屉”里去，根据抽屉原理， 至少有一个抽屉里有 3 个人。不妨假定 在“与编号 1 认识” 的抽屉里有 3 个人， 他们是编号 2、编号 3、编号 4。如果编 号 2、编号 3、编号 3 这三人互不认识， 那么我们就找到了 3 个互不认识的人； 如果编号 2、编号 3、编号 3 三人中有 两个互相认识，例如编号 2 与编号 3 认 识，那么，编号 1、编号 2、编号 3 就 是 3 个互相认识的人。所以不管哪种情 况，本题的结论都是成立的。例题 2：（第 6 届国际中学生数学奥林匹克 试题）17 名科学家中每两名科学家都和 其他科学家通信，在他们通信时，只讨 论三个题目，而且任意两名科学家通信 时只讨论一个题目，证明：其中至少有 三名科学家，他们相互通信时讨论的是 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 同一个题目。分析：这道题目和例题 1 类似，是例题 1 的一个变形。在解决本 题是，首先视 17 个科学家为 17 个点， 每两个点之间连一条线表示这两个科学 家在讨论同一个问题，若讨论第一个问 题则在相应两点连红线，若讨论第 2 个 问题则在相应两点连条黄线，若讨论第 3 个问题则在相应两点连条蓝线。三名 科学家研究同一个问题就转化为找到一 个三边同颜色的三角形。考虑科学家 A，他要与另外的 16 位科学家每人通信 讨论一个问题，相应于从 A 出发引出 16 条线段，将它们染成 3 种颜色，而 16=35+1，因而必有 6=5+1 条同色， 不妨记为 AB1，AB2 ，AB3 ，AB4，AB5 ，AB6 同红色，若 Bi（i=1，2，6）之间 有红线，则出现红色三角线，命题已成 立；否则 B1，B2 ，B3，B4 ，B5，B6 之间的连线只染有黄蓝两色。考虑从 B1 引出的 5 条线， B1B2，B1B3，B1B4，B1B5，B1B6， -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 用两种颜色染色，因为 5=22+1，故必 有 3=2+1 条线段同色，假设为黄色，并 记它们为 B1B2，B1B3 ， B1B4。这时若 B2，B3，B4 之间有黄线，则有黄色三 角形，命题也成立，若 B2，B3，B4， 之间无黄线，则B2，B3，B4，必为蓝 色三角形，命题仍然成立。回顾上面证 明过程，对于 17 点染 3 色问题可归结 为 6 点染 2 色问题，又可归结为 3 点染 一色问题。反过来，我们可以继续推广。 从以上（3，1）（6，2） （17，3）的过程，易发现： 6=（3-1 ）2+2 ，17=（6-1） 3+2，66= （ 17-1）4+2 ， 同理可得（66-1） 5+2=327， （ 327-1）6+2=1958记为 r1=3，r2=6，r3=17，r4=66，r5=327，r 6=1958， 我们可以得到递推关系式： rn=n（rn-1-1）+2，n=2，3，4这样就 可以构造出 327 点染 5 色问题，1958 点 染 6 色问题，都必出现一个同色三角形。 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 四、结语 通过上述的例题看以看出，虽然 抽屉原理的叙述比较简单，但是其被广 泛的应用，其延伸出了很多中题目。在 这类题型中，最重要的下手点就是构造 抽屉，在是构造抽屉的几种方法，这是 灵活应用抽屉原理的关键。从上面的例 子中，可以发现，解