第一节 鸽巢原理的简单形式

1、 鸽巢原理鸽巢原理(也称也称“抽屉原理抽屉原理”)为组合学中的一个重要为组合学中的一个重要原理原理, 鸽巢原理最早是由鸽巢原理最早是由19世纪的德国数学家迪里赫莱世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题而提出来的）运用于解决数学问题而提出来的, 所以又称为所以又称为“迪里赫莱原理迪里赫莱原理”. 应用它可以解决许多有趣的问题，并且应用它可以解决许多有趣的问题，并且常常得到一些令人惊异的结果常常得到一些令人惊异的结果.它常被用来证明一些存在性它常被用来证明一些存在性的数学问题的数学问题.并且在数论和密码学中也有着广泛的应用并且在数论和密码学中也有着广泛的应用. .对于对于

2、一些比较特殊的问题，若用一般的数学方法去研究，很复一些比较特殊的问题，若用一般的数学方法去研究，很复杂或根本解决不了，但用鸽巢原理往往能起到事半功倍的杂或根本解决不了，但用鸽巢原理往往能起到事半功倍的效果效果. . “ 6只鸽子飞进只鸽子飞进5个鸽巢中，至少有个鸽巢中，至少有1个鸽巢中有两只（或个鸽巢中有两只（或两只以上）的鸽子；两只以上）的鸽子；7个苹果放进个苹果放进3个抽屉中，至少有个抽屉中，至少有1个抽屉个抽屉中放入的苹果不少于中放入的苹果不少于3个个”这个原理并无深奥之处，其正这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的组合问确性也是显而易见的，但利用它可以

3、解决许多有趣的组合问题，得到一些很重要的结论，它在数学的历史上起了很重要题，得到一些很重要的结论，它在数学的历史上起了很重要的作用的作用. 匈牙利数学家路易匈牙利数学家路易波萨波萨11岁时匈牙利大数学家厄杜斯给他岁时匈牙利大数学家厄杜斯给他出了个问题出了个问题: “如果你手头上有如果你手头上有n+1个整数，这些整数是小于或等于个整数，这些整数是小于或等于2n的，那的，那么你手上一定会有一对数是互素的。你知道这是什么原因吗？么你手上一定会有一对数是互素的。你知道这是什么原因吗？”波萨仅思考了半分钟就巧妙地回答了这个问题。波萨仅思考了半分钟就巧妙地回答了这个问题。鸽巢原理的简单形式可以描述为：鸽巢

4、原理的简单形式可以描述为：鸽巢原理的简单形式可以描述为： 定理定理 1 如果把如果把n+1个物品放入个物品放入n个盒子中个盒子中, 那么至少有那么至少有一个盒子中有两个或更多的物品一个盒子中有两个或更多的物品. 证明证明 如果每个盒子中至多有一个物品，那么如果每个盒子中至多有一个物品，那么n个盒子个盒子中至多有中至多有n个物品，而我们共有个物品，而我们共有n+1个物品，矛盾，故定理个物品，矛盾，故定理成立成立. 显然当把显然当把n个物品放入个物品放入n个盒子中，定理的结论就个盒子中，定理的结论就不一定成立了，所以不一定成立了，所以n +1为结论成立的最小数为结论成立的最小数11/2 例例2 在

5、边长为在边长为1的正方形内任取的正方形内任取5点，则至少存在有两点，则至少存在有两 点，它们之间的距离不超过点，它们之间的距离不超过 .22例例1 在任意在任意13个人中个人中,必有两个人的属相相同必有两个人的属相相同. 证明证明 把边长为把边长为1的正方形分成的正方形分成4个边长为个边长为1/2的小正方形形的小正方形形(如图所示如图所示).在大正方形内任取在大正方形内任取5点，点，则这则这5点分别落在点分别落在4个小正方形中，由鸽巢原理知，个小正方形中，由鸽巢原理知，至少有两点落在同一个小正方形中，从而这两点至少有两点落在同一个小正方形中，从而这两点间的距离小于或等于小正方形对角线的长间的距

6、离小于或等于小正方形对角线的长22度，所以两点间的距离不超过度，所以两点间的距离不超过 . 例例3 给定给定m个整数个整数 , 证明证明: 必存在整数必存在整数k , l 使得使得 12,ma aa(0)klm 12()kklm aaa证明证明 构造部分和序列构造部分和序列11212,sasaammaaas21则有如下两种可能：则有如下两种可能：（i）存在整数）存在整数h(1h m), 使得使得 . 此时此时, 取取k=0,l=h即满即满足题意足题意./hm s（ii）对任一整数）对任一整数i，均有，均有 .令令 ，| (1)imsim (mod)iisrm11 (1),irmim 则有则有这

7、样这样, m个余数均在个余数均在1到到m-1之间之间. 由鸽巢原理知由鸽巢原理知, 存在整数存在整数 , 使得使得 . (1,)klk lmlkrr 不妨设不妨设l k，则，则12()(mod)0(mod).kkllklkaaassrrmm综合（综合（i）和（）和（ii），结论成立），结论成立.12 ()kklm aaa即 例例4 4 试证明从试证明从11，2 2，kn 中选中选n+1+1个数个数, ,总存在总存在2 2个数个数, ,它们之间最多相差它们之间最多相差k-1.-1. 例例5 一位棋手有一位棋手有11周时间准备锦标赛，他决定每天至少周时间准备锦标赛，他决定每天至少下一盘棋，一周至多

8、下下一盘棋，一周至多下12盘棋盘棋. 证明：在此期间的连续一些证明：在此期间的连续一些天中他正好下棋天中他正好下棋21盘盘. 证明证明 把把1，2，kn分为分为n部分部分1，2，3，,k, k+1, k+2 , 2k,(n-1)k+1, (n-1)k+2, , kn,即做即做n个个鸽巢，从中任选鸽巢，从中任选n+1个数个数,由鸽巢原理由鸽巢原理,必有必有2个数选在同一个数选在同一个鸽巢中，所以它们的差最大为个鸽巢中，所以它们的差最大为k-1。 证明证明 设设ai表示这个棋手从第表示这个棋手从第1天到第天到第i (i =1,2,77)天下天下棋的总盘数棋的总盘数,因为他每天至少下一盘棋，一周至多

9、下因为他每天至少下一盘棋，一周至多下12盘棋，盘棋，所以有所以有12377112 11132,aaaa考虑数列考虑数列12771277, ; 21,21,21,a aaaaa 它们都在它们都在1与与132+21=153之间之间, 共有共有154项项, 由鸽巢原理由鸽巢原理知，其中必有两项相等知，其中必有两项相等 ,因为前因为前77项互不相等项互不相等, 后后77项项也互不相等也互不相等, 所以必存在所以必存在 使得使得177ij 21,jiaa即即21,jiaa所以所以,从第从第i+1天到第天到第j天这连续天这连续 j-i 天中，他正好下了天中，他正好下了21盘棋盘棋由于由于 , 所以所以 只

10、能取只能取1,3,5,2n-1 这这n个奇数个奇数, nai21) 11 (niri 例例6 从从1至至2n的所有整数中任取的所有整数中任取n+1个个, 则这则这n+1个整数中个整数中至少有一对数至少有一对数, 其中的一个一定能被另一个整除其中的一个一定能被另一个整除 证明证明 设设 是被选出的是被选出的n+1个整数个整数. 对任一整对任一整数数 ，都可以唯一地写成如下的形式：，都可以唯一地写成如下的形式：121,naaaia) 1, 2 , 1(2niraisii其中，其中， 为非负整数，为非负整数， 为奇数，为奇数，isir而而 共有共有n+1项项, 由鸽巢原理知，由鸽巢原理知， 121,

11、nrrr存在存在 , 使得使得11nji ,ijrr不妨设不妨设 ,则则jiss 222jjiisssjjsiiarar整数，即即 能被能被 整除整除.jaia 例例7 (中国余数定理中国余数定理) 设设m,n为两个互素的正整数为两个互素的正整数, a, b是是满足满足0 a m-1, 0 b n-1的整数的整数. 证明证明:存在正整数存在正整数x, 使得使得x除以除以m的余数为的余数为a, 除以除以n的余数为的余数为b, 即存在即存在p,q , 使得使得, .xpmaxqnb证明证明 考虑以下考虑以下n个整数个整数, a满足满足0 a m-1, , , 2, . , (1),amamanma

12、这这n个整数除以个整数除以m的余数都是的余数都是a. 若这若这n个数中存在两个数除以个数中存在两个数除以n的的余数相同，设为余数相同，设为r. 设这两个数为设这两个数为im+a和和jm+a，其中，其中0 ij n-1.则存在整数则存在整数qi, qj, 使得使得im+a=qin+r和 jm+a=qjn+r 同时成立同时成立. 将上两式相减就可以得将上两式相减就可以得（j-i) m=（qj-qi）n. 从上式可以看出，从上式可以看出，n是是(j-i)m的一个因子的一个因子.而由题设条件可而由题设条件可知，知，m, n互素，它们的最大公因子为互素，它们的最大公因子为1. 因此，因此，n是是j-i的

13、因子的因子.由前面的推导过程有由前面的推导过程有0 ij n-1, 所以所以 0j-i n-1, n不可能是不可能是j-i的因子，矛盾的因子，矛盾. 所以所以, , 2, . , (1)a mamanma取遍取遍0, 1, , n-1 这这n个数个数.所以对于所以对于0 b n-1, 存在存在0 p n-1,使得使得 x=pm+a除以除以n的余数为的余数为b, 即存在整数即存在整数q, 使得使得x=qn+b. 综上所述，综上所述，x=pm+a, x=qn+b 满足例题中要证明的结论满足例题中要证明的结论. 从上面的几个例子可以看出，尽管鸽巢原理很简单，但从上面的几个例子可以看出，尽管鸽巢原理很简单，但它却能解决一些看似复杂的组合问题它却