抽屉原理的应用

来自计算思维百科
跳转至: 导航搜索
抽屉原理的应用1.jpg

1947年,匈牙利全国数学竞赛有一道这样的试题:“证明:任何六个人中,一定可以找到三个互相认识的人,或者三个互不认识的人。”

解决方案

抽屉原理是组合数学一个非常重要的概念。用一个例子来解释抽屉原理就是有5个苹果,要放到四个抽屉里,那么至少有一个抽屉里面至少放两个苹果。回到上面的数学竞赛题,我们用集合的韦恩图表示人与人之间的关系,之后利用抽屉原理来进行解题。

用A、B、C、D、E、F代表六个人,从中随便找一个,例如A吧,把其余五个人放到“与A认识”和“与A不认识”两个集合里去,根据抽屉原理,至少有一个抽屉里有三个人。不妨假定在“与A认识”的抽屉里有三个人,他们是B、C、D,如下图所示:

抽屉原理的应用2.png

如果B、C、D三人互不认识,那么我们就找到了三个互不认识的人,不认识的人的颜色不一样,如下图所示:

抽屉原理的应用3.png

如果B、C、D三人中有两个互相认识,例如B与C认识,那么,A、B、C就是三个互相认识的人,如下图所示:

抽屉原理的应用4.png

因此,不管哪种情况,本题的结论都是成立的。

运用的计算思维

抽屉原理的应用体现的是一种启发式和抽象的计算思维,因为它是利用前人已经得出的结果来进行解题的。

参考文献

http://news.xinhuanet.com/science/2015-12/18/c_134930275.htm