第6讲鸽巢原理

《第6讲鸽巢原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、应用组合数学第6讲鸽巢原理张坤龙zhangkl@tju.edu.cn目录•鸽巢原理•Ramsey定理鸽巢原理[鸽巢原理]若有n个鸽巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子*鸽巢原理主要用于解存在性问题鸽巢原理-例题（1）[例1]从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数，其中一个是另一个的倍数。证明：设n+1个数是a,a,···,a。每个数去12n+1掉一切2的因子，直至剩下一个奇数为止得到序列r,r,···,r。这n+1个数仍在[1,2n]中，且都是12n+1奇数，但[1,2n]中只有n个奇数

2、，故有r=r=r。再ijα设a=2αir，a=2jr，若a>a，则a是a的倍数。ijijij鸽巢原理-例题（2）[例2]设a,a,a为任意3个整数，bbb为a,a,a的123123123任一排列，则a－b,a－b,a－b中至少有一个是112233偶数证明：由鸽巢原理，a,a,a中必有两个同奇偶．设123这3个数被2除的余数为xxy。假设a－b,a－b,a11223－b中没有一个是偶数，则它们被2除的余数没有一3个为０，从而b,b,b这3个数被2除的余数为yyx，123矛盾。鸽巢原理-例题（3）[例3]设a,a,···,a是由1

3、和2组成的序列,已知从12100其任一数开始的顺序10个数的和不超过16．证明至少存在h和k，k>h，使得a+a+…+a=39h+1h+2k证明：令S=a+a+…+a，显然Sh，S－S=39，即a+a+…+a=39khh+1h+2k

4、鸽巢原理的推广1若有n个鸽巢，kn+1个鸽子，则至少有一个巢内有至少有k+1个鸽子[定理2]m只鸽子，n个鸽巢，则至少有一个鸽巢里有⎢m−1⎥不少于+1只鸽子。⎢⎥⎣n⎦证明：反证法鸽巢原理的推广1-例题（1）[例4]若序列a1,a2,?an2+1的n2+1个元素是不相等的实数，则该序列或者包含一个n+1项的递增子序列，或者包含一个n+1项的递减子序列。证明：对每一项a关联一个数t，表示从a开始的iii最长递增子序列中有多少项，显然有n2+1个t。若i存在某个t≥n+1，则得到所求的递增序列，否则所有t≤n，根据鸽巢原理必有n

5、+1个t相等。现在证明这些相等的t关联的a构成一个递减子序列：假设a,ia(ia，否则将形成从a开始jiji的长为t+1的递增子序列。鸽巢原理的推广1-例题（2）[例5]A={1,2,…,99},X是A的子集，且

6、X

7、=10，则可以找到X的两个非空真子集Y和Z，使得Y的元素之和和Z的元素之和相等。证明：由于

8、X

9、=10，所以的X非空真子集的数目为1022。另一方面，X的非空真子集的元素之和大于等于1且小于等于855。问题相当于将1022只鸽子放入855个鸽巢。鸽巢原理的推广2[定理3]设有p+p+…+p

10、-n+1只鸽子，有标12n号分别为1,2,…,n的鸽巢，则存在至少一个标号为j的鸽巢至少有p只鸽子，j=1,2,…,nj证明：反证法鸽巢原理的推广2-例题[例6]为了保证能从钱罐里取出8个1元的硬币，或者7个五角的硬币，或者6个1角的硬币，至少应该在钱罐中存放几枚硬币？解：8+7+6-3+1=19。目录•鸽巢原理•Ramsey定理Ramsey定理[定理4]6个人中至少存在3个人相互认识或者相互不认识证明：考虑第一个人A，其余5个人分为两类F=与第一个人相互认识S=与第一个人相互不认识则其中至少有一类有3个成员。若类F有3个成员

11、，则他们或者相互不认识，或者至少有一对P,Q相互认识，后面一种情况时P,Q加上第一个人A就构成3个人相互认识。否则，类S有3个成员，他们或者互相认识，或者至少有一对L,M相互不认识，后面一种情况时L,M加上第一个人A就构成3个人相互不认识。判断树

12、F

13、≥3?YNF中有3个人

14、S

15、≥3,S中有相互不认识？3个人相互认识？YNYN√F中P,Q相√S中L,M相互认识互不认识A,P,Q相A,L,M相互认识互不认识完全图的着色顶点表示人，红边连接相互认识的人，蓝边连接相互不认识的人。6个顶点的完全图K中一定存在一个红色三角形K或63者一

16、个蓝色三角形K，但是5个顶点的完全图K就不具备这35一性质。那么，至少要多少个人才能保证有四个人相互认识或者相互不认识？或者说至少多少个顶点的完全图的边染红蓝两色时一定存在一个红色或者蓝色的完全四边形K？4Ramsey数[定义1]给定一对正整数a,b(a,b≥2)，若存在一个