精选优质文档-倾情为你奉上第1章 鸽巢原理鸽巢原理（又叫抽屉原理）指的是一件简单明了的事实：为数众多的一群鸽子飞进不多的巢穴里，则至少有一个巢穴飞进了两只或更多的鸽子。这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的组合问题，得到一些很重要的结论，它在数学的历史上起了很重要的作用。1.1 鸽巢原理的简单形式鸽巢原理的简单形式可以描述为：定理1.1.1 如果把个物品放入个盒子中，那么至少有一个盒子中有两个或更多的物品。证明 如果每个盒子中至多有一个物品，那么个盒子中至多有个物品，而我们共有个物品，矛盾。故定理成立。鸽巢原理只断言存在一个盒子，该盒中有两个或两个以上的物品，但它并没有指出是哪个盒子，要想知道是哪一个盒子，则只能逐个检查这些盒子。所以，这个原理只能用来证明某种安排的存在性，而对于找出这种安排却毫无帮助。例1 共有12个属相，今有13个人，则必有两人的属相相同。例2 在边长为1的正方形内任取5点，则其中至少有两点，它们之间的距离不超过。证明 把边长为1的正方形分成4个边长为的小正方形，如图
