《“鸽子洞原理”的16种运用》转载自译言网。以下为正文：
数学逻辑能够推理一些极其细微的现象。你可知道，每一个极小的瞬间，在世界的某个角落不会有风的存在？这是真的，证据来自不动点原理的一种运用，一年前我曾探讨过它。
本文继续在感恩节讨论数学的细小运用的传统。这16个有趣的话题包括以下不连续的主题，生日，理发，WordPress Blog，以及鸡尾酒会。让人感觉不可思议的是，结果都产生于对将鸽子塞入鸽子洞现象的基本理解。
鸽子洞原理
鸽子洞原理是分析数学组合的有力工具。但是其概念简单，可以通过以下具体的问题加以阐述。
设想要将3只鸽子装进2个鸽子洞里。可以做到吗？回答是肯定的，但存在一个定式，即无论鸽子是怎样装入的，必然有一个鸽子洞要装入2个以上的鸽子。
这一推理方式可用于更广泛的数字。鸽子洞原理认为，如果有超过n只鸽子要放入n个鸽子洞中，有一些鸽子洞就要装进2个以上的鸽子。尽管这一原理显而易见，但其意义却让人吃惊。原因是，这一原理证明了某一具体现象的存在（或不可能）。
鸽子洞原理（更为广义）
另外一种版本的鸽子洞原理迟早也能碰到。那就是“对任何非空有限实数集合来说，最大值最起码是平均值”（感谢迪斯杰特拉教授）
可别让这些数学术语把你吓倒。其概念可以单凭直觉感知。具体到具体的数字集合，平均值就是“中间“值，因此最大的数字应尽可能的大。这一版本听起来（与前一版本）不同，但从数学意义上来说，是一致的。让我们看看它们之间的联系吧。
重新设想将鸽子装入鸽子洞，再设想一下平均值。如果我们有超过n个鸽子，有n个鸽子洞，那么平均值（鸽子／鸽子洞）比1大。这表示最大值应比1大。换句话说，存在超过一个鸽子对应于一个鸽子洞的一个值。实际上，以上两个版本说的是一回事。
现在我们对鸽子洞原理有了较好的理解，现在来是怎么运用的。以难易程度分类，我喜欢的有16种：
容易（1－8）
1.在美国宪法中每27个连续的英语单词，至少有2个单词将以同一个英文字母开头。
假如27个单词能以26个不同的英文字母中的一个开头（类同于将27个”鸽子“”放入26个鸽子洞中），根据鸽子洞原理，必有2个单词以同一字母为首。
2.在纽约市，有两个不是秃头的人长着数量一样多的头发。
人类头上的头发约有几十万根，最多可达50万。与这一数字相对比，纽约有几百万人，因此，至少有2个人有数量一样多的头发。
3.读这篇博客的所有读者中，有2个或2个以上的人生日相同。
包括润年的2月29日在内，全年366天中的某一天都可以成为某人的生日。这篇博客有超过367名读者，因此必有2名读者生日相同。
4.感恩节的时候，如果将吃掉的火鸡的重量精确到百万分之一磅，那么，有2只或更多的火鸡重量相同。
火鸡的体重约为15磅，记载中体重最重的是37磅，如果我们能将所有火鸡的体重都称量精确到百万分之一磅，那么我们有3700万不同的火鸡体重值。与之对比，大纸头有4600万火鸡在感恩节被吃掉。根据鸽子洞原理，其中的2只火鸡体重最接近于精确到百万分之一磅的数值。
5.至少有2个WordPress.com的博客每年有相同的评论数。
在写本文时，已经开通了475万WordPress.com博客。假如一个博客每年一百万条评论数是一个可靠的最大值。据此，由鸽子洞原理表明，至少有2个WordPress.com博客每年的评论数相同。
6.一场封闭入场的卡内基音乐厅表演观众中，有2个人的姓和名有相同的首字母。
每个首字母都是26个英文字母中的一个，意味着有26x 2＝276种姓和名的首字母组合情况。卡内基音乐大厅约有2800个座位。因此，在对外表演的音乐会上，有2个观众必有相同的姓和名首字母。
7.通常一副扑克有52张牌，如果你从其中拿出5张，至少有2张的花色相同。
五张纸牌可以分属于四种花色中的种。根据鸽子洞原理，2张或以上的纸牌必有相同的花色。
8.如果你有10只白袜子和10只黑袜子，你要随机的挑选袜子，你只需挑出3只袜子，就可能找到一双颜色相同的。
这3只袜子的颜色是2种中的一种。由鸽子洞原理，至少有2只有相同的颜色。
解答这一问题的另一种方法是，一只袜子一只袜子的思考。如果第二只袜子与第一只袜子颜色相配，我们就成功了。否则，我们在再挑选出一只袜子，我们原先挑出的袜子已经有了两种不同的颜色，第三只袜子的颜色必是其中的一种，这样，我们就挑选出了一双颜色相同的袜子。
较难（9－14）
9.新年在纽约时代广场，有超过820个人生日相同。
现在鸽子洞原理的第二个版本“最大值最小也是平均值。”
出席新年广场庆祝活动的人数约为30万，分属于366个生日。每个生日平均有300,000／366＝819.7人。最大值最小也必须是平均值，因此，最少有820人的生日相同。
10.假设某所大学有6，000名美国学生，50个州中每个州至少有1名学生。那么，至少有120名学生来自同一个州。
再一次，我们引用第二个版本“最大值最小也是平均值。”
每个州平均有6000／50＝120学生。最大值最小也是平均值，因此至少有120名学生来自同一个州。
11.如果从1到8的整数中选5个数字，那么其中有两个数字的和必然是9.
每个数字都可以与另外一个数字加起来等于9.从1到8的8个数字中，有四组这样的组合：1＋8,2＋7,3＋6,及4＋5。
选取的5个数字都是这四个组合中的数字。由鸽子洞原理，其中的两个数字必来自于同一组，即其和是9。
12.如果你用不掉色的笔在一个橙子的表面上点上5个点，那么有一种可能，当把橙子切成两块时，其中的四个点在同一个半块上（假设一个点在切的时候正好处在橙子的切点上）。
球面上的两点确定一条圆弧，因此任意两点可将橙子切成两块。余下的三个点可处于任意2个半块的橙子上。由鸽子洞原理，至少有2个点属于同一个半块的橙子，加上原先的两点切点，总共是4个点在同一个半块上。
13.加里参加三项全能运动训练。他保证在30天内，他每天都要训练一次其中的一项，每项总共训练45次。那么有那么相连的几天他每天总共要训练14次。
这一问题及证明基于加里·麦吉利弗雷教授的讲义(pdf)。
设Si表示第i天累计训练的次数，由于每天都有一个训练，单一项目总的训练次数是45次，我们得出：
1 ≤ S1 < S2 < … < S30 = 45
我们需要证明有某一天当i
15 ≤ S1 + 14 < S2 + 14 < … < S30 + 14 = 59
这两个不等式表示有60个数字(S1, S2, …, S30 and S1 + 14, S2 + 14, …, S30 + 14)可以推出从1到59的作弄一一个整数值。据鸽子洞原理，有2个数字必然相同。
哪两个数字呢？注意数字S1, S2, …, S30中没有一个能够等于另一个（加里每天至少有一个训练，每天的训练总次数都在增加）。这一推理也适用于组合 S1 + 14, S2 + 14, …, S。
于是，在数组S1, S2, …, S30中必有一个值等于数组S1 + 14, S2 + 14, …, S30 + 14中的一个，这正是我们需要求证的。
14.在任何有2个人或2个人以上参加的鸡尾酒会上，必有至少2个人有相同数量的朋友。（假定“朋友”是相互的，即如果x是y的朋友，那么y也是x的朋友。）
设想一次酒会有n个人。那么每一个人可以有0～n-1个朋友。
情形1：每个人至少有1个朋友
如果每个人至少有1个朋友，那么每个人的朋友数可以为1～n-1个。出席酒会的n个人可以列为n-1个朋友值，因此，根据鸽子洞原理，至少有2个人的朋友值相同，即朋友数相同。
情形2：某人没有朋友
如果有人没有朋友，那么这人都是其他的所有人的陌生人。因为朋友是相互的，这“其它的所有人”的最大数只能是“n-2″,也就是这“n-2″个人可以是除那个没有朋友的人之外，任一人的朋友。因此，每个人有0～n-2个朋友。意即，n个参加酒会的人可以分类为n-1个值中的一个，有2个人有相同的值，或数量相同的朋友。
难（15－16）
15.假设你要用多米诺骨牌去盖一副国际象棋，每个多米诺骨牌刚好能盖2个方格。如果你移开连成斜线的相对的2个方格，那么无法盖住棋盘。
请看例2,切绳子上的结（Cut The Knot）。（如果那个链接断了，请试这一个）。
16.在6个人当中，必有三个人相互间是朋友或相互间不认识。（假定“朋友”是相互的，即如果x是y的朋友，那么y也是x的朋友。）
这一问题让人想起用几何学加以解答。设想6个人是6个点，每2点画成的一条直线表示朋友。不管怎样画，我们要画出有三个点总是连接的，另外的三个点总是没有连接。
考虑任意1个点。有其它5个点可以与之连接。根据鸽子洞原理，这个点要么至少与其它三个点相连，要么至少没有与其它三个点相连。
情形1：这个点（至少）与其它三个点相连
如果这些点相互连接，我们得到一个三角形，有三对人互为朋友。（四个点中的两个点相连，加上它们又都与最初的一个点相连）。
否则，表示任一三个点都不相连，他们互相不认识。表示三个点间没有任何连接。
情形2：这个点（至少）没有与其它三个点相连
由此，我们得到一个互为陌生人的三角形。（四个点中的两个点不相连，加上它们又都不与最初的一个点相连）。
否则，表示任一三个点相连，他们互为朋友。表示三个点间有连接。
额外收获：无损耗数据压缩不能保证对所有输入的数据文件进行压缩。
令人惊奇的是，这同样是鸽子洞原理的运用！
原文：http://article.yeeyan.org/view/115616/148851
