鸽巢原理在中学数学中的应用

一、鸽巢原理

鸽 巣 原理又名抽屉原理，或者由发明人命名为狄利克雷原理，其发现归功于德国数学家狄利克雷(Divichlet，1805—1855)。鸽巢原理在组合数学中起着非常重要的作用，在数论和密码学中应用丰富。鸽巢的构建是巧妙用鸽巢原理解决问题的关键，即通过转化找出符合题设要求的分类准则。

二、中学数学中鸽巢原理的构造方法

鸽巢构造的方法较多，其中有两大类最具有普遍性和参考意义：（1）分割图形、等分区间的方式；（2）鸽巢通过分组和分类的方法来构建的。

（一）分割图形构造鸽巢

几何图形题中存在多个点时，一般讲图形进行分割，将分割得出的子图做为鸽巢。通常使得鸽 巣 间的元素既互不重复，且覆盖所有元素，但也不绝对，某些情况下根据题设情况，鸽巣间也可以包含公共元素。

例1如果直径为5的圆内有10个点，其中有某两个点的距离小于2。

证明 如图（3）所示，将圆等分成8个扇形，中心作直径d=1.8的圆，把已知的圆分成了九个鸽巢。由鸽巢原理，圆内的10个点，必有两点落在同一区域内，只需证明每个区域中的两个点距离都小于2。

显然，小圆内任两点间的距离小于2，曲边扇形ABCD中，AB＜2，AD＜2,CD＜2,而任两点距离最大者 AC，有

图（3）

（二）等分区间构造鸽巢

若某区间内存在若干个的点，一种构造方式是把区间等分成n-1个子区间（若有n个点）。根据鸽巢原理，则必有两点落于同一子区间，且间距小于等于。该构造法对于一些不等式的证明具有奇效[6]。

例 2 已知 11 个数 x1,x2,…，x11，全满足 0≤xi≤1，i=1,2,…,11。证明必有两个 xi,xj(i≠j)，满足。

证明 如图（2），将实数轴上0到1线段等分为10小段，每小段长为 。根据鸽巢原理，则11个点中至少有个点落在同一条小线段上，设为xi,xj,(i≠j)，这两点相应的数之差的绝对值。

图（2）

注表示大于等于a的最小整数。

（三）分组构造鸽巢

用这种方法解决鸽巢的分组问题的关键是确定鸽巢分组。只有把鸽子分成合适数量的鸽子，才能应用鸽子原理。

例3对于n+1个不大于2n的不相等的正整数，其中必然存在两个数是互素的。

证明 先证明以下的事实：任何两个相邻的正整数是互素的。用反证法。假如n与n+1有公因子q(q≥2)，则有

n=qp1,n+1=qp2,p1,p2是整数。

因此得qp1+1=qp2，即q(p1-p2)=1，这与q≥2,p1-p2是整数矛盾。

把1,2,…，2n分成以下n组:｛1,2｝，｛3,4｝，…，｛2n-1,2n｝。从1,2,…，2n中任取n+1个不同的 巣数，由鸽 原理可知至少有两个数是取自同一组的，它们是相邻的数，所以是互素的。

（四）按余数分类构造鸽巣

对于诸多自然数的问题，一种惯用的手法是对模同余分类法，即构造n 巣个鸽 ，以n为模，将所有自然数分为｛余数为0的自然数｝，｛余数为1的自然数｝，…，｛余数为n-1的自然数｝，共n个鸽巣。

例4证明:对于任意给定的12个不同的自然数，两个数的和或差可以被20整除。

证明:自然数按余数除以20分为20类。任何给定的12个不同的自然数，如果它们中的两个落在同一个类中（即，两个数的剩余除以20），那么它们的差是20的倍数，并且结论成立。

如果给定一个给定的12个不同的自然数，则每两个数字不在同一类中，即，在20个类中的大部分中已知的数（或不）。在这一点上，自然数根据余数除以20而被分类:｛1,19｝，｛2,18｝，｛3,17｝，…，｛9,11｝，｛10｝，｛0｝。

一般来说，如果取一个不同的自然数，则必须有两个数的和或差的倍数。

证明 设所给的自然数是，有

则个自然数的余数，分为种情况，可看作个鸽巢，必有两个数ai，aj属于同一个鸽巢，即。

（1）当 ri=rj时，ai-aj是 n 的倍数；

（2）当 ri=-rj时，ai+aj是 n 的倍数。

综合（1）、（2）可知，该命题成立。

三、总结

鸽巢原理在中学数学提供了广泛的应用，本课题仅探讨了其中的部分应用，生活中也有很多情形可以采用鸽巢原理的思想来解决。在相同的问题中应用鸽巢原理有很多方法。

[1]虞华芳.发兴趣，走出误区——高中数学教学探索[J].考试周刊，2016(56):84.

[2]陈景林，阎满富.组合数学与图论.北京中国铁道出版社出版，2000.04

文章来源：《中学数学》 网址: http://www.zxsxzz.cn/qikandaodu/2020/0718/395.html