抽屜原理和六人集會(huì)問題
“任意367個(gè)人中,必有生日相同的人.”
“從任意5雙手套中任取6只,其中至少有2只恰為一雙手套.”
“從數(shù)1,2,...,10中任取6個(gè)數(shù),其中至少有2個(gè)數(shù)為奇偶性不同.”
.
大家都會(huì)認(rèn)為上面所述結(jié)論是正確的.這些結(jié)論是依據(jù)什么原理得出的呢?這個(gè)原理叫做抽屜原理.它的內(nèi)容可以用形象的語言表述為：
“把m個(gè)東西任意分放進(jìn)n個(gè)空抽屜里（m>n）,那么一定有一個(gè)抽屜中放進(jìn)了至少2個(gè)東西.”
在上面的第一個(gè)結(jié)論中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日.這相當(dāng)于把367個(gè)東西放入366個(gè)抽屜,至少有2個(gè)東西在同一抽屜里.在第二個(gè)結(jié)論中,不妨想象將5雙手套分別編號(hào),即號(hào)碼為1,2,...,5的手套各有兩只,同號(hào)的兩只是一雙.任取6只手套,它們的編號(hào)至多有5種,因此其中至少有兩只的號(hào)碼相同.這相當(dāng)于把6個(gè)東西放入5個(gè)抽屜,至少有2個(gè)東西在同一抽屜里.
抽屜原理的一種更一般的表述為：
“把多于kn個(gè)東西任意分放進(jìn)n個(gè)空抽屜（k是正整數(shù)）,那么一定有一個(gè)抽屜中放進(jìn)了至少k+1個(gè)東西.”
利用上述原理容易證明：“任意7個(gè)整數(shù)中,至少有3個(gè)數(shù)的兩兩之差是3的倍數(shù).”因?yàn)槿我徽麛?shù)除以3時(shí)余數(shù)只有0、1、2三種可能,所以7個(gè)整數(shù)中至少有3個(gè)數(shù)除以3所得余數(shù)相同,即它們兩兩之差是3的倍數(shù).
如果問題所討論的對(duì)象有無限多個(gè),抽屜原理還有另一種表述：
“把無限多個(gè)東西任意分放進(jìn)n個(gè)空抽屜（n是自然數(shù)）,那么一定有一個(gè)抽屜中放進(jìn)了無限多個(gè)東西.”
抽屜原理的內(nèi)容簡明樸素,易于接受,它在數(shù)學(xué)問題中有重要的作用.許多有關(guān)存在性的證明都可用它來解決.
1958年6/7月號(hào)的《美國數(shù)學(xué)月刊》上有這樣一道題目：
“證明在任意6個(gè)人的集會(huì)上,或者有3個(gè)人以前彼此相識(shí),或者有三個(gè)人以前彼此不相識(shí).”
這個(gè)問題可以用如下方法簡單明了地證出：
在平面上用6個(gè)點(diǎn)A、B、C、D、E、F分別代表參加集會(huì)的任意6個(gè)人.如果兩人以前彼此認(rèn)識(shí),那么就在代表他們的兩點(diǎn)間連成一條紅線；否則連一條藍(lán)線.考慮A點(diǎn)與其余各點(diǎn)間的5條連線AB,AC,...,AF,它們的顏色不超過2種.根據(jù)抽屜原理可知其中至少有3條連線同色,不妨設(shè)AB,AC,AD同為紅色.如果BC,BD,CD3條連線中有一條（不妨設(shè)為BC）也為紅色,那么三角形ABC即一個(gè)紅色三角形,A、B、C代表的3個(gè)人以前彼此相識(shí)：如果BC、BD、CD3條連線全為藍(lán)色,那么三角形BCD即一個(gè)藍(lán)色三角形,B、C、D代表的3個(gè)人以前彼此不相識(shí).不論哪種情形發(fā)生,都符合問題的結(jié)論.
六人集會(huì)問題是組合數(shù)學(xué)中著名的拉姆塞定理的一個(gè)最簡單的特例,這個(gè)簡單問題的證明思想可用來得出另外一些深入的結(jié)論.這些結(jié)論構(gòu)成了組合數(shù)學(xué)中的重要內(nèi)容-----拉姆塞理論.從六人集會(huì)問題的證明中,我們又一次看到了抽屜原理的應(yīng)用.