阳帅奥数课堂系列——抽屉原理（一）

这周的面授和直播都讲了抽屉原理，所以今天晚上到家之后就分享一下抽屉原理呢。上海地区的杯赛考试抽屉原理基本每年都会涉及，不过难度都不是很高，送分题为主。但是除了这些送分题以外，抽屉原理还有很多很有意思的题目，我们慢慢说。...



作者简介：


北京集训队教练，超常班教练，华杯赛优秀教练员，学而思网校首批明星教师，从小学开始学奥数，热爱数学，喜欢分享，人称阳帅。

这周的面授和直播都讲了抽屉原理，所以今天晚上到家之后就分享一下抽屉原理呢。上海地区的杯赛考试抽屉原理基本每年都会涉及，不过难度都不是很高，送分题为主。但是除了这些送分题以外，抽屉原理还有很多很有意思的题目，我们慢慢说。

先说下抽屉原理的表述：m个物体放入n的抽屉，必有一个抽屉中至少有（m÷n＋1）个苹果。（注意我标色的部分哦）

三件事情强调一下：

第一，抽屉原理说的是最多的抽屉中苹果的最小值，也就是最多的抽屉的最不利情况，这点如果可以理解，那么抽屉原理就基本没有概念上的障碍了。

第二，有些比较复杂的题目，找苹果和找抽屉比较困难的，我们可以先把题目的要求按如下的句型造句：______的_______相同，填在前一个横线上的就是苹果，填在后一个横线上的就是抽屉。

第三，抽屉原理说的是一定会发生的事情，所以很多要说明必然性的题目首选抽屉原理。

举个简单的例子，一次中环杯比赛，满分为100 分，参赛学生中，最高分为83 分，最低分为30 分（所有的分数都是整数），一共有8000 个学生参加，那么至少有_____个学生的分数相同。

先造句，这道题目的要求是：学生的分数相同，所以学生是苹果，分数是抽屉，学生有8000人，抽屉有54个，接下来直接用抽屉原理就可以解题了。

再比如，17名同学参加一次考试，考试题是3道判断题（答案只有对错之分），每名同学都在答题纸上依次写上了3道题目的答案。试说明至少有3名同学的答案是一样的。

先造句，这道题目的要求是：同学的答案相同，所以同学是苹果，答案是抽屉，同学有17名，答案有8种（2×2×2＝8种），所以至少有3名同学的答案一样。

这些题目都是抽屉原理的入门级题目，掌握这些基本杯赛无忧，但是我们今天讲一个挺有趣的结论——拉姆塞理论。

六个人参加了一次聚会，任意两人之间要么是互相认识，要么就是互相不认识，那么我们会发现一个有趣的现象，不管六人之间的关系如何，一定会找到这样三个人，他们之间都认识，或者都不认识。

这个结论的证明就可以用到抽屉原理，把六个人简化成六个点，互相认识的之间连红线，不认识的之间连蓝线，如果有三人互相认识，就会出现一个红色三角形，如果三人互相不认识，就会出现一个蓝色三角形，我们只要证明这样的三边同色三角形一定存在就可以啦。

从A出发要连5条线，但是只有两种颜色，所以必有三条线的颜色一样，不妨假设都是红线，为了不让红色三角形那么轻易出现，BC，BD和CD之间都要连上蓝线，但是出现了一个蓝色三角形，这就是所谓躲得了初一，躲不过十五啊，即使在最不利的情况下，也出现同色三角形，所以同色三角形是必然会出现的。

紧接着就是新的问题，为什么一定要六个人呢，五个人一定会存在同色三角形吗？

答案是否定的，比如下面这幅图，就没有以ABCDE为顶点的同色三角形。所以六人是必然出现同色三角形的最小数值，而这样的一个性质就是我们之前说的拉姆塞理论。



那么学了这个理论有个什么用处呢，下面这道题目就是拉姆塞理论的运用。

国王有2012名武士，每两名武士要么互相是朋友，要么互相是敌人，要么互相不认识。每人只同朋友讲话。但不巧的是，每名武士的任意两个朋友都互为敌人，他的任意两个敌人都互为朋友。国王为了让这2012名武士都知道他的一项命令，最少要通知______名武士。

如果你知道拉姆塞理论，这道题目会非常简单，我们规定朋友连红线，敌人连蓝线，因为题目中说每名武士的任意两个朋友都互为敌人，他的任意两个敌人都互为朋友，换句话说就是没有同色三角形，所以每组有关系的武士不能达到6人，最多5人之间可以互相传达消息，所以国王最少要通知403名武士才能传达他的命令，当个国王也不容易啊……

    关注 阳帅说奥数