综上,n的最大值为8.
例5 设n(n?3)是整数, 在一次会议上有n位数学家,每一对数学家只能用会议规定的n种办公语言之一进行交流,对于任意3种不同的办公语言,都存在3位数学家用这3种语言互相交流.求所有可能的n,并证明你的结论.
证:当n位奇数时,结论成立.
原命题等价于将完全图Kn的边染以n种颜色之一,使得对于任意3种颜色,都存在3个顶点,它们相互所连的边为这3种颜色.由于n种颜色有Cn种选取方法,而顶点也有Cn种选取方法,这就意味着每3个顶点相连的边一定被染为确定的3种颜色,不能染为其他情况的颜色,反之亦然.
特别地,对于每一个三角形其3条边为3种不同颜色.
固定颜色S,恰好有Cn?1个三角形,其有一条边为颜色S,而颜色为S的边可以与其他n?22Cnn?1?1?个顶点构成n?2个三角形.于是,有条边被染为颜色S.所以,n不能为偶数. n?22233当n为奇数时,将n个顶点分别记为顶点1,2,,n,n种颜色记为S1,S2,,Sn,连结顶点i,j的边染为颜色St,其中t?i?j(modn).则对于任意3种颜色St1,St2,St3,有同余方程组
?i?j?t1(modn)??j?k?t2(modn). 利用消元法,可得在?1,2,?k?i?t(modn)3?,n?内有唯一的解(i,j,k),且i,j,k互不
相同. 所以,对于任意3种颜色,存在唯一的三角形,其3条边的颜色为这3种颜色.
例6 一个元素都是0或1的方阵称为二进制方阵. 若二进制方阵其主对角线（左上角到右下角的对角线）以上（不包括主对角线）的元素都相同，而且主对角线以下（不包括主对角线）的元素也相同，则称它为一个“好方阵”. 给定正整数m. 证明：存在一个正整数M，使得对任意正整数n?M和给定的n?n二进制方阵An,可选出整数1剟i1?i2??in?mn，从An中删除第
i1,i2,,in?m行和第i1,i2,,in?m列后所得到的二进制方阵Bm是“好方阵”.
证:记An中第i行，第j列的元素为ai,j，Kn表示n阶完全图. 我们对Kn的边按如下方式染色：对于连接顶点i,j(1剟i?jn)的边
⑴ 若ai,j?aj,i?0，则染红色； ⑵ 若ai,j?0,aj,i?1，则染绿色； ⑶ 若ai,j?1,aj,i?0，则染蓝色； ⑷ 若ai,j?aj,i?1，则染白色.
按照上面的染色方式，则一个单色完全子图Km对应于An的一个“好子方阵”.事实上，若
vi1,vi2,,vim,是Km的顶点，我们可以删去指标j?{1,2,3,,n}\\{i1,i2,,im}的n?m行和
n?m列，得到一个“好子方阵”Bm.
我们只需取M使得，对任何n?M，四染色的Kn必定包含一个单色子图Km.根据Ramsey定理，我们可取M?R(m,m,m,m)即可.
例7 现有十个互不相同的非零数.现知它们之中任意两个数的和或积是有理数.证明:每个数的平方都是有理数.
证:考查其中任意6个数.作一个图,在它的6个顶点上分别放上我们的6个数.如果某两个数的和为有理数,就在相应的两个顶点之间连一条蓝边;如果某两个数的积为有理数,就在相应的两个顶点之间连一条红边.由Ramsey定理,此图中存在一个同色三角形.
⑴ 若存在蓝色三角形,则表明存在三个数x,y,z,使得x?y,y?z,z?x都是有理数.因而
(x?y)?(z?x)?(y?z)?2x为有理数,亦即x为有理数.同理可知y和z也都是有理数.此时
我们再来观察其余的任意一个数t.显然,无论由xt的有理性(由已知,所有的数均非0),还是由x?t的有理性,都可以推出t为有理数.所以此时10个数都是有理数.
⑵ 若存在红色三角形,则表明存在三个数x,y,z,使得xy,yz,zx都是有理数.因而
(xy)(zx)2?x为有理数,同理可知y2和z2也都是有理数.如果x,y,z三者中至少有一个为有理yz数,那么只要按照前一种情况进行讨论,即可得知我们的10个数都是有理数.现在设x?ma,其中a为有理数,而m??1.由于xy?may?b是有理数,所以y?bba??ca,其中mamac?m为有理数.再观察其余的任意一个数t,若xt或yt为有理数,则经过与上述类似的讨论,可
2知t?da,其中d为有理数,因而t为有理数.而若x?t与y?t都是有理数,则(x?t)?(y?t)是有理数,但(x?t)?(y?t)?(m?c)a为无理数,矛盾.
综上,我们已证或者每个数都是有理数,或者每个数的平方都是有理数.
练习
1.旅行团一行6人到一个城市观光,此城市开放15个景点,每人可选择若干个景点参观(亦可不选或全选). 求证: 或者必有3人,他们选择的景点各不相同; 或者必有4人,在他们选择的景点中有相同的.
2.设一次至少有5人参加的循环赛的结果满足如下条件:若A胜B,则胜A而负于B的人数不少于胜B而负于A的人数.证明:对任意两人x,y,总有另外两人z,w,使得若x胜y,则y胜z、z胜
w、w胜x.
3．在一个足球联赛里有20支球队.第一轮它们分成10对互相比赛,第二轮也分成10对互相比赛(每支球队两轮比赛的对手不一定不同).求证:在第三轮开赛之前,一定可以找到10支球队,它们两两没有比赛过.
4.某国际社团共有 1978 名成员，他们来自六个国家,用号码1,2,3,,1978给成员编号．证明至
少有一名成员,他的编号是他的某个同胞的 2 倍,或者是两位同胞编号之和．
练习题答案
1.证:用6个点表示6个人,再用15个点表示15个景点.若某人选择了某个景点,则在相应两点之间连一条边,得一偶图.以Ni表示点vi在图中的邻域,它表示第i个人选择的景点的集合(i?1,2,,6).
假设结论不真,则⑴任意三个Ni有公共元,且⑵任意四个Ni无公共元. 由⑴知,对每个Ni,在Njj?i,1剟j?6?中每取两个与Ni的交均非空,故可确定Ni的一
2个元素,用这样的方式可确定C5?10个元素.
2由⑵知,这些元素各不相同,故每个Ni至少有C5?10个不同的元素.对每个i(1剟i6)这样
2做,得到6C5?60个元素.又由⑵知,每个元素至多是3个Ni的公共元,故每个元素至多重复计算
6C52?20个,即至少有20个景点,矛盾. 3次.故其中不同的元素至少有32. 证：由题意知,若A胜B且存在胜B而负于A的人,则必存在胜A而负于B的人.任取两选手x,y且x胜y,分三种情况讨论:
⑴若存在w胜y且有x胜y而负于w,根据条件,存在z胜w而负于y; ⑵若存在z同时负于x,y,则y胜z而x同时胜y,z,同情形⑴;
⑶若不存在有同时胜(或同时负于)x,y的人,在其余3人中,胜x而负于y的至少有2人,设为w,z,且z胜w,则x,y,z,w符合题意.
3. 证:用20个点表示20个球队,第一轮互相赛过的队之间连红线,第二轮互相赛过的队之间连蓝线,则每个点都连有一红一蓝两条边,从而整个图必由一个或若干个偶圈组成.在每个偶圈中可以选出半数定点,任两个不相邻,共选出10支球队,两两未赛过.
4.证: 用顶点表示成员，并加上编号．于是任意两顶点vi,vj编号差大于 0 而小于 1978．如果这个差是第i(1剟i6)国成员的编号，则将(vi,vj)边染上第i种颜色Ci,这样我们就用六种颜色染
了K1978的所有边. 以下首先证明,六色完全图K1978中必定含有单色三角形．
取K1978的任一顶点v,与它关联的 1977 条边分为 6 种颜色，于是其中必有一种颜色的边至少有??1977??1?330条. 不妨设vu1,vu2,??6?,vu330是C1色边．如果K1978中以u1,u2,,u330为顶
点的完全子图K330中含有C1色边(ui,uj)(1剟i,j330),则vuiuj为C1色三角形，命题得证．如
果K330不含C1色边，则K330是五色完全图．从它的顶点u1引出的 329 条边中至少有
?329??1?66条边同色（C1色之外的某色）,不妨设u1u2,u1u3,???5?u2,u3,,u1u67边为C2色．以
67),那么在K1978中就有
,u67为顶点的完全子图K66中如果有C2色边(us,ut)(2剟s,tC2色三角形u1usut,命题得证．若此K66中没有C2色边，则此K66是4色完全图．由K66的顶点u2伸出的65条边,共4种颜色，至少有??65??1?17条边是除C1,C2外的某种颜色．不妨设?4??,u19为顶点的完全子图K17中若含C3(u2,u3),(u2,u4),,(u2,u19)是C3色边．K66中以u3,u4,色边(up,uq)(3剟p,q19),则u2upuq为C3色三角形．否则K17为三色完全图．由例3可知必有
单色三角形．因此六色完全图K1978中必有单色三角形．
其次，设三角形xyz是K1978中的Ci色三角形．其中x?y?z，由染色方法，若a?x?y,
b?y?z,c?x?z,则a,b,c都是第i国成员的编号．显然c?a?b,如果a?b，那么c?2a.
证明完毕．
相关推荐：
loading