514

更新時間: 2013-07-29

廣告

桌上有十個蘋果,要把這十個蘋果放到九個抽屜里,無論怎樣放,我們會發現至少會有一個抽屜裡面至少放兩個蘋果。這一現象就是我們所說的「抽屜原理」。 抽屜原理的一般含義為:「如果每個抽屜代表一個集合,每一個蘋果就可以代表一個元素,假如有n+1或多於n+1個元素放到n個集合中去,其中必定至少有一個集合里有兩個元素。」 抽屜原理有時也被稱為鴿巢原理(「如果有五個鴿子籠,養鴿人養了6隻鴿子,那麼當鴿子飛回籠中后,至少有一個籠子中裝有至少2隻鴿子」)。它是組合數學中一個重要的原理。

廣告

1常見形式

3狄利克雷

4一般表述

在上面的第一個結論中,由於一年最多有366天,因此在367人中至少有2人出生在同月同日。這相當於把367個東西放入 366個抽屜,至少有2個東西在同一抽屜里。在第二個結論中,不妨想象將5雙手套分別編號,即號碼為1,2,...,5的手套各有兩隻,同號的兩隻是一雙。任取6隻手套,它們的編號至多有5種,因此其中至少有兩隻的號碼相同。這相當於把6個東西放入5個抽屜,至少有2個東西在同一抽屜里。
抽屜原理的一種更一般的表述為:
「把多於kn+1個東西任意分放進n個空抽屜(k是正整數),那麼一定有一個抽屜中放進了至少k+1個東西。」
利用上述原理容易證明:「任意7個整數中,至少有3個數的兩兩之差是3的倍數。」因為任一整數除以3時餘數只有0、1、2三種可能,所以7個整數中至少有3個數除以3所得餘數相同,即它們兩兩之差是3的倍數。
如果問題所討論的對象有無限多個,抽屜原理還有另一種表述:
「把無限多個東西任意分放進n個空抽屜(n是自然數),那麼一定有一個抽屜中放進了無限多個東西。」
用高斯函數來敘述一般形式的抽屜原理的是:將m個元素放入n個抽屜,則在其中一個抽屜里至少會有
(m-1)÷n+1個元素。
抽屜原理的內容簡明樸素,易於接受,它在數學問題中有重要的作用。許多有關存在性的證明都可用它來解決。
這個問題可以用如下方法簡單明了地證出:
在平面上用6個點A、B、C、D、E、F分別代表參加集會的任意6個人。如果兩人以前彼此認識,那麼就在代表他們的兩點間連成一條紅線;否則連一條藍線。考慮A點與其餘各點間的5條連線AB,AC,...,AF,它們的顏色不超過2種。根據抽屜原理可知其中至少有3條連線同色,不妨設AB,AC,AD同為紅色。如果BC,BD ,CD 3條連線中有一條(不妨設為BC)也為紅色,那麼三角形ABC即一個紅色三角形,A、B、C代表的3個人以前彼此相識:如果BC、BD、CD 3條連線全為藍色,那麼三角形BCD即一個藍色三角形,B、C、D代表的3個人以前彼此不相識。不論哪種情形發生,都符合問題的結論。
六人集會問題是組合數學中著名的拉姆塞定理的一個最簡單的特例,這個簡單問題的證明思想可用來得出另外一些深入的結論。這些結論構成了組合數學中的重要內容-----拉姆塞理論。從六人集會問題的證明中,我們又一次看到了抽屜原理的應用。

5經典練習

廣告