Can you summarize the following document?
        
  雖然鴿巢原理看起來很容易理解,但有時使用鴿巢原理會得到一些有趣的結論:  另一個例子:  另一個例子:  更不直觀一點的例子:  鴿巢原理經常在計算機領域得到真正的應用。比如:雜湊表的重複問題(衝突)是不可避免的,因為Keys的數目總是比Indices的數目多,不管是多麼高明的演算法都不可能解決這個問題。這個原理,還證明任何無失真壓縮演算法,在把一些輸入變小的同時,作為代價一定有其他的輸入增大,否則對於長度為L的輸入集合,該壓縮演算法總能將其對映到一個更小的長度小於L的輸出集合,而這與鴿巢理論相悖。

  一種表達是這樣的:如果要把n個物件分配到m個容器中,必有至少一個容器容納至少formula_1個物件。

  

  設把n+1個元素分為n個集合formula_2,記formula_3表示這n個集合裡相應的元素個數。  假設formula_4  因為formula_5  所以formula_6  所以formula_7  這與題設矛盾,因此結論得證。

  將m個元素隨機放入n個集合formula_8中(m > n)。規定formula_9如果n整除m。隨機選擇一個集合,它的大小的期望值是: formula_10 由於formula_11只能是整數,所以必有一個m,使得formula_12

  設 皆是正整數,現有  個物件要分配在個箱子中,那麼以下敘述至少一者成立:  這個原理一樣可以使用反證法證明,即假設上述所有敘述為假並得出矛盾,方法與前述簡單情況類似。

  藉由康託的無窮基數可將鴿巢原理推廣到無窮集中:如果集合A的勢大於集合B的勢,那麼不存在由A到B的單射。
鴿巢原理,又名狄利克雷抽屜原理、鴿籠原理。