组合数学讲义 5章 抽屉原理

《组合数学》 第五章 抽屉原理和Ramsey理论

第五章 抽屉原理和Ramsey理论

抽屉原理又称鸽巢原理或重叠原理，是组合数学中两大基本原理之一，是一个极其初等而又应用较广的数学原理。其道理并无深奥之处，且正确性也很明显。但若能灵活运用，便可能得到一些意料不到的结果。

抽屉原理要解决的是存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。

1930年英国逻辑学家F. P. Ramsey将这个简单原理作了深刻推广，即Ramsey定理，也被称为广义抽屉原理。它是一个重要的组合定理，有许多应用。

5.1 抽屉原理

（一）基本形式

定理5.1.1 （基本形式）将n＋1个物品放入n个抽屉，则至少有一个抽屉中的物品数不少于两个。

证 反证之。将抽屉编号为：1,2, ?,n，设第i个抽屉放有qi个物品，则 q1?q2???qn?n?1 但若定理结论不成立，即qi从而有

?1，即有q1?q2???qn≤n，

n?1?q1?q2???qn?n

矛盾。

例 5.1.1 一年365天，今有366人，那么，其中至少有两人在同一天过生日。

注：与概率的区别：抽屉原理讲的是所给出的结论是必然成立的，即100%成立。而概率反映的是不确定性现象发

1/37

《组合数学》 第五章 抽屉原理和Ramsey理论

生的可能性问题，不讨论100%成立的确定性概率问题。 生日悖论：随机选出n个人，则其中至少有二人同一天出生的概率为

Pn?A?=1?P365365nn

特例：P23?A?=50.73%，P100?A?=99.99997%

例 5.1.2 箱子中放有10双手套，从中随意取出11只，则至少有两只是完整配对的。

（二）推广形式

定理5.1.2 （推广形式）将q1?q2???qn?n?1个物品放入n个抽屉，则下列事件至少有一个成立：即第i个抽屉的物品数不少于qi个。

（证）反证。不然，设第i个抽屉的物品数小于qi（i＝1,2, ?,n）(即该抽屉最多有qi?1个物品)，则有

?qi?n?1＝物品总数≤??qi?1???qi?n

i?1i?1i?1nnn与假设矛盾。

q1?q2???qn?n?1=

?q1（三）特例

?1???q2?1?????qn?1??1

推论1 将n(r－1)＋1个物品放入n个抽屉，则至少有一个抽屉中物品个数不少于r个。

推论2 将m个物品放入n个抽屉，则至少有一个抽屉中物品个数不少于??m?1??m＝?1??n??n?2/37

?其中?x?表示取x?个。?《组合数学》 第五章 抽屉原理和Ramsey理论

的整数部分，?x?表示不小于x的最小整数。

推论3 若n个正整数qi?i?1,2,?n?满足

q1?q2???qnn?r?1

则至少存在一个qi，满足qi?r。

（四）例

例 5.1.3 有 n位代表参加会议，若每位代表至少认识另外一个代表，则会议上至少有两人认识的人数相同。 (证) 设某代表认识的人数为k个，则k??1,2,?,n?1?（视为n－1个抽屉）。而会议上有n个代表，故每位代表认识的人数共为n个数（视为n个物品）。那么，由基本定理，结论成立。

例 5.1.4 任意一群人中，必有两人有相同数目的朋友。 (证) 设有n个人?n?2?，分三种情形讨论： (1) 每人都有朋友，由例5.1.3即知结论成立； (2) 只有一人无朋友，余下的n－1人都有朋友，由(1)知此n－1人中必有两人有相同数目的朋友；

(3) 有两人或两人以上的人无朋友，则朋友数为零的人已经有两个了，同样满足条件。

例 5.1.5 边长为2的正方形内有5个点，其中至少有两点，距离不超过2。

(证) 首先制造抽屉：将原正方形各对边中点相连，构成4个边长为1的小正方形（见图5.1.1(a)），视为抽屉。其次，

3/37

《组合数学》 第五章 抽屉原理和Ramsey理论

由基本原理，至少有一个小正方形里点数不少于2。最后，从几何角度可以看出，同一小正方形内的两点的距离不超过小正方形的对角线之长度2，证毕。

* * *

*

* * * * * * 图5.1.1 抽屉的选择

注意，如果抽屉选择不当，可能于事无益。如图5.1.1(b)，将正方形分为4个直角边长为2的等腰直角三角形是达不到目的的。

习题1、2

5.2 应用

§5.2.1 抽屉原理的应用

例 5.2.1 任意三个整数，必有两个之和为偶数（其差也为偶数）。 (证) 制造两个抽屉：“奇数”和“偶数”，3个数放入两个抽屉，必有一个抽屉中至少有两个数，由整数求和的奇、偶性质即知此二数之和必为偶数。 同理可知，二者之差也为偶数。

任给3个整数，其中必存在两个整数，其和能被2整除。提另法一证明．记这3数为a1,a2,a3，令ri?ai mod 2 4/37

《组合数学》 第五章 抽屉原理和Ramsey理论

则ri=0，1（i=1，2，3）。 以0，1为两个抽屉，3个ai为物品，以ri决定将ai放入哪个抽屉。 由抽屉原理，某个抽屉中至少有两个ai，其除以2的余数相同。那么，此2数即满足要求。 问题：任给n个整数，其中必存在3个整数，其和能被3整除。问n最小应为多少？ 常规思路：n=7（证明思路同上） 但7不是最少数字，最小的n=5。 证明．记这5个数为a1,3 a2,?,令ri?ai mod a5，扩展则ri=0，1，2（i=1，2，?，5）。那么（构造抽屉和物品的方法同上） ① 若有某3个ri相同，则对应的3个ai满足条件。 ② 否则，5个ri中最多有2个ri相同（即每个抽屉中最多放2个物品），此时，每个抽屉不空。那么，从每个抽屉选一整数，该3个数即满足条件。 任给n个整数，其中必存在k个整数，其和能被k整除。问n最小应为多少？ 一般提例如：k=2 时，n=3； 法 k=3 时，n=5（而非7）； k=4 时，n=7（而非13）； ① 一维数轴上有3个整数点（坐标为整数的点），则几何角其中必存在两个点xi和xj，其几何中心度(便于?xi?xj?2也是一个整点。 推广到多维空 间) ② 一维数轴上有5个整数点，则其中必存在3个点5/37

《组合数学》 第五章 抽屉原理和Ramsey理论

xi、xj和xk，其几何中心xi?xj?xk??3也是一个整点。 更一t维空间有n个整点，其中必存在k个整点，其几何般的中心也是整点。 问题 例1 t=1，问题同上。k=2，n=3，k=3，n=5 t=k=2，n=5 例2 证．设5个平面点为?xi,yi?（i=1,2,3,4,5） t=2，k=3，n=9 t任意，k=2，n=2+1 t例3 例4

例 5.2.2 从1,2,?,2n中任取n＋1个数，其中至少有一对数，一个是另一个的倍数。

（证）设所取的n＋1个数为a1,a2, ?,an+1，并 （1）表示 ai?2iri??i?0?，i＝1,2, ?,n＋1且ri为奇数。

（2）设置抽屉与物品：1~2n之间只有n个奇数（抽屉），故由抽屉原理知此n＋1个ri中至少有两个是相同的。设为 rj ＝ rk ＝r，即aj?2?j?rj?2?jr，ak?2?krk?2?kr，

显然有：要么ajak，要么akaj。

（3）说明：这里已是最好的“可能结果”，即针对各种条件，稍加放松，则结论不一定成立。

? 改为取n个数，只要取n＋1,n＋2, ?,2n这n个数，显然不满足结论。 ? 改为在1,2,?,2n+1中选n＋1个数，则结论也不一定成立。例如n=5，选6，7，8，9，10，11

6/37

《组合数学》 第五章 抽屉原理和Ramsey理论

例 5.2.3 设a1,a2, ?,am为任意m个正整数，则其中必存在若干个相继的数，其和是m的倍数。即至少存在正整数j和k(1≤j＜k≤m)，使得m能整除

k?ai=aj?aj?1???ak。

i?ji(证) 构造数列 si?s1

?ajj?1=a1?a2???ai ，则

ri?si mod m ，则0≤ri＜m （i＝1,2,?,m）

若有某 rk＝0，则msk，问题得证。否则，所有ri≠0，由抽屉原理知，至少存在j

km ，从而有msk?sj??ai。

i?j?1本题构造“抽屉”与“物品”的技巧在于并不直接针对正整数ai，而是构造出适合利用抽屉原理的n个数ri。为了构造ri，间接利用了si以达到目的。其中的抽屉是取关于模m的剩余类：0,1, ?,m－1，并且在应用抽屉原理时分为两步走。第一步先将ri分为两大类，即0与非0（或看作两个大抽屉）；第二步，针对非0情形，分为m－1种情况（或看作m－1个小抽屉）。

例 5.2.4 设正整数序列a1,a2,?,a25满足ai+1＋ ai+2＋?＋ ai+5≤6，i＝0,1,?20。 试证明至少存在正整数j、k（1≤j＜k≤25），使得aj＋aj+1＋?＋ak＝19。

i(证) 构造序列 si?s1

?ajj?1=a1?a2???ai ，则

若有某个sk＝19，那么，问题得证（j＝1）。

7/37

《组合数学》 第五章 抽屉原理和Ramsey理论

否则，所有si≠19。 令集合

A＝{ s1，s2，?，s25，s1＋19，s2＋19，?，s25＋19} 且有 20≤s1＋19＜s2＋19＜?＜s25＋19≤49。

集合A中共有50个数，每个数的取值在1到49之间，由抽屉原理，其中必有两数相同。又知i≠j时，si≠sj，从而 si＋19≠sj＋19 。 所以，相等的两项必为 sk ＝ sj＋19（显然k>j）， 即

k19?sk?sj??ai=aj?1?aj?2???ak ，证毕。

i?j?1

问题一般化：设正整数序列a1,a2,?,amn满足ai+1＋ ai+2＋?＋ ai+n≤p，i＝0,1,?,n(m－1)。 若要求存在正整数j

分析：令 si ＝a1＋a2＋?＋ai， i＝0,1,?,nm 设 A＝{ s1，s2，?, smn，s1＋q，s2＋q , ?，smn＋q } 且有 1≤s1< s2< ?< smn， q< s1＋q< s2＋q

要用抽屉原理，A中元素个数必须大于A中最大数smn＋q，即mp＋q<2mn，或mp?q?2mn?1，由此得结论：q≤m(2n－p)－1 。

本例中，m＝n＝5，p＝6，q＝19 。 若选m＝n＝10，p＝16，则q≤39 。

变异：一学生用37天共60小时复习功课，第i天复习ai小时（ai为正整数），则无论如何安排，总存在相继若干天，这些天的复习时数之和恰为13 。

此问题实际上隐含着m＝1，n＝37，p＝60，q＝13 。 这时，问题可以描述为：m个正整数a1,a2,?,am满足

8/37

《组合数学》 第五章 抽屉原理和Ramsey理论

a1＋a2＋?＋am＝n，要存在1?j?k?m，使得aj＋ aj+1＋?＋ ak ＝q，必须有q≤2m－n－1（这只要在一般问题中取m＝1，n＝m，p＝n即可）。

例 5.2.5 将65个正整数1,2, ?,65随意分为4组，那么，至少有一组，该组中最少存在一个数，是同组中某两数之和或另一数的两倍。

(证) 用反证法。设任何一组数中的每一个数，它既不等于同组中另外两数之和，也不等于同组中另一数的两倍。即任何一组数中的的任意两个数之差总不在这个组中。 由抽屉原理，四组中至少有一组（称为A组），其中至少有17个数。从中取17个：记为a1,a2,?,a17，不妨设a17最大。令

ai?1??a17?ai， i＝1,2, ?,16

显然1?ai?1??65 。 由假设知ai?1??A（否则，就有某个ak和ak满足a17=ak+aj），所以，该16个数必在另外三组B、C、D中。

再由抽屉原理知，B、C、D三组中至少有一组（设为B组），至少含有6个ai1。只取其中6个，记为b1,b2,?,b6，

?1?同理可设b6最大，并令bi?b6?bi（i＝1,2,?,5）。同样有

??1?bi?1??65 且bi?1??1??B。而且由假设知

bi?b6?bi?a17?aj??a17?ak??ak?aj?A

??（aj?ak）

故该5个数一定在C或D中。

又由抽屉原理，设C组中至少有3个bi?1?，取其中3个记为c1?c2?c3 。 同理可证d1?c3?c2,d2?c3?c1（d1?d2，1?di?65）也不在A、B、C三组中，故必在D组中。进一步，可证得e?d2?d1?c2?c1不在A、B、C、D中，且满足1?e?65 。 这说明从1到65的这65

9/37

《组合数学》 第五章 抽屉原理和Ramsey理论

个整数中有一个不在A、B、C、D这4组的任何一组中，与题设矛盾。

例 5.2.6 由mn＋1个不同实数构成的序列?aii?1,2,?mn?1?中必存在一个(m＋1)项的递增子序列或(n＋1)项的递减子序列。

(证) 某个序列?bnn?1,2,?n?是递增的，是指该序列满足：b1?b2???bn；反之，若b1?b2???bn，则称其是递减的。

针对每一个ai，以ai为首项，向后寻找递增子序列，最长子序列的项数（即长度）记为t（i＝1,2, ?,mn＋1），则1≤ti≤mn＋1 (若ai之后每一项都比ai小，则t ＝1；若ai之后有一项aj比ai大，则t＝2；若aj之后还有一项ak比aj大，则t＝3 ?)。

iii例如，对m=2，n=4序列

4 5 2 9 3 1 8 6 7

t1=4，t2=3，t3=4，t4=1，t5=3，t6=3，t7=1，t8=2，t9=1

若有某个 ti≥m＋1，则问题得证。

否则，所有 1≤ti≤m，由推论1，至少有n＋1个ti相等，设

tk?tk???tk12n?1， 且1?k1?k2???kn?1?mn?1

那么，必有ak1?ak2???akn?1，从而构成n＋1个实数的递减子序列。事实上，若ki?kj时，有aki?akj，则以aki为首项的最长子序列比以akj为首项的最长子序列多一项，即tki?tkj，矛盾。

本例已达到最好的可能结果。

特例：m＝n 。 实际的问题为：不同高度的n2?1个人

10/37

《组合数学》 第五章 抽屉原理和Ramsey理论

5.4 Ramsey数

问题：对于给定的正整数p、q≥2，是否存在一个最小的正整数r，具有下述性质：对完全图Kn的每条边涂以颜色C1或C2，当n≥r时，在Kn中必含有一个完全子图Kp，其所有边涂的是颜色C1（即同色Kp），或含有一个完全子图Kq，其所有边涂的是颜色C2（即同色Kq）。

定义5.4.1 满足上述条件的数r称为Ramsey数，记为r(p,q;2)，简记为r(p, q)。

已经知道r(3,3)＝6，r(3,4)＝9。 例5.4.1 证明r(4,4)＝18。

（证）设v0,v1,v2,?,v17是完全图K18的顶点，现考察K18中从v0出发的17条线段，它们分成了红、蓝两类，由抽屉原理可知：至少有9条是同色的，不妨设它们为红色（蓝色）。进一步再来考察这9条红色（蓝色）线段里，异于v0的9个端点所构成的K9，其中一定会出现一个红色（蓝色）K3，或一个蓝色（红色）K4。若是前者，则这个红色（蓝色）K3的三个顶点和v0一起便构成一个红色（蓝色）K4，若是后者，则本身已存在蓝色（红色）K4。 由此可知，r(4,4)≤18，下面证r(4,4)>17，从而有r(4,4)＝18。

在一个圆周上画出共17个等分点，将其依次编号为v0,v1,?,v16，把整数1，2，?，16分成两组

X组：1，2，4，8，9，13，15，16 Y组：3，5，6，7，10，11，12，14

选取正整数a，b?0?a,b?16?，按以下规则进行涂色： 当a?b?X时，边vavb涂红色（或蓝色）； 当a?b?Y时，边vavb涂蓝色（或红色）

21/37

《组合数学》 第五章 抽屉原理和Ramsey理论

这样涂得的K17不会出现同色的K4。

由上述涂色规则可以看出，两点连线为红色的顶点对有：?v0,v1?，?v0,v2?，?v0,v4?，?v0,v16?，?v1,v3?，?v1,v2?，?，

?v1,v5?，?，?v1,v16?，?，?v15,v16?；连线为蓝色的顶点对有：?v0,v3?，?v0,v5?，?v0,v6?，?，?v0,v14?，?v1,v4?，?v1,v6?，?v1,v7?，?，?v1,v15?，?，?v11,v14?。读者可

以按此方法画出具有两种颜色的边的K17，并观察结果。 §5.4.1 Ramsey数的性质

对于任意的正整数p、q，要求出r(p,q)，是相当困难的。这里只给出Ramsey数的有关性质和上、下界的估计。

定理5.4.1 Ramsey数r(1,q;2)具有以下性质

(1) r(p,q)＝ r(q,p); (2) r(1,q)＝ r(p,1)＝1; （3）r(2,q)＝q, r(p,2)＝p;

（4）当p、q≥2时，有r(p,q)≤r(p,q-1)＋ r(p-1,q)，若r(p,q-1)和 r(p-1,q)都为偶数，不等式严格成立。 （证）（1）、（2）显然成立。

对于Kq，当所有边都涂的是同一种颜色时，Kq本身即满足条件。否则，至少有两点的连线涂的是另一色，那么，该两点构成一个同色的K。所以r(2,q)＝q成立，同理可证r(p,2)＝p也成立。即性质（3）成立。

2至于性质（4），令n＝r(p,q-1)＋r(p-1,q)，可以证明，对Kn的边用红、蓝着色后，其中必存在红色的Kp或蓝色的

Kq，从而可知n≥r(p, q)。原因如下：

任取Kn的一个顶点v，由抽屉原理，v与其余n－1个顶点的连线中，要么红边不少于r(p-1, q)，要么蓝边不少于r(p, q-1)。若是前者，即由v出发与之以红边相连的顶点有r?p?1,q?个，按照r?p?1,q?的定义，这r?p?1,q?个顶

22/37

《组合数学》 第五章 抽屉原理和Ramsey理论

点本身所构成的完全图Kr?p?1,q?即可导出蓝色的Kq或红色的Kp?1，而Kp?1再加上顶点v即可构成红色的Kp。若为

后者，同理由与v以蓝边相连的r(p,q－1)个点再加上顶点v所构成的完全图Kr?p,q?1??1中就存在红色Kp或蓝色Kq。 若r(p,q－1)和 r(p－1,q)都为偶数，令m＝r(p,q－1)＋ r(p－1,q)－1（m为奇数），可以证明在涂过色的K上存在红色的Kp或蓝色的Kq，从而可知r(p,q) ≤m

m首先证明：在Km上存在一点vk，以它为端点的红边一定是偶数条。若不然，设cj是以顶点vj为端点的全部红边数

m（j＝1,2,?，m），所有cj为奇数，从而知c?c?cj?1j为奇数，

而Km上的全部红边数＝≠整数，矛盾（注意，按顶点统

2计时，将Km的每条红边都计数两次）。 其次，以前述的vk为端点的m－1＝ r(p,q－1)＋ r(p－1,q)－2条边中，或者至少有r(p－1,q)条红边，或者至少有r(p,q－1)条蓝边。再仿照前边的证明，即得结论。

例5.4.2 证明r(3,5)＝14。 （证）由性质（4）知

r?3,5??r?2,5??r?3,4?=5＋9=14

对于K13，可以给出一种边2染色方案，其中既无红色边组成的K3，又无蓝色边组成的K5。方法是将圆周等分为13等份，视各等分点为K3的顶点，从某点开始对各点依此编号为0，1，?，12，当i与k满足

k?i?1,i?5,i?8,i?12,mod13，

?i?0,1,?,12?

时，第i点与第k点之间连红色线，否则连蓝色线。

23/37

《组合数学》 第五章 抽屉原理和Ramsey理论

定理5.4.2 关于Ramsey数的上、下界，有如下结论：

?1（1）r?p,q??Cp； p?q?2p（2）r?p,p??22，p?2；

p????2????2??O?1???r?p,q??t?Cp（3）p22??e?????p????ln?lnp?lnp， t为常数。

?1（4）r?p,q??q?Cp?， s为常数。 p?q?2s22（5）

c1q?lnq?2?r?3,q??c2qlnq， c1、c2为常数。

关于Ramsey数的部分结果，可见表5.4.1。

表5.4.1 p、q较小时的r(p,q) q p 3 4 5 6 7 8 9 10 3 6 4 9 18 5 14 25 42/55 6 18 34/36 57/94 102/169 7 23 41/59 126/586 8 28/29 ?/88 282/? 9 36 10 39/44 ?/124 ?/168 374/? 458/? 注：？表示目前还无结果

§5.4.2 Ramsey数的推广

将染色问题可以推广到一般情形：

（1） 增加颜色数：设有n个顶点的平面完全图Kn，用

24/37

《组合数学》 第五章 抽屉原理和Ramsey理论

m种颜色c1,c2,?,cm随意给Kn的边着色。那么，对于给定的正整数p1, p2, ?pm,（pi≥2，i＝1,2, ?,m），是否存在最小的正整数r?p1,p2,?,pm;2?，当n≥r?p1,p2,?,pm;2?时，在Kn中一定含有某个Kpi，它的所有边都为颜色ci 。

（2） 扩大空间的维数：设Kn为k维空间上的具有n个顶点的完全图，对同样的问题，是否也存在r?p1,p2,?,pm;2?。

比较：两种情况的不同点是Kn的顶点所在的空间的维数不同，共同点是颜色增多，且最关键之处是被染色的对象都是Kn中任意两点所连接成的边。

用第三种方式描述：设集合A??e1,e2,?,en?，令S??XX?A,X?2?（以A上所有二元子集为元素构成的集合），再用?S1,S2,?,Sm?表示S的一个m分拆，即

S1?S2???Sm?S，

SiSj??，

Si可空

n≥r?p1,p2,?,pm;2?时，对集合A中的元素，下面结论至少有一个成立：在A中存在pi?1?i,j?m,i?j?。那么，当

个元素，其全部二元子集都属于Si?i?1,2,?,m?。

相应于（1）、（2）的结论称作“两点结合的Ramsey定理”，或称“边的Ramsey定理”。 （3） 增多子集X中元素的个数：“设集合A??e1,e2,?,en?，令S??XX?A,X?t，t?1?（以A上所有t元子集为元素构成的集合），再用?S1,S2,?,Sm?表示S的一个m分拆，即S1?S2???Sm?S，SiSj??，S可空?1?i,j?m,i?j?。那么，总存在一个仅依赖于p1,p2,?,pm和t的正整数N，当n≥N时，对集合A中的元素，下面结论至少有一个成立：在A中存在pi个元素，其全部t元子集都属于Si?i?1,2,?,m?”。称这样的数N为广义Ramsey数，记为r?p1,p2,?,pm;t?。

i几何角度：当k=t=3，m=2时，考虑空间中任何四点都

25/37

《组合数学》 第五章 抽屉原理和Ramsey理论

不共面的n个点组成的集合A，将每三个点构成的三角形涂以红色或蓝色，当任意给定了正整数p,q?p,q?3?后，只要点数n超过某一个有限数时，则下列两种情况必有一种成立：或者存在p个点，其中每三个点构成的三角形均为红色（蓝色）；或者存在q个点，其中每三个点构成的三角形均为蓝色（红色）。 这就是“三点结合的Ramsey定理”，或者称作“三角形Ramsey定理”。相应的染色问题叫做面2-染色问题。 一般情形，首先将完全图的概念加以推广，设k维空间有n个点，从中任取t个点及其相邻的边结合在一起，称作t级边（当t=2时就是普通的边， t=3时是三角形， t=4是四面体）。把这n个点与其所有的t级边组成的图叫做t

t级完全图，记做Kn，又称作超图。假如用m种颜色c1,c2,?,cm去涂染这n个点中全部的t级边，每个t级边任意涂染一色，从而将这些t级边划分成了m类，当任意给定一组正整数

tp1,p2,?,pm后，则在n充分大时，t级完全图Kn中一定含有一个t级完全子图Kqt，其所有t级边的颜色都是同一色

ici?1?i?m?。满足上述条件的最小的整整数

n，就是广义

Ramsey数r?p1,p2,?,pm;t?。

特例，当t=1时，就是§6.1所述的抽屉原理，其中 （1） r?p,q;1??p?q?1——两个抽屉时的抽屉原理；（2） r?p1,p2,?,pm;1??p1?p2???pm?n?1——推广形式的抽屉原理；

??r?2,2,?,2;1??n?1——抽屉原理的基本形式。 （3） ???????n个??其次还有，r?p,t;t??p?p?t?，r?t,q;t??q?q?t?。 定理5.4.3 广义Ramsey数r?p1,p2,?,pm;k?是存在的。

26/37

《组合数学》 第五章 抽屉原理和Ramsey理论

例5.4.3 有17位学者，每人给其它人各写一封信，讨论三个问题中的某一个问题，且两人之间互相通信讨论的是同一个问题。证明至少有三位学者，他们之间通信讨论的是同一问题（1964年第六届国际奥林匹克数学比赛题目）。 此问题等价于对K的每条边涂以红、蓝、黄三色之一（即边3－着色），其中必存在同色K 。由此可知，r?3,3,3;2??17。

173（证）设v0,v1,?,v16为给定的17个点，任取一点，不妨设为v0，将v0与其余16点连接成16条边，当用三色涂

?16?染时，由抽屉原理知至少有???6条边被涂上同一颜色，

?3?不妨设为v0vi ?i?1,2,?,6?且这六条边同为红色。考虑由v1,v2,?,v6组成的完全图K6，分两种情况讨论： 如果在这个K6中有一条边，比如v1v2也是红色，则?v0v1v2就是一个同色三角形。否则在这个K6中没有红色的边，于是只能涂上蓝色或黄色，则归结为K6的边2－染色问题，已知其必存在同色的三角形。

例5.4.4 证明r?3,3,3;2??16，即对于K6，存在一种边3－着色方案，使得其中不存在同色K。

3（证）考虑由二进制码组成的集合G＝{0000，0001，0010，?，1111}，定义各元素的加法为二进制的逐位异或运算，即0+0＝0，1+0＝0+1＝1，1+1＝0。则集合G对于加法构成一个16阶交换群（参见§6.1），其中0000为单位元。把G中除去单位元的15个元素分成三个不封闭的子集G1,G2,G3，即使得每个子集里的任意两个元素相加所得的元素不在同一子集里：

G1??1100,0011,1001,1110,1000?， G2??1010,0101,0110,1101,0100?， G3??0001,0010,0111,1011,1111?

然后，建立G与K16的一个映射，使K16的顶点和群G的元

27/37

《组合数学》 第五章 抽屉原理和Ramsey理论

素一一对应起来，并按下面方法用三种颜色对边染色： 取x,y?G，且x?y。那么，当x?y?Gi时，则用颜色i染顶点x与y的连线；当x?Gi时亦用颜色i把0000与x用一线段连接（请读者自己完成）。 按照上述方法构造的经过边3-染色的K16中不存在同色的K。由此可知r?3,3,3;2??16，从而最后可确定r?3,3,3;2??17。

3

???若令R?m?=r3,3,?,3;2m?，即R?m?表示用????????m个3?m种颜色涂染

完全图的边存在同色三角形的最少点数，目前已知R?1??3，

R?2??6，R?3??17。那么，一般的R?m?应该为何？准确地求

出R?m?是困难的，目前只知道关于它的上界的递归不等式。

定理5.4.4 R?m?≤m?R?m?1??1??2

令n=m?R?m?1??1??2，对完全图Kn的边用m种颜色染色后，从其顶点v1引出m?R?m?1??1??1条边，由抽屉原理知，至少有R?m?1?条边为同一种颜色，不妨设边

v1v3v1v2，

，??，v1vR?m?1??1均为红色，v2,v3,?,vR?m?1??1,构成一个

完全图KR?m?1?，则有

（1） KR?m?1?中有一条红色边，比如v2v3，则?v1v2v3就

是一个同色三角形；

（2） KR?m?1?中没有红色的边，则它的边只有m?1种不

同的颜色，根据R?m?1?的定义，这个KR?m?1?中有一个同色三角形。

28/37

《组合数学》 第五章 抽屉原理和Ramsey理论

推论1 R?m?≤m!??1??11!?12!???1???1 m!?（证）用数学归纳法： 当m设m?1时，R?1??3??1?1??1，不等式成立； ?k?1时命题成立，即

??111?1?????R?k?1?≤?k?1?!????1 ??1!2!k?1!??当m?k时，由定理5.4.4知

R?k??k?R?k?1??1??2

由归纳假设得

??111?1?????R?k?≤k??k?1?!????2?k?1?!?1!2!?

即

?11111??R?k??k!?1??????????2?k?1?!k!k!?1!2!?

=k!??1??11!?12!???1???1 k!?由归纳法原理，命题成立。 推论2 R?m?≤?m!e??1。 （证）因为

m!e=m!?k?0?1k!=m!?k?0m+m!?k!1?1k?m?1k!=am?bm

而当m≥1时

29/37

《组合数学》 第五章 抽屉原理和Ramsey理论

?bm=m!?k?m?1?1k!=

1m?11???m?1??m?2???m?i?

i?2?1＜==

1m?11???m?i?1??m?i?

i?2?m?12m?1??i?211?????

?m?i?1m?i?≤1

由此可见：

bm只是m!e的小数部分，所以

?m!e?=m!?1???11!?12!???1?? m!?再由推论1便可得到推论2。 推论3 R?m?≤3m!。

（证）用归纳法：当m=1时，R?1??3?3?1!，结论成立； 设m?k?1时命题成立，即

R?k?1?≤3?k?1?!

当m?k≥2时，由定理5.4.4知

R?k??k?R?k?1??1??2

由归纳假设得

R?k?≤k?3?k?1?!?1??2=3k!??k?2?≤3k!

由归纳法原理，命题成立。

30/37

本文来源：https://www.bwwdw.com/article/xhh.html