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

《组合数学第三章第四节鸽巢原理ppt课件》由会员分享，可在线阅读，更多相关《组合数学第三章第四节鸽巢原理ppt课件（38页珍藏版）》请在装配图网上搜索。

1、第第3章章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.1 De Morgan 3.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 Mobius2.

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

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

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

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

6、a2,s3=a1+a2+a3,s1=a1,s2=a1+a2,s3=a1+a2+a3,sm=a1+a2+am,sm=a1+a2+am,则则s1s2sms1s2kLk。sL=a1+a2+ak+ak+1+aL sL=a1+a2+ak+ak+1+aL -)sk=a1+a2+ak -)sk=a1+a2+ak sL-sk=ak+1+aL sL-sk=ak+1+aL sL-sk=0 (mod m)也就是说：也就是说：sL-sk=ak+1+aL是是m倍数。倍数。3.13 鸽巢原理举例鸽巢原理举例 3.13.3,A 3.13.3,A是是1,2,.,2n1,2,.,2n中任意中任意n+1n+1个数，个数，试证至少

7、存在一对试证至少存在一对a,bAa,bA使得使得a a与与b b互素。互素。相邻数互素；相邻数互素；证明：证明：从从A A中任意取中任意取n+1n+1个数，必有两个数相邻，个数，必有两个数相邻，相邻数互素；相邻数互素；设这设这n+1n+1个数为个数为a1,a2,an+1a1,a2,an+1，如果两两，如果两两不相邻；不相邻；构造序列构造序列a1,a1+1,a2,a2+1,an,an+1,an+1a1,a1+1,a2,a2+1,an,an+1,an+1，是，是2n+12n+1个个不同的正整数；不同的正整数；与已知条件矛盾。与已知条件矛盾。3.13 鸽巢原理举例鸽巢原理举例 例例3.13.4 3.

8、13.4 设设a1,a2,a100a1,a2,a100是由是由1 1和和2 2组成的序列，已知组成的序列，已知从其中任意一个数开始的连续从其中任意一个数开始的连续1010个数的和不超过个数的和不超过1616，即对于，即对于1i91,1i91,恒有恒有ai+ai+1+ai+916ai+ai+1+ai+916 则至少存在则至少存在h h和和k k，kh,kh,使得使得 ah+1+ak=39 ah+1+ak=39证明：证明：s100=(a1+a2+a10)+(a11+a12+a20)+s100=(a1+a2+a10)+(a11+a12+a20)+(a91+a92+a100)+(a91+a92+a10

9、0)根据条件：根据条件：s10010s1001016=16016=160 作序列作序列s1=a1,s2=a1+a2,s1=a1,s2=a1+a2,s100=a1+a2+a100s100=a1+a2+a100。由于每个。由于每个aiai都是正整数，因此：都是正整数，因此：s1 s2 s100 s1 s29n-36 5119n-36 X X的非空子集的数目？的非空子集的数目？C(9,1)+C(9,2)+C(9,9)C(9,1)+C(9,2)+C(9,9)X X的任何子集的元素和都小于或等于的任何子集的元素和都小于或等于9n-369n-36 解这个不等式可得：解这个不等式可得：n60.77n60.7

10、7 n n是正整数，因此是正整数，因此n n6060 因此：因此：9n609n60。=29-1=511=29-1=5113.13 鸽巢原理举例鸽巢原理举例*3.14 鸽巢原理的推广鸽巢原理的推广推广形式之一推广形式之一 设设k k和和n n都是任意的正整数，若至少有都是任意的正整数，若至少有kn+1kn+1只鸽子分配在只鸽子分配在n n个鸽巢里，则至少存在一个鸽巢个鸽巢里，则至少存在一个鸽巢中有不少于中有不少于k+1k+1只鸽子。只鸽子。推论推论3.7 m3.7 m只鸽子，只鸽子，n n个鸽巢，则至少有一个鸽巢，则至少有一个鸽巢里有不少于个鸽巢里有不少于11nm只鸽子。只鸽子。推论推论3.8

11、3.8 若取若取n(m-1)+1n(m-1)+1个球放进个球放进n n个盒子，则至少有个盒子，则至少有1 1个盒个盒子的球数不少于子的球数不少于m m个。个。推论推论3.9 3.9 若若m1,m2,mnm1,m2,mn是是n n个正整数，而且个正整数，而且1.21rnmmmn则则m1,m2,mnm1,m2,mn中至少有中至少有1 1个数不小于个数不小于r r。3.14 鸽巢原理的推广鸽巢原理的推广例例3.14.83.14.8：设：设A=a1a2a20A=a1a2a20是是1010个个0 0和和1010个个1 1组成组成的的2020位进制数。位进制数。B=b1b2b20B=b1b2b20是任意的

12、是任意的2020位位2 2进制数。进制数。C=b1b2b20b1b2b20=C1C2C40,C=b1b2b20b1b2b20=C1C2C40,则存在则存在某个某个i,1i21,i,1i21,使得使得CiCi+1Ci+19CiCi+1Ci+19与与a1a2a20a1a2a20至少有至少有1010位对应数字相同。位对应数字相同。.AC第第 i 格格第第 i+19格格1 2 19 20 1 2 19 20 1 2 19 20 1 19 20B B3.14 鸽巢原理的推广鸽巢原理的推广.A1 2 19 204、因此必有一次相同数字的格数不少于、因此必有一次相同数字的格数不少于10位位1 1、假想着、假

13、想着A A如图所示从左向右一格一格移动。如图所示从左向右一格一格移动。2 2、在移动到最后时。每一个、在移动到最后时。每一个bjbj都遍历了都遍历了a1,a2,a20a1,a2,a20。因为。因为A A中有中有1010个个0 0和和1010个个1 1，每一个，每一个bjbj都有都有1010位次对应相等。位次对应相等。3 3、在、在2020次的移动过程中共有次的移动过程中共有101020=20020=200位次对应位次对应相等。相等。.C 1 2 19 20 1 19 203.14 鸽巢原理的推广鸽巢原理的推广定理定理.7.7若序列若序列13212,.,naaaa的的n2+1n2+1个元素是不相

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

15、+1,li,i=1,2,n2+1,于是得一序列于是得一序列(L),.,1212nlll3.14 鸽巢原理的推广鸽巢原理的推广 1 1：若序列：若序列(L)(L)中有一个元素中有一个元素lkn+1,lkn+1,则定理得证。则定理得证。2 2：设不存在元素个数超过：设不存在元素个数超过n n的单调增子序列，即的单调增子序列，即:1,.,2,1,02ninli 根据鸽巢原理的推论根据鸽巢原理的推论3.73.7，至少存在，至少存在n+1n+1个：个：121,.,nkkklll 的值相等的值相等llllnkkk121.设3.14 鸽巢原理的推广鸽巢原理的推广 设设k1k2kn+1,k1k2kn+1,已知

16、条件中已知条件中alal是不同的实数，则是不同的实数，则有如下结论有如下结论(A).121nkkkaaa如若不然，设如若不然，设kikj,kikj,有有akiakj,akib,ab,2a-2b=(h-m)n2a-2b=(h-m)n2b(2a-b-1)=(h-m)n2b(2a-b-1)=(h-m)nnmhbba2122a-b-12a-b-1即为所求：即为所求：3.14 鸽巢原理的推广鸽巢原理的推广 例例3.14.113.14.11：能否在一个：能否在一个n nn n的棋盘的每个方格的棋盘的每个方格填上填上1,21,2或或3 3，使得棋盘上各行各列以及对角线上的，使得棋盘上各行各列以及对角线上的数

17、字之和都不相等。数字之和都不相等。解：棋盘上各行各列以及对角线上的数字之和解：棋盘上各行各列以及对角线上的数字之和共有共有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 鸽巢原理的推广鸽巢原理的推广 例例3.14.12 3.14.12 试证试证6 6个人在一起，其中至少存个人在一起，其中至少存在在3 3个人或互相认识，或互相不认识。个人或互相认识，或互相不认识。vavbvcv

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

19、，或者存在一个蓝色边三角形。边三角形，或者存在一个蓝色边三角形。vavbvcvdvevf3.14 鸽巢原理的推广鸽巢原理的推广 在图论中经常用补图的概念来表述：在图论中经常用补图的概念来表述：6 6个顶点的图个顶点的图G G中要么有一个三角形，要么中要么有一个三角形，要么图图G G的补图中有一个三角形。的补图中有一个三角形。vavbvcvdvevf图图G Gvavbvcvdvevf图图G G的补图的补图3.14 鸽巢原理的推广鸽巢原理的推广 Va Va点和其他点和其他5 5个顶点相连有个顶点相连有5 5条边，每条边或条边，每条边或着以红色，或着以蓝色。依据鸽巢原理，其中至着以红色，或着以蓝色。

20、依据鸽巢原理，其中至少有少有3 3条边同色，不妨假定有条边同色，不妨假定有3 3条边着以红色，条边着以红色，vavbvcvdvevf 3 3条边的另外条边的另外3 3个端点设为个端点设为ve,vd,vbve,vd,vb。这这3 3个端点间的联线或同个端点间的联线或同色或不同色，色或不同色，若同色。则已存在一个同色三角形，如果不同若同色。则已存在一个同色三角形，如果不同色，则至少有一条边是红色，色，则至少有一条边是红色，3.14 鸽巢原理的推广鸽巢原理的推广 对于对于A A以外的以外的5 5个人可分为个人可分为FriendFriend和和StrangeStrange两个两个集合。集合。Frien

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

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

23、识互相认识Strange中人中人互相认识？互相认识？Strange有有3人人互相认识。互相认识。Strange有有L,M互不相识？互不相识？Y YN NY YN NY YN NA,L,M互不相识？互不相识？推理过程如下：推理过程如下：A以外的以外的5个人个人3.11.3 3.11.3 推广形式之二推广形式之二 定理定理3.12 3.12 设有设有p1+p2+pn-n+1p1+p2+pn-n+1只只鸽子，有标号分别为：鸽子，有标号分别为：1,2,n1,2,n的鸽巢，的鸽巢，则存在至少一个标号为则存在至少一个标号为j j的鸽巢至少有的鸽巢至少有pjpj只鸽子，只鸽子，j=1,2,nj=1,2,n。3.14 鸽巢原理的推广鸽巢原理的推广*一对常数一对常数a a和和b b，对应于一个整数，对应于一个整数r,r,使得使得r r个人或个人或a a个人互相认识，或有个人互相认识，或有b b个互个互不认识；（或有不认识；（或有a a个人互不认识，或有个人互不认识，或有b b个人互相认识，）这个数个人互相认识，）这个数r r的最小值用的最小值用R(a,b)R(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)=18