组合3容斥原理鸽巢原理共89张课件.ppt

组合数学,帅天平,北京邮电大学数学系,Email:tpshuaigmail,组合数学帅天平北京邮电大学数学系Email:tpshuai,第三章排列组合,3.1 容斥原理3.2 容斥原理应用3.3 广义容斥原理3.4 广义容斥原理应用3.5 鸽巢原理及其应用3.6 Ramsay数3.7 应用举例,第三章排列组合3.1 容斥原理,计数问题是组合数学研究的重要问题之一。已学过的一些计数方法：如 加法法则，母函数方法等；两个重要的计数原理：容斥原理和Plya计数定理。本次课我们学习容斥原理及其应用。,3.1 容斥原理,计数问题是组合数学研究的重要问题之一。3.1 容斥,解：2的倍数是：2，4，6，8，10，12，14，16，18，20。共10个；,3.1 容斥原理,例1 求不超过20的正整数中2或3的倍数的个数。,否！因为6，12，18在两类中重复计数，应减去。,3 的倍数是：3，6，9，12，15，18。共 6个；,答案是10+6=16个吗？,故答案是：16-3=13,解：2的倍数是：2，4，6，8，10，12，14，16，,对于求两个有限集合A和B的并的元素数目，我们有,即具有性质A或B的元素的个数等于具有性质A的元素个数和具有性质B的元素个数减去同时具有性质A和B的元素个数。,3.1 容斥原理,对于求两个有限集合A和B的并的元素数目，我们有即具有性质A,3.1 容斥原理,A,B,AB,U,3.1 容斥原理 A BABU,3.1 容斥原理,证若AB=，则|AB|=|A|+|B|,否则,同理,3.1 容斥原理证若AB=，则|AB|=|,3.1 容斥原理,(iii)(i)(ii)得,|AB|A|+|B|AB|,定理2,3.1 容斥原理(iii)(i)(ii,3.1 容斥原理,A,B,C,AB,AB C,BC,AC,U,3.1 容斥原理ABABAB CBCACU,3.1 容斥原理,证明,3.1 容斥原理证明,例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？,3.1 容斥原理,解：令A为修数学的学生集合；B 为修物理的学生集合；C 为修化学的学生集合；,例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课,即学校学生数为336人。,3.1 容斥原理,即学校学生数为336人。3.1 容斥原理,同理可推出：,利用数学归纳法可得一般的定理：,3.1 容斥原理,同理可推出：利用数学归纳法可得一般的定理：3.1 容斥原理,3.1 容斥原理,(4),定理3 设A1,A2,An是有限集合，则,3.1 容斥原理(4)定理3 设A1,A2,An是有,3.1 容斥原理,(5),容斥原理指的就是（4）和（5）式。用来计算有限集合的并或交的元素个数。,3.1 容斥原理(5)容斥原理指的就是（4）和（5）式。,例3 求从1到500的整数中能被3或5除尽的数的个数.,3.1 容斥原理,解：令A为从1到500的整数中被3除尽的数的集 合，B为被5除尽的数的集合,被3或5除尽的数的个数为,例3 求从1到500的整数中能被3或5除尽的数的个数.3.1,解：令A、B、C分别为不出现a，b，c符号的集合。,即有,3.1 容斥原理,例4 求由a,b,c,d四个字母构成的n位符号串中a,b,c都至少出现一次的符号串数目。,a,b,c都至少出现一次的n位符号串数目为,解：令A、B、C分别为不出现a，b，c符号的集合。即有3.1,例5 用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。,3.1 容斥原理,解：所有排列中，令,则,出现dog字样的排列，相当于把dog作为一个单元参加排列，故,例5 用26个英文字母作不允许重复的全排列，要求排除dog,类似有：,由于god,dog不可能在一个排列中同时出现，故：,3.1 容斥原理,由于gum,dog可以在dogum中同时出现，故有：,类似有,类似有：由于god,dog不可能在一个排列中同时出现，故：3,3.1 容斥原理,其余多于3个集合的交集都为空集。,故满足要求的排列数为：,3.1 容斥原理其余多于3个集合的交集都为空集。故满足要,例6，求不超过120的素数个数。,解:因1111=121,故不超过120的合数必然是2、3、5、7的倍数,而且不超过120的合数的因子不可能都超过11.设 Ai为不超过120的数i的倍数集，i=2,3,5,7.,3.1 容斥原理,例6，求不超过120的素数个数。解:因1111=121,3.1 容斥原理,3.1 容斥原理,3.1 容斥原理,注意：27并非就是不超过120的素数个数，因为这里排除了2,3,5,7着四个数,又包含了1这个非素数。2,3,5,7本身是素数.故所求的不超过120的素数个数为：27+4-1=30.,3.1 容斥原理 注意：27并非就是不超过120的素数个,例7，三个0，三个1，三个2 的排列中，相同数字不能三个相连的排列有多少？,3.1 容斥原理,解：令A1表示三个0相连的排列的集合A2表示三个1相连的排列的集合A3表示三个相连的排列的集合,例7，三个0，三个1，三个2 的排列中，相同数字不能三个相连,3.1 容斥原理,例 8：某人有六位朋友，他与这些朋友每一个都一起吃过12 次晚餐，其中：跟他们中的任意二位一起吃过6 次晚餐；跟他们中的任意三位一起吃过4 次晚餐；跟他们中的任意四位一起吃过3 次晚餐；跟他们中的任意五位一起吃过2 次晚餐；与全部朋友一起吃过1 次；此外，自己单独在外吃晚餐8 次。问，他共在外面吃过几次？,解：令Ai表示与第位朋友共进晚餐的日期的集合。,3.1 容斥原理例 8：某人有六位朋友，他与这些朋友每一个,3.1 容斥原理,3.1 容斥原理,3.1 容斥原理,例 9：在一个长为5 的0,1 序列中，至少有两个1 相邻的序列有多少个？,3.1 容斥原理例 9：在一个长为5 的0,1 序列中，至,3.1 容斥原理,设A12为墙1与2涂相同颜色方案的集合A23为墙2与3涂相同颜色方案的集合A34为墙3与4涂相同颜色方案的集合A41为墙4与1涂相同颜色方案的集合,例 10：用三种不同颜色粉刷一长方形房间内墙壁，使恰在每一角落处颜色都改变，有多少方案？,3.1 容斥原理设A12为墙1与2涂相同颜色方案的集合例,1.再解错排问题,n个元素依次给以标号1，2，n。n个元素的全排列中，求每个元素都不在自己原来位置上的排列数。设Ai 为元素i在第i位上的全体排列,i=1,2,n。则有|U|=n!，因元素i不能动，因而有：,3.2 容斥原理应用,1.再解错排问题 n个元素依次给以标号1，2，,同理,每个元素都不在原来位置的排列数为,3.2 容斥原理应用,同理 每个元素都不在原来位置的排列数为3.2 容斥原理应,3.1 容斥原理,例 11：数1,2,9 的全排列中，求偶数在原来位置上，其余都不在原来位置上排列。,解：等价于五个元素的错排。数目为,例 12：八个字母A,B,C,D,E,F,G,H 的全排列，要求使A，C，E，G 四个字母都不在原来位置，其它字母位置不限的错排数目。,解：设A1表示A在原来位置的排列的集合；A2表示B在原来位置的排列的集合;A3表示C在原来位置的排列的集合;A4表示D在原来位置的排列的集合。问题即求,3.1 容斥原理例 11：数1,2,9 的全排列中，求,3.2 容斥原理应用,3.2 容斥原理应用,3.2.容斥原理应用,2.1 棋盘多项式,n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子,x,x,x,x,x,排列41352对应于如图所示的布局。,3.2.容斥原理应用2.1 棋盘多项式 n个不同,3.2.容斥原理应用,可以把棋盘的形状推广到任意形状：,布子规定同上。,令rk(C)表示k个棋子布到棋盘C上的方案数。,3.2.容斥原理应用 可以把棋盘的形状推广到任意,3.2.容斥原理应用,3.2.容斥原理应用r1()=1r1(,3.2.容斥原理应用,规定 r0(C)=1，包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有,rk(C)=rk-1(Ci)rk(Ce),3.2.容斥原理应用规定 r0(C)=1，包括C=时,3.2.容斥原理应用,从而,3.2.容斥原理应用从而R(C)=rk(C,3.2.容斥原理应用,例如：,3.2.容斥原理应用例如：R()=1+x,3.2.容斥原理应用,如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：,R(C)=R(C1)R(C2)(4),故,3.2.容斥原理应用 如果C由相互分离的C1，C2组成,3.2.容斥原理应用,利用()和()，可以把较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。,3.2.容斥原理应用利用()和()，可以把较复杂的,3.2.容斥原理应用,2.2 有禁区的排列,例14设对于排列P=P1 P2 P3 P4，规定P1，P,4，P2,，P42。,这样的排列对应于有禁区的布子。如左图有影线的格子表示禁区。,3.2.容斥原理应用2.2 有禁区的排列例14设对于,3.2.容斥原理应用,定理4:设 rk 为 k 个棋子布入禁区的方案数，k=1,2,n。则有禁区的布子方案数（即禁区内不布子的方案数）为,3.2.容斥原理应用定理4:设 rk 为 k 个棋子,3.2.容斥原理应用,例15,四位工人，A,B,C,D四项任 务。条件如下：不干B；不干B、C；不干C、D；不干D。问有多少种可行方案？,3.2.容斥原理应用例15,四位工人，,3.2.容斥原理应用,解:由题意，可得如下棋盘：,其中有影线的格子表示禁区。,方案数=4!6(41)!+10(42)!4(43)!+0(44)!=4,3.2.容斥原理应用解:由题意，可得如下棋盘：其中,例16 一婚姻介绍所，登记有5名男性A，B，C，D，E和4名女性1，2，3，4，经了解：1不能与B,C,D,E，2不能与A,D,E,3不能与A,B,C，4不能与A,B,C,D求可能婚配的方案数。,解：,A B C D E,1234,3.2.容斥原理应用,45,例16 一婚姻介绍所，登记有5名男性A，B，C，D,解：,A B C D E,1234,R(C),=(1+x)(1+2x)(1+3x+x2)=1+6x+12x2+9x3+2x4,3.2.容斥原理应用,46,解：A B C,3.2.容斥原理应用,例17三论错排问题 错排问题对应的是nn的棋盘的主对角线 上的格子是禁区的布子问题。,R(C)=,则有,故错排问题的解为:,3.2.容斥原理应用例17三论错排问题C=,欧拉函数是指小于n且与n互素的正整数的个数。,设1到n的n个数中pi 倍数的集合为,解：若n分解为素数的乘积,3.2.容斥原理应用,3 欧拉函数(n),欧拉函数是指小于n且与n互素的正整数的个数。,3.2.容斥原理应用,则有,3.2.容斥原理应用则有,3.2.容斥原理应用,3.2.容斥原理应用,即比60小且与60互素的数有16个：1，7，11，13，17,19,23，29，31，37，41，43，47，49，53，59。,3.2.容斥原理应用,即比60小且与60互素的数有16个：3.2.容斥原理应,例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？,3.3.广义容斥原理,若将.1中的例子2改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”则如何计算？,例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课,3.3.广义容斥原理,若将.1中的例子2改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”,类似的,3.3.广义容斥原理若将.1中的例子2改为“单修一门数学,同样的,3.3.广义容斥原理,同样的3.3.广义容斥原理,设有与性质,2,n相关的元素N个，Ai为有第 i 种性质的元素的集合.i=1,2,n,定义a(0)=N；当m1时,b(m)是正好具有m个性质的元素的个数。,3.3.广义容斥原理,设有与性质,2,n相关的元素N个，Ai为有第 i,例如，对于n=3,m=2,利用这些记号,b(1)=a(1)-2a(2)+3a(3),b(2)=a(2)-3a(3),3.3.广义容斥原理,例如，对于n=3,m=2利用这些记号 b(1)=a(1),定理5（广义容斥原理）：,特别的，当m=0时,3.3.广义容斥原理,定理5（广义容斥原理）：特别的，当m=0时3.3.广义容斥,3.3.广义容斥原理,证设某一元素恰有k种性质，则其对a(k)的某一项的贡献为，而对a(k+1),a(k+2),a(n)的贡献都是。若某一元的性质少于k种,则其对a(k+1),a(k+2),a(n)的贡献都是.若恰有k+j种性质,则其对a(k)的贡献是C(k+j,k),对a(k+i)的贡献是C(k+j,k+i),3.3.广义容斥原理证设某一元素恰有k种性质，则其对a(k,3.3.广义容斥原理,即某恰有k+j种性质的元素对上式右边总的贡献为0,3.3.广义容斥原理即某恰有k+j种性质的元素对上式右,例18 某校有12个教师，已知教数学的有8位，教物理的有6位，教化学的5位；数、理5位，数、化4位，理、化3位；数理化3位。问教其他课的有几位？只教一门的有几位？只教两门的有几位？,解:令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则 a(0)12，a(1)|A1|+|A2|+|A3|8+6+519;a(2)|A1A2|+|A1A3|+|A2A3|12；a(3)|A1A2A3|3；,3.3.广义容斥原理,例18 某校有12个教师，已知教数学的有8位，教物理的有6位,故教其他课的老师数为：b(0)=a(0)-a(1)+a(2)-a(3)=2,只教一门的教师数为：b(1)=a(1)-2a(2)+3a(3)=4,恰好教两门的老师数为：b(2)=a(2)-3a(3)=3,3.3.广义容斥原理,故教其他课的老师数为：只教一门的教师数为：恰好教两门的老师数,3.4.广义容斥原理应用,1、非负整数解,线性方程的非负整数解：,非负整数解的个数为C(n+r-1,r),非负整数解一一对应于r个相同的球放入n个不同的盒子中的方案,3.4.广义容斥原理应用1、非负整数解线性方程的非负整数解：,例19：给定方程,求满足附加条件,的解的个数。,若无上界条件限制，则非负整数解的个数为C(15+3-1,15)=C(17,2)加上限制则不可套用此公式了。,3.4.广义容斥原理应用,例19：给定方程求满足附加条件的解的个数。若无上界条件限制,令 N为全体非负整数解；,对于A1，相当于求方程,的非负整数解,类似的,3.4.广义容斥原理应用,令 N为全体非负整数解；为其中的解；为其中的解；为其中的解,故方程满足条件的解为,3.4.广义容斥原理应用,故方程满足条件的解为3.4.广义容斥原理应用,另解：做变量替换,则问题转化为求方程,的非负整数解。,其个数为C(3+3-1,3)=C(5,2)=10,3.4.广义容斥原理应用,另解：做变量替换则问题转化为求方程的非负整数解。其个数为C,鸽巢原理，又叫抽屉原理，是一个重要而又初等的组合学原理，它能够解决各种有趣的问题，常常得出一些令人惊奇的结论.它指的是一个简单的事实：如果鸽子的数目比巢穴的数目多，那么至少要有一个鸽巢被两只或多只鸽子占据(简单的说,即“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”).下面我们将给出更精确的叙述，以及鸽巢原理的应用举例.,3.5 鸽巢原理,3.5.1 引论,鸽巢原理，又叫抽屉原理，是一个重要而又初等3.5 鸽巢原理,3.5 鸽巢原理,证明:设这n+1个数是 a1,a2,an+1,3.5.2 鸽巢原理的形式,鸽巢原理的简单形式如下：定理 3.5.1 如果把n+1个鸽子放入n个鸽巢，那么至少有一个鸽巢中有两个或更多的鸽子.,【例20】在13个人中至少有两个人在同一个月过生日.,【例21】从1到2n的正整数中任取n+1个，则这n+1个数中至少有一对数，其中一个是另一个的倍数.,3.5 鸽巢原理证明:设这n+1个数是 a1,3.5 鸽巢原理,对此序列中的每一个数去掉一切2的因子，直至剩下一个奇数为止.例如，682217，则去掉22，只留下17.那么我们会得到一个由奇数组成的序列 b1,b2,bn+11到2n之间只有n个奇数，故序列 b1,b2,bn+1中至少有两个是相同的.设bi=bj=b，则bi=2pa，bj=2qa,由于bibj，显然，其中一个是另一个的倍数.,可以看出，应用鸽巢原理可以巧妙的解决看似复杂的问题，其关键是如何去构造问题中的“鸽子”和“鸽巢”.,3.5 鸽巢原理对此序列中的每一个数去掉一切2的因子，直至,【例22】边长为1的等边三角形内任意5个点，至少有两个点，其距离不超过1/2,证:三条边的中点把等边三角形分成4个边长为1/2的等边三角形 由鸽巢原理，任意5个点必有2个落入同一个，其距离不超过1/2.,3.5 鸽巢原理,【例22】边长为1的等边三角形内任意5个点，证:三条边的,例23：1、在边长为2的正方形中任取5 点，证明：存在2 点其间距离不超过21/22、在边长为1 的正三角形中任取10 点，证明：存在2 点其间距离不超过1/3,3.5鸽巢原理,例23：1、在边长为2的正方形中任取5 点，证明：存在2 点,【例24】设 a1,a2,am是正整数序列，则至少存在一个k和 l,1k l m，使得和 ak+al 是m的倍数。,h=1,2,m.若存在 l,Sl0(mod m)，则命题成立否则，1rhm-1对所有h=1,2,m由鸽巢原理，故存在 rk-1=rl,即Sk-1 Sl，不妨设 l k-1则 SlSk-1=ak+ak+1+al 0(mod m),3.5 鸽巢原理,【例24】设 a1,a2,am是正整数,【例25】设a1,a2,a100是由1和2组成的序列,已知从其任一数开始的顺序10个数的和不超过16即 ai+ai+1+ai+9 16，1 i 91则至少存在一对h和k，k h，使得 ah+1+ak=39,3.5 鸽巢原理,【例25】设a1,a2,a100是由1,根据假定有S1001016=160作序列S1,S2,S100,S1+39,S100+39.共200项其中最大项 S100+39160+39由鸽巢原理，必有两项相等而且必是前段中某项与后段中某项相等设 Sk=Sh+39，khSkSh=39 即 ah+1+ak=39,3.5 鸽巢原理,根据假定有S1001016=1603.5 鸽巢原,例26：一位象棋大师以11 周时间准备一次比赛，他决定每天至少下一盘棋，为了不至于太累，他限定每一周不多于12 盘对局，证明，存在连续若干天，在这些天中他恰下了21 盘棋。解：令ai是第1天到第i天下的总盘数(i=1,2,77;11周共77天),3.5 鸽巢原理,类似的题目,例26：一位象棋大师以11 周时间准备一次比赛，他决定每天至,3.5 鸽巢原理,例27：一个学生用37 天准备考试，据经验她知道复习的总时间不会超过60 小时，而她又希望每天至少复习1 小时，证明：不管怎样安排每天复习的小时数，有连续的若干天，其间恰好复习13 小时。解法类似上例,这154个数均在1-153之间，故必有两个数相等，且容易知道这两个数是一个在前段，一个在后段，即一个为ai，一个为aj+21，ai=aj+21立知ai-aj=21，ji,即第j+1天至第i天之间总共下了21盘,3.5 鸽巢原理例27：一个学生用37 天准备考试，据经验,3.5 鸽巢原理,定理 3.5.2 设a1,a2,an都是正整数.如果把a1+a2+an-n+1个鸽子住入n个鸽巢，那么或者第一个鸽巢至少住入a1个鸽子，或者第二个鸽巢至少住入a2个鸽子,或者第n个鸽巢至少住入an个鸽子。证明 设将a1+a2+an-n+1个鸽子住入n个鸽巢中.如果对于每个i=1,2,n，第i个鸽巢都不能住入ai个或更多的鸽子，那么所有鸽巢中的鸽子的总数不超过(a1-1)+(a2-1)+(an-1)=a1+a2+an-n比原鸽子数少1.因此，必存在某个i，使得第i个鸽巢至少含有ai个鸽子.,3.5 鸽巢原理定理 3.5.2 设a1,a2,an,3.5鸽巢原理,例28：证明任意给定的52 个整数中，总存在两个数，它们的和或差能被100 整除。,设此52个整数为a1,a2,a52.被除的余数分别为r1,r2,r520,1,99.构造鸽子巢为0,1,99,2,98,3,97,49,51,50共51个，这52个余数必有2个落入同一个巢，比如说是ri，rj,若它俩相等则ai-aj被100整除，否则ri+rj=100，此时ai+aj被100整除。,3.5鸽巢原理例28：证明任意给定的52 个整数中，总存在两,3.5 鸽巢原理,推论 3.5.1 若把n(r-1)+1个鸽子住入n个鸽巢，那么至少有一个鸽巢中有r个鸽子住入.,也可以写成如下形式：,在定理3.5.2中，如果令ai=2(i=1,2,n)，就是定理3.5.1如果ai=r(i=1,2,n)，则变成了：,推论 3.5.2 若将m个鸽子放入n个鸽巢中，则至少有一个鸽巢中有不少于 只鸽子.,3.5 鸽巢原理推论 3.5.1 若把n(r-1)+1个,3.5 鸽巢原理,推论 3.5.3 设a1,a2,an是n个整数，而且 则a1,a2,an中至少有一个数不小于r.,3.5 鸽巢原理推论 3.5.3 设a1,a2,an,【例29】若序列S=a1,a2,amn+1中的各数是不等的，m,n 是正整数，则 S有一长度为m+1的严格增子序列或长度为n+1的减子序列，而且 S有一长度为m+1的减子序列或长度为n+1的增子序列,证由S中的每个 ai 向后选取最长增子序列，设其长度为li，从而得序列L=l1,l2,lmn+1 若存在 lkm+1，则结论成立,3.5 鸽巢原理,【例29】若序列S=a1,a2,am,不妨设 i1 ai2 ain+1，,li1=li2=lin=lin+1,3.5 鸽巢原理,即有一长度为n+1的减子列,矛盾,否则，若,不妨设 i1i2 in+1，否则所有的,证从ai 向后取最长增子列及减子列，设其长度分别为 li，li.若对任意 i，都有li 1，m,li1，n,不超过mn种对则存在 j lk，若aj ak，则 lj lk，矛盾,3.5 鸽巢原理,证从ai 向后取最长增子列及减子列，设3.5 鸽巢原理,【例30】将 1,67 划分为个子集，必有一个子集中有一数是同子集中的某两数之差,证:用反证法设命题不真即存在划分P1 P2 P3P4 1，67，Pi中不存在一个数是Pi中两数之差，i=1,2,3,4.因(67-1)/4+1=17，故有一子集，其中至少有17个数，设这17个数从小到大为a1,a17 不妨设 A=a1,a17 P1。令bi=ai+1 a1，i=1，16。,3.5 鸽巢原理,【例30】将 1,67 划分为个子集，必有一个证,设Bb1,b16，B 1,67。由反证法假设，BP1=。因而 B(P2 P3 P4)因为(16-1)/3+1=6，不妨设b1,b6 P2，令ci=bi1b1，i=1,5设Cc1,c5，C 1,67 由反证法假设，C(P1P2)=，故有 C(P3P4)因为(5-1)/2+1=3，不妨设c1,c2,c3 P3,3.5 鸽巢原理,设Bb1,b16，B 1,令di=ci+1 c1，i=1,2设D d1,d2,D 1,67。由反证法假设，D(P1P2P3)=，因而 D P4由反证法假设，d2d1 P1P2P3 且d2d1 P4，故 d2d1 1,67，但显然 d2d1 1,67，矛盾。,3.5 鸽巢原理,令di=ci+1 c1，i=1,23.5,【例31】一个抽屉里由20件衬衫，其中4件蓝色，7件灰色，9件红色.从中随意取出至少多少件，才能保证有4件是同色的？保证5，6，7，8，9件同色呢？,解:1、33110保证4件同色。2、442113保证5件同色。3、452115保证6件同色。4、462117保证7件同色。5、477119保证8件同色。6、478120保证9件同色。,3.5 鸽巢原理,【例31】一个抽屉里由20件衬衫，其中4件蓝色，7件解:,3.5 鸽巢原理,定理3.5.3 假设类型i的物品有xi件，i=1,2,n,且,从中任意取出至少ar件才能保证至少有r件同类型的物品，则,3.5 鸽巢原理定理3.5.3 假设类型i的物品有xi件,谢谢！,谢谢！,