原理概述：
有ｎ只鸽子和ｍ个鸽洞，所有鸽子都住在鸽洞里，如果ｎ＞ｍ，那么至少有二只鸽子必须住在同一鸽洞里。
函数观点：
把鸽子看成是定义域Ａ中元素ａi，鸽洞看成是值域Ｂ中的元素ｂj，鸽子住鸽洞作为函数关系。
鸽洞原理：
设ｆ是从有限集Ａ到有限集Ｂ的函数，若｜Ａ｜＞｜Ｂ｜，则必有ａ1，ａ2∈Ａ，ａ1≠ａ2，使ｆ（ａ1）＝ｆ（ａ2）＝b∈Ｂf 包含于Ｂ（Ｂf是象域）。
反证：若对任意ａ1，ａ2∈Ａ，ａ1≠ａ2，ｆ（ａ1）≠ｆ（ａ2），｜Ａ｜＝｜Ｂf｜≤｜Ｂ｜与｜Ａ｜＞｜Ｂ｜矛盾
注：
鸽洞原理本质上是对一个非一对一函数的充分性判别。
这个原理看上去容易理解，且有广泛的应用。
例１：在ｎ2＋１个不同整数的任意排列中，证明一定存在长为ｎ＋１的上升子序列或下降子序列。
证明：
设此序列为：ａ1，ａ2，…，ａk，…，从ａk开始上升子序列长度为ｘk，下降子序列长度为ｙk，每一个ａk（ｋ＝１，２，…，ｎ２＋１）都对应了（ｘk，ｙk）。
若不存在长为ｎ＋１的上升或下降子序列，那么ｘk ≤ｎ，ｙk≤ｎ，形如（ｘk，ｙk）的不同点对至多有ｎ2个，而ａk有ｎ2＋１个，必有ａi，ａj（１≤ｉ＜ｊ≤ｎ＋１）同时对应（ｘi，ｙi）＝（ｘj，ｙj）。
由于ａi≠ａj，若ａi＜ａj，则ｘi至少比ｘj大１，若ａi＞ａj，则ｙi至少比ｙj大１，与（ｘi，ｙj）＝（ｘj，ｙj）矛盾。
例２： １３２个球放入７７个盒子内，每盒至少放一球，求证：一定有２１个球放在相邻的某几只盒子里。
证明：
设第ｋ个盒子里放的球为ｂk，得到ｂ1，ｂ2，…，ｂ77，按题意，欲寻找ｉ和ｊ，ｉ＞ｊ≥０，使ｂj+1＋ｂj+2＋…＋ｂi＝２１，即完成证明。
设ａk＝，得到ａ1，ａ2，…，ａ77，显然，｛ａk｝是严格单调上升的，ａi≠ａj （ｉ≠
设 Ｃk＝，得到Ｃ1，Ｃ2，…，Ｃ77，｛Ｃk｝也是严格单调上升的，Ｃi≠Ｃj （ｉ≠ｊ），且Ｃ77＝１５３，Ｃi＝ａi＋２１。
｛ａk｝与｛Ｃk｝合在一起共有１５４个，但只能在１～１５３中取值，由鸽洞原理，必有二个相同，且不会同是ａk中的，也不会同是Ｃk中的，不妨ａi＝Ｃj＝ａj＋２１，ａi－ａj＝２１，即，得到ｂj+1 ＋ｂj+2＋…＋ｂi＝２１。
例３：
设ｘ1，ｘ2，…，ｘn是任意排列的任意整数，证明其中存在连续的若干个数，它们之和是ｎ的倍数。
证明： 设ａi＝
若ａi中有ｎ的倍数，则命题成立
若ａi中没有ｎ的倍数，由ｎ除ａi的余数只能在１～ｎ－１中取
以ａi（ｉ＝１，２，…，ｎ）作鸽子，１～ｎ－１作鸽洞，ａi，ａj，使ａi≡ａj（ｍｏｄｎ）（ｉ＞ｊ），则 ｎ｜（ａi－ａj）， 即ｘj+1＋ｘj+2＋…＋ｘi是ｎ的倍数。
摘录自百度文库：鸽子洞原理
原文：http://www.cnblogs.com/xiangyangzhu/p/5372875.html