组合数学-第一节：鸽巢原理(共6页)

1、精选优质文档-倾情为你奉上第1章 鸽巢原理鸽巢原理（又叫抽屉原理）指的是一件简单明了的事实：为数众多的一群鸽子飞进不多的巢穴里，则至少有一个巢穴飞进了两只或更多的鸽子。这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的组合问题，得到一些很重要的结论，它在数学的历史上起了很重要的作用。1.1 鸽巢原理的简单形式鸽巢原理的简单形式可以描述为：定理1.1.1 如果把个物品放入个盒子中，那么至少有一个盒子中有两个或更多的物品。证明 如果每个盒子中至多有一个物品，那么个盒子中至多有个物品，而我们共有个物品，矛盾。故定理成立。鸽巢原理只断言存在一个盒子，该盒中有两个或两个以上的物品，

2、但它并没有指出是哪个盒子，要想知道是哪一个盒子，则只能逐个检查这些盒子。所以，这个原理只能用来证明某种安排的存在性，而对于找出这种安排却毫无帮助。例1 共有12个属相，今有13个人，则必有两人的属相相同。例2 在边长为1的正方形内任取5点，则其中至少有两点，它们之间的距离不超过。证明 把边长为1的正方形分成4个边长为的小正方形，如图1.1.1所示，在大正方形内任取5点，则这5点分别落在4个小正方形中。由鸽巢原理知，至少有两点落在某一个小正方形中，从而这两点间的距离小于或等于小正方形对角线的长度。例3 给出个整数，证明：必存在整数，使得证明 构造部分和序列则有如下两种可能：（i）存在整数，使得，

3、此时，取即满足题意。（ii）对任一整数i，均有，令，则有，这样，个余数均在1到m-1之间。由鸽巢原理知，存在整数，使得。不妨设，则综合（i）和（ii），即知题设结论成立。例4 一个棋手有11周时间准备锦标赛，他决定每天至少下一盘棋，一周中下棋的次数不能多于12次，证明：在此期间的连续一些天中他正好下棋21次。证明 令分别为这11周期间他每天下棋的次数，并作部分和根据题意，有且所以有（1.1.1）考虑数列它们都在1与之间，共有154项，由鸽巢原理知，其中必有两项相等，由（1.1.1）式知这77项互不相等，从而这77项也互不相等，所以一定存在，使得因此这说明从第天到第天这连续天中，他刚好下了21盘

4、棋。例5 从1到200的所有整数中任取101个，则这101个整数中至少有一对数，其中的一个一定能被另一个整除。证明 设是被选出的101个整数，对任一，都可以唯一地写成如下的形式：，其中，为整数，为奇数。例如：由于，所以只能取1，3，5，199这100个奇数，而，共有101项，由鸽巢原理知，存在，使得不妨设，则整数即能被整除。从上面的几个例子可以看出，尽管鸽巢原理很简单，但它却能解决一些看似很复杂的组合问题。在将其应用到具体的组合问题时，需要一定的技巧去构造具体问题中的“鸽子”与“鸽巢”。1.2 鸽巢原理的强形式定理1.2.1 设都是正整数，如果把个物品放入个盒子，那么或者第1个盒子至少包含个物

5、品，或者第2个盒子至少包含个物品，或者第个盒子至少包含个物品。证明 若对所有的，第个盒子至多只有个物品，则个盒子中至多有个物品，而我们现在有个物品，矛盾。故定理成立。在定理1.2.1中令，则变成了鸽巢原理的简单形式。在定理1.2.1中令，则得到如下的推论：推论1.2.1 若将个物品放入个盒子中，则至少有一个盒子中有个物品。推论1.2.1也可以叙述如推论1.2.2所描述的另一种形式：推论1.2.2 设是个整数，而且则中至少有一个数不小于。推1.2.3 若将个物品放入n个盒子中，则至少有一个盒子中有不少于个物品。其中，是不小于的最小整数。例1 设有大小两只圆盘，每个都划分成大小相等的200个小扇形

6、，在大盘上任选100个小扇形漆成黑色，其余的100个小扇形漆成白色，而将小盘上的200个小扇形任意漆成黑色或白色。现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上的小扇形之内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。证明 如图1.2.1所示，使大小两盘中心重合，固定大盘，转动小盘，则有200个不同的位置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘上的200个小扇形中有100个漆成黑色，100个漆成白色，所以小盘上的每个小扇形无论漆成黑色或白色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色，因而小盘上的200个小扇形在200个

7、重合位置上共同色次，平均每个位置同色次。由鸽巢原理知，存在着某个位置，使同色的小扇形数大于等于100个。例2 任意个实数（1.2.1）组成的序列中，必有一个长为的非降子序列，或必有一个长为的非升子序列。在证明本例之前先看一个具体的例子，对于序列从中可以选出几个递增子序列：也可以选出如下几个递减子序列：证明 方法1 假设长为的实数序列（1.2.1）中没有长度为的非降子序列，下面证明其必有一长度为的非升子序列。令表示从开始的最长非降子序列的长度，因为实数序列（1.2.1）中没有长度为的非降子序列，所以有这相当于把个物品放入个盒子1，2，n中，由鸽巢原理知，必有一盒子里面至少有个物品，即存在：及：。

8、使得（1.2.2）对应于这些下标的实数序列必满足：（1.2.3）它们构成一长为的非增子序列。否则，若有某个，使得，那么由从开始的最长非降子序列加上，就得到一个从开始的长度为的非降子序列。由的定义知这与（1.2.2）式矛盾。因此（1.2.3）式成立，从而定理的结论成立。方法2 对应于实数序列（1.2.1）中的每个，定义一个有序偶其中，为从开始的最长非降子序列的长度，为从开始的最长非长子序列的长度，则对应于序列（1.2.1），有以下的有序偶序列（1.2.4）若实数序列（1.2.1）中既没有长为的非升子序列，也没有长为的非降子序列，则有（1.2.5）满足条件（1.2.5）的有序偶最多只有个，由鸽巢原

9、理知，序列（1.2.4）中至少有两个有序偶相同。即存在，使得即不妨设，由方法1的分析知，若，则，与矛盾；若，则，与矛盾。所以，实数序列（1.2.1）中必有一长为的非降子序列，或有一长为的非升子序列。例3 将1到16的16个正整数任意分成三部分，其中必有一部分中的一个元素是某两个元素之差（三个元素不一定互不相同）。证明 用反证法。设将1到16的16个整数任意分成和三个部分，若这三部分中无一具有问题所指的性质，即其中一个元素是其中某两个元素之差，由此我们来导出矛盾，从而证明问题的结论是正确的。（1）将1到16的整数任意分成三部分，由鸽巢原理知，其中必有一部分至少有个元素，不妨设中含有6个元素，为令，若A中存在一个元素是某两个元素之差，则满足问题的要求。否则，令并令。显然，即B中的元素仍是1到16的整数。根据假设，无一属于。否则，与中不存在一元素等于某两元素之差相矛盾。所以，B中元素属于或（2）与（1）类似，不妨设B中至少个元素属于，设为并令。由假设，C中不存在一元素是某两个元素之差。令并令。显然，D中元素不属于，否则，与中不存在一元素是某两个元素之差