18抽屜原則
現在有五本書要放到四個抽屜裏去,放法是很多的,有的抽屜可以不放,有的可以放一本,有的可以放二本、三本、四本甚至放五本。但是,隨便怎樣放法,至少總可以找到一個抽屜裏至少放上二本書的。
如果每一個抽屜代表一個集合,每一本書就代表一個元素。假使有n+1或比n+1多的元素要放到n個集合裏去,那也沒有疑問,其中必定至少有一個集合裏至少放進二個元素。這就是“抽屜原則”的抽象涵義。
現在我們班上有54個同學,我說,這54個同學中至少有二個人是同一個星期出生的。你一定會驚奇,我怎麼會知道的呢?這很簡單,按照我們學校目前招生的情況,學生們的生日不會相差一年,因為一年之中隻有53個星期,現在學生有54人,我們運用抽屜原則的知識,把星期作為抽屜,學生作為書本,那麼,這53個抽屜裏,至少有一個抽屜放進至少二本書的,也就是至少有二個同學在同一星期出生。這不是很容易解答的嗎?
一般的情況,書本的數目並不一定比抽屜數目多1,可以更多一些,例如多6本、7本放到四個抽屜裏。如果更多呢?例如21本書放到4個抽屜裏,道理也是一樣,也就是無論怎樣放法,至少可以找到一個抽屜裏至少有6本書。這樣的情況,即把(m×n+1)或比(m×n+1)多的元素放到n個集合裏的話,無論怎樣放法,其中必定至少有一個集合裏至少放進m+1個元素。
我們來試試看,假使在一個平麵上有任意六個點,無三點共線,每二點用紅色或藍色的線段連起來,都連好以後,能不能找到一個由這些線段構成的三角形,它們的三條邊是同一顏色的?
我們可以隨便選擇其中任何一點,可以看到這一點到其他五個點之間連接了5條線段,這5條線段中,至少有三條是同一顏色,假定是紅色。現在我們單獨來看這三條紅色的線段吧,這三條線段的另一端不是也有不同顏色的線段連接起來構成三角形的嗎?假使其中有一條是紅色的,那麼,這條紅色的線段和其他原來連接的兩條紅色線段就組成了一個我們所要找的三角形。假使這三條都是藍色的呢,那麼,這三條藍色線段本身組成的也是我們所要找的三角形。所以,無論你怎樣著色,在這任意六個點之間所有的線段中至少能找到同一種顏色的一個三角形。
假使在一場乒乓賽中,從所有的隊員裏任選六個人,你能證明他們當中必然有三個人互相握過手,或者彼此都沒有握過手嗎?
19在滿箱子裏再裝一個零件
某包裝工人要把一批圓形零件裝箱,他把40個零件放進一個箱子裏剛好裝滿,一點也不鬆動。但他計算一下後發現,如果每個箱子再能放進一個零件,那麼將節省很大一筆錢。你能幫他忙嗎?
這個問題表麵看來是根本辦不到的。因為零件在箱子裏可謂“充分飽和”,要想再放進一個零件,必須重新安排結構,對於圓形零件的“緊湊”擺法也隻有“三圓兩兩外切”這一種情況可試了。一經試驗立刻獲得成功。
這種擺法我們隻計算一下長度就可以了。設圓形零件的半徑為r,則相鄰的兩行的圓必距離為3r,這樣9行零件的總長度為(83+2)r。前麵一種擺法總長度為16r。
把兩個長度比較一下:
83+2<8×1774+2=1592<16
由此可見,後一種擺法不但能放進41個零件,還略有餘地呢!