鸽笼原理的妙用

鸽笼原理是《组合数学》中一个重要的原理，它虽然简单，但应用广泛，可以解答很多有趣的问题，其中有些问题还具有相当的难度。

鸽笼原理（又名抽屉原理）：假设n+1件物体放入到n个盒子里，至少有一个盒子包含2件或更多件物体。

证明：（反证法）假设n个盒子里无一个盒子包含2件或更多件物体，则物体总数小于或等于n，这与假设有n+1件物体矛盾。得证。

先通过以下这个例子，看看怎样运用鸽笼原理。

例1 从2、4、6、…、30这15个偶数中，任取9个数，证明其中一定有两个数之和是34。

分析与解答：利用题设中的15个偶数制造8个“盒子”，此“盒子”特点：凡是“盒子”中有两个数的，其和是34。现从题设中的15个偶数中任取9个数，由鸽笼原理（因为“盒子”只有8个），必有两个数可以在同一个“盒子”中（符合上述特点）。由制造的“盒子”的特点，这两个数的和是34。

类似这样的题目，看似无从入手，但应用鸽笼原理来解决就显得很简捷。运用此原理解题构造“盒子”是一大关键，下面谈谈如何构造“盒子”。

一、分割区间构造“盒子”