6第六章--鸽笼原理和Ramsey定理

第六章鸽笼原理和Ramsey定理§1鸽笼定理Pigeonholeprinciple鸽笼原理的简单形式11(1,2,,),,||||.niiiniiAAAinAAAA定理设是有限集，且则1||1,(1,2,,),,(1,||2.inikiAAnAAinAAkknA定理（鸽笼原理的简单形式）设是有限集，且则必有正整数）使得例证明：如果在一个边长为1的等边三角形内任取5个点，则必有2个点，他们的距离不大于1/2.12341,2,,211.nnn例证明：在中任取个不同的数，则个数中必有两个数，其中一个数是另一个数的倍数2,21sn其中非负，是奇数，且{|,(21)2,}iAssAsi是非负整数1212,,,0l).nkklaaanklknaaan例设是个正整数，求证：必存在整数和（，使得能被整除1(1,2,,),{|mod,01}iijjisainAssinin令1211,,,2(11).nliikaaanklklnan例设数列各项之和为，且每项均是正整数，求证：必有正整数和，使得1(1,2,,1),{|mod,01}kkiiibaknAbbinin令例某棋手参加一次为期11周共77天的集训，已知他每天至少下一盘棋，而每周至多下12盘，证明在集训期间必有连续的若干天，在这几天里该棋手共下21盘棋。鸽笼原理的一般形式1(2)(1,2,,)1(1)||1.niiikAmmAAinAAmkknAn定理（鸽笼原理的一般形式）设是元集，且，则必有正整数，使得:53例证明从任意给出的个整数中必能选出个数，他们的和能被3整除.{|mod3,02}iAaaii111.mnmn例证明：任一个项数为的实数列必有一个项数为的递增子数列，或者有一个项数为的递减子数列例分别将大小两个圆盘分成200个全等的扇形，任选100个大扇形，将其余100个大扇形涂成蓝色，把200个小扇形中的每一个任意地涂成红色和蓝色，然后将小圆盘放在大圆盘上面，使得两个圆盘的中心重合，证明：必可适当地转动小圆盘，使得至少有100个小扇形都落在同样颜色的大扇形内.鸽笼原理的加强形式12121,,,||1,(1,2,,),(1),||.nninikkiAqqqAqqqnAAinAAkknAq定理（鸽笼原理的加强形式）设是有限集，都是正整数，如果且则必有正整数使得1||(1)1,(1,2,,)(1)||.iniiAAmnAAinAAkknAm推论设是有限集，且，则必有正整数，1212,,,(1)1,(1),||,.nnkkqqqqqqmnkknAmqm推论设都是正整数，如果则必有正整数使得即101,2,,1017.例随意地给正十边形的个顶点编上号码，求证：必有一个顶点，该顶点及与之相邻的两个顶点的号码之和不小于§2Ramsey定理(2).nnnrrKKrK定义用种颜色去图的边，每条边涂一种颜色，所得的每条边都涂了颜色的称为着色完全图的边着色62K定理着色必含有一个单色三角形6推论任意个人中必有3个人，他们彼此握过手或者彼此没有握过手.62.nnK推论当时，着色中必有一个单色三角形Ramsey定理(,),(,)(,)nababrabnrabKKKrabRamsey定理对任意给定的两个正整数和，如果存在最小的正整数使得当时，对任意进行2-着色，则必有单色的或，称为Ramsey数.部分Ramsey数R(a,b)234567892345678923456789369141823283649182551425618723828936作业•1，2，5，9，14，18