抽屉原理

在研究组合问题时，我们有一些最基本的原理，其中最重要的是抽屉原理。抽屉原理也称为鸽洞或鸽笼原理，它非常简单，但是却很有用处。鸽笼原理最简单的形式是这样的，如果要把n+1只或更多的鸽子放进 n个鸽笼子里，那么至少有一个鸽笼中有两只或两只以上鸽子。值得注意的是，把n+1只鸽子放进n个笼子里的办法有许多，我们可以把n+1只鸽子都放在一个笼子中，也可以每个笼子放一只，最后一个笼子放两只。因此，我们的兴趣不在于怎样放法，而是用来证明一些情况的存在性。例如，一个生日宴会上有400人参加，那么一定有不少人同一天过生日，因为一年有365或366天，但是究竟这400人都是一天过生日，还是没有一个人当天过生日（假定过生日的主人不在400人之内），鸽洞原理并不能判断。这个看来用处不大的原理能解决不少问题。举例讲，一个边长为1的正方形内最多能找到几个点，使这些点之间的距离大于 1/2。碰到这类问题，虽然可以凑出来答案，但是要严格证明，却需要鸽洞原理。
     方法是把正三角形三边中点作一个小的正三角形，这样正三角形分成四个小三角形，这四个小三角形中点的关系有两方面：（1）如果两个点在不同的小三角形中，则这两点的距离可能大于 1/2，当然也可能等于或小于1/2。（2）如果两个点在同一个小三角形中，则这两点的距离一定小于1/2。现在我们有4个小三角形，如果有5个点，那至少有一个小三角形中有两个点，它们之间距离小于1/2。因此，我们在正三角形之内最多只能找到4个点它们彼此之间的距离大于1/2。同样在这个正三角形中.最多找到9个点，它们彼此之间距离大于 1/2，类似我们还可以解决更一般的问题。