论文部分内容阅读
【摘 要】Ramsey问题是组合数学、离散数学、图论、算法研究领域的著名难题和热门课题，Ramsey理论在上述各数学分支中所处的地位举足轻重。文中简单介绍了Ramsey问题的相关理论，并把一些定理进行了推广；讨论了Ramsey理论的具体应用，分类介绍了数学竞赛中Ramsey问题的基本理论以及处理这些问题的一些基本技巧，同时也探讨了Ramsey数在通信中的应用 。
【关键词】Ramsey型问题；Ramsey数；竞赛数学；通信
1 Ramsey型问题及相关背景
Ramsey理论起始于20世纪20年代末，30年代初，最初由英国数学家F.P.Ramsey提出，其思想已日益被人们理解、接受并得到了一定的发展。对于Ramsey数的研究，以取得初步成果。下面就介绍一下关于Ramsey的理论知识及其性质定理以及Ramsey型问题在数学竟赛和通信方面中的应用。
2 Ramsey型问题的基本定理与性质
2.1 Ramsey定理
对任意给定的自然数及都存在时，对的所有元集的任一种染色（每一个元集染上种颜色中的一种），必有一个有一个元子集，它的所有元集是同一种颜色的。
2.2 若干推论
对Ramsey型问题有以下结论：
2.2.1 对6个顶点的完全图的边用红蓝二色任意着色，结果至少有两个同色的三角形。
2.2.2 10个人中若不是3个人互不相识，则必有4个人互相认识。同样10个人中若不是3个人互相认识，则必有4个人互不相识。其实此结论只要有9个人就够了。问题相当于9个顶点的完全图用红，蓝二色任意着色，必然是红色三角形和蓝色的完全四边形两者必有其一。类似地有红色完全四边形和蓝色边的三角形两者必有其一[2].
2.2.3 18个人至少有4个人或互相认识或互相不认识。这个问题相当于对18个顶点的完全图的边用红，蓝二色任意着色，则至少存在一个同色完全四边形[2].
以上推论可写成
2.3 Ramsey数的一些简单性质
Ramsey数具有一些特殊性质，如下所示：
2.3.1 . （对称性）
2.3.2 .（个顶点的完全图的边用红蓝两色染色或存在一个个顶点着红（蓝）色的完全图，或至少存在一条着蓝（红）色的边）。
2.3.3 对任意正整数存在
2.3.4 对任意正整数，有.
推论：对所有整数和 ，若和是偶数，则. （详见参考文献[1]）。
2.3.5 对于有.
3 Ramsey数的推广
定理3.1 对任意的正整数有
定理3.2 对任意的正整数有
。
定理3.3 对任意正整数有
定理3.4 若则.
4 应用
4.1 竞赛数学中的Ramsey型问题的分类解法与分析
在各国的竞赛中，往往会出现一些有关图的染色的试题。其原因是，图的染色问题有着深刻的背景，即来自著名的Ramsey理论。这就促使辅导数学竞赛的一些文章和读物总要拿出一定的篇幅来讲述图论的基本知识、Ramsey理论的基本概念、定理以及处理图的染色问题的方法和技巧。本文拟谈在数学竞赛中所遇到的有关Ramsey型问题的基本理论以及处理这类图的染色问题的一些基本技巧。
4.1.1 构造法
例1：给定空间的9个点，其中任何4点都不共面，在每一对点之间都连有一条线段，这些线段可染为蓝色或红色，也可不染色。试求出最小的值使得将其中任意条线段中的每一条任意地染为红蓝二色之一，在这条线段的集合中都必然包含有一个各边同色的三角形。
解：本题的背景是以下两个熟知的结果
引理1：对五阶完全图的边作二染色，存在一种染色方法使得染色后的图中没有单色边三角形。如图1.1所示，虚实线分别表示两种颜色的边。这时图中无单色边三角形。
图1.1 图1.2
引理2：对边作二染色的六阶完全图中一定存在单色边三角形。
为了求解本题，借助于引理1。我们构造一个9点图，如图1.2所示。这个图的顶点编号为1，2，…，9其中边染成红（实线）。顶点1与2之间没有边连接，类似地，圆圈内的顶点3与4，顶点5与6，顶点7与8均没有边相连，显然，这个图中没有单色边三角形，容易算出，这个图中的边数是所以，另一方面，染色的线段至少有33条，则由于线段共条，不染色的线段至多3条。
若点引出不染色的线段，则去掉及所引出的线段，若剩下的图中还有引出不染色的线段，则去掉及所引出的线段，依此进行，由于不染色的线段至多有3条，所以至多去掉3个顶点（及从它们引出的线段），这时至少剩下6个点。每两点之间的连线染上红色或蓝色，由引理2知，必存在一个同色三角形。
综上所述，的最小值为33。
4.1.2 抽屉原理
处理Ramsey型问题的基本方法是抽屉原理。
例2：有17位科学家，其中每一人和其他所有人通信。他们通信中只讨论3个题目，且每两个科学家之間只讨论一个题目。求证：至少有3个科学家相互之间讨论同一个题目。
证明：将科学家对应于点，两科学家之间讨论的题目对应两点连线的颜色。原题转化为：17个点两两连边，边用红，蓝，白之一染色，每边一色，证明必存在同色三角形。
点引出的16条边，根据抽屉原理，其中至少有6条同色。不妨设6条边同为红色，另一端点分别为再考虑这6个点两两连线的颜色。如果其中有一条为红色则存在红色三角形，如果其中任一边都不是红色，那么只能是蓝白两色。于是由引出的五条边至少有3条同色。同蓝色，考虑的三边，若有一边为蓝，则存在蓝色三角形，若任一边都是白色，则为白色三角形。命题成立。 4.1.3 算两次
对于同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的。这种方式称为算两次。算两次，不仅可以建立左右两边关系不大明显的恒等式，也可以建立不等式或其它关系。在反证法中，算两次又可用来构造矛盾。
例3：将的每边染成红色或蓝色，证明必有两个同色三角形（这两个三角形的颜色不一定相同）。
证：考虑自同一点引出两条边。如果它们颜色相同，就称它们组成一个“同色角”。设点引出条红边，条蓝边。则点引出的同色角共个。
易知上式在或3时取得最小值4。因此中至少有4个同色角。另一方面，每个同色三角形中有3个同色角。每个边不全同色的三角形中只有1个同色角。设同色三角形有个，则不同色的三角形有个。
因此，同色角共综合以上两个方面，得从而
对于竞赛数学中的Ramsey型问题的分类解法与分析以上列举了三种，其实方法还有很多，比如枚举法、一般化，数学归纳法等等。
4.2 Ramsey数在通信中的应用
在通信过程中，由于信号通道上的噪声等意外因素的干扰，某些字母被认为“极易混同”。为了避免这种混同所带来的危害，人们首先想到，能否从现有的字母表中挑选出尽可能多的一组字母，保证在任何通信环境下，该组中的任意两个字母都不会混同，或者说，其可能混同的概率几乎处处为零。采取的一种方法就是：设字母集合以为顶点集构造一个完全图对中的两个不同顶点若二者容易混同，则连一条红线，否则，连一条蓝线。问题就变为在着色的上寻找最大的蓝色完全子图。该子图的顶点集就是要找的那些不易混同的字母子集。
实际上，从26个字母中剔除容易混同的字母后，往往所剩无几。一个自然的想法就是用字母串来表示一个符号，然后再从中寻找最大的非混符号集。例如，可用长度为2的字母串来构造符号集，那么，字母串与可能混同的充要条件是下面三个条件中的一个成立：
（1）可能与混同，且与也可能混同；
（2）=，且与可能混同；
（3）=，且与可能混同；
为了借助边2着色的完全图来寻找最大非混符号集，可设符号集，然后以为顶点集构造一个完全图 （即图与的正规积，记为），点与之间连一条红边当且仅当下面三个条件中的一个成立：
（1）和，且和在中連的都是红边；
（2）=，和在中以红边相连；
（3）=，与在中以红边相连；
除此之外的边都为蓝色边。
关心的是上最大蓝色完全子图的顶点集对此，有如下的结论：
记中顶点个数为则其中，Ramsey数中的满足
在信息高速发展的今天，Ramsey数已渗透到生活的各个方面，它的应用相当广泛，这里介绍了Ramsey数在通信中的应用。随着社会的发展，它的用途将越来越细。
5 结论与展望
本文阐述了Ramsey型问题的基本定理与性质。讨论了Ramsey理论的具体应用，分类讨论了数学竞赛中Ramsey问题的基本理论以及处理这些问题的一些基本技巧，同时也讨论了Ramsey数在通信中的应用。重点讲述了Ramsey型问题在数学竟赛方面中的应用。竞赛题既有非常抽象、非常专业化的题目，又有非常实际、非常生活化的题目。而无论哪类题目，Ramsey型问题都能满足竞赛题对内容的现代化、陈述的趣味以及技巧的独创的要求，而成为严肃数学和趣味数学的结合体“非常规题”。
参考文献：
[1] 孙淑玲，许胤龙.组合数学引论[M].合肥：中国科学技术大学出版社，2005.
[2] 姜建国，岳建国.组合数学[M].西安：西安电子科技大学出版社，2003.
[3] Richard-A.Brualdi.Introductory Combinatorics（Third dition）[M]. 北京：机械工业出版社出版，2003.
[4] 杨振生.组合数学及其算法[M].合肥：中国科技大学出版社，2003.
[5] F.P.Ramsey.On a Problem of Formal Logic[P]. Proceedings of the London Mathematical Society，30（1930）：264-286.
[6] 董莉，佩捷著.最新世界著名数学智力趣题300个[M].哈尔滨：哈尔滨出版社，1995.
【关键词】Ramsey型问题；Ramsey数；竞赛数学；通信
1 Ramsey型问题及相关背景
Ramsey理论起始于20世纪20年代末，30年代初，最初由英国数学家F.P.Ramsey提出，其思想已日益被人们理解、接受并得到了一定的发展。对于Ramsey数的研究，以取得初步成果。下面就介绍一下关于Ramsey的理论知识及其性质定理以及Ramsey型问题在数学竟赛和通信方面中的应用。
2 Ramsey型问题的基本定理与性质
2.1 Ramsey定理
对任意给定的自然数及都存在时，对的所有元集的任一种染色（每一个元集染上种颜色中的一种），必有一个有一个元子集，它的所有元集是同一种颜色的。
2.2 若干推论
对Ramsey型问题有以下结论：
2.2.1 对6个顶点的完全图的边用红蓝二色任意着色，结果至少有两个同色的三角形。
2.2.2 10个人中若不是3个人互不相识，则必有4个人互相认识。同样10个人中若不是3个人互相认识，则必有4个人互不相识。其实此结论只要有9个人就够了。问题相当于9个顶点的完全图用红，蓝二色任意着色，必然是红色三角形和蓝色的完全四边形两者必有其一。类似地有红色完全四边形和蓝色边的三角形两者必有其一[2].
2.2.3 18个人至少有4个人或互相认识或互相不认识。这个问题相当于对18个顶点的完全图的边用红，蓝二色任意着色，则至少存在一个同色完全四边形[2].
以上推论可写成
2.3 Ramsey数的一些简单性质
Ramsey数具有一些特殊性质，如下所示：
2.3.1 . （对称性）
2.3.2 .（个顶点的完全图的边用红蓝两色染色或存在一个个顶点着红（蓝）色的完全图，或至少存在一条着蓝（红）色的边）。
2.3.3 对任意正整数存在
2.3.4 对任意正整数，有.
推论：对所有整数和 ，若和是偶数，则. （详见参考文献[1]）。
2.3.5 对于有.
3 Ramsey数的推广
定理3.1 对任意的正整数有
定理3.2 对任意的正整数有
。
定理3.3 对任意正整数有
定理3.4 若则.
4 应用
4.1 竞赛数学中的Ramsey型问题的分类解法与分析
在各国的竞赛中，往往会出现一些有关图的染色的试题。其原因是，图的染色问题有着深刻的背景，即来自著名的Ramsey理论。这就促使辅导数学竞赛的一些文章和读物总要拿出一定的篇幅来讲述图论的基本知识、Ramsey理论的基本概念、定理以及处理图的染色问题的方法和技巧。本文拟谈在数学竞赛中所遇到的有关Ramsey型问题的基本理论以及处理这类图的染色问题的一些基本技巧。
4.1.1 构造法
例1：给定空间的9个点，其中任何4点都不共面，在每一对点之间都连有一条线段，这些线段可染为蓝色或红色，也可不染色。试求出最小的值使得将其中任意条线段中的每一条任意地染为红蓝二色之一，在这条线段的集合中都必然包含有一个各边同色的三角形。
解：本题的背景是以下两个熟知的结果
引理1：对五阶完全图的边作二染色，存在一种染色方法使得染色后的图中没有单色边三角形。如图1.1所示，虚实线分别表示两种颜色的边。这时图中无单色边三角形。
图1.1 图1.2
引理2：对边作二染色的六阶完全图中一定存在单色边三角形。
为了求解本题，借助于引理1。我们构造一个9点图，如图1.2所示。这个图的顶点编号为1，2，…，9其中边染成红（实线）。顶点1与2之间没有边连接，类似地，圆圈内的顶点3与4，顶点5与6，顶点7与8均没有边相连，显然，这个图中没有单色边三角形，容易算出，这个图中的边数是所以，另一方面，染色的线段至少有33条，则由于线段共条，不染色的线段至多3条。
若点引出不染色的线段，则去掉及所引出的线段，若剩下的图中还有引出不染色的线段，则去掉及所引出的线段，依此进行，由于不染色的线段至多有3条，所以至多去掉3个顶点（及从它们引出的线段），这时至少剩下6个点。每两点之间的连线染上红色或蓝色，由引理2知，必存在一个同色三角形。
综上所述，的最小值为33。
4.1.2 抽屉原理
处理Ramsey型问题的基本方法是抽屉原理。
例2：有17位科学家，其中每一人和其他所有人通信。他们通信中只讨论3个题目，且每两个科学家之間只讨论一个题目。求证：至少有3个科学家相互之间讨论同一个题目。
证明：将科学家对应于点，两科学家之间讨论的题目对应两点连线的颜色。原题转化为：17个点两两连边，边用红，蓝，白之一染色，每边一色，证明必存在同色三角形。
点引出的16条边，根据抽屉原理，其中至少有6条同色。不妨设6条边同为红色，另一端点分别为再考虑这6个点两两连线的颜色。如果其中有一条为红色则存在红色三角形，如果其中任一边都不是红色，那么只能是蓝白两色。于是由引出的五条边至少有3条同色。同蓝色，考虑的三边，若有一边为蓝，则存在蓝色三角形，若任一边都是白色，则为白色三角形。命题成立。 4.1.3 算两次
对于同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的。这种方式称为算两次。算两次，不仅可以建立左右两边关系不大明显的恒等式，也可以建立不等式或其它关系。在反证法中，算两次又可用来构造矛盾。
例3：将的每边染成红色或蓝色，证明必有两个同色三角形（这两个三角形的颜色不一定相同）。
证：考虑自同一点引出两条边。如果它们颜色相同，就称它们组成一个“同色角”。设点引出条红边，条蓝边。则点引出的同色角共个。
易知上式在或3时取得最小值4。因此中至少有4个同色角。另一方面，每个同色三角形中有3个同色角。每个边不全同色的三角形中只有1个同色角。设同色三角形有个，则不同色的三角形有个。
因此，同色角共综合以上两个方面，得从而
对于竞赛数学中的Ramsey型问题的分类解法与分析以上列举了三种，其实方法还有很多，比如枚举法、一般化，数学归纳法等等。
4.2 Ramsey数在通信中的应用
在通信过程中，由于信号通道上的噪声等意外因素的干扰，某些字母被认为“极易混同”。为了避免这种混同所带来的危害，人们首先想到，能否从现有的字母表中挑选出尽可能多的一组字母，保证在任何通信环境下，该组中的任意两个字母都不会混同，或者说，其可能混同的概率几乎处处为零。采取的一种方法就是：设字母集合以为顶点集构造一个完全图对中的两个不同顶点若二者容易混同，则连一条红线，否则，连一条蓝线。问题就变为在着色的上寻找最大的蓝色完全子图。该子图的顶点集就是要找的那些不易混同的字母子集。
实际上，从26个字母中剔除容易混同的字母后，往往所剩无几。一个自然的想法就是用字母串来表示一个符号，然后再从中寻找最大的非混符号集。例如，可用长度为2的字母串来构造符号集，那么，字母串与可能混同的充要条件是下面三个条件中的一个成立：
（1）可能与混同，且与也可能混同；
（2）=，且与可能混同；
（3）=，且与可能混同；
为了借助边2着色的完全图来寻找最大非混符号集，可设符号集，然后以为顶点集构造一个完全图 （即图与的正规积，记为），点与之间连一条红边当且仅当下面三个条件中的一个成立：
（1）和，且和在中連的都是红边；
（2）=，和在中以红边相连；
（3）=，与在中以红边相连；
除此之外的边都为蓝色边。
关心的是上最大蓝色完全子图的顶点集对此，有如下的结论：
记中顶点个数为则其中，Ramsey数中的满足
在信息高速发展的今天，Ramsey数已渗透到生活的各个方面，它的应用相当广泛，这里介绍了Ramsey数在通信中的应用。随着社会的发展，它的用途将越来越细。
5 结论与展望
本文阐述了Ramsey型问题的基本定理与性质。讨论了Ramsey理论的具体应用，分类讨论了数学竞赛中Ramsey问题的基本理论以及处理这些问题的一些基本技巧，同时也讨论了Ramsey数在通信中的应用。重点讲述了Ramsey型问题在数学竟赛方面中的应用。竞赛题既有非常抽象、非常专业化的题目，又有非常实际、非常生活化的题目。而无论哪类题目，Ramsey型问题都能满足竞赛题对内容的现代化、陈述的趣味以及技巧的独创的要求，而成为严肃数学和趣味数学的结合体“非常规题”。
参考文献：
[1] 孙淑玲，许胤龙.组合数学引论[M].合肥：中国科学技术大学出版社，2005.
[2] 姜建国，岳建国.组合数学[M].西安：西安电子科技大学出版社，2003.
[3] Richard-A.Brualdi.Introductory Combinatorics（Third dition）[M]. 北京：机械工业出版社出版，2003.
[4] 杨振生.组合数学及其算法[M].合肥：中国科技大学出版社，2003.
[5] F.P.Ramsey.On a Problem of Formal Logic[P]. Proceedings of the London Mathematical Society，30（1930）：264-286.
[6] 董莉，佩捷著.最新世界著名数学智力趣题300个[M].哈尔滨：哈尔滨出版社，1995.