数学竞赛中的抽屉原理

【摘 要】虽然抽屉原理的叙述比较简单，但是其被广泛的应用，其延伸出了很多中题目。在这类题型中，最重要的下手点就是构造抽屉，在是构造抽屉的几种方法，这是灵活应用抽屉原理的关键

【关键词】数学竞赛；抽屉原理；题型

一、引言

本文以抽屉原理为研究对象，对其理论、竞赛题目等内容进行分析和总结。

二、抽屉原理概述

抽屉原理在国内外都被广泛的应用，我国被记录的最早运用这个理论的是在《晏子春秋》中有一个“二桃杀三士”的故事，讲的是晏子采用借“桃”杀人的办法，不费吹灰之力，杀了得罪他的三个齐国勇士的故事。抽屉原理形成理论是由19世纪德国数学家狄利克雷完成成，所以抽屉原理又被称为狄利克雷原来，建立成理论后，以后逐渐地应用到引数论、集合论、组合论等数学分支中，逐步的成为各级数学竞赛常见的题目。抽屉原理被首次应用是在1947年，由匈牙利数学家把这一原理引用到当时的数学竞赛中。当时匈牙利全国数学竞赛中有这样一道题目，即：“证明：任何6个人中，一定可以找到3个互相认识的人，或者3个互不认识的人。”这道题是数学竞赛中的经典题目，这道题目从表面看起来，是相互矛盾的，也是不符合常识的。但如果你懂得抽屉原理，要证明这个问题是十分简单的。由于这是一道非常创新的题目，在很短的时间内，被全世界广泛的流传，随着也使得更多的人知道了这一原理。通过这道题目，使得抽屉原理被广泛的流传。由于这个试题的形式新颖，解法巧妙，很快就在全世界广泛流传，使不少人知道了这一原理。在我国身边，最长见的如招生考试、招聘、工作分配等等，都可以看到抽屉原理的作用。在我国古代文献中，有不少成功地运用抽屉原理来分析问题的例子。我国古代科学家虽然很早就会用抽屉原理来分析具体问题，但是在古代文献中并未发现关于抽屉原理的概括性文字，没有人将它抽象为一条普遍的原理。最后还不得不将这一原理冠以数百年后西方学者狄里克雷的名字。

三、抽屉原理在数学竞赛中的题目分析及总结

在上文中，对抽屉原理在数学竞赛中和生活中的应用进行说明，可见抽屉原理在生活中被广泛的应用。抽屉原理在数学竞赛题目分析与解答。例题1：“证明：任何6个人中，一定可以找到3个互相认识的人，或者3个互不认识的人。”分析：看到这道题目，首先要把用编号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名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而且任意两名科学家通信时只讨论一个题目，证明：其中至少有三名科学家，他们相互通信时讨论的是同一个题目。分析：这道题目和例题1类似，是例题1的一个变形。在解决本题是，首先视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。考虑科学家A，他要与另外的16位科学家每人通信讨论一个问题，相应于从A出发引出16条线段，将它们染成3种颜色，而16=3×5+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，用两种颜色染色，因为5=2×2+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，r6=1958，…

我们可以得到递推关系式：rn=n（rn-1-1）+2，n=2，3，4…这样就可以构造出327点染5色问题，1958点染6色问题，都必出现一个同色三角形。

四、结语

通过上述的例题看以看出，虽然抽屉原理的叙述比较简单，但是其被广泛的应用，其延伸出了很多中题目。在这类题型中，最重要的下手点就是构造抽屉，在是构造抽屉的几种方法，这是灵活应用抽屉原理的关键。从上面的例子中，可以发现，解决抽屉原理的问题时，主要有三个步骤：1、构成分类的对象有个元素；2、找出分类的规则，将个元素分成个抽屉，并证明每个抽屉中的元素符合题意；3、应用抽屉原理证明结论成立，应用的关键在于构造抽屉的方法，构造抽屉主要依赖于自身的经验和技巧，充分体现了个人解题思维的灵活性。