拉蒙塞问题是组合数学中鸽巢原理的一个推广.
一个最典型的例子: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个的组合数).
