北京奥数 抽屉原理（1）

前面几天和同学们介绍了平面几何求面积的相关问题，

相关解题方法都大同小异，相关例题只是起到“师傅领进门”

的效果，能够修行到什么程度，还需要看同学们自身的努力程度

一定要多练习，做到胸有成竹。

今天要和同学们介绍一类新的问题——抽屉问题

解答抽屉问题的关键在于找到最差的情况

也叫做“最不利原则”

首先我们来看一下抽屉问题中的一个金典问题——拉姆塞问题

证明：世界上任意六个人中，一定有三个人互相认识

或者互不认识

解析：我们知道，任意两个人之间的状态只有两种：认识和不认识

不可能存在既认识又不认识的两个人存在，除非暂时性失忆

那么我们将六个人分别进行编号：1、2、3、4、5、6

那么1号与2、3、4、5、6的状态也最多只有两种：认识、不认识

我们假设认识则两者之间的连线为黑色，不认识则两者之间的连线为

白色，考虑最差的情况即1和2连线为黑色、1和3连线为白色，

即可得出至少有三个人连线为白色，即不认识

或者至少有三个人连线为黑色，即认识

其他情况同理可得。

那么拉姆塞问题就证明完成了，其他情况自己在本子上证明，下期再见！！！