鴿巢原理數學定理 / 維基百科,自由的 encyclopedia 鴿巢原理,又名狄利克雷抽屜原理、鴿籠原理。 10隻鴿子放進9個鴿籠,那麼一定有一個鴿籠放進了至少兩隻鴿子。 其中一種簡單的表述法為: 若有n個籠子和n+1隻鴿子,所有的鴿子都被關在鴿籠裏,那麼至少有一個籠子有至少2隻鴿子。 另一種為: 若有n個籠子和kn+1隻鴿子,所有的鴿子都被關在鴿籠裏,那麼至少有一個籠子有至少k+1隻鴿子。 集合論的表述如下: 若A是n+1元集,B是n元集,則不存在從A到B的單射。 拉姆齊定理是此原理的推廣。
鴿巢原理,又名狄利克雷抽屜原理、鴿籠原理。 10隻鴿子放進9個鴿籠,那麼一定有一個鴿籠放進了至少兩隻鴿子。 其中一種簡單的表述法為: 若有n個籠子和n+1隻鴿子,所有的鴿子都被關在鴿籠裏,那麼至少有一個籠子有至少2隻鴿子。 另一種為: 若有n個籠子和kn+1隻鴿子,所有的鴿子都被關在鴿籠裏,那麼至少有一個籠子有至少k+1隻鴿子。 集合論的表述如下: 若A是n+1元集,B是n元集,則不存在從A到B的單射。 拉姆齊定理是此原理的推廣。