§0 (综述)
§1 (图的基本概念与应用)
§2
(特殊图)
§3 (染色问题)
§4 (竞赛中的问题)
(本页)
§4 竞赛中的问题
1947 年匈牙利数学竞赛中有这样一个问题，它也是 1953 年美国普特南数学竞赛题，1958 年被收入《美国数学月刊》，编号为 E1332．下面我们来讨论这个问题．
例 14 证明任意六个人中，总有三个人互相认识，或者互相不认识．
证 用六个顶点代表六个人，如果两人互相认识，就在相应顶点间连一条红边，如果互相不认识，就连上一条蓝边．这样，把完全图
的边，染了红色或蓝色．本题断言，在任意一个双色完全图 
中，要么有一个红三角形，有么有一个蓝三角形．
任取一个顶点 
，因为以它为端点的 5 条边染了两种颜色，所以一定有一种颜色的边数 
．不妨设 
，
，
是红边．再看
，
，
，如果这三条边中出现一条红边，例如 
是红边，那么 
是红三角形．不然地话，这三条边全是蓝边，就有了蓝三角形 
（图 12）．证毕．
|
|
|
图 12 |
图 13 |
这个问题中的人数如果减少到 5，结论就不成立（图
13）.由此可见，在完全图 
中，将其边用红、蓝两色任意染色，要么出现红三角形，要么出现蓝三角形，
的最小值应为 6．记为 
．
一般地，对于任意一对自然数 
、
，可以提出这样的问题；在任意 
阶双色完全图中，要么有红色的完全子图 
，有么有蓝色的完全子图 
，问 
的最小值应是多少？这个非负整数 
，被记为 
，称为关于
，
的 Ramsey 数．
确定 Ramsey 数，一般来说是很困难的．迄今为止，对于 
，只得到了七个准确值和一些上、下界（参看第九讲 §3）．
上述 Ramsey 问题还可进一步推广，提出所谓广义 Ramsey 数．
例 15 17 名科学家中，每人都和其它人通信．在他们的通信中只讨论三个题目．而且任意两名科学家通信时，只讨论一个题目．证明，其中至少有三名科学家，他们相互通信时，讨论的是同一个题目．（6 届 IMO 试题）
证 用顶点代表科学家，两人相互通信则连上一条边．若两人在通信中讨论
题，则在此边上染 
色．在这个三色完全图 
中，任取一个顶点，从它“伸出”的 16 条边中，至少有一种颜色 
的边的数目不小于 6．从其中取出 6 条 
色边，如果这些边的另一端点所构成的子图 
中含 
色边，这就构成 
色三角形．否则，
就是双色完全图．由上例克知，其中必有单色三角形．这就是说，有三位科学家在通信中讨论的是同一题目．证毕．
不难证明，如果本例中的 17 减少为 16，结论将不成立．这就是说，任意三色完全图 
要含有单色三角形，
的最小值为 17 ．称为广义 Ramsey 数，记为 
在国际数学竞赛中，经常出现与 Ramsey 数有关的问题．
例 16 某个协会有 10 名成员，其中任意 3 人中总有两人是相互认识的．证明，这协会中必有 4 个人，他们相互认识．（英国数学竞赛题）．
证 用 10 个顶点代表 10 名成员．两人互相认识则在相应顶点上连上一条红边，否则连上一条蓝边，这样得到一个二色完全图
．这个问题用图论语言叙述为：在二色完全图 
中，若没有蓝色的 
，一定有红色的 
．问题的实质就是要证明 
．
由于 Ramsey 数满足性质：
．根据 Ramsey 数的这一性质，立即得出 
．而 
，
．因此 
.(定理 见相关知识
注4）
如果不直接引用上述定理，那么应当如何证明这个问题? 留给读者作为练习．
例 17 1978 年国际奥林匹克数学竞赛巧用 1978 这个数字，出了这样一道试题：某国际社团共有
1978 名成员，他们来自六个国家，用号码 
给成员编号．证明至少有一名成员，他的编号是他的某个同胞的 2 倍，或者是两位同胞编号之和．
证明 (见相关知识 注5)
例 18 两个航空公司为 10 个城市通航，使得任何两个城市间恰有一个公司开设直达航班进行服务，试证至少有一个公司能提供两个互不相交的旅游圈，每圈可游览奇数个城市．（ 31 届 IMO 备选题）
证明 (见相关知识 注6)
例 19 设 
是一正整数且 
是某个集合 
的子集，设
（1）每一个 
恰有 
个元素；
（2）
恰有一个元素；
（3）
中每一个元素属于至少两个子集 
．
问：对于怎样的值 
，可以对 
中的每一个元素贴一张写有 0 或 1 的标签，使得每个 
中恰好有 
个贴上了写有 0 的标签的元素? （ 29 届 IMO，1988）
证明 (见相关知识 注7)
