1、中国余数定理是说明：一个整数 x与两个互质的整数 n,m相除，可以得到两种表示结果：x = pm + a 和 x = qn+ b ， 其中 a 和 b 分别是小于除数 m 和 n的 余数，例如：19 = 92+1 = 35+4； 其中 m=2； n=5是 互质而选择 n=4的话： 19 = 44+3=82+2=pm+2只有一种表示形式。1Ramsey问题可以看成是鸽巢原理的推广下面举例说明 Ramsey问题。例 1 6 个人中至少存在人相互认识或者相互不认识。证 :这个问题与 K6的边着色存在同色三角形等价。假定用红蓝两种颜色对完全图 K6着色 。第二章 鸽巢原理2.2 Ramsey定理2设
2、K6的顶点集为 v1 , v2 , , v6 ， dr(v)表示与顶点 v 关联的红色边的条数， db(v)表示与 v 关联的蓝色边的条数。在 K6 中，有：dr(v) db(v)， 由鸽巢原理将 5条边分配成2种颜色，至少有：(5-1)/2+1=条边同色。现将证明过程用判断树表示如下：v1v6v5 v4v3v23dr(v1)3?db(v1)3 设 (v1v2) (v1v3) (v1v4)为红边设 (v1v2) (v1v3) (v1v4)为蓝边 v2v3v4是红 ? v2v3v4是蓝 ?设 ( v2v3 )是蓝边设 ( v2v3 )是红边 v1v2v3是蓝 v1v2v3是红 YNNNYYv6v
3、5 v4v3v2v14定理说明：六点够成的完全图中，用红、兰两种颜色对边涂色，总能得到一个红三角形或者是一个兰三角形，注意 : 6是染两色时出现同色三角形的最小点数。若取 5点，则可举出反例 (如 P22图 2.2 所示 )，图中就没有同色的三角形，即可使 K5不存在同色三角形。 v5v4 v3v2v15例 2 9人行，或有 3人互相认识，或有 4人互 不认识。例 3 18人行，定有 4人或互相认识，或互不认识。上述问题，可用图论的方法予以解决。 即将n个人视为 n个顶点（设 n个顶点中任意 3点不共线），并构造 n点完全图 Kn， 对 Kn中的边染6以红、蓝两种颜色， 2人相识染红色，不相识
4、染蓝色， 最后求证图中必存在同色三角形，或同色完全四边形。例 2证明第一步：若将 K9染色，则其中必存在一点，从这点到其余 8点的边中，同色者不等于 3。 设若不然， K9中每个点与其余 8个顶点所成之边都是恰染 3条红色（或蓝色）， 现从每个端点统计各7点引出的这些红色（或蓝色）边的总数应是39=27， 但这是不可能的， 因每条边关联两个端点，对这种统计， 所有点引出的红色（或蓝色）连边的总数应为偶数。结论是，必存在一点， 从该点到其余各点的边染红色（或蓝色）者一定大于 3或小于 3。第二步：（ 1）设从 v1向其余 8点引出的边中，染红色者多于 3条，即至少有 4条，不妨设为:8(v1,
5、v2), (v1, v3), (v1, v4), (v1, v5)。 再看 v2, v3, v4 , v5所成完全图 K4， 若有一红色边，则其两端点连同 v1已构成红色三角形 , 否则全为蓝色，这时 v2, v3, v4 , v5就构成一蓝色完全四 边形。（ 2）设从 v1向其余 8点引出的边中，红色边少于 3条，即至多有 2条，这时从 v1引出的蓝色边至少会有 6条 ,不妨设为 (v1, v2), (v1, v3), , (v1, v7) 。9再看 v1, v2, v3, v4, v5, v6所成完全图 K6， 由定理 1， 其中若有红色三角形，则结论已真；若 K6中有蓝色三角形，则其 3个顶点连同 v1即构成一蓝色完全四边形 ，结论亦真。 由（ 1）及（ 2）， 定理得证。 注意：当 n 9时，定理 2自然成立。但当 n=8时，可举出反例 (如下图所示 )，即可使其既无同色三角形，又无同色完全四边形。10
