《组合数学课件第三章第四节鸽巢原理》由会员分享，可在线阅读，更多相关《组合数学课件第三章第四节鸽巢原理（37页珍藏版）》请在金锄头文库上搜索。
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.11 Mobius反演定理反
2、演定理 2.12 2.12 鸽巢原理鸽巢原理 2.13 2.13 鸽巢原理举例鸽巢原理举例 2.14 2.14 鸽巢原理的推广鸽巢原理的推广 * *2.15 Ramsey2.15 Ramsey数数1组合数学课件第三章第四节鸽巢原理3.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
4、任取任取1111个数，求证其中至少有两个个数，求证其中至少有两个数它们的差是数它们的差是1010的倍数。的倍数。 证明：证明： 一个数是不是一个数是不是1010的倍数取决于这个数的个位的倍数取决于这个数的个位数是不是数是不是0 0，是，是0 0就是就是1010的倍数；的倍数； 一个数的个位数只可能是一个数的个位数只可能是0,1,.,90,1,.,9十个数，十个数，任取任取1111个数，其中必有两个数个位数相同，个数，其中必有两个数个位数相同，那么这两个数的差的个位数必然是那么这两个数的差的个位数必然是0 0。3.13 鸽巢原理举例鸽巢原理举例4组合数学课件第三章第四节鸽巢原理 例例3.13.2
5、 3.13.2 设设a1,a2,am。是正整数的序列，则。是正整数的序列，则至少存在整数至少存在整数k k和和L, 1kL, 1kLm,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 2 ssm m3.13 鸽巢原理举例鸽巢原理举例5组合数学课件第三章第四节鸽巢原理 (2) (2)设在上面的序列中没有任何一个元素设在上
6、面的序列中没有任何一个元素是是m m的倍数，的倍数， 序列序列s1=a1,s2=a1+a2,s3=a1+a2+a3,sm=a1+a2+am , ,则则s s1 1ss2 2 skLk。 sL=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,A 3.13.3,A是是1,2,.,2n1,2,.,2n中任意中任意n+1n+1个数，个数，试证至少存在一对试证至少存在一对a,bA
7、a,bA使得使得a a与与b b互素。互素。相邻数互素；相邻数互素；证明：证明： 从从A A中任意取中任意取n+1n+1个数，必有两个数相邻，个数，必有两个数相邻，相邻数互素；相邻数互素； 设这设这n+1n+1个数为个数为a a1 1,a,a2 2, ,a,an+1n+1，如果两两不，如果两两不相邻；相邻； 构造序列构造序列a a1 1,a,a1 1+1,a+1,a2 2,a,a2 2+1,+1,a an n,a,an n+1,a+1,an+1n+1，是是2n+12n+1个不同的正整数；个不同的正整数；与已知条件矛盾。与已知条件矛盾。3.13 鸽巢原理举例鸽巢原理举例8组合数学课件第三章第四节
8、鸽巢原理 例例3.13.4 3.13.4 设设a1,a2,a100是由是由1 1和和2 2组成的序列，组成的序列，已知从其中任意一个数开始的连续已知从其中任意一个数开始的连续1010个数的和不超个数的和不超过过1616，即对于，即对于1i91,1i91,恒有恒有ai+ai+1+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,
9、 s100=a1+a2+a100。由于。由于每个每个ai都是正整数，因此：都是正整数，因此： s1 s29n-365119n-36 X X的非空子集的数目？的非空子集的数目？C(9,1)+C(9,2)+C(9,1)+C(9,2)+C(9,9)+C(9,9)X X的任何子集的元素和都小于或等于的任何子集的元素和都小于或等于9n-369n-36 解这个不等式可得：解这个不等式可得：n60.77n60.77 n n是正整数，因此是正整数，因此n n 6060 因此：因此：9n609n60。=2=29 9-1=511-1=5113.13 鸽巢原理举例鸽巢原理举例*15组合数学课件第三章第四节鸽巢原理3
10、.14 鸽巢原理的推广鸽巢原理的推广推广形式之一推广形式之一 设设k k和和n n都是任意的正整数，若至少有都是任意的正整数，若至少有kn+1kn+1只鸽子分配在只鸽子分配在n n个鸽巢里，则至少存在一个鸽巢个鸽巢里，则至少存在一个鸽巢中有不少于中有不少于k+1k+1只鸽子。只鸽子。 推论推论3.7 m3.7 m只鸽子，只鸽子，n n个鸽巢，则至少有一个个鸽巢，则至少有一个鸽巢里有不少于鸽巢里有不少于只鸽子。只鸽子。16组合数学课件第三章第四节鸽巢原理 推论推论3.8 3.8 若取若取n(m-1)+1n(m-1)+1个球放进个球放进n n个盒子，则至少个盒子，则至少有有1 1个盒子的球数不少于
11、个盒子的球数不少于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 1组组成的成的2020位进制数。位进制数。B=bB=b1 1b b2 2b b2020是任意的是任意的2020位位2 2进进制数。制数。C=C=b b1 1b b2 2b b2020b
12、b1 1b b2 2b b2020= C= C1 1C C2 2C C4040, ,则存在某则存在某个个i i,1i21,1i21,使得使得C Ci iC Ci+1i+1C Ci+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 19 204、因此必有一次相同数字的格数不少于因此必有一次相同数字的格数不少于1010位位1 1、假想着、假想着A
13、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 鸽巢原理的推广鸽巢原理的推广19组合数学课件第三章第四节鸽巢原理定理定理.7.7若序列若序列的的n n2 2+1+1
14、个元素是不相等的实数，则从这个序列个元素是不相等的实数，则从这个序列中至少可选出一组由中至少可选出一组由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向后可选出若干向后可选出若干个单调增子序列，其中有一个元素最多的单调增子序个单调增子序列，其中有一个元素最多的单调增子序列，设其元素个数为列，设其元素个数为li,i
15、=1,2,i=1,2,n,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 2 kkn+1 n+1 , ,已知条件中已知
16、条件中al是不同的实数，是不同的实数，则有如下结论则有如下结论如若不然，设如若不然，设k ki ikkj j, ,有有akikib,ab,2 2a a-2-2b b=(h-m)n=(h-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，使得棋盘上各行各列以及对角线上的，使得棋盘上各行各列以及对角线上的数字之和都不相
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 鸽巢原理的推广鸽巢原理的推广29组合数学课件第三章第四节鸽巢原理 例例3.14.12 3.14.12 试证试证6 6个人在一起，其中至少存个人在一起，其中至少存在在3 3个人或互相认识，或互相不认识。个人或互相认识，或
18、互相不认识。vavbvcvdvevf 不认识的两个人对应不认识的两个人对应的顶点联线着蓝色。的顶点联线着蓝色。 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个顶点的完全图的边，用个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边红、蓝二色任意着色，
19、必然至少存在一个红色边三角形，或者存在一个蓝色边三角形。三角形，或者存在一个蓝色边三角形。 vavbvcvdvevf3.14 鸽巢原理的推广鸽巢原理的推广31组合数学课件第三章第四节鸽巢原理 在图论中经常用补图的概念来表述：在图论中经常用补图的概念来表述： 6 6个顶点的图个顶点的图G G中要么有一个三角形，要么中要么有一个三角形，要么图图G G的补图中有一个三角形。的补图中有一个三角形。vavbvcvdvevf图图G Gvavbvcvdvevf图图G G的补图的补图3.14 鸽巢原理的推广鸽巢原理的推广32组合数学课件第三章第四节鸽巢原理 Va Va点和其他点和其他5 5个顶点相连有个顶点相
20、连有5 5条边，每条边或条边，每条边或着以红色，或着以蓝色。依据鸽巢原理，其中至着以红色，或着以蓝色。依据鸽巢原理，其中至少有少有3 3条边同色，不妨假定有条边同色，不妨假定有3 3条边着以红色，条边着以红色，vavbvcvdvevf 3 3条边的另外条边的另外3 3个端点设为个端点设为v ve e,v,vd d,v,vb b。 这这3 3个端点间的联线或同个端点间的联线或同色或不同色，色或不同色， 若同色。则已存在一个同色三角形，如果不同若同色。则已存在一个同色三角形，如果不同色，则至少有一条边是红色，色，则至少有一条边是红色，3.14 鸽巢原理的推广鸽巢原理的推广33组合数学课件第三章第四
21、节鸽巢原理 对于对于A A以外的以外的5 5个人可分为个人可分为FriendFriend和和StrangeStrange两个集两个集合。合。Friend=Friend=其余其余5 5人中与人中与A A互相认识的集合；互相认识的集合；Strange=Strange=其余其余5 5人中与人中与A A不认识的人的集合；不认识的人的集合； 依据鸽巢原理，依据鸽巢原理，FriendFriend和和StrangeStrange中有一个集合至中有一个集合至少有少有3 3个人，首先假设是集合个人，首先假设是集合friendfriend。 Friend Friend中所有人若是彼此互相不认识，则问题已得中所有人
22、若是彼此互相不认识，则问题已得到证明，到证明， 否则有两个人互相认识，不妨设这两个人是否则有两个人互相认识，不妨设这两个人是P P和和Q Q，则则A A，P P，Q Q这这3 3个人彼此认识。个人彼此认识。3.14 鸽巢原理的推广鸽巢原理的推广34组合数学课件第三章第四节鸽巢原理否则设否则设L L和和M M互不相识，则互不相识，则A,L,MA,L,M互不相识。互不相识。若是若是StrangeStrange至少有至少有3 3个人个人, ,可以同样讨论如下可以同样讨论如下: : 若若StrangeStrange中所有人彼此互相认识中所有人彼此互相认识, ,则问题的条件已则问题的条件已得到满足得到满
23、足, ,3.14 鸽巢原理的推广鸽巢原理的推广35组合数学课件第三章第四节鸽巢原理|Friend|3? Friend中人中人互不相识？互不相识？Friend有有3人人互不相识。互不相识。Friend有有P，Q二人互相认识二人互相认识A,P,Q互相认识互相认识Strange中人中人互相认识？互相认识？Strange有有3人人互相认识。互相认识。Strange有有L,M互不相识？互不相识？Y YN NY YN NY YN NA,L,M互不相识？互不相识？推理过程如下：推理过程如下：A以外的以外的5个人个人36组合数学课件第三章第四节鸽巢原理3.11.3 3.11.3 推广形式之二推广形式之二 定理定理3.12 3.12 设有设有p p1 1+p+p2 2+ +p+pn n-n+1-n+1只只鸽子，有标号分别为：鸽子，有标号分别为：1,2,1,2,n,n的鸽巢，的鸽巢，则存在至少一个标号为则存在至少一个标号为j j的鸽巢至少有的鸽巢至少有p pj j只鸽子，只鸽子，j=1,2,j=1,2,n,n。3.14 鸽巢原理的推广鸽巢原理的推广*37组合数学课件第三章第四节鸽巢原理
