组合数学鸽巢原理

2023年2月2日第二章鸽巢原理和Ramsey定理§2.2鸽巢原理的加强形式定理2.2.1(鸽巢原理的加强形式)2023年2月2日第二章鸽巢原理和Ramsey定理推论2.2.1

若n(r－1)+1个物品放入n个盒子。则至少有一个盒子里含有r个或者更多的物品。

推论2.2.2若设有n个正整数m1,m2,…,mn满足下面的不等式

(m1+…+mn)/n>

r－1,

则

m1,…,mn中至少有一个数≥

r推论2.2.3

设m和n都是正整数且m>n，若将m个物体放入n个盒子中，则至少有一个盒子中有大于等于个物体2023年2月2日第二章鸽巢原理和Ramsey定理

推论2.2.2若设有n个正整数m1,m2,…,mn满足下面的不等式

(m1+…+mn)/n>

r－1,

则

m1,…,mn中至少有一个数≥

r

另外两个平均原理：设有n个正整数m1,m2,…,mn满足下面的不等式

(m1+…+mn)/n<

r+1,

则

m1,…,mn中至少有一个数<r+12023年2月2日第二章鸽巢原理和Ramsey定理推论2.2.3

设m和n都是正整数且m>n，若将m个物体放入n个盒子中，则至少有一个盒子中有大于等于个物体2023年2月2日第二章鸽巢原理和Ramsey定理例2.2.3设有大小两只圆盘，每个都划分成大小相等的200个小扇形，在大盘上任选100个小扇形涂成黑色，其余的100个小扇形涂成白色，而将小盘上的200个小扇形任意涂成黑色或白色。现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上小扇形之内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。2023年2月2日第二章鸽巢原理和Ramsey定理2023年2月2日第二章鸽巢原理和Ramsey定理证明

如图2.2.1所示，使大小两盘中心重合，固定大盘，转动小盘，则有200个不同位置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘上的200个小扇形中有100个涂成黑色，100个涂成白色，所以小盘上的每个小扇形无论涂成黑色或白色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色，因而小盘上的200个小扇形在200个重合位置上共同色100×200=20000次，平均每个位置同色20000÷20=100次。由推论2.2.3知，存在着某个位置，使同色的小扇形数大于等于100个。

2023年2月2日第二章鸽巢原理和Ramsey定理例2.2.4用鸽巢原理的加强形式证明证明：任意n2+1个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。

2023年2月2日第二章鸽巢原理和Ramsey定理证明：假设长为n2+1的实数序列中没有长度为n+1的递增子序列，下面证明其必有一长度为n+1的递减子序列。 令mk表示从ak开始的最长递增子序列的长度，因为实数序列中没有长度为n+1的递增子序列，所以有：

根据推论2.2.3，这相当于把n2+1个物体

放入n个盒子1，2，…，n中，必有一个盒子i里面至少有个物体，即存在n+1个mk取值相同，有使得（2.2.1）

对应于这些下标的实数序列必满足

（2.2.2）

它们构成一长为n+1的递减序列。否则，若有某个j（）使得，那么由从开始的最长递增子序列加上，就得到一个从开始的长度为的递增子序列。由的定义知这与（2.2.1）式矛盾。因此（2.2.2）式成立。同理可证若没有长度为n+1的递减子序列，则必有一长度为n+1的递增子序列。因此，结论成立。§2.3Ramsey定理

任何一个6人聚会，必有3个人相互认识或者相互不认识其思想可以概括为“在任何一个足够大的结构中必定包含一个给定大小的规则子结构”。例2.3.1

设K6是6个顶点的完全图，用红、蓝两色涂色K6的边，则存在一个红色三角形，或存在一个蓝色三角形。证明：设K6的顶点为v1,v2,v3,v4,v5,v6.对于任意一种涂色方案，根据鸽巢原理加强形式的推论3，与v1关联的5条边至少有条同色边不妨设这三条边为{v1

,v2},{v1,v3},{v1,v4}（1）若这三条边均为红色v1v2v3v4(a)当v2,v3,v4

之间有一条红边，如{v2,v3}(b)v2,v3,v4

之间没有红边，v1v2v3v4v1v2v3v4(a)(b)（2）若这三条边均为蓝色，同理可证.2023年2月2日第二章鸽巢原理和Ramsey定理例2.3.2

用红、蓝两色涂色K9的边，证明或者存在一个蓝色的三角形或红色的完全四边形。Ramsey定理简单形式定理2.3.1

设p，q是正整数，p，q≥2，则存在最小的正整数R(p,q)，使得当n≥R(p,q)时，用红、蓝两色涂色Kn的边，或者存在一个蓝色的完全p边形Kp，或者存在一个红色的完全q边形Kq。

称R(p,q)为Ramsey数；确定精确的Ramsey数的值是相当困难的工作。到目前为止，仅有极少数小p，q的Ramsey数被找到。

2023年2月2日第二章鸽巢原理和Ramsey定理qp3456789103691418232836404341825354149615684691159214954349588780143101216121316141442610216511129812749516978017811717205540216103123217132826828218703173583609095656588580126771079823556证明思路：归纳法归纳假设

R(p,2)≤p,R(2,q)≤q,

归纳步骤

R(p-1,q)，R(q-1,p)存在⇒R(p,q)≤R(p-1,q)+R(q-1,p)假设对正整数p’,q’,p’≤p,q’≤q,p’+q’<p+q为真，则R(p-1,q),R(p,q-1)存在.令n≥R(p-1,q)+R(p,q-1)，用蓝红两色涂色Kn的边，则case1v1关联R(p-1,q)条蓝边，case2v1关联R(p,q-1)条红边.对于case1，如为蓝色Kp-1,构成蓝色Kp；如为红色Kq，则满足要求.对于case2可以类似分析.R(p,q)≤R(p-1,q)+R(q-1,p)

例2.3.3

证明：R(3,3)=6证明：由例2.3.1知R(3,3)≤6。而图2.3.2中的实线代表蓝色的边，虚线代表红色的边，则这个的涂色方案既不包含蓝三角形，也不包含红三角形。所以R(3,3)>5。因此R(3,3)=6。

定理2.3.2

设p,q是正整数，p，q≥2，则

R(p,q)=R(q,p)

证明：令n≥R(p,q)。对于蓝、红两色涂色Kn的边的任何一种方案，将蓝边换红边，红边换蓝边，则或存在一个蓝色的完全p边形，或存在一个红色的完全q边形。而原来的涂色方案中必存在一个红色的完全p边形或一个蓝色的完全q边形，即R(q,p)≥R(p,q)。同理可证R(p,q)≥R(q,p)。因此，R(p,q)=R(q,p)R(p,q)的图表示R(p,q)的集合表述Kn

的顶点集V集合SKn

的边集ES的2元子集的集合T用2色涂色Kn

的边将T划分成E1,E2存在蓝色完全p边形存在S的p子集其所有2元子集∈E1存在红色完全q边形存在S的q子集其所有2元子集∈E2集合表述具有更强的表达能力.定理推广（1）

将2元子集推广到r元子集

对于任意给定的正整数p,q,r,(p,q≥r)存在一个最小的正整数R(p,q;r)使得当集合S的元素数大于等于R(p,q;r)时，将S的r子集族任意划分成E1,E2，则或者S有p子集A，A的所有r元子集属于E1,或者存在q子集B，B的所有r元子集属于E2.定理推广（2）

将T划分成E1,E2,…,Ek

设r,k≥1,qi≥r,i=1,2,…,k,是给定正整数，则存在一个最小的正整数R(q1,q2,…,qk;r)，使得当n≥R(q1,q2,…,qk;r)时,当n元集S的所有r元子集划分成k个子集族T1,T2,…,Tk，那么存在S的q1元子集A1,其所有的r元子集属于T1,或者存在S的q2元子集