组合数学第二章鸽巢原理

《组合数学第二章鸽巢原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、三、Ramsey问题与Ramsey数一、鸽巢原理的简单形式二、鸽巢原理的加强形式四、Ramsey数的推广第二章鸽巢原理2.1鸽巢原理的简单形式定理2.1.1:如果把n+1个物品放入n个盒子中，那么至少有一个盒子中有两个或更多的物品。例1.13个人中必有两人的属相相同。例2.在边长为1的正方形内任取5点，则其中至少有两点，它们之间的距离不超过机动目录上页下页返回结束例3：从1到200的所有整数中任取101个，则这101个整数中至少有一对数，其中的一个一定能被另一个整除。机动目录上页下页返回结束例4.给定m个整数证明：必存在整

2、数k,l使得例5.一个棋手有11周时间准备锦标赛，他决定每天至少下一盘棋，一周中下棋的次数不能多于12次，证明：在此期间的连续一些天中他正好下棋21次。例6：（中国余数定理）设m,n为两个互素的正整数，a,b是满足的整数。证明：存在正整数x,使得x除以m的余数为a，除以n的余数为b，即存在p,q，使得机动目录上页下页返回结束2.2鸽巢原理的加强形式定理2.2.1:设机动目录上页下页返回结束都是正整数，如果把个物品放入n个盒子，那么或者第1个盒子中至少有q1个物品，或者第2个盒子中至少有q2个物品，……,或者第n个盒子中至少

3、有qn个物品.推论2.2.1:若将n(r-1)+1个物品放入n个盒子中，则至少有一个盒子中有r个物品。推论2.2.2:设机动目录上页下页返回结束是n个整数，而且则中至少有一个数不小于r。推论2.2.3:若将m个物品放入n个盒子中，则至少有一个盒子中有不少于个物品。例1：设有大小两只圆盘，每个都划分成大小相等的200的小扇形，机动目录上页下页返回结束在大盘上任选100个小扇形漆成黑色，其余的100个小扇形漆成白色，而将小盘上的200个小扇形任意漆成黑色或白色，现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上

4、的小扇形之内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。例2.任意个实数组成的序列中，必有一个长为n+1的递增子序列，或必有一个长为n+1的递降子序列。机动目录上页下页返回结束例3.将1到16这16个正整数任意分成三部分，其中必有一部分中的一个元素是该部分某两个元素之差（三个元素不一定互不相同）。2.3Ramsey问题与Ramsey数命题2.3.1:对6个顶点的完全图K6任意进行红、蓝两色边着色，都存在一个红色三角形或一个蓝色三角形。机动目录上页下页返回结束命题2.3.2:对6个顶点的完全图K6

5、任意进行红、蓝两色边着色，都至少存在两个同色三角形。2.3Ramsey问题与Ramsey数机动目录上页下页返回结束命题2.3.3:对10个顶点的完全图K10任意进行红、蓝两色边着色，都或者有一个红色K4，或者有一个蓝色K3。命题2.3.4:对9个顶点的完全图K9任意进行红、蓝两色边着色，都或者有一个红色K4，或者有一个蓝色K3。定义:对于任意给定的两个正整数a和b，如果存在最小正整数r(a,b)，使得当对KN任意进行红、蓝两色边着色，KN中均有红色Ka或蓝色Kb，则称为Ramsey数。性质：机动目录上页下页返回结束定理2.

6、3.1:对任意的正整数机动目录上页下页返回结束有若都是偶数，定理2.3.2:上面不等式严格成立。对任意的正整数有2.4Ramsey数的推广机动目录上页下页返回结束定义:对于任意给定的正整数n色边着色，KN中或出现c1红色如果存在最小正整数使得当或出现c2红色……，或出现cn红色则称为广义Ramsey数。2.4Ramsey数的推广定理2.4.1:机动目录上页下页返回结束对任意的正整数有定理2.4.2:对任意的正整数有定理2.4.3:机动目录上页下页返回结束设是集合且的任一划分，即则存在某一个i,Si中有三个数x,y,z(不一

7、定不同),满足方程其中定理2.4.4:(Ramsey定理)机动目录上页下页返回结束设是正整数，且使得当则必存在最小的正整数时，设S是一集合且

8、S

9、=m，将S的所有t元子集任意分放到n个盒子里，那么要么有S中的q1个元素，它的所有t元子集全在第一个盒子里；要么有S中的q2个元素，它的所有t元子集全在第二个盒子里；……；要么有S中的qn个元素，它的所有t元子集全在第n个盒子里。注:定理2.4.5: