不可思议的鸽笼原理

德国狄利克雷在1834年成为第一位叙述鸽笼原理的数学家，只不过当时他所用的是“抽屉原理”这个字眼。第一位在专业数学期刊中使用鸽笼原理这个词汇的，则是1940年的罗宾森(RaphaelM.Robinson)。简单来讲，如果在m个鸽笼中住着n只鸽子，只要n>m的话我们就可以确定起码有一个鸽笼里住着不止一只鸽子。

上述的简单立论运用范围广泛，从计算机数据压缩到无限元素集合之间能否形成一对-对应关系的问题皆属之。鸽笼原理在概率上的一般化推论是:将n 只鸽子随机放入m个鸽笼的概率都是1/m，则至少有一个鸽笼住着一只以上鸽子的概率是1-m!/[(m-n)!m”。以下让我们看几个鸽笼原理非直观式的运用例子。

根据鸽笼原理，纽约市里面起码有两个人的头发数量一模一样。在这个例子中，我们可以把头发数量比作鸽笼，把纽约市人口数比作鸽子;纽约市住了800万以上的人，而每个人头上的头发数量远远不到100万，因此，一定起码有两个人头上的头发数量是一模一样的。

再来一个例子。在一张一美元大小纸张的表面上随意涂上红、蓝两色，无论涂色方式有多么错综复杂，我们是否一定可以找到一对距离整整一英吋的两个点是相同颜色的?画一个边长一英吋的等边三角形就能回答这个问题。我们在此设定红、蓝两色为两个鸽笼，三角形的三个预点是三只鸽子，则三个顶点中一定起码有两个顶点的颜色是一样的，这就证明我们一定可以找出相距整整一英时、颜色相同的两个点。