按照上面的染色方式，则一个单色完全子图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.
证明完毕．