拉蒙塞数

拉蒙塞问题是组合数学中鸽巢原理的一个推广.

一个最典型的例子:6个人在一起,其中至少3个人互相认识或者不认识.

该问题等价于:对一个凸六边形的每条顶点连线着以蓝色或者红色,则必然至少构成一个红色或者蓝色三角形. 实际上,它可以构成2个同色三角形.

一般的拉蒙赛问题:

一对常数a和b,对应一个整数r,使得r个人中有a个互相认识,或者b个互不认识;或者a个互不认识,b个互相认识.r的最小值即为拉蒙塞数,记为R(a,b).例如R(3,3)=6,R(3,4)=9,R(4,4)=18.

关于拉蒙塞数有如下几个定理:

定理1:R(a,b)=R(b,a),R(a,2)=a.

定理2:对任意整数a,b≥2,R(a,b)是存在的.

定理3:R(a,b)≤R(a,b-1)+R(a-1,b)-1.

定理4:R(a,b)≤C(a+b-2,a-1) (C(n,m)代表从n个数中取m个的组合数).