鸽巢原理（狄利克雷抽屉原理）资料整合

狭义鸽巢原理： 如果K+1个或者更多的物体放在k个盒子里，那么至少有一个盒子包含了两个或者更多的物体。 原理证明：（此处采用反证法）假定k个盒子每个盒子最多包含的物品数量为1个那么总共的个数是k个，与k+1个物体矛盾。 推论： 一个从有k+1甚至更多的元素的集合到k个元素集合的函数 f 不是一对一函数。(一对一函数概念补充：当且仅当对于 f 定义域中的所有a和b有 f(a)= f(b)，蕴含a = b。） 推论证明： 假设f的陪域中的每个元素y都有一个盒子与之对应的x。但是根据题意中的是有k+1个或者更多的元素，因此，这些盒子里有的至少包含2个或者更多的x元素。这说明 f 不是一对一函数。

广义鸽巢原理： 　把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体。 该原理的另外一种表述：如果N个物体放入k个盒子里，那么至少有一个盒子包含[N/k](取上限，因为此处不好表示，只好用”[ ]"表示，请谅解） （第一种表述）原理证明：（此处采用反证法）若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。 （第二种表述）原理证明：（此处采用反证法）假设没有一个盒子包含[N/k]多的物体，那么物体的总数是（如图） 事例: 证明：对每个整数n,存在一个数是n的倍数且在它的十进制表示中只出现0和1。 **解答：**令n是正整数， 构造n+1个全是1的数，例如1，11,111,1111…让其中的每个数除以n,因为余数只有n种可能，所以必定有两个数有同样的余数，让这两个数相减得到的结果就可以得出整除n并全是十进制表示只有1和0组成的数。 事例：

1). 同年出生的367人中至少有2个人的生日相同。 解：将一年中的365天视为365个抽屉，367个人看作367个物体，由抽屉原理1可以得知：至少有2人的生日相同. 367/365=1…2,1+1=2.

2). 假设计算机科学实验室有15台工作站和10台服务器。可以用一条电缆直接把工作站连接到服务器。同一时刻只有一条到服务器的直接连接是有效的。我们想保证在任何时刻任何一组不超过10台工作站可以通过直接连接同时访问不同的服务器。尽管我们可以通过将每台工作站直接连接到服务器（使用150条连线），但是达到这个目标所需的最少的直接连接数量是多少呢？ 解： 将工作站分为编号k=1,2,3,4,5…14,15。服务器编号为1，2，3…9,10。那么我们可以假设将前10台工作站先连接到10台服务器，然后将剩下的11，12，13，14，15再连接到10台服务器，总共60条直接连线。证明一下：如果没有60条连线，假设最多有59条连线，那么有一台服务器至多连接在5台工作站。这就意味着剩下的9台服务器要连接10台工作站，这明显不够用了。因此，至少需要60条直接连线，即证。

鸽巢原理的经典运用 (来源于离散数学及其应用 原书第7版 [（美）KENNETH H.ROSEN著；徐六通，杨娟，吴斌]) 例一： 在边长为1的三角形放5个点，至少有两个点之间的距离