鸽巢原理(Pigeonhole PRinciple)

目录

1.什么是鸽巢原理2.鸽巢原理的形式3.鸽巢原理的应用4.参考文献

什么是鸽巢原理

鸽巢原理又名抽屉原理或狄利克雷原理，它由德国数学家狄利克雷(Divichlet，1805—1855)首先发现。鸽巢原理在组合学中占据着非常重要的地位，它常被用来证明一些关于存在性的数学问题，并且在数论和密码学中也有着广泛的应用。使用鸽巢原理解题的关键是巧妙构造鸽巢或抽屉，即如何找出合乎问题条件的分类原则。

鸽巢原理的形式

鸽巢原理的简单形式：如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或者更多的物体。

证明：如果这n个盒子中的每一个都至多含有一个物体，那么物体的总数最多是n。既然我们有n+1个物体，于是某个盒子就必然包含至少两个物体。

鸽巢原理的加强形式：令]双鞋。

推论2：n(m-1)+1只鸽子放入n个鸽笼，则至少有一个鸽笼中有m只鸽子。

推论3：设>r-1，则

鸽巢原理的应用

1.用于几何图形

(1)在边长为1的等边三角形内任意选择5个点，存在2个点，其间距离至多为1/2。

证明：由题意，可以构造出4个抽屉，每个抽屉满足在其问的距离至多为1/2(见图1)。根据鸽巢原理，在4个抽屉里分别放置4个点，不论第5个点如何放置，都满足两点之间的距离最多为1/2。

(2)证明在边长为1的等边三角形内任意选择10个点，存在两个点，其间距离至多为1/3。

证明：按照图2的构造可以证明该题。

归纳：在边长为1的等边三角形内任意选择]+1=3个点，而这样的小正方形外接圆半径是。又由得得/10<1/7，所以至少有三个点在半径为1/7的一个圆内。

(4)在直径为5的圆内任意给定10个点，证明存在两个点，它们之间的距离小于2。

证明：根据题意，我们最先考虑到把圆等分成9个扇形而构造出9个抽屉，但是虽然必有两个点在某一扇形内，但不能确认它们之间的距离小于2。于是我们考虑先用一个与已知圆同心，半径为1的不包含边界的小圆作为一个抽屉，然后再把圆环部分等分成八个部分，(如图3所示)这样就构成了9个抽屉。

根据抽屉原理可知，存在两个点在同一个抽屉(包括边界)中，若这两个点在小圆(不包含边界)中，显然它们之间的距离小于2。若这两个点在圆环部分的八个等分中的某一图形里，不妨设在图形ABCD中。由于

由此可知，这时两个点之间的距离也小于2，从而命题得证。

2.用于数的整除关系

(1)在前12个自然数中任取7个数，一定存在两个数，其中的一个数是另一个数的整数倍。

分析：若能把前12个自然数划分成6个集合，即构成6个抽屉，使每个抽屉内的数或只有一个，或有任意的两个数，其中的一个是另一个的整数倍，这样就可以由抽屉原理推出结论。那么如何对这12个自然数进行分组?我们知道，一个自然数，它要么是奇数，要么是偶数。若是偶数，我们总能把它表达为奇数与指数K可以等于零，则每一个自然数都可表达成“奇数×××和也之间总存在倍数关系，即一个数是另一个数的整数倍。

(2)证明任意五个整数中，必有三个整数的和是3的倍数。

证明：任一整数被3除余数只可能是0，l，2。

若给定的五个整数被3除所得的余数中0，l，2都出现，那么余数分别为O，l，2的三个数的和一定能被3整除，如果余数中至多只出现0，l，2中的两个，那么由抽屉原理，其中必有一个余数至少出现三次。而这余数相同的三个数的和一定能被3整除。

(3)证明对任意给定的52个整数，存在其中的两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

证明：任意一个整数a除以100产生的余数不外乎为O，1，2，…，99。题目中的52个整数新产品，每年最多试制19种新产品。试证明：一定存在连续的几个月，恰好试制24种新产品。

证明：设五年期间该厂各个月试制的新产品个数分别为

参考文献