鴿巢原理維基百科,自由的 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的單射。 拉姆齐定理是此原理的推廣。