抽屉原理(鸽巢原理)和拉姆齐定理

1、抽屉原理:把十个苹果放到九个抽屉,那么至少有一个抽屉里的苹果不少于两个。

2、拉姆齐定理:在总人数大于等于6的时候,一定存在这样的三个人,他们相互认识,或者相互不认识。

其中,证明如下:
不妨假设有6个人,设有A、B、C、D、E、F。
红线连接两个人,表示他们认识,用蓝线连接两个人,表示他们不认识
根据鸽巢原理可以知道,A至少认识三个人,或者至少不认识三个人。
不妨设A认识三个人B、C、D,也就是AB、AC、AD是红线。
抽屉原理(鸽巢原理)和拉姆齐定理

1、如果BC、BD、CD任意一条也是红线,那么会形成一个红色三角形,表示三个人相互认识。
2、如果BC、BD、CD都不是红线,即都是蓝线,那么B、C、D会形成一个蓝色三角形,表示这三个人相互不认识。

综上得证。