组合数学课件--第三章第四节 鸽巢原理.ppt

《组合数学课件--第三章第四节 鸽巢原理.ppt》由会员分享，可在线阅读，更多相关《组合数学课件--第三章第四节 鸽巢原理.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.1 De Morgan3.1 De Morgan定理定理 3.2 3.2 容斥原理容斥原理 3.3 3.3 容斥原理举例容斥原理举例 3.4 3.4 棋盘多项式与有限制的排列棋盘多项式与有限制的排列 3.5 3.5 有禁区的排列有禁区的排列 3.6 3.6 广义的容斥原理广义的容斥原理 3.7 3.7 广义容斥原理的应用广义容斥原理的应用 2.8 2.8 第二类第二类StirlingStirling数的展开式数的展开式 2.9 2.9 欧拉函数欧拉函数(n)(n)2.10 n 2.10 n对夫妻问题对夫妻问题*2.11 2.11 Mobiu

2、sMobius反演定理反演定理 2.12 2.12 鸽巢原理鸽巢原理 2.13 2.13 鸽巢原理举例鸽巢原理举例 2.14 2.14 鸽巢原理的推广鸽巢原理的推广*2.15 Ramsey2.15 Ramsey数数13.12 鸽巢原理鸽巢原理 1 1、366366个人中必然有至少两人生日相个人中必然有至少两人生日相同同(不包括闰年不包括闰年)；2 2、抽屉里散放着、抽屉里散放着1010双手套，从中任意双手套，从中任意抽取抽取1111只，其中至少有两只是成双的；只，其中至少有两只是成双的；3 3、某次会议有、某次会议有n n位代表参加，则至少位代表参加，则至少有两个人认识的人数是一样的；有两个人

3、认识的人数是一样的；4 4、任给、任给5 5个整数，其中至少有个整数，其中至少有3 3个数的个数的和被和被3 3除尽；除尽；2 鸽巢原理：鸽巢原理：n n个鸽子巢，若有个鸽子巢，若有n+1n+1只鸽子在里面，只鸽子在里面，则至少有一个巢里的鸽子数不少于则至少有一个巢里的鸽子数不少于2 2。抽屉原理：如果把抽屉原理：如果把n+1n+1个物体放到个物体放到n n个抽屉里，个抽屉里，则必有一个抽屉里至少放了两个物体。则必有一个抽屉里至少放了两个物体。3.12 鸽巢原理鸽巢原理3 3.13.1 3.13.1 任取任取1111个数，求证其中至少有两个个数，求证其中至少有两个数它们的差是数它们的差是101

4、0的倍数。的倍数。证明：证明：一个数是不是一个数是不是1010的倍数取决于这个数的个位的倍数取决于这个数的个位数是不是数是不是0 0，是，是0 0就是就是1010的倍数；的倍数；一个数的个位数只可能是一个数的个位数只可能是0,1,.,90,1,.,9十个数，十个数，任取任取1111个数，其中必有两个数个位数相同，个数，其中必有两个数个位数相同，那么这两个数的差的个位数必然是那么这两个数的差的个位数必然是0 0。3.13 鸽巢原理举例鸽巢原理举例4 例例3.13.2 3.13.2 设设a1,a2,am。是正整数的序列，。是正整数的序列，则至少存在整数则至少存在整数k k和和L,1kL,1kLm,

5、Lm,使得和使得和ak+ak+1+aL是是m m的倍数。的倍数。证明：证明：有两种可能：有两种可能：(1)(1)若有一个若有一个s sh h是是m m的倍数，那么上式成立。的倍数，那么上式成立。构造一个序列构造一个序列s1=a1,s2=a1+a2,s3=a1+a2+a3,sm=a1+a2+am,则则s s1 1ss2 2s sm m3.13 鸽巢原理举例鸽巢原理举例5 (2)(2)设在上面的序列中没有任何一个元素设在上面的序列中没有任何一个元素是是m m的倍数，的倍数，序列序列s1=a1,s2=a1+a2,s3=a1+a2+a3,sm=a1+a2+am,则则s s1 1ss2 2kLk。sL=

6、a1+a2+ak+ak+1+aL -)sk=a1+a2+ak sL-sk=ak+1+aL sL-sk=0 (mod m)也就是说：也就是说：sL-sk=ak+1+aL是是m倍数。倍数。3.13 鸽巢原理举例鸽巢原理举例7 3.13.3,A3.13.3,A是是1,2,.,2n1,2,.,2n中任意中任意n+1n+1个数，个数，试证至少存在一对试证至少存在一对a,bAa,bA使得使得a a与与b b互素。互素。相邻数互素；相邻数互素；证明：证明：从从A A中任意取中任意取n+1n+1个数，必有两个数相邻，个数，必有两个数相邻，相邻数互素；相邻数互素；设这设这n+1n+1个数为个数为a a1 1,a

7、,a2 2,a,an+1n+1，如果两两不，如果两两不相邻；相邻；构造序列构造序列a a1 1,a,a1 1+1,a+1,a2 2,a,a2 2+1,a+1,an n,a,an n+1,a+1,an+1n+1，是是2n+12n+1个不同的正整数；个不同的正整数；与已知条件矛盾。与已知条件矛盾。3.13 鸽巢原理举例鸽巢原理举例8 例例3.13.4 3.13.4 设设a1,a2,a100是由是由1 1和和2 2组成的序列，组成的序列，已知从其中任意一个数开始的连续已知从其中任意一个数开始的连续1010个数的和不超个数的和不超过过1616，即对于，即对于1i91,1i91,恒有恒有ai+ai+1+

8、ai+91616 则至少存在则至少存在h h和和k k，kh,kh,使得使得 ah+1+ak=39=39证明：证明：s100=(a1+a2+a10)+)+(a11+a12+a20)+)+(a91+a92+a100)根据条件：根据条件：s1001016=160 作序列作序列s1=a1,s2=a1+a2,s100=a1+a2+a100。由。由于每个于每个ai都是正整数，因此：都是正整数，因此：s1 s29n-365119n-36 X X的非空子集的数目？的非空子集的数目？C(9,1)+C(9,2)+C(9,9)C(9,1)+C(9,2)+C(9,9)X X的任何子集的元素和都小于或等于的任何子集的

9、元素和都小于或等于9n-369n-36 解这个不等式可得：解这个不等式可得：n60.77n60.77 n n是正整数，因此是正整数，因此n n 6060 因此：因此：9n609n60。=2=29 9-1=511-1=5113.13 鸽巢原理举例鸽巢原理举例*153.14 鸽巢原理的推广鸽巢原理的推广推广形式之一推广形式之一 设设k k和和n n都是任意的正整数，若至少有都是任意的正整数，若至少有kn+1kn+1只鸽子分配在只鸽子分配在n n个鸽巢里，则至少存在一个鸽巢个鸽巢里，则至少存在一个鸽巢中有不少于中有不少于k+1k+1只鸽子。只鸽子。推论推论3.7 m3.7 m只鸽子，只鸽子，n n个

10、鸽巢，则至少有一个个鸽巢，则至少有一个鸽巢里有不少于鸽巢里有不少于只鸽子。只鸽子。16 推论推论3.8 3.8 若取若取n(m-1)+1n(m-1)+1个球放进个球放进n n个盒子，则至少个盒子，则至少有有1 1个盒子的球数不少于个盒子的球数不少于m m个。个。推论推论3.9 3.9 若若m m1 1,m,m2 2,m mn n是是n n个正整数，而且个正整数，而且则则m m1 1,m,m2 2,m mn n中至少有中至少有1 1个数不小于个数不小于r r。3.14 鸽巢原理的推广鸽巢原理的推广17例例3.14.83.14.8：设：设A=a1a2a20是是1010个个0 0和和1010个个1

11、1组成的组成的2020位进制数。位进制数。B=bB=b1 1b b2 2bb2020是任意的是任意的2020位位2 2进制数。进制数。C=C=b b1 1b b2 2bb2020b b1 1b b2 2bb2020=C C1 1C C2 2CC4040,则存在某个则存在某个i i,1i21,1i21,使得使得C Ci iC Ci+1i+1CCi+19i+19与与a1a2a20至少有至少有1010位对应位对应数字相同。数字相同。.AC第第 i 格格第第 i+19格格1 2 19 20 1 2 19 20 1 2 19 20 1 19 20B B3.14 鸽巢原理的推广鸽巢原理的推广18.A1 2

12、 19 204、因因此必有一次相同数字的格数不少于此必有一次相同数字的格数不少于1010位位1 1、假想着、假想着A A如图所示从左向右一格一格移动。如图所示从左向右一格一格移动。2 2、在移动到最后时。每一个、在移动到最后时。每一个b bj j都遍历了都遍历了a1,a2,a20。因为因为A A中有中有1010个个0 0和和1010个个1 1，每一个，每一个b bj j都有都有1010位次对应相等。位次对应相等。3 3、在、在2020次的移动过程中共有次的移动过程中共有1020=2001020=200位次对应位次对应相等。相等。.C 1 2 19 20 1 19 203.14 鸽巢原理的推广鸽

13、巢原理的推广19定理定理.7.7若序列若序列的的n n2 2+1+1个元素是不相等的实数，则从这个序列个元素是不相等的实数，则从这个序列中至少可选出一组由中至少可选出一组由n+1n+1个元素组成的或为单调增个元素组成的或为单调增或为单调减的子序列。或为单调减的子序列。例如：对于序列：例如：对于序列：5,3,16,10,15,14,9,11,6,75,3,16,10,15,14,9,11,6,7。共共3 32 2+1+1个元素。个元素。证明证明1 1：从序列中的每一个元素：从序列中的每一个元素ai向后可选出若干向后可选出若干个单调增子序列，其中有一个元素最多的单调增子序个单调增子序列，其中有一个

14、元素最多的单调增子序列，设其元素个数为列，设其元素个数为li,i,i=1,2,n=1,2,n2 2+1,+1,于是得一序列于是得一序列3.14 鸽巢原理的推广鸽巢原理的推广20 1 1：若序列：若序列(L)(L)中有一个元素中有一个元素lkn+1,n+1,则定理得证。则定理得证。2 2：设不存在元素个数超过：设不存在元素个数超过n n的单调增子序列，即的单调增子序列，即:根据鸽巢原理的推论根据鸽巢原理的推论3.73.7，至少存在，至少存在n+1n+1个：个：的值相等的值相等3.14 鸽巢原理的推广鸽巢原理的推广21 设设k k1 1kk2 2kkn+1 n+1,已知条件中已知条件中al是不同的

15、实数，是不同的实数，则有如下结论则有如下结论如若不然，设如若不然，设k ki i k kj j,有有akikib,ab,2 2a a-2-2b b=(=(h-m)nh-m)n2 2b b(2(2a-ba-b-1)=(h-m)n-1)=(h-m)n2 2a-ba-b-1-1即为所求：即为所求：3.14 鸽巢原理的推广鸽巢原理的推广28 例例3.14.113.14.11：能否在一个：能否在一个n n n n的棋盘的每个方格的棋盘的每个方格填上填上1,21,2或或3 3，使得棋盘上各行各列以及对角线上的，使得棋盘上各行各列以及对角线上的数字之和都不相等。数字之和都不相等。解：解：棋盘上各行各列以及对

16、角线上的数字之和棋盘上各行各列以及对角线上的数字之和共有共有2n+22n+2个数。个数。从从1,21,2或或3 3中取中取n n个数，个数，答案是否定的答案是否定的。从从1,21,2或或3 3中取中取n n个数，最大和值是个数，最大和值是3n,3n,最小和值最小和值是是n,n,共有共有2n+12n+1个数值。个数值。3.14 鸽巢原理的推广鸽巢原理的推广29 例例3.14.12 3.14.12 试证试证6 6个人在一起，其中至少存个人在一起，其中至少存在在3 3个人或互相认识，或互相不认识。个人或互相认识，或互相不认识。vavbvcvdvevf 不认识的两个人对应不认识的两个人对应的顶点联线着

17、蓝色。的顶点联线着蓝色。6 6个人设为个人设为A,B,C,D,E,F,A,B,C,D,E,F,分别用分别用6 6个顶点个顶点va,vb,vc,vd,ve,vf表示，过此表示，过此6个顶点作完全图，个顶点作完全图，互相认识的两个人，对应顶点的连线着红色。互相认识的两个人，对应顶点的连线着红色。3.14 鸽巢原理的推广鸽巢原理的推广30 问题等价于证明这问题等价于证明这6 6个顶点的完全图的边，用个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边红、蓝二色任意着色，必然至少存在一个红色边三角形，或者存在一个蓝色边三角形。三角形，或者存在一个蓝色边三角形。vavbvcvdvevf3.1

18、4 鸽巢原理的推广鸽巢原理的推广31 在图论中经常用补图的概念来表述：在图论中经常用补图的概念来表述：6 6个顶点的图个顶点的图G G中要么有一个三角形，要么中要么有一个三角形，要么图图G G的补图中有一个三角形。的补图中有一个三角形。vavbvcvdvevf图图G Gvavbvcvdvevf图图G G的补图的补图3.14 鸽巢原理的推广鸽巢原理的推广32 VaVa点和其他点和其他5 5个顶点相连有个顶点相连有5 5条边，每条边或条边，每条边或着以红色，或着以蓝色。依据鸽巢原理，其中至着以红色，或着以蓝色。依据鸽巢原理，其中至少有少有3 3条边同色，不妨假定有条边同色，不妨假定有3 3条边着以

19、红色，条边着以红色，vavbvcvdvevf 3 3条边的另外条边的另外3 3个端点设为个端点设为v ve e,v,vd d,v,vb b。这这3 3个端点间的联线或同个端点间的联线或同色或不同色，色或不同色，若同色。则已存在一个同色三角形，如果不同若同色。则已存在一个同色三角形，如果不同色，则至少有一条边是红色，色，则至少有一条边是红色，3.14 鸽巢原理的推广鸽巢原理的推广33 对于对于A A以外的以外的5 5个人可分为个人可分为FriendFriend和和StrangeStrange两个集两个集合。合。Friend=Friend=其余其余5 5人中与人中与A A互相认识的集合；互相认识的

20、集合；Strange=Strange=其余其余5 5人中与人中与A A不认识的人的集合；不认识的人的集合；依据鸽巢原理，依据鸽巢原理，FriendFriend和和StrangeStrange中有一个集合至中有一个集合至少有少有3 3个人，首先假设是集合个人，首先假设是集合friendfriend。FriendFriend中所有人若是彼此互相不认识，则问题已得中所有人若是彼此互相不认识，则问题已得到证明，到证明，否则有两个人互相认识，不妨设这两个人是否则有两个人互相认识，不妨设这两个人是P P和和Q Q，则则A A，P P，Q Q这这3 3个人彼此认识。个人彼此认识。3.14 鸽巢原理的推广鸽巢

21、原理的推广34否则设否则设L L和和M M互不相识，则互不相识，则A,L,MA,L,M互不相识。互不相识。若是若是StrangeStrange至少有至少有3 3个人个人,可以同样讨论如下可以同样讨论如下:若若StrangeStrange中所有人彼此互相认识中所有人彼此互相认识,则问题的条件已则问题的条件已得到满足得到满足,3.14 鸽巢原理的推广鸽巢原理的推广35|Friend|3?Friend中人中人互不相识？互不相识？Friend有有3人人互不相识。互不相识。Friend有有P，Q二人互相认识二人互相认识A,P,Q互相认识互相认识Strange中人中人互相认识？互相认识？Strange有有

22、3人人互相认识。互相认识。Strange有有L,M互不相识？互不相识？Y YN NY YN NY YN NA,L,M互不相识？互不相识？推理过程如下：推理过程如下：A以外的以外的5个人个人363.11.3 3.11.3 推广形式之二推广形式之二 定理定理3.12 3.12 设有设有p p1 1+p+p2 2+p+pn n-n+1-n+1只只鸽子，有标号分别为：鸽子，有标号分别为：1,2,n1,2,n的鸽巢，的鸽巢，则存在至少一个标号为则存在至少一个标号为j j的鸽巢至少有的鸽巢至少有p pj j只鸽子，只鸽子，j=1,2,nj=1,2,n。3.14 鸽巢原理的推广鸽巢原理的推广*37 一对常数一对常数a a和和b b，对应于一个整数，对应于一个整数r,r,使得使得r r个人或个人或a a个人互相认识，或有个人互相认识，或有b b个互个互不认识；不认识；（或有（或有a a个人互不认识，或有个人互不认识，或有b b个人互相认识，）个人互相认识，）这个数这个数r r的最小值用的最小值用R(a,bR(a,b)来表示。来表示。称作称作RamseyRamsey数数3.15 Ramsey 数数*R(3,3)=6R(3,3)=6，R(3,4)=9,R(4,4)=18R(3,4)=9,R(4,4)=1838