46 拉姆斯定理.doc

4.6*? 拉姆斯定理 ? 假设平面上有6个点（任意3点不在一直线上），每2个点都有红色或蓝色线段相连，现在我们要证明：存在3个点，由这3个点所构成的三角形的3条边用同一颜色的线段构成。 取一点P0，这时P0与另外5个点相联的5条线段至少有3条是同一颜色的（例如为红色）。设这3条线为P0 P1，P0 P2，P0 P3，如果线段P1 P2，P1 P3，P2 P3中有一条是红色的，例如P1 P2是红色的，则三角形P0 P1 P2就全由红色线段构成，如果P1 P2，P1 P3，P2 P3三条线都是蓝色线段，则P1 P2 P3全由兰色线段构成，这样就证明了平面上6个点中，一定存在3个点，它们所构成的三角形是用同一颜色线段组成。 现在我们要说明：6是保证上述论断的最小正整数。 例如，如果平面上有5个点P1 ,P2 ,P3 ,P4, P5,它们之间的连线的颜色如下： ? 均为红色，????? 均为蓝色 容易看出，这5个点中不存在3个点，他们所构成的三角形的三条边是同一颜色的。 ??? 上述问题如将其一般化，就得到拉姆斯定理。 定理4.9（拉姆斯定理）S是含N个元素的集合，T是S中所有由r个元素构成的子集所组成的集合（即T中有个元素），设T=（即T是两个不相交的子集合的并），这时存在一个数n(p,q,r)（这个数只与p,q,r有关，与集合S无关），只要则S中存在p个元素，这p个元素的所有r个元素的子集合全在A1中，或存在q个元素，这q个元素的所有r个元素的子集合全在A2中。 证明 ?我们对p,q,r采用归纳证明。首先给出3个等式： ?????????????? ?????????? （4-6-1）式的证明如下：如果取集合A1中p-1个元素，集合A2中取q-1个元素，则既不存在p个元素使它的所有1个元素的子集合在A1中，也不存在q个元素，使它的所有1个元素的子集全在A2中，所以。如果，这时集合A1与A2至少有一个不等式成立，所以，或者有p个元素，它的1个元素所构成的子集都在A1中；或者有q个元素，它的1个元素所构成的子集都在A2中。 （4-6-2）式证明如下：对于（4-6-2）式，显然有。若集合A1非空，则自然存在r个元素，它的r子集就在A1中 ；若A1是空集，则q个元素所有r个子集都在A2中。所以 . （4-6-3）式与（4-6-2）式证明类似。 由上面3个等式可以归纳：假设定理对 均正确，现证明：定理对也正确。 如果我们能断定 ????????? 其中???????? 那以，拉姆斯定理显然成立。 设S含有N个元素，，由S中选出一个固定元素，令个元素；令中所有r-1个元素所构成的子集的集合（个元素），同时。 因为至少含有个元素，所以中至少有p1个元素，由它的所有r-1个元素所构成子集的集合完全在中；或者中至少有q1个元素，由它的所有r-1个元素所构成子集的集合完全在中。 现在把加到的每一个元素中，则变为由r个元素所构成子集的集合A1。同理把加到的每一个元素中，则变为由r个元素所构成子集的集合A2。 如果存在p1个元素，它的r-1个元素所构成子集的集合完全在中，因为，则p1中存在q个元素，它的r子集的集合完全在A2中，这时定理成立。否则p1中存在p-1个元素，它的r子集的集合完全在A1中，这时加在p-1个元素中，则这p个元素满足定理要求。 如果存在q1个元素，它的r-1个元素的子集的集合完全在中，类似论断也成立。所以，有 ??? 定理成立。 由定于4.9可以看出，以前所举例子中，n(3,3,2)=6,实际上S是6个点的集合，T是任意两点连线的集合（共个线段）。A1是由红色线段所构成的集合，A2是由蓝色线段所构成的集合。 如果一个多边形内部任意两点的连线也在这个多边形内部，则称此多边形为凸多边形。 定义4.1 ?包含点集M的最小凸图称为点集M的凸包。 任意有限n个点，一定存在一个凸包为一凸多边形，此凸多边形的作法如图4-3所 示。若n个点在一条直线上，则此直线即为凸包；否则画一直线l,使得M中所有点均在l上方，然后向上平移l,遇到M的第一个点A0，右端点为A1；以A1为中心，逆时针旋转l,使其遇到第一个M中的点为止。这时l变为l1,l1上有M中的若干点，其中左端点为A1，设右端点为A2；再以A2为中心逆时针旋转l1，依以上操作程序进行下去，使得最后一个直线遇到A0为止。由于任何k个点所构成的多边形都不能把变为内部的点，所以这时所得凸多边形即为所求。 定理4.10? 有限点的凸包存在而且惟一。 证明? 存在性已如上述作法。设有限点集M的凸包有两个，则 将是包含M的更小的凸包，这与是凸包定义矛盾，所以有限点的凸包是惟一的。 引理4.10(1)? 平面上5个点，其中任意3点不在一条直线上，则一定存在4个点，由此4个点构成一凸多边形。 证明?