第二章(Chapter 2)鸽巢原理(The Pigeonhole Principle)

第二章(Chapter2)鸽巢原理(ThePigeonholePrinciple)2.1问题的引入鸽巢原理又称抽屉原理(theDirichletdrawerprinciple)或鞋盒原理(shoeboxprinciple)原理阐释：有许多鸽子飞进不足够多的鸽子巢内，那么至少要有一个鸽巢被两个或多个鸽子占据。2.1问题的引入实例：⒈366个人中必然有至少两人生日相同。⒉抽屉里散放着10双手套，从中任意抽取11只，其中至少有两只使成双的。⒊某次会议有n位代表参加，每位代表认识其他代表中某些人，则至少有两个人认识的人数是一样的。⒋任给5个不同的整数，其中至少有3个数的和被3整除。这些例子中都包含着鸽巢原理的一般意义。2.2鸽巢原理的简单形式：定理2.1

如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多个物体。证明：如果这n个盒子中的每一个都至多含有一个物体，那么物体的总数最多是n。既然我们有n+1个物体，于是某个盒子就必然包含至少两个物体。[注]：①鸽巢原理仅能被用于证明一个排列或某种现象的存在性，不能对任何构造排列或寻找现象的例证给出任何指示。

②一些与鸽巢原理相关的其他原理：如果n个物体放入n个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体；如果n个物体放入n个盒子并且没有盒子被放入多于一个物体，，那么每个盒子中恰好有一个物体；③上述三个原理的抽象表述形式：令X和Y是两个有限集，并令f：X→Y是一个从X到Y的函数，如果X的元素多于Y的元素，那么f就不是一一对应的。如果X和Y含有相同个数的元素，并且f是映上(onto)的,那么f就是一一对应的。如果X和Y含有相同个数的元素，并且f是一对一的，那么f就是映上的。④若把将物体放入盒子改为用n中颜色中的一种颜色对每一个物体涂色，则鸽巢原理可断言：如果n+1个物体用n中颜色涂色，那么必然有两个物体被涂成相同颜色。下面介绍鸽巢原理简单形式的应用：例题2.2.1：从1到2n的正整数中任取n+1个，则这n+1个数中至少有一对数，其中一个数是另一个数的倍数。解证明：设所取n+1个数分别为：对序列中的每一个数去掉一切2的因子，直至剩下一个奇数为止。例如，68=2×34=22×17，去掉2的因子22，留下奇数17，结果得到由奇数组成的序列：……(R)1到2n中只有n个奇数，故序列(R)中至少有两个是相同的。设为：，对应地有：，，若＞，则是的倍数。例题2.2.2：设是正整数序列，则至少存在整数和，＜，使得和：是的倍数.（即，在序列中存在连续个，这些之和能被整除）。解例题2.2.3：设是3个任意整数；是的任一排列，则至少有一个是偶数。

解：例题2.2.4（中国余氏定理）令和为二互素的正整数，并令和为两整数，且0≤≤以及0≤≤。于是，存在一个整数，使得除以的余数为，并且除以的余数为；即可以写成的同时又可以写成的形式，这里和是两个整数。

解：2.3鸽巢原理的推广形式（也称加强形式）定理2.2令为正整数。如果将个物体放入盒子内，那么，或者第一个盒子至少含有个物体，或者第二个盒子至少含有个物体，……,或者第个盒子至少含有个物体。

证明：[注]：⑴鸽巢原理的简单形式是由其加强形式通过令而得到的。⑵鸽巢原理的加强形式可用着色的术语表述为：如果个物体中的每一个物体被指定用种颜色中的一种着色，那么存在一个这样的，使得第种颜色的物体至少有个。⑶鸽巢原理加强形式的直接表述：只鸽子，个鸽巢，则至少有一个鸽巢里有不少于只鸽子。（其中，表示的取整，即不超过的最大整数）⑷在初等数学中，鸽巢原理加强形式常用于都等于同一个整数的特殊情况。此时，该原理可叙述为：

1）如果个物体放入个盒子中，那么至少有一个盒子含有个或更多个物体。

2）如果个非负整数的平均数大于，即：＞，那么至少有一个整数大于或等于。

3）如果个非负整数的平均数小于，即：＜，那么其中

至少有一个整数小于。4）如果个非负整数的平均数至少等于，那么这个整数中至少有一个满足≥。下面介绍鸽巢原理加强形式的应用：例题2.3.1：一篮子水果装有苹果、香蕉和橘子。为了保证篮子里或者至少8个苹果或者至少6个香蕉或者至少9个橘子，则放入篮子中的水果的最小件数是多少？解：例题2.3.2：设A是个正整数的集合，≥1，证明：存在非空子集BA，使得B的元素之和被除尽。解：例题2.3.3：(Erdos/Szekeres定理)——具体见Acombinatorialproblemingeometry,CompositioMathematica,2(1935),463-470试证：每个由个不相等实数构成的序列或者含有长度为的递增子序列，或者含有长度为的递减子序列。解：例题2.3.