02 第二章 鸽巢原理和Ramsey定理.pptx

第1页：封面

本章将介绍三个存在性定理：§2.1鸽巢原理的最简单形式§2.2鸽巢原理的加强形式§2.3Ramsey定理

第2页：鸽巢原理的最简单形式

§2.1鸽巢原理的最简单形式鸽巢原理是组合学中最简单、最基本原理也叫抽屉原理(又称为或重叠原理或狄利克雷原理）。

定理2.1.1若把n+1个物体放入n个盒子中，则至少有一个盒子中有2个或更多的物体

第3页：证明(反证法)如果每个盒子中至多

• 证明(反证法)如果每个盒子中至多有一个物体，那么n个盒子中至多有n个物体，而我们共有n+1个物体，矛盾。故定理成立。
• 这个原理只能用来证明某种安排的存在性，而却不能找到具体满足要求的安排

第4页：例2.1.1 共有12个属相

例2.1.1共有12个属相，今有13个人，则必有两人的属相相同几个例子13人中至少有２人是同月出生的。

367人中至少有２人的生日相同。

第5页：例2.1.2 有5双不同的袜子混在一个抽

例2.1.2有5双不同的袜子混在一个抽屉里，我们至少从中选出多少只袜子才能保证找到1双袜子？

设有n对夫妇，问至少要从这2n个人中选出多少人，才能保证能够有一对夫妇被选出？

第6页：解应用定理2.1.

• 解应用定理2.1.1，共有5个盒子，每个盒子对应1双袜子。如果选择5+1=6只袜子分别放到它所属那双袜子的盒子中，则必有两只袜子落入同一个盒子中，即为一双袜子。因此我们至少从中选出6只袜子才能保证找到1双袜子。
• 本例实际上是知道n个盒子，而找n+1个物体的问题。

第7页：补充在边长为2的等边三角形

补充在边长为2的等边三角形中任意放5个点，证明至少有两个点之间的距离不大于1。

1432

第8页：思考题在边长为1的等边三角形内

思考题在边长为1的等边三角形内任意放10个点，证明一定存在两个点，其距离不大于1/3。

第9页：例2.1.3 对任意给定的52个整数

例2.1.3对任意给定的52个整数，证明：其中必存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

第10页：分析：对于这个问题

分析：对于这个问题，显然不能像上个例子那样直接找出n和n+1的对应关系。

分析要证明的结论，根据数论的知识，两个整数的和能被100整除，则它们各自都能被100整除或者它们除以100的余数的和是100；

两个整数的差能被100整除，则它们除以100后的余数相同。

第11页：证明：对于任意一个整数

证明：对于任意一个整数，它除以100的余数显然只能有如下100种情况，0，1，2，3，……，99而现在有任意给定的52个整数，我们需要构造51个盒子，即对这100个余数进行分组，共51组：{0}，{1，99}，{2，98}，{3，97}，……，{49，51}，{50}

第12页：根据定理2.1.

根据定理2.1.1，这52个整数，必有两个整数除以100的余数落入上面51组中的同一组中，若是{0}或{50}则说明它们的和及都能被100整除；

若是剩下的49组的话，因为一组有两个余数，余数相同则它们的差能被100整除，余数不同则它们的和能被100整除。

第13页：例2.1.4 一名象棋大师有11周时间准

例2.1.4一名象棋大师有11周时间准备一场锦标赛，她决定每天至少下一盘棋，为了不能太累一周中下棋的次数不能多于12盘。

证明：她一定在此期间的连续若干天中恰好下棋21盘。

证明:令b1，b2，…，b77分别为这11周中他每天下棋的次数，并作部分和a1=b1,a2=b1+b2,…，a77=b1+b2+…+b77.

第14页：所以有1≤a1<

所以有1≤a1<a2<a3<…<a77≤12×11=132 (2.1.1)考虑数列a1,a2,…，a77，a1+21,a2+21,…，a77+21,它们都在1与132+21=153之间，共有154项，由定理2.1.1知，其中必有两项相等根据题意，有bi≥1(1≤i≤77),且bi+bi+1+…+bi+6≤12(1≤i≤71),

第15页：由（2.1.1）式知a

由（2.1.1）式知a1,a2,…，a77这77项互不相等，从而a1+21,a2+21,…，a77+21这77项也互不相等，所以一定存在1≤i<j≤77，使得aj=ai+21.因此21=aj-ai=(b1+b2+…+bi+bi+1+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+…+bj.这说明从第i+1天到第j天这连续j-i天中，她刚好下了21盘棋。

第16页：某学生有37天的时间准备考试

某学生有37天的时间准备考试。

根据她过去的经验至多需要复习60个小时，但每天至少要复习个小时。

证明无论怎样安排部存在连续的若干天，使得她在这些天里恰好复习了13小时。

思考题：能否将题目中的11周改为其他的数字?

第17页：例2.1.5 将一个矩形分成4行19列的

例2.1.5将一个矩形分成4行19列的网格，每个单元格涂1种颜色，有3种颜色可以选择，证明：无论怎样涂色，其中必有一个由单元格构成的矩形的4个角上的格子被涂上同一种颜色。

证明：首先对每一列而言，因为有4行，但只有3种颜色选择。

根据定理2.1.1，则必有两个单元格的颜色相同。

另外，每列中两个单元格的不同位置组合有6种，这样一列中两个同色单元格的位置组合共有18种情况，

第18页：而现在共有19列

而现在共有19列，根据定理2.1.1，无论怎样涂色，则必有两列与图中的某一列相同，即各自所包含的两个同色单元格的位置相同、颜色相同。

即结论成立。

第19页：鸽巢原理的加强形式

§2.2鸽巢原理的加强形式定理2.2.1 (鸽巢原理的加强形式)

第20页：定理2.2.1 的证明(反证法)对于i＝

定理2.2.1的证明(反证法)对于i＝1，2，…，n，假设第i个盒子里至多含有qi-1个物品，则n个盒子里物品数的总和不超过q1+q2+…+qn-n这与已知条件中的物品总数为(q1+q2+…+qn–n+1)相矛盾。

故假设不真，原结论成立。

第21页：与简单形式的关系上节的鸽巢原

与简单形式的关系上节的鸽巢原理的简单形式是这一原理的特殊情况，即q1= q2= … = qn= 2，有q1+ q2+… +qn－n + 1 = n + 1

第22页：定理2.2.1 的推论推论2.2.

定理2.2.1的推论推论2.2.1若n(r－1) + 1个物品放入n个盒子。

则至少有一个盒子里含有r个或者更多的物品。

证明在定理2.2.1中取q1=q2=…=qn=r即可。

第23页：推论2.2.2 若设有n个正整数m

推论2.2.2若设有n个正整数m1, m2, … ,mn满足下面的不等式(m1+ … +mn)/n≥r,则m1,…,mn中至少有一个数≥r证明由上面的不等式得m1+ … +mn≥(r－1)n+1，由推论2.2.1，存在mi，使得mi≥r。

第24页：推论2.2.3 设m和n都是正整数且m&

推论2.2.3设m和n都是正整数且m>n，若将m个物体放入n个盒子中，则至少有一个盒子中有大于等于个物体表示取天棚运算是大于等于的最小正整数证明：根据的定义有：

第25页：反证法。假定每个盒子里的物体都小

• 反证法。假定每个盒子里的物体都小于个。，则至多是个，那么n个盒子里的物体总数≤n( )<n
• =m，与m个物体矛盾。因此原结论成立。

第26页：例2.2.1 一个袋子里装了10个苹果

例2.2.1一个袋子里装了10个苹果，11个橘子，12个香蕉，至少取出多少个水果才能保证已经取出10个相同种类的水果解根据定推论2.2.1，若将3×(10-1)+1=28个物体放入3个盒子中，则至少有一个盒子中有10个物体。

第27页：例2.2.2 至少有一辆6座以上的汽车

例2.2.2一家汽车租赁公司共有105辆汽车，共有座位600个，证明至少有一辆6座以上的汽车？

证明：根据推论2.2.3，所以至少有一辆6座以上的汽车。

第28页：例2.2.3 设有大小两只圆盘

例2.2.3设有大小两只圆盘，每个都划分成大小相等的200个小扇形。

从大盘上任选100个扇形涂上红色，其余的涂上蓝色，而在小盘的每个小扇形中任意涂上红色或蓝色；

然后把小盘放到大盘上，并使两个盘的圆心重合。

证明在旋转小盘时可以找到某个位置,使得至少有100个小扇形落在同样颜色的大扇形内。

第29页：大圆盘小圆盘

大圆盘小圆盘

第30页：证明(1)任取一个小扇形

证明(1)任取一个小扇形，与大扇形的颜色就构成一颜色组。

共200组颜色组，其中同色的100组。

(2)小扇形共有200个，同色组总数为:100 x 200＝20000组，(3)而小盘与大盘的相对位置有200种，每个位置平均有20000／200＝100组同色组，(4)由定理2.2.1的推论2，必存在着某个位置使得至少有100个小扇形落在同色的大扇形内。

第31页：例2.2.4 必存在长为n+1的递减子序

例2.2.4证明假设不存在长为n+1的递增子序列，我们来证明必存在长为n+1的递减子序列。

令mk表示从ak开始的递增子序列的最大长度,对每个k(k=1,2,…,n2+1)，

第32页：n+1个mk取值相等

n+1个mk取值相等，不妨设为由假设可知1≤mk≤n。

考虑

第33页：n+1个mk取值相等（续）

本页源文件未提取到正文文字，仅含章节眉标。该页位于「n+1个mk取值相等」与「例2.1.6 证明：任意n2+1个实数组」之间，建议对照原课件图片补充本页要点说明。

第34页：例2.1.6 证明：任意n2+1个实数组

例2.1.6证明：任意n2+1个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。

证明：由题意，设Li是从ai开始的递减子序列的最大长度，Mi是从ai开始的递增子序列的最大长度，则对于i从1到n2+1的每个i的取值，都有（Li,Mi）与之对应。

第35页：（1）若ai>

（1）若ai>aj，则ai与从aj开始的最长递减子序列合并，组成的子序列的长度Li≥Lj+1>Lj；

这与Li=Lj矛盾；

反证法。

假设即不存在长度为n+1的递增子序列，也不存在长度为n+1的递减子序列即1≤Li≤n且1≤Mi≤n，其中1≤i≤n2+ 1，由集合论的知识知道集合{(Li,Mi)}的元素数为n2，根据定理2.1.1，必然有（Li,Mi）= (Lj,Mj)（i<j），当然Li=Lj，而且Mi=Mj。

对于序列中的元素ai,aj，分两种情况：

第36页：（2）若ai<

• （2）若ai<aj，则ai与从aj开始的最长递增子序列合并，组成的子序列的长度Mi≥Mj+1>Mj，这又与Mi=Mj矛盾。所以假设1≤Li≤n且1≤Mi≤n不成立。原结论成立。
• 这个例子的结论是1935年由数学家保罗·艾狄胥（Erdös）和乔治·塞克尔斯（Szekeres）首先给出的，它还有更为有趣的表述：n2+1个人肩并肩地站成一排，则总能选除n+1个人，让他们向前迈出一步，所形成新一排的身高是递增或递减的。

第37页：Ramsey定理

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

第38页：例2.3.1 设K6是6个顶点的完全图

例2.3.1设K6是6个顶点的完全图，用红、蓝两色涂色K6的边，则存在一个红色三角形，或存在一个蓝色三角形。

证明：设K6的顶点为v1,v2,…,v6。

对于K6的任何一种涂色方案，由推论2.2.3.，v1关联的边中必有条同色边。

不妨设这三条边为{v1,v2},{v1,v3},{v1,v4}

第39页：若这三边为红色

• 若这三边为红色，当v2,v3,v4之间有一条红边，比如说是{v2,v3},则v1v2v3构成一个红三角形；当v2,v3,v4之间没有红边，则v2v3v4构成一个蓝三角形。
• 若这三边为蓝色时，同理可证。
• 因此，结论成立。

第40页：当使用红

当使用红、蓝两色对一个完全图的边任意涂色的时候，要使得这个完全图中包含一个蓝色的完全p边形或红色的完全q边形，我们把满足这一条件的最小正整数记作R(p, q)。

这些数就是Ramsey数。

第41页：定理2.3.1 设p，q是正整数

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

证明：采用数学归纳法。

设p为任意正整数，q=2。

用红、蓝两色涂色Kp的边，若没有一条红边，则存在一个蓝色的完全p边形；

若有一条红边，则构成一个完全红2边形，因此R(p,2)≤p。

同理可证R(2,q)≤q。

第42页：假设对一切正整数p

• 假设对一切正整数p,q(p+q<p+q)命题为真。令n≥R(p-1,q)+ R(p,q-1)。用红、蓝两色涂色Kn的边，则v1或关联R(p-1,q)条蓝边或关联R(p,q-1)条红边。
• 如若不然，v1至多关联R(p-1,q)-1+ R(p,q-1)-1=R(p-1,q)+ R(p,q-1)+2条边，与n≥R(p-1,q) R(p,q-1)矛盾。
• 若v1关联R(p-1,q)条蓝边，由归纳假设这R(p-1,q)个顶点中或含有一个蓝色的完全p-1边形，或含有一个红色的完全q边形。如为前者，则这个p-1边形加上v1构成一个蓝色的完全p边形，命题为真；如为后者，命题也为真。

第43页：若v1关联R(p

若v1关联R(p,q-1)条红边，同理可证Kn中必含有一个蓝色的完全p边形或红色的完全q边形，从而证明了R(p,q)≤R(p-1,q)+R(p,q-1).因此结论成立。

例2.3.2证明：R(3, 3)= 6证明：由例2.3.1知R(3,3)≤6。

而图2.3.2中的实线代表蓝色的边，虚线代表红色的边，则这个的涂色方案既不包含蓝三角形，也不包含红三角形。

所以R(3,3)>5。

因此R(3,3)=6。

第44页：

本页源文件未提取到正文文字，仅有图片。该页位于「若v1关联R(p」与「定理2.3.2 设p,q是正整数」之间，建议对照原课件图片补充本页要点说明。

第45页：定理2.3.2 设p,q是正整数

定理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)