拉蒙塞數

拉蒙塞問題是組合數學中鴿巢原理的一個推廣.
一個最典型的例子: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個的組合數).