第一抽屜原理
原理1: 把多于n+k個的物體放到n個抽屜里,則至少有一個抽屜里的東西不少于兩件。
證明(反證法):如果每個抽屜至多只能放進一個物體,那么物體的總數至多是n×1,而不是題設的n+k(k≥1),故不可能。
原理2 :把多于mn(m乘以n)(n不為0)個的物體放到n個抽屜里,則至少有一個抽屜里有不少于(m+1)的物體。
證明(反證法):若每個抽屜至多放進m個物體,那么n個抽屜至多放進mn個物體,與題設不符,故不可能。
原理3 :把無窮多件物體放入n個抽屜,則至少有一個抽屜里 有無窮個物體。
原理1 、2 、3都是第一抽屜原理的表述。
第二抽屜原理
把(mn-1)個物體放入n個抽屜中,其中必有一個抽屜中至多有(m—1)個物體(例如,將3×5-1=14個物體放入5個抽屜中,則必定有一個抽屜中的物體數少于等于3-1=2)。
在上面的第一個結論中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日。這相當于把367個東西放入 366個抽屜,至少有2個東西在同一抽屜里。在第二個結論中,不妨想象將5雙手套分別編號,即號碼為1,2,...,5的手套各有兩只,同號的兩只是一雙。任取6只手套,它們的編號至多有5種,因此其中至少有兩只的號碼相同。這相當于把6個東西放入5個抽屜,至少有2個東西在同一抽屜里。
抽屜原理的一種更一般的表述為:
“把多于kn+1個東西任意分放進n個空抽屜(k是正整數),那么一定有一個抽屜中放進了至少k+1個東西?!?br />
利用上述原理容易證明:“任意7個整數中,至少有3個數的兩兩之差是3的倍數。”因為任一整數除以3時余數只有0、1、2三種可能,所以7個整數中至少有3個數除以3所得余數相同,即它們兩兩之差是3的倍數。
如果問題所討論的對象有無限多個,抽屜原理還有另一種表述:
“把無限多個東西任意分放進n個空抽屜(n是自然數),那么一定有一個抽屜中放進了無限多個東西?!?br />
用高斯函數來敘述一般形式的抽屜原理的是:將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個人以前彼此不相識。不論哪種情形發生,都符合問題的結論。
六人集會問題是組合數學中著名的拉姆塞定理的一個最簡單的特例,這個簡單問題的證明思想可用來得出另外一些深入的結論。這些結論構成了組合數學中的重要內容-----拉姆塞理論。從六人集會問題的證明中,我們又一次看到了抽屜原理的應用。
希望可以幫到您
抽屜原理是指把八個蘋果任意地放進七個抽屜里,不論怎樣放,至少有一個抽屜放有兩個或兩個以上的蘋果。 抽屜原理的一般含義為:“如果每個抽屜代表一個集合,每一個蘋果就可以代表一個元素,假如有n+1個元素放到n個集合中去,其中必定有一個集合里至少有兩個元素?!?抽屜原理有時也被稱為鴿巢原理。它是組合數學中一個重要的原理。