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

1、组合数学组合数学帅天平帅天平北京邮电大学数学系Email:tpshuaigmail第三章第三章排列组合排列组合3.1 容斥原理3.2 容斥原理应用3.3 广义容斥原理3.4 广义容斥原理应用3.5 鸽巢原理及其应用3.6 Ramsay数3.7 应用举例 计数问题是组合数学研究的重要问题之一。已学过的一些计数方法：如 加法法则，母函数方法等；两个重要的计数原理：容斥原理和Plya计数定理。本次课我们学习容斥原理及其应用。3.1 3.1 容斥原理容斥原理 解：解：2的倍数是：2，4，6 6，8，10，1212，14，16，1818，20。共10个；3.1 3.1 容斥原理容斥原理例例1 求不超过2

2、0的正整数中2或3的倍数的个数。否！因为6 6，1212，1818在两类中重复计数，应减去。3 的倍数是：3，6 6，9，1212，15，1818。共 6 6个；答案是10+6=16个吗？故答案是：16-3 3=1313 对于求两个有限集合A和B的并的元素数目，我们有即具有性质A或B的元素的个数等于具有性质A的元素个数和具有性质B的元素个数减去同时具有性质A和B的元素个数。ABABAB(1)定理定理13.1 3.1 容斥原理容斥原理3.1 3.1 容斥原理容斥原理 A BABU3.1 3.1 容斥原理容斥原理证证若AB=，则|AB|=|A|+|B|,否则同理AB(A(BB)(B(AA)(AB)

3、(AB)(BA)(BA)ABABBA (iii)|()|()()|()|()|(i)AABBABABABAB|()|()|(ii)BBABA3.1 3.1 容斥原理容斥原理(iii)(i)(ii)得|AB|A|+|B|AB|(|)(|)|ABABABABBAABABBABAAB 定理定理2 (2)ABCABCABACBCABC -3.1 3.1 容斥原理容斥原理AB CABAB CBCACU3.1 3.1 容斥原理容斥原理()()()()()ABCACBCABCABCABACBCABCABBCABC根据 C-A()()ABCABCABCABC证明证明例例2 一个学校只有三门课程：数学、物理、化

4、学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？3.1 3.1 容斥原理容斥原理解：解：令A为修数学的学生集合；B 为修物理的学生集合；C 为修化学的学生集合；AB CABCABA CB CAB C 即学校学生数为336人。3.1 3.1 容斥原理容斥原理1701301204520223336170,130,120,4520,22,3ABCABA CBCABC同理可推出：利用数学归纳法可得一般的定理：3.1 3.1 容斥原理容斥原理 (3)A

5、BCDABCDABACADBCBDCDABCABDACDBCDABCD3.1 3.1 容斥原理容斥原理12111112.(1).nnnniijijkiij iij i kjnnAAAAAAAAAAAA(4)定理定理3 设A1,A2,An是有限集合，则,AUA又 3.1 3.1 容斥原理容斥原理12121112.(1)nnnnniijijkiij iij i kjnnAAAUAAAUAAAAAAAAA=1-(5)容斥原理指的就是（4）和（5）式。用来计算有限集合的并或交的元素个数。例例3 求从1到500的整数中能被3或5除尽的数的个数.500500166,100;355003315ABAB3.1

6、 3.1 容斥原理容斥原理解：解：令A为从1到500的整数中被3除尽的数的集 合，B为被5除尽的数的集合被3或5除尽的数的个数为ABABAB16610033233 解：解：令A、B、C分别为不出现a，b，c符号的集合。即有3nABC3.1 3.1 容斥原理容斥原理2nABACBC例例4 求由a,b,c,d四个字母构成的n位符号串中a,b,c都至少出现一次的符号串数目。4nU 1ABC a,b,c都至少出现一次的n位符号串数目为4()()33123nnnUABCABACBBCABACC 例例5 用26个英文字母作不允许重复不允许重复的全排列，要求排除dog，god，gum，depth，thing

7、字样的出现，求满足这些条件的排列数。3.1 3.1 容斥原理容斥原理解：解：所有排列中，令12345AdogAgodAgumAdepthAthing为出现的排列的全体；为出现的排列的全体；为出现的排列的全体；为出现的排列的全体；为出现的排列的全体；26!U 则出现dog字样的排列，相当于把dog作为一个单元参加排列，故24!A 1类似有：2345,24!22!AAAA由于god,dog不可能在一个排列中同时出现，故：120;AA 14150,0,AAAA3.1 3.1 容斥原理容斥原理 由于gum,dog可以在dogum中同时出现，故有：1322!AA类似有2324253435450,20!1

8、9!,20!19!AAAAAAAAAAAA123124125134135145234235245,000,AAAAAAAAAAAAAAAAAAAAAAAAAAA3.1 3.1 容斥原理容斥原理其余多于3个集合的交集都为空集。34517!AAA 故满足要求的排列数为：26!(22!3 20!2 1(3 24!2 22!)17!)!9 26!324!22!320!2 19!17!例例6 6，求不超过120的素数个数。解:因1111=121,故不超过120的合数必然是2、3、5、7的倍数,而且不超过120的合数的因子不可能都超过11.设 Ai为不超过120的数i的倍数集，i=2,3,5,7.3.1

9、3.1 容斥原理容斥原理235712012012012060402417,2357AAAA，232527351201202012,2310120120881415AAAAAAAA，3.1 3.1 容斥原理容斥原理3757235237120120532135120120422 3 52 3 7AAAAAAAAAA ，257235712010257AAAAAAA，235723572325273537572352372573572357120AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA3.1 3.1 容斥原理容斥原理120(604024 17)(20 128853)(42

10、 1 1)27.注意：注意：27并非就是不超过120的素数个数，因为这里排除了2,3,5,7着四个数,又包含了1这个非素数。2,3,5,7本身是素数.故所求的不超过120的素数个数为：27+4-1=3027+4-1=30.例例7 7，三个0，三个1，三个2 的排列中，相同数字不能三个相连的排列有多少？3.1 3.1 容斥原理容斥原理解：令A1表示三个0相连的排列的集合A2表示三个1相连的排列的集合A3表示三个相连的排列的集合3.1 3.1 容斥原理容斥原理例 8：某人有六位朋友，他与这些朋友每一个都一起吃过12 次晚餐，其中：跟他们中的任意二位一起吃过6 次晚餐；跟他们中的任意三位一起吃过4

11、次晚餐；跟他们中的任意四位一起吃过3 次晚餐；跟他们中的任意五位一起吃过2 次晚餐；与全部朋友一起吃过1 次；此外，自己单独在外吃晚餐8 次。问，他共在外面吃过几次？解：令Ai表示与第位朋友共进晚餐的日期的集合。3.1 3.1 容斥原理容斥原理3.1 3.1 容斥原理容斥原理例 9：在一个长为5 的0,1 序列中，至少有两个1 相邻的序列有多少个？3.1 3.1 容斥原理容斥原理设A12为墙1与2涂相同颜色方案的集合A23为墙2与3涂相同颜色方案的集合A34为墙3与4涂相同颜色方案的集合A41为墙4与1涂相同颜色方案的集合例 10：用三种不同颜色粉刷一长方形房间内墙壁，使恰在每一角落处颜色都改

12、变，有多少方案？1.再解错排问题再解错排问题 n个元素依次给以标号1，2，n。n个元素的全排列中，求每个元素都不在自己原来位置上的排列数。设Ai 为元素i在第i位上的全体排列,i=1,2,n。则有|U|=n!，因元素i不能动，因而有：3.2 3.2 容斥原理容斥原理应应用用(1)!,1,2,.,iAnin,1,2,.,(2)!ijinAnijA 同理 每个元素都不在原来位置的排列数为12.!(,1)(1)!(,2)(2)!(1)(,)1!nnAAAnC nnC nnC n n 3.2 3.2 容斥原理容斥原理应应用用111!(1(1)1!2!nnn 3.1 3.1 容斥原理容斥原理例 11：数

13、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.2 3.2 容斥原理容斥原理应应用用3.2.3.2.容斥原理容斥原理应应用用2.1 棋盘多项式棋盘多项式 n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个

14、棋子xxxxx排列41352对应于如图所示的布局。3.2.3.2.容斥原理容斥原理应应用用 可以把棋盘的形状推广到任意形状：布子规定同上。令rk(C)表示k个棋子布到棋盘C上的方案数。3.2.3.2.容斥原理容斥原理应应用用r1()=1r1()=2r1()=2r2()=0r2()=13.2.3.2.容斥原理容斥原理应应用用规定 r0(C)=1，包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk-1(Ci)rk(Ce)3.2.3.2.容斥原理容斥原理应应用用从而R(C)=rk(C)xk =1+rk-1(Ci)+

15、rk(Ce)xk =x rk(Ci)xk+rk(Ce)xk =xR(Ci)+R(C e)(3)k=0k=1k=0k=0定义定义1 1 设C为一棋盘，称R(C)=rk(C)xk为C的棋盘多项式。k=03.2.3.2.容斥原理容斥原理应应用用例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=x R()+R()=x(1+x)+1+x =1+2x+x23.2.3.2.容斥原理容斥原理应应用用 如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：R(C)=(ri(C1)rk-i(C2)xk =(ri(C1)xi)(rj(C2)xj)j=

16、0nnkni=0i=0k=0 R(C)=R(C1)R(C2)(4)i=0krk(C)=ri(C1)rk-i(C2)故3.2.3.2.容斥原理容斥原理应应用用利用()和()，可以把较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例例13:R()=xR()+R()=x(1+x)2 +(1+2x)2 =1+5x+6x2+x3*R()=xR()+R()=1+6x+10 x2+4x3*3.2.3.2.容斥原理容斥原理应应用用2.2 2.2 有禁区的排列有禁区的排列例例1414设对于排列P=P1 P2 P3 P4，规定P1，P,4，P2,，P42。1 2 3 4P1P2P3P4这样的排列对

17、应于有禁区的布子。如左图有影线的格子表示禁区。3.2.3.2.容斥原理容斥原理应应用用定理定理4:4:设 rk 为 k 个棋子布入禁区的方案数，k=1,2,n。则有禁区的布子方案数（即禁区内不布子的方案数）为 n!r1(n1)!r2(n2)!(1)nrn(1)k rk(nk)!k=0n3.2.3.2.容斥原理容斥原理应应用用例例15 ,四位工人，A,B,C,D四项任 务。条件如下：不干B；不干B、C；不干C、D；不干D。问有多少种可行方案？3.2.3.2.容斥原理容斥原理应应用用解解:由题意，可得如下棋盘：其中有影线的格子表示禁区。A B C D1 2 3 4 R()=1+6x+10 x2+4

18、x3 方案数=4!6(41)!+10(42)!4(43)!+0(44)!=4 例例16 16 一婚姻介绍所，登记有一婚姻介绍所，登记有5 5名男性名男性A A，B B，C C，D D，E E和和4 4名女性名女性1 1，2 2，3 3，4 4，经了解：，经了解：1 1不能与不能与B,C,D,EB,C,D,E，2 2不能与不能与A,D,E,3A,D,E,3不能与不能与A,B,CA,B,C，4 4不能与不能与A,B,C,DA,B,C,D求可能婚配的方案数。求可能婚配的方案数。解：解：A B C D E12343.2.3.2.容斥原理容斥原理应应用用 解：解：A B C D E1234R(C)R(C

19、)=(1+x)(1+2x)(1+3x+x=(1+x)(1+2x)(1+3x+x2 2)=1+6x+12x=1+6x+12x2 2+9x+9x3 3+2x+2x4 43.2.3.2.容斥原理容斥原理应应用用3.2.3.2.容斥原理容斥原理应应用用例例1717三论错排问题 错排问题对应的是nn的棋盘的主对角线 上的格子是禁区的布子问题。C=R(C)=0(1)(,),nnkkxC n k x则有(,),krC n k故错排问题的解为:1!(1)(,)()!nkknC n k nk01!(1).!nkknk欧拉函数是指小于n且与n互素的正整数的个数。1212.kaaaknppp 设1到n的n个数中pi

20、 倍数的集合为,1,2,.,.iA ik解解：若n分解为素数的乘积3.2.3.2.容斥原理容斥原理应应用用3 3 欧拉函数欧拉函数(n)1212.kaaakUnp pp3.2.3.2.容斥原理容斥原理应应用用则有,1,2,.,.iinAikp,1,2,.,.ijijnAAi jk ijp p .12.knAAA()=3.2.3.2.容斥原理容斥原理应应用用121213112(.)(.)(1)kknnknnnnnnpppp pp pnnppp pp 12111(1)(1)(1)knppp 260235,111(60)60(1)(1)(1)16235n例如则即比60小且与60互素的数有16个：1，

21、7，11，13，17,19,23，29，31，37，41，43，47，49，53，59。3.2.3.2.容斥原理容斥原理应应用用例例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？3.3.广义容斥原理广义容斥原理若将.1中的例子2改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”则如何计算？3.3.广义容斥原理广义容斥原理若将.1中的例子2改为“单修一门数学的学生有

22、多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”单修一门数学的用ABC来表示，则有ABCAABACABC类似的ABCBBABCABCABCCCACBABC23ABCABCABCABCABACBCABC同样的3ABCABCABCABACBCABC3.3.广义容斥原理广义容斥原理设有与性质,2,n相关的元素N个，Ai为有第 i 种性质的元素的集合.i=1,2,n定义a(0)=N；当m1时12()miiia mAAAb(m)是正好正好具有m个性质的元素的个数。3.3.广义容斥原理广义容斥原理例如，对于n=3,m=2121323(2)aAAAAAA212313123(2)bAAAAAAA

23、AA利用这些记号 b(1)=a(1)-2a(2)+3a(3)b(2)=a(2)-3a(3)3.3.广义容斥原理广义容斥原理定理定理5（广义容斥原理）：（广义容斥原理）：1()()(1)(1)()(1)()n mnk mk mmnb ma ma ma nmmka km 特别的，当m=0时(0)(0)(1)(2)(1)()nbaaaa n 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

24、+j种性质,则其对a(k)的贡献是C(k+j,k),对a(k+i)的贡献是C(k+j,k+i)jii 0kjki(1)kiijii 0kjki(1)kikjii 0kjj(1)ki jii 0kjj(1)ki 3.3.广义广义容斥原理容斥原理jii 0kjki(1)kiijii 0kjj(1)ki kj00k即某恰有k+j种性质的元素对上式右边总的贡献为0例例18 某校有12个教师，已知教数学的有8位，教物理的有6位，教化学的5位；数、理5位，数、化4位，理、化3位；数理化3位。问教其他课的有几位？只教一门的有几位？只教两门的有几位？解解:令教数学的教师属于A1，教物理的属于A2，教化学的属于

25、A3。则 a(0)12，a(1)|A1|+|A2|+|A3|8+6+519;a(2)|A1A2|+|A1A3|+|A2A3|12；a(3)|A1A2A3|3；3.3.广义容斥原理广义容斥原理故教其他课的老师数为：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)=33.3.广义容斥原理广义容斥原理3.4.广义容斥原理应用广义容斥原理应用1 1、非负整数解、非负整数解12nxxxr线性方程的非负整数解：非负整数解的个数为C(n+r-1,r)非负整数解一一对应于r个相同的球放入n

26、个不同的盒子中的方案例19：给定方程12315xxx求满足附加条件12305,06,07xxx的解的个数。若无上界条件限制，则非负整数解的个数为C(15+3-1,15)=C(17,2)加上限制则不可套用此公式了。3.4.广义容斥原理应用广义容斥原理应用令 N为全体非负整数解；1A为其中16x 的解；2A为其中27x 的解；3A为其中38x 的解；对于A1，相当于求方程123(6)15xxx的非负整数解1(93 1,9)(11,2)ACC类似的 23(10,2),(9,2),ACAC3.4.广义容斥原理应用广义容斥原理应用123(1)(11,2)(10,2)(9,2)136aAAACCC1213

27、23(2)(4,2)(3,2)(2,2)10aAAAAAACCC123(3)0aAAA故方程满足条件的解为(0)(0)(1)(2)(3)10baaaa3.4.广义容斥原理应用广义容斥原理应用另解：做变量替换1122335,6,7xxx则问题转化为求方程1233的非负整数解。其个数为C(3+3-1,3)=C(5,2)=103.4.广义容斥原理应用广义容斥原理应用鸽巢原理，又叫鸽巢原理，又叫抽屉原理抽屉原理，是一个重要而又初等，是一个重要而又初等的组合学原理，它能够解决各种有趣的问题，常的组合学原理，它能够解决各种有趣的问题，常常得出一些令人惊奇的结论常得出一些令人惊奇的结论.它指的是一个简单的它

28、指的是一个简单的事实：事实：如果鸽子的数目比巢穴的数目多，那么至如果鸽子的数目比巢穴的数目多，那么至少要有一个鸽巢被两只或多只鸽子占据少要有一个鸽巢被两只或多只鸽子占据(简单的说简单的说,即即“若有若有n个个鸽子巢，鸽子巢，n+1+1个鸽子，则至少有一个鸽子，则至少有一个巢内有至少有两个鸽子。个巢内有至少有两个鸽子。”).).下面我们将给出更下面我们将给出更精确的叙述，以及鸽巢原理的应用举例精确的叙述，以及鸽巢原理的应用举例.3.5 鸽巢原理鸽巢原理3.5.1 引论引论3.5 鸽巢原理鸽巢原理证明证明:设这设这n+1个数是个数是 a1,a2,an+1 3.5.2 鸽巢原理的形式鸽巢原理的形式鸽

29、巢原理的鸽巢原理的简单形式简单形式如下：如下：定理定理 3.5.1 如果把如果把n+1个鸽子放入个鸽子放入n个鸽巢，那个鸽巢，那么至少有一个鸽巢中有两个或更多的么至少有一个鸽巢中有两个或更多的鸽子鸽子.【例例20】在在13个人中至少有两个人在同一个月过生日个人中至少有两个人在同一个月过生日.【例例21】从从1到到2n的正整数中任取的正整数中任取n+1个，则这个，则这n+1个数中至少有一对数，其中一个是另一个的倍数个数中至少有一对数，其中一个是另一个的倍数.3.5 鸽巢原理鸽巢原理对此序列中的每一个数去掉一切对此序列中的每一个数去掉一切2的因子，直至的因子，直至剩剩下一个奇数为止下一个奇数为止.

30、例如，例如，682217，则去，则去掉掉22，只留下，只留下17.那么我们会得到一个由奇数那么我们会得到一个由奇数组成的序列组成的序列 b1,b2,bn+11到到2n之间只有之间只有n个奇数，故序列个奇数，故序列 b1,b2,bn+1中中至少有两个是相同的至少有两个是相同的.设设bi=bj=b，则，则bi=2pa，bj=2qa,由于由于bibj，显然，其中一个是另一个的倍数，显然，其中一个是另一个的倍数.可以看出，应用鸽巢原理可以巧妙的解决看似复可以看出，应用鸽巢原理可以巧妙的解决看似复杂的问题，其杂的问题，其关键是如何去构造问题中的关键是如何去构造问题中的“鸽子鸽子”和和“鸽巢鸽巢”.【例例

31、22】边长为边长为1的等边三角形内任意的等边三角形内任意5个点，个点，至少有两个点，其距离不超过至少有两个点，其距离不超过1/2证证:三条边的中点把等边三角形分成三条边的中点把等边三角形分成4个边个边长为长为1/2的等边三角形的等边三角形 由鸽巢原理，任意由鸽巢原理，任意5个点必有个点必有2个落入同个落入同一个，其距离不超过一个，其距离不超过1/2.3.5 鸽巢原理鸽巢原理例23：1、在边长为2的正方形中任取5 点，证明：存在2 点其间距离不超过21/22、在边长为1 的正三角形中任取10 点，证明：存在2 点其间距离不超过1/33.5鸽巢原理【例例24】设设 a1,a2,am是正整数序列，则

32、至少是正整数序列，则至少存在存在一个一个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)hhihhhiSa Srmrm1:,(mod),01 证证 设设3.5 鸽巢原理鸽巢原理【例例25】设设a1,a2,a100是由是由1和和2组成的序组成的序列列,已知从其任一数开始的顺序已知从其任一数开始

33、的顺序10个数的和个数的和不超过不超过16即即 ai+ai+1+ai+9 16，1 i 91则至少存在则至少存在一对一对h和和k，k h，使得，使得 ah+1+ak=39S1S2hSkSh=39 即即 ah+1+ak=39 3.5 鸽巢原理鸽巢原理例26：一位象棋大师以11 周时间准备一次比赛，他决定每天至少下一盘棋，为了不至于太累，他限定每一周不多于12 盘对局，证明，存在连续若干天，在这些天中他恰下了21 盘棋。解：令ai是第1天到第i天下的总盘数(i=1,2,77;11周共77天)3.5 鸽巢原理鸽巢原理类似的题目3.5 鸽巢原理例例27：一个学生用37 天准备考试，据经验她知道复习的总

34、时间不会超过60 小时，而她又希望每天至少复习1 小时，证明：不管怎样安排每天复习的小时数，有连续的若干天，其间恰好复习13 小时。解法类似上例这154个数均在1-153之间，故必有两个数相等，且容易知道这两个数是一个在前段，一个在后段，即一个为ai，一个为aj+21，ai=aj+21立知ai-aj=21，ji,即第j+1天至第i天之间总共下了21盘3.5 鸽巢原理鸽巢原理定理定理 3.5.2 设设a1,a2,an都是正整数都是正整数.如果把如果把a1+a2+an-n+1个个鸽子鸽子住入住入n个个鸽鸽巢，那么或者第一个巢，那么或者第一个鸽鸽巢至少巢至少住入住入a1个个鸽子鸽子，或者第二个，或者

35、第二个鸽鸽巢至少住入巢至少住入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鸽巢原理例28：证明任意给定的52

36、 个整数中，总存在两个数，它们的和或差能被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 鸽巢原理鸽巢原理推论推论 3.5.1 若把若把n(r-1)+1个个鸽子鸽子住入住入n个个鸽鸽巢，巢，那么至少有一个那么至少有一个鸽鸽巢中有巢中有r个个鸽子鸽子住入住入.也可以写成如下形式：也可以写成如下形式：在定理在定理3.5.2中，如果

37、令中，如果令ai=2(i=1,2,n)，就是，就是定理定理3.5.1如果如果ai=r(i=1,2,n)，则变成了：，则变成了：11mn 推论推论 3.5.2 若将若将m个鸽子放入个鸽子放入n个个鸽鸽巢中，则至少巢中，则至少有一个有一个鸽鸽巢中有不少于巢中有不少于 只鸽子只鸽子.3.5 鸽巢原理鸽巢原理推论推论 3.5.3 设设a1,a2,an是是n个整数，而且个整数，而且 则则a1,a2,an中至少有一个数不小于中至少有一个数不小于r.121naaarn 【例例29】若序列若序列S=a1,a2,amn+1中的中的各数是不等的，各数是不等的，m,n 是正整数，则是正整数，则 S有一长有一长度为度

38、为m+1的严格增子序列或长度为的严格增子序列或长度为n+1的减的减子序列，而且子序列，而且 S有一长度为有一长度为m+1的减子序列的减子序列或长度为或长度为n+1的增子序列的增子序列证由证由S中的每个中的每个 ai 向后选取最长增子序向后选取最长增子序列，设其长度为列，设其长度为li，从而得序列，从而得序列L=l1,l2,lmn+1 若存在若存在 lkm+1，则结论成立则结论成立3.5 鸽巢原理鸽巢原理不妨设不妨设 i1i2 ai2 ain+1，mn111n1m 否则所有的否则所有的 li 1,m,其中必有其中必有个相等，于是设个相等，于是设li1=li2=lin=lin+1 3.5 鸽巢原理

39、鸽巢原理即有一长度为即有一长度为n+1的减子列的减子列矛盾矛盾1212iiiiaall否则，若否则，若 证从证从ai 向后取最长增子列及减子列，设向后取最长增子列及减子列，设其长度分别为其长度分别为 li，li.若对任意若对任意 i，都有，都有li 1，m,l i1，n,不超过不超过mn种对种对则存在则存在 j k，(lj,l j)=(lk,l k)但是但是 若若aj lk，若若aj ak，则，则 l j l k，矛盾，矛盾3.5 鸽巢原理鸽巢原理【例例30】将将 1,67 划分为个子集，必有一个划分为个子集，必有一个子集中有一数是同子集中的某两数之差子集中有一数是同子集中的某两数之差证证:用

40、反证法设命题不真用反证法设命题不真即存在划分即存在划分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 鸽巢原理鸽巢原理设设Bb1,b16，B 1,67。由反证法假设，由反证法假设，BP1=。因而。因而 B (P2 P3 P4)因为因为(16-1)/3+1=6，不妨设，不妨设b1,b6 P2，令令

41、ci=bi1b1，i=1,5设设Cc1,c5，C 1,67 由反证法假设，由反证法假设，C(P1P2)=，故有，故有 C (P3P4)因为因为(5-1)/2+1=3，不妨设，不妨设c1,c2,c3 P33.5 鸽巢原理鸽巢原理令令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 鸽巢原理鸽巢原理【例例31】一个一个抽屉里由抽屉里由20件衬衫，其中件衬衫，其

42、中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 鸽巢原理鸽巢原理3.5 鸽巢原理鸽巢原理定理定理3.5.3 假设类型假设类型i的物品有的物品有xi件，件，i=1,2,n,且且12nxxx从中任意取出至少从中任意取出至少ar件才能保证至少有件才能保证至少有r件同类件同类型的物品，则型的物品，则11121223111(1)1,(1)(1)1,(2)(1)1,(1)(1)1,rnnnn rrxxnrxrxaxxnrxrxxxrxrx