《组合数学课件-第三章第四节鸽巢原理.ppt》由会员分享，可在线阅读，更多相关《组合数学课件-第三章第四节鸽巢原理.ppt（38页珍藏版）》请在三一办公上搜索。
1、1,第3章 容斥原理与鸽巢原理,3.1 De Morgan定理 3.2 容斥原理 3.3 容斥原理举例 3.4 棋盘多项式与有限制的排列 3.5 有禁区的排列 3.6 广义的容斥原理 3.7 广义容斥原理的应用 2.8 第二类Stirling数的展开式 2.9 欧拉函数(n)2.10 n对夫妻问题*2.11 Mobius反演定理 2.12 鸽巢原理 2.13 鸽巢原理举例 2.14 鸽巢原理的推广*2.15 Ramsey数,2,3.12 鸽巢原理,1、366个人中必然有至少两人生日相同(不包括闰年)；2、抽屉里散放着10双手套，从中任意抽取11只，其中至少有两只是成双的；3、某次会议有n位代表
2、参加，则至少有两个人认识的人数是一样的；4、任给5个整数，其中至少有3个数的和被3除尽；,3,鸽巢原理：n个鸽子巢，若有n+1只鸽子在里面，则至少有一个巢里的鸽子数不少于2。,抽屉原理：如果把n+1个物体放到n个抽屉里，则必有一个抽屉里至少放了两个物体。,3.12 鸽巢原理,4,3.13.1 任取11个数，求证其中至少有两个数它们的差是10的倍数。,证明：,一个数是不是10的倍数取决于这个数的个位数是不是0，是0就是10的倍数；,一个数的个位数只可能是0,1,.,9十个数，任取11个数，其中必有两个数个位数相同，,那么这两个数的差的个位数必然是0。,3.13 鸽巢原理举例,5,例3.13.2
3、设a1,a2,am。是正整数的序列，则至少存在整数k和L,1kLm,使得和ak+ak+1+aL是m的倍数。,证明：,有两种可能：,(1)若有一个sh是m的倍数，那么上式成立。,构造一个序列s1=a1,s2=a1+a2,s3=a1+a2+a3,sm=a1+a2+am,则s1s2sm,3.13 鸽巢原理举例,6,(2)设在上面的序列中没有任何一个元素是m的倍数，,序列s1=a1,s2=a1+a2,s3=a1+a2+a3,sm=a1+a2+am,则s1s2sm,假定上面的序列中所有的项都非m的倍数，也就是r1,r2,rm无一为0，而且所有rh均小于m。,3.13 鸽巢原理举例,令shrh(mod m
4、),其中h=1,2,3,m。,7,不超过m-1的正整数只有m-1个，其中至少存在一对rL与rk,满足rL=rk。即sL和sk满足 sksL(mod m),设Lk。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 鸽巢原理举例,8,3.13.3,A是1,2,.,2n中任意n+1个数，试证至少存在一对a,bA使得a与b互素。,相邻数互素；,证明：,从A中任意取n+1个数，必有两个数相邻，相邻数互素；,设这n+1个数为a1,a2,an+1，如果两两不相邻；,构造序列a1,
5、a1+1,a2,a2+1,an,an+1,an+1，是2n+1个不同的正整数；,与已知条件矛盾。,3.13 鸽巢原理举例,9,例3.13.4 设a1,a2,a100是由1和2组成的序列，已知从其中任意一个数开始的连续10个数的和不超过16，即对于1i91,恒有ai+ai+1+ai+916 则至少存在h和k，kh,使得 ah+1+ak=39,证明：,s100=(a1+a2+a10)+(a11+a12+a20)+(a91+a92+a100)根据条件：s1001016=160,作序列s1=a1,s2=a1+a2,s100=a1+a2+a100。由于每个ai都是正整数，因此：s1 s2 s100,3.
6、13 鸽巢原理举例,10,作序列s1,s2,s100,s1+39,s2+39,s100+39,共200项。,最后一项s100+39160+39=199。,但序列共200项。是从1到199的正整数。根据鸽巢原理，其中必有两项相等。,但前100项严格单调递增，后100项也严格单调递增。,存在h和k，有 sk=sh+39,1h,k100 则：sk-sh=39 即：a1+a2+ak-(a1+a2+ah)=39也就是 ah+1+ah+2+ak=39,3.13 鸽巢原理举例,11,例3.13.5 一间屋内有10个人,其中没有人超过60岁(只能是整数),证明:总能够找出两组人(两组不含相同的人)，各组中人的
7、年龄和是相同的。题中10是否能换成更小的数？,3.13 鸽巢原理举例,有多少组？,必有两组年龄和相同,29-1=511,各组的年龄值在什么范围？,1-600,C(10,1)+C(10,2)+C(10,9)+C(10,10),=210-1=1023,12,例3.13.6 A=1,2,99,X是A的子集，X=10，试证：可以找到X的两个非空真子集Y和Z，YZ=，使得Y的元素之和和Z的元素之和相等。,解：求X的非空真子集的数目：,另一方面，X的非空真子集A，其元素之和有：,C(10,1)+C(10,2)+C(10,9)=210-2=1022,3.13 鸽巢原理举例,13,非空真子集的数量有1022个
8、，而非空真子集的元素之和小于或等于855，因此至少有两个非空真子集的元素之和相等，设这两个子集分别为A和B，使得：,如果,则结果成立。否则：,令：,Y和Z就是满足条件的两个集合。,3.13 鸽巢原理举例,14,例3.13.7 X是9个不同正整数的集合，E是X的子集，S(E)是集合E的元素和。n是X的元素的最大值。求n的值，使X至少存在两个集合A和B，使S(A)=S(B)。,解：,设E是X的任意子集。S(E)n+(n-1)+(n-2)+(n-8)=9n-36 也就是说X的任何子集的元素和都小于或等于9n-36,X的任意子集的元素之和小于X的所有子集的数目时！,3.13 鸽巢原理举例,15,根据鸽
9、巢原理，当非空子集数大于任意子集的元素和的个数时，必有两个子集的元素和相等。,5119n-36,X的非空子集的数目？,C(9,1)+C(9,2)+C(9,9),X的任何子集的元素和都小于或等于9n-36,解这个不等式可得：n60.77 n是正整数，因此n60 因此：9n60。,=29-1=511,3.13 鸽巢原理举例,*,16,3.14 鸽巢原理的推广,推广形式之一,设k和n都是任意的正整数，若至少有kn+1只鸽子分配在n个鸽巢里，则至少存在一个鸽巢中有不少于k+1只鸽子。,推论3.7 m只鸽子，n个鸽巢，则至少有一个鸽巢里有不少于,只鸽子。,17,推论3.8 若取n(m-1)+1个球放进n
10、个盒子，则至少有1个盒子的球数不少于m个。,推论3.9 若m1,m2,mn是n个正整数，而且,则m1,m2,mn中至少有1个数不小于r。,3.14 鸽巢原理的推广,18,例：设A=a1a2a20是10个0和10个1组成的20位进制数。B=b1b2b20是任意的20位2进制数。C=b1b2b20b1b2b20=C1C2C40,则存在某个i,1i21,使得CiCi+1Ci+19与a1a2a20至少有10位对应数字相同。,.,.,.,.,.,.,A,C,第 i 格,第 i+19格,1 2 19 20 1 2 19 20,1 2 19 20 1 19 20,B,3.14 鸽巢原理的推广,19,.,A,
11、1 2 19 20,4、因此必有一次相同数字的格数不少于10位,1、假想着A如图所示从左向右一格一格移动。,2、在移动到最后时。每一个bj都遍历了a1,a2,a20。因为A中有10个0和10个1，每一个bj都有10位次对应相等。,3、在20次的移动过程中共有1020=200位次对应相等。,3.14 鸽巢原理的推广,20,定理.7若序列,的n2+1个元素是不相等的实数，则从这个序列中至少可选出一组由n+1个元素组成的或为单调增或为单调减的子序列。,例如：对于序列：5,3,16,10,15,14,9,11,6,7。共32+1个元素。,证明1：从序列中的每一个元素ai向后可选出若干个单调增子序列，其
12、中有一个元素最多的单调增子序列，设其元素个数为li,i=1,2,n2+1,于是得一序列,3.14 鸽巢原理的推广,21,1：若序列(L)中有一个元素lkn+1,则定理得证。,2：设不存在元素个数超过n的单调增子序列，即:,根据鸽巢原理的推论3.7，至少存在n+1个：,的值相等,3.14 鸽巢原理的推广,22,设k1k2kn+1,已知条件中al是不同的实数，则有如下结论,如若不然，设kikj,有akiakj,从akj开始向后的最长的单调增序列为l，从aki开始向后的最长的单调增序列也是l，,如果把元素aki加到从akj开始的长度为l的单调增序列的前面，构成从aki开始的长度为l+1的单调增序列，
13、这和l是从aki向后的最长单调增序列的假设矛盾。,3.14 鸽巢原理的推广,23,序列(A)是一个单调减子序列，这就证明了若不存在n+1个元素的单调增子序列，便存在一个有n+1个元素的单调减子序列。,3.14 鸽巢原理的推广,24,例：随意地给正十边形的10个顶点编上号码1,2,3,4,5,6,7,8,9,10,求证：必有一个顶点及与之相邻的两顶点之和不小于17。,证明：以A1,A2,A3,A10表示正十边形的10个顶点，,以qi表示顶点Ai与Ai相邻的两顶点号码之和,求qi,=(1+2+10)3=165,3.14 鸽巢原理的推广,因此必存在qi17,25,例：下图中画出了3行9列共27个小方
14、格，将每一个方格涂上红色或者蓝色，证明：无论如何涂色，其中必有至少两列它们的涂色方式完全相同。,解：每个方格的涂色方案有红和蓝2种，每列有3个格子，因此每列有：,222=8种涂色方案。,现在有9列，根据鸽巢原理，必有至少两列它们的涂色方式完全相同。,3.14 鸽巢原理的推广,26,3.57,n是大于等于3的整数，则下列数的集合：2-1,22-1,23-1,.,2n-1-1中存在一数被n除尽。,首先这是n-1个奇数，假如n是偶数时，不可能成立；,当n=4时，数列为1，3，7不可能被4除尽。,3.14 鸽巢原理的推广,27,3.57,n是大于1的奇数，则下列数的集合：2-1,22-1,23-1,.
15、,2n-1-1,2n-1中至少存在一数被n除尽。,证：,2-1,22-1,23-1,.,2n-1-1,2n-1整除n可得n个余数，,除以n的余数共有0,1,2,n-1个。,如果2-1,22-1,23-1,.,2n-1-1,2n-1除以n所得余数互不相等,则结论成立。,否则：,3.14 鸽巢原理的推广,28,设a,bn,ab,2a-1(modn)=2b-1(modn)=r,2a-1=hn+r,2b-1=mn+r,设ab,2a-2b=(h-m)n,2b(2a-b-1)=(h-m)n,2a-b-1即为所求：,3.14 鸽巢原理的推广,29,例：能否在一个nn的棋盘的每个方格填上1,2或3，使得棋盘上
16、各行各列以及对角线上的数字之和都不相等。,解：棋盘上各行各列以及对角线上的数字之和共有2n+2个数。,从1,2或3中取n个数，,答案是否定的。,从1,2或3中取n个数，最大和值是3n,最小和值是n,共有2n+1个数值。,3.14 鸽巢原理的推广,30,例3.14.12 试证6个人在一起，其中至少存在3个人或互相认识，或互相不认识。,va,vb,vc,vd,ve,vf,不认识的两个人对应的顶点联线着蓝色。,6个人设为A,B,C,D,E,F,分别用6个顶点va,vb,vc,vd,ve,vf表示，过此6个顶点作完全图，互相认识的两个人，对应顶点的连线着红色。,3.14 鸽巢原理的推广,31,问题等价
17、于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或者存在一个蓝色边三角形。,va,vb,vc,vd,ve,vf,3.14 鸽巢原理的推广,32,在图论中经常用补图的概念来表述：,6个顶点的图G中要么有一个三角形，要么图G的补图中有一个三角形。,va,vb,vc,vd,ve,vf,图G的补图,3.14 鸽巢原理的推广,33,Va点和其他5个顶点相连有5条边，每条边或着以红色，或着以蓝色。依据鸽巢原理，其中至少有3条边同色，不妨假定有3条边着以红色，,3条边的另外3个端点设为ve,vd,vb。,这3个端点间的联线或同色或不同色，,若同色。则已存在一个同色三角形，如
18、果不同色，则至少有一条边是红色，,3.14 鸽巢原理的推广,34,对于A以外的5个人可分为Friend和Strange两个集合。,Friend=其余5人中与A互相认识的集合；,Strange=其余5人中与A不认识的人的集合；,依据鸽巢原理，Friend和Strange中有一个集合至少有3个人，首先假设是集合friend。,Friend中所有人若是彼此互相不认识，则问题已得到证明，,否则有两个人互相认识，不妨设这两个人是P和Q，则A，P，Q这3个人彼此认识。,3.14 鸽巢原理的推广,35,否则设L和M互不相识，则A,L,M互不相识。,若是Strange至少有3个人,可以同样讨论如下:,若Str
19、ange中所有人彼此互相认识,则问题的条件已得到满足,3.14 鸽巢原理的推广,36,|Friend|3?,Friend中人互不相识？,Friend有3人互不相识。,Friend有P，Q二人互相认识,A,P,Q互相认识,Strange中人互相认识？,Strange有3人互相认识。,Strange有L,M互不相识？,Y,N,Y,N,Y,N,A,L,M互不相识？,推理过程如下：A以外的5个人,37,3.11.3 推广形式之二,定理3.12 设有p1+p2+pn-n+1只鸽子，有标号分别为：1,2,n的鸽巢，则存在至少一个标号为j的鸽巢至少有pj只鸽子，j=1,2,n。,3.14 鸽巢原理的推广,*,38,一对常数a和b，对应于一个整数r,使得r个人或a个人互相认识，或有b个互不认识；（或有a个人互不认识，或有b个人互相认识，）这个数r的最小值用R(a,b)来表示。称作Ramsey数,3.15 Ramsey 数,*,R(3,3)=6，R(3,4)=9,R(4,4)=18,
