朱全民组合数学鸽巢原理

1、.7鸽巢原理之一 鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”例367人中至少有人的生日相同。例10双手套中任取11只，其中至少有两只是完整配对的。例参加一会议的人中至少有人认识的别的参加者的人数相等。.7鸽巢原理之一例从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数，其中一个是另一个的倍数。证设n+1个数是 a1 , a2 , , an+1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列 r1 , r2, , , rn+1。这n+1个数仍在1 , 2n中，且都是奇数。而1 , 2n中只

2、有n个奇数 . 故必有 ri = rj = r , 则 ai = 2i r, aj = 2j r若ij ，则 ai 是 aj 的倍数。.7鸽巢原理之一例设 a1 , a2 , , am是正整数序列，则至少存在k和 l , 1k l m，使得和ak + ak+1 + + al 是m的倍数。证设Sk = ai , Sh rh mod m 0rhm-1h = 1 , 2 , , m . 若存在 l , Sl0 mod m 则命题成立否则，1rhm-1但h = 1 , 2 , , m由鸽巢原理，故存在 rk = rh , 即Sk Sh，不妨设 h k则 ShSk = ak+1 + ak+2 + + a

3、h 0 mod m i=1h.7鸽巢原理之一例设 a1 , a2 , a3为任意个整数，b1b2b3为a1 , a2 , a3的任一排列，则 a1b1 , a2b2 , a3b3中至少有一个是偶数证由鸽巢原理， a1 , a2 , a3必有两个同奇偶设这个数被除的余数为 xxy，于是b1 , b2 , b3中被除的余数有个x，一个y这样a1b1 , a2b2 , a3b3被除的余数必有一个为.7鸽巢原理之一例设a1 , a2 , , a100是由 1和组成的序列 , 已知从其任一数开始的顺序10个数的和不超过16即 ai + ai+1 + + ai+9 16，1 i 91则至少存在 h 和 k

4、 ，k h，使得 ah + ah+1 + + ak = 39 证令Sj = ai，j =1 , 2 , ,100显然S1S2hSkSh =39 即 ah + ah+1 + + ak = 39 .8鸽巢原理之二鸽巢原理二m1 , m2 , , mn都是正整数，并有m1 + m2 + +mnn + 1个鸽子住进n个鸽巢，则至少对某个 i 有第 i 个巢中至少有mi个鸽子，i = 1 , 2 , , n上一小节的鸽巢原理一是这一原理的特殊情况，即m1 = m2 = = mn= 2， m1 + m2 + +mnn + 1 = n + 1如若不然，则对任一 i， 都有第 i 个巢中的鸽子数mi1则.8鸽

5、巢原理之二鸽子总数 m1 + m2 + +mnn ，与假设相矛盾推论m只鸽子进n个巢，至少有一个巢里有 |只鸽子nm推论n(m1) + 1只鸽子进n个巢，至少有一个巢内至少有m只鸽子推论若m1 , m2 , , mn是正整数，且 r1,则 m1, , mn至少有一个不小于rm1 + +mn n.8鸽巢原理之二例设A= a1a2a20是10个0和10个1 组成的进制数B=b1b2b20是任意的进制数C = b1b2b20 b1b2b20 = C1C2C40，则存在某个i ，1 i 20，使得CiCi+1Ci+19与a1a2a20至少有10位对应相等. . . . .ABC第 i 格第 i +19

6、格1 2 19 20 1 2 19 20 1 2 19 20 1 19 20.8鸽巢原理之二证在C = C1C2C40中，当 i 遍历1 , 2 , ,20时，每一个bj历遍 a1 , a2 , , a20因A中有10个0和10个1，每一个bj都有10位次对应相等从而当 i历遍1 , , 20时，共有10 20=200位次对应相等故对每个 i平均有200 20 = 10位相等，因而对某个 i 至少有10位对应相等.8鸽巢原理之二定理若序列S = a1 , a2 , , amn+1中的各数是不等的m , n 是正整数，则 S有一长度为m+1的严格增子序列或长度为n+1的减子序列，而且 S有一长度

7、为m+1的减子序列或长度为n+1的增子序列证由S中的每个 ai 向后选取最长增子序列，设其长度为li ，从而得序列L = l1 , l2 , , lmn+1 若存在 lkm+1则结论成立.8鸽巢原理之二否则所有的 li 1 , m，其中必有 | = n+1个相等设li1 = li2 = = lin= lin+1 不妨设 i1i2 ai2 ain+1 ，即有一长度为n+1的减子列否则不妨设ai1 li2 ，矛盾mn+1 m.8鸽巢原理之二证从ai 向后取最长增子列及减子列，设其长度分别为 li ，li .若任意 i ，都有li 1，m, li，n,不超过mn种对则存在 j k，( lj , lj

8、 ) = ( lk , lk )若aj lk，若aj ak，则 lj lk ，矛盾.8鸽巢原理之二例将 1 , 65 划分为个子集，必有一个子集中有一数是同子集中的两数之差证用反证法设次命题不真即存在划分P1 P2 P3P4 1，65 ，Pi中不存在一个数是Pi中两数之差，i=1,2,3,4因 = 17，故有一子集，其中至少有17个数，设这17个数从小到大为a1 , , a17 不妨设 A=a1 , , a17 P1。令bi1= aia1，i = 2，17。65 4.8鸽巢原理之二设Bb1 , , b16，B 1 , 65 。由反证法假设BP1 = 。因而 B ( P2 P3 P4 )。 因为

9、 6，不妨设b1 , , b6 P2 ， 令Ci1=bib1，I = 2， ，6设C C1 , , C5 ，C 1 , 65 由反证法假设C( P1P2 ) =，故有 C (P3P4 )因为 3，不妨设C1 , C2 , C3 P316 352.8鸽巢原理之二令di1= CiC1，I = 2 , 3设D d1 , d2 , D 1 , 65。由反证法假设 D( P1P2P3 )=，因而 D P4。由反证法假设 d2d1 P1P2P3 且d2d1 P4 ，故 d2d1 1 , 65 ，但显然 d2d1 1 , 65 ，矛盾。.9Ramsey 问题Ramsey问题 Ramsey问题可以看成是鸽巢原

10、理的推广下面举例说明Ramsey问题例6 个人中至少存在人相互认识或者相互不认识证这个问题与K6的边着色存在同色三角形等价假定用红蓝着色.9Ramsey 问题设K6的顶点集为v1 , v2 , , v6 ，dr(v)表示与顶点 v 关联的红色边的条数，db(v)表示与 v 关联的蓝色边的条数在K6 中，有dr(v) db(v)，由鸽巢原理可知，至少有条边同色现将证明过程用判断树表示如下：.9Ramsey 问题dr(v1)3?db(v1)3设(v1v2) (v1v3) (v1v4)为红边设(v1v2) (v1v3) (v1v4)为蓝边v2v3v4是红 ?v2v3v4是蓝 ?设( v2v3 )是蓝

11、边设( v2v3 )是红边v1v2v3是蓝v1v2v3是红YNNNYY.9Ramsey 问题若干推论( a )K6的边用红蓝任意着色，则至少有两个同色的三角形证由前定理知，有同色三角形，不妨设v1v2v3是红色三角形可由如下判断树证明.9Ramsey 问题v1v4v5是蓝设 (v4v5)为蓝边v4v5v6是红?设(v1v4) (v1v5) (v1v6)为蓝边db(v1)3dr(v1)3?设 (v1v4)为红边(v4v2) (v4v3) 为蓝边?设 (v4v2)为红边db(v4)3?v1v2v4是红dr(v4)3设 (v4v5)为蓝边(v4v5) (v4v6) 为红边v2v3v5是红?设 (v2

12、v5)为蓝边v2v4v5是蓝v4v5v6是红v1v5v6是蓝?设 (v5v6)为红边yyyyyynnnnn.9Ramsey 问题( b )K9 的边红蓝两色任意着色，则必有红K4或蓝色三角形(蓝K4或红色三角形)证设个顶点为 v1 , v2 , , v9对个顶点的完全图的边的红、蓝着色图中，必然存在 vi ，使得 dr(vi)3 否则，红边数 dr(vi) ，这是不可能的不妨设 dr(v1)3，可得如下判断树证明结论1227 2.9Ramsey 问题dr(v1)4?db(v1)6设(v1v2) (v1v3) (v1v4)(v1v5)是4红边设(v1v2) (v1v7)是6条蓝边K4(v2v3v

13、4v5)是蓝K4 ?K6(v2v7)中有红 ?设(v2v3)是红边v1v2v3是红设v2v3v4是红K4(v2v3v4v5)是蓝K4YYYNNN.9Ramsey 问题K9的边红、蓝着色，必有红色三角形或蓝色K4同理可证 K9的红、蓝着色，必有蓝色三角形或红色K4 (红 蓝K4) (蓝 红K4)存在同色K4或红及蓝 同色K4 (红 蓝 ).9Ramsey 问题( c )K18的边红，蓝着色，存在红K4或蓝K4 证设18个顶点为v1 , v2 , , v18 从v1引出的17条边至少有条是同色的，不妨先假定为红色从而可得下面的判断树证明命题.9Ramsey 问题dr(v1)9db(v1)9设(v1

14、v2) (v1v10)是红边K9(v2 v10)中有同色K4或红加蓝K10( v1v2 v10)中有同色K4设(v1v2) (v1v10)是蓝边K9(v2 v10)中有同色K4或红加蓝K10( v1v2 v10)中有同色K4YN.10Ramsey数将上一节的问题一般化：给定一对正整数a、b，存在一个最小的正整数 r ,对 r 个顶点的完全图的边任意红、蓝着色，存在 a 个顶点的红边完全图或 b 个顶点的蓝边完全图。记为 r ( a , b )。比如：r ( 3 , 3 )6，r ( 3 , 4 )9，r ( 4 , 4 )18Ramsey数的简单性质.10Ramsey数定理r ( a , b

15、) r ( b , a )；r ( a , 2 )a证K r(a , b )的边红蓝着色，有红Ka或蓝Kb将红蓝色对换，就有红Kb或蓝Ka设r ( a , b ) r ，Kr的边任意红蓝着色红蓝互换后仍是Kr的边的着色，由r(a,b)的定义，有红Ka或蓝Kb再红蓝对换恢复原图有红Kb或蓝Ka .10Ramsey数例K9的边任意红蓝着色，有红三角形或蓝K4红蓝对换后，仍有红三角形或蓝K4，再对换一次，回到原来的着色方案，有蓝三角形或红K4第二个等式容易看出Ka红蓝着色若不全红(红Ka)，则必有一条蓝边.10Ramsey数定理当a , b 时，r ( a , b ) r ( a 1 , b ) r

16、 ( a , b1 ) 证对r ( a 1 , b ) r ( a , b1 ) 个顶点的完全图红蓝着色任取其中一点 v，有 dr(v) + db(v) = r( a 1 , b ) + r( a , b1 )1从而可得判断树如下.10Ramsey数定理若 a ，则 r ( a , a) 2a2证Kn有 ( )条边，对边红蓝着色有2 种方案其中同色Ka的方案数不超过n2n2( )a2( )( ) 2 2n2( ) n2Ka的个数可红可蓝可任意着色边数同色边数.10Ramsey数这是一个上界Kn中含Ka的方案被重复计数若取n足够小，便得a2( ) ( ) 2na( ) + 1 n an即( )

17、2 n= 2 时( ) 2a2 .10Ramsey数Ramsey数的推广若将着色改为k 着色，同色Ka或同色Kb改为同色Ka i i = 1 , 2 , , k即得Ramsey数 r ( a1 , a2 , ,ak)对于给定的正整数 ai ( ai 2) ，i = 1 , 2 , , k存在最小正整数r对Kr的边用k中颜色Ci ( i = 1 , 2 , , k)任意着色则存在 i ，出现全Ci色的Ka i (即边都是Ci色的ai个顶点的完全图）；这个最小正整数 r 用 r (a1 , , ak)表示.10Ramsey数有 r (a1 , a2 , , ak) r ( a1 , r ( a2 , , ak) ) 证设r ( a1 , r ( a2 , , ak) ) = p， r (a2 , , ak) = q；对Kp的边着色，出现第一色Ka1或第二色Kq，用n1中色对Kq的边着色，至少