资源描述：
《组合数学—第二章鸽巢原理和Ramsey定理(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2021年9月7日第二章鸽巢原理和Ramsey定理§2.2鸽巢原理的加强形式定理2.2.1(鸽巢原理的加强形式)2021年9月7日第二章鸽巢原理和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个盒子中，则至少有一个盒子中有大于等于个物体2021年9月7日第二章鸽巢原理和
2、Ramsey定理推论2.2.2若设有n个正整数m1,m2,…,mn满足下面的不等式(m1+…+mn)/n>r－1,则m1,…,mn中至少有一个数≥r另外两个平均原理：设有n个正整数m1,m2,…,mn满足下面的不等式(m1+…+mn)/nn，若将m个物体放入n个盒子中，则至少有一个盒子中有大于等于个物体2021年9月7日第二章鸽巢原理和Ramsey定理例2.2.3设有大小两只圆盘，每个都
3、划分成大小相等的200个小扇形，在大盘上任选100个小扇形涂成黑色，其余的100个小扇形涂成白色，而将小盘上的200个小扇形任意涂成黑色或白色。现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上小扇形之内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。2021年9月7日第二章鸽巢原理和Ramsey定理2021年9月7日第二章鸽巢原理和Ramsey定理证明如图2.2.1所示，使大小两盘中心重合，固定大盘，转动小盘，则有200个不同位置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘
4、上的200个小扇形中有100个涂成黑色，100个涂成白色，所以小盘上的每个小扇形无论涂成黑色或白色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色，因而小盘上的200个小扇形在200个重合位置上共同色100×200=20000次，平均每个位置同色20000÷20=100次。由推论2.2.3知，存在着某个位置，使同色的小扇形数大于等于100个。2021年9月7日第二章鸽巢原理和Ramsey定理例2.2.4用鸽巢原理的加强形式证明证明：任意n2+1个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个
5、长度为n+1的递减子序列。2021年9月7日第二章鸽巢原理和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（
6、）使得，那么由从开始的最长递增子序列加上，就得到一个从开始的长度为的递增子序列。由的定义知这与（2.2.1）式矛盾。因此（2.2.2）式成立。同理可证若没有长度为n+1的递减子序列，则必有一长度为n+1的递增子序列。因此，结论成立。§2.3Ramsey定理任何一个6人聚会，必有3个人相互认识或者相互不认识其思想可以概括为“在任何一个足够大的结构中必定包含一个给定大小的规则子结构”。例2.3.1设K6是6个顶点的完全图，用红、蓝两色涂色K6的边，则存在一个红色三角形，或存在一个蓝色三角形。证明：设K6的顶点为v1,v2,v
7、3,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）若这三条边均为蓝色，同理可证.2021年9月7日第二章鸽巢原理和Ramsey定理例2.3.2用红、蓝两色涂色K9的边，证明或者存在一个蓝色的三角形或红色的完全四边形。Ramse
8、y定理简单形式定理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
