【正文】 么這三條線段也組成我們所需要的同色三角形。因而無論怎樣著色，在這六點之間的所有線段中至少能找到一個同色三角形?！　±?′（六人集會問題）證明在任意6個人的集會上，或者有3個人以前彼此相識，或者有三個人以前彼此不相識?！薄　±?”：17個科學家中每個人與其余16個人通信，他們通信所討論的僅有三個問題，而任兩個科學家之間通信討論的是同一個問題。證明：至少有三個科學家通信時討論的是同一個問題?！　〗猓翰环猎OA是某科學家，他與其余16位討論僅三個問題，由鴿籠原理知，他至少與其中的6位討論同一問題。設這6位科學家為B，C，D，E，F(xiàn)，G，討論的是甲問題?！　∪暨@6位中有兩位之間也討論甲問題，則結論成立。否則他們6位只討論乙、丙兩問題。這樣又由鴿籠原理知B至少與另三位討論同一問題，不妨設這三位是C，D，E，且討論的是乙問題。　　若C，D，E中有兩人也討論乙問題，則結論也就成立了。否則，他們間只討論丙問題，這樣結論也成立?！　∪圃斐閷鲜沁\用原則的一大關鍵　　例1 從…、30這15個偶數(shù)中，任取9個數(shù)，證明其中一定有兩個數(shù)之和是34。　　分析與解答我們用題目中的15個偶數(shù)制造8個抽屜：　　凡是抽屜中有兩個數(shù)的，都具有一個共同的特點：這兩個數(shù)的和是34。現(xiàn)從題目中的15個偶數(shù)中任取9個數(shù)，由抽屜原理（因為抽屜只有8個），這兩個數(shù)的和是34。　　例2：從…、120這20個自然數(shù)中，至少任選幾個數(shù)，就可以保證其中一定包括兩個數(shù)，它們的差是12?！　》治雠c解答在這20個自然數(shù)中，差是12的有以下8對：｛20，8｝，｛19，7｝，｛18，6｝，｛17，5｝，｛16，4｝，｛15，3｝，｛14，2｝，｛13，1｝?！　×硗膺€有4個不能配對的數(shù)｛9｝，｛10｝，｛11｝，｛12｝，共制成12個抽屜（每個括號看成一個抽屜）.只要有兩個數(shù)取自同一個抽屜，那么它們的差就等于12，根據(jù)抽屜原理至少任選13個數(shù)，即可辦到（取12個數(shù)：從12個抽屜中各取一個數(shù)（例如取1，2，3，…，12），那么這12個數(shù)中任意兩個數(shù)的差必不等于12）?！　±?：從1到20這20個數(shù)中，任取11個數(shù)，必有兩個數(shù)，其中一個數(shù)是另一個數(shù)的倍數(shù)?！　》治雠c解答根據(jù)題目所要求證的問題，應考慮按照同一抽屜中，看成10個抽屜（顯然，它們具有上述性質）：　?。?，2，4，8，16｝，｛3，6，12｝，｛5，10，20｝，｛7，14｝，｛9，18｝，｛11｝，｛13｝，｛15｝，｛17｝，｛19｝?！　倪@10個數(shù)組的20個數(shù)中任取11個數(shù)，根據(jù)抽屜原理，所以這兩個數(shù)中，其中一個數(shù)一定是另一個數(shù)的倍數(shù)?！　±?：某校校慶，來了n位校友，在這n個校友中至少有兩人握手的次數(shù)一樣多?！　》治雠c解答共有n位校友，每個人握手的次數(shù)最少是0次，即這個人與其他校友都沒有握過手；最多有n1次，如果有一個校友握手的次數(shù)是0次，那么握手次數(shù)最多的不能多于n2次；如果有一個校友握手的次數(shù)是n1次，、…、n2，還是后一種狀態(tài)…、n1，到會的n個校友每人按照其握手的次數(shù)歸入相應的“抽屜”，根據(jù)抽屜原理，至少有兩個人屬于同一抽屜，則這兩個人握手的次數(shù)一樣多?！　≡谟行﹩栴}中，“抽屜”和“物體”不是很明顯的，需要精心制造“抽屜”和“物體”.如何制造“抽屜”和“物體”可能是很困難的，一方面需要認真地分析題目中的條件和問題，另一方面需要多做一些題積累經驗。　　抽屜原理　　把八個蘋果任意地放進七個抽屜里，不論怎樣放，至少有一個抽屜放有兩個或兩個以上的蘋果。抽屜原則有時也被稱為鴿巢原理，它是德國數(shù)學家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題，因此，也稱為狄利克雷原則。它是組合數(shù)學中一個重要的原理。把它推廣到一般情形有以下幾種表現(xiàn)形式?！　⌒问揭唬鹤C明：設把n＋1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數(shù)，需要證明至少存在某個ai大于或等于2（用反證法）假設結論不成立，即對每一個ai都有ai＜2，則因為ai是整數(shù)，應有ai≤1，于是有：　　a1＋a2＋…＋an≤1＋1＋…＋1＝n＜n＋1這與題設矛盾。所以，至少有一個ai≥2，即必有一個集合中含有兩個或兩個以上的元素?！　⌒问蕉涸O把n?m＋1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數(shù)，需要證明至少存在某個ai大于或等于m＋1。用反證法）假設結論不成立，即對每一個ai都有ai＜m＋1，則因為ai是整數(shù)，應有ai≤m，于是有：　　a1＋a2＋…＋an≤m＋m＋…＋m＝n?m＜n?m＋1　　n個m 這與題設相矛盾。所以，至少有存在一個ai≥m＋1　　高斯函數(shù)：對任意的實數(shù)x,[x]表示“不大于x的最大整數(shù)”.　　例如：[]＝3，[]＝2，[－]＝－3，[7]＝7，……一般地，我們有：[x]≤x＜[x]＋1　　形式三：證明：設把n個元素分為k個集合A1，A2，…，Ak，用a1，a2，…，ak表示這k個集合里相應的元素個數(shù)，需要證明至少存在某個ai大于或等于[n/k]。（用反證法）假設結論不成立，即對每一個ai都有ai＜[n/k]，于是有：　　a1＋a2＋…＋ak＜[n/k]+[n/k]+…+[n/k] ＝k?[n/k]≤k?(n/k)＝n　　k個[n/k] ∴ a1＋a2＋…＋ak＜n 這與題設相矛盾。所以，必有一個集合中元素個數(shù)大于或等于[n/k]　　形式四：證明：設把q1＋q2＋…＋qn－n＋1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數(shù)，需要證明至少存在某個i，使得ai大于或等于qi。（用反證法）假設結論不成立，即對每一個ai都有ai＜qi，因為ai為整數(shù)，應有ai≤qi－1，于是有：a1＋a2＋…＋an≤q1＋q2＋…＋qn－n ＜q1＋q2＋…＋qn－n＋1這與題設矛盾?！　∷裕僭O不成立，故必有一個i,在第i個集合中元素個數(shù)ai≥qi　　形式五：證明：（用反證法）將無窮多個元素分為有限個集合，假設這有限個集合中的元素的個數(shù)都是有限個，則有限個有限數(shù)相加，所得的數(shù)必是有限數(shù)，這就與題設產生矛盾，所以，假設不成立，故必有一個集合含有無窮多個元素?！　±}１：：生日從1月1日排到12月31日，共有366個不相同的生日，我們把366個不同的生日看作366個抽屜，400人視為400個蘋果，由表現(xiàn)形式1可知，至少有兩人在同一個抽屜里，所以這400人中有兩人的生日相同.　　解：將一年中的366天視為366個抽屜，400個人看作400個蘋果，由抽屜原理的表現(xiàn)形式1可以得知：至少有兩人的生日相同.　　例題2：任取5個整數(shù)，必然能夠從中選出三個，使它們的和能夠被3整除.　　證明：任意給一個整數(shù)，它被3除，余數(shù)可能為0，1，2，我們把被3除余數(shù)為0，1，2的整數(shù)各歸入類r０，r1，：１176。.某一類至少包含三個數(shù)；２176。.某兩類各含兩個數(shù)，第三類包含一個數(shù).　　若是第一種情況，就在至少包含三個數(shù)的那一類中任取三數(shù)，其和一定能被3整除；若是第二種情況，在三類中各取一個數(shù)，其和也能被3整除..綜上所述，原命題正確.　　例題3：某校派出學生204人上山植樹15301株，其中最少一人植樹50株，最多一人植樹100株，則至少有5人植樹的株數(shù)相同.　　證明：按植樹的多少，從50到100株可以構造51個抽屜，則個問題就轉化為至少有5人植樹的株數(shù)在同一個抽屜里.　　(用反證法)假設無５人或５人以上植樹的株數(shù)在同一個抽屜里，那只有５人以下植樹的株數(shù)在同一個抽屜里，而參加植樹的人數(shù)為204人，所以，每個抽屜最多有4人，故植樹的總株數(shù)最多有：　　4(50＋51＋…＋100)＝4 ＝15300＜，至少有５人植樹的株數(shù)相同.　　練習：1．邊長為1的等邊三角形內有5個點，.　　2．邊長為1的等邊三角形內，若有n2＋1個點，則至少存在2點距離小于 .　　3．求證：任意四個整數(shù)中，至少有兩個整數(shù)的差能夠被3整除.　　4．某校高一某班有50名新生，試說明其中一定有二人的熟人一樣多.　　5．某個年級有202人參加考試，滿分為100分，且得分都為整數(shù)，總得分為10101分，則至少有3人得分相同.　　“任意367個人中，必有生日相同的人?！薄　　皬娜我?雙手套中任取6只，其中至少有2只恰為一雙手套。”　　“從數(shù)1，2，...，10中任取6個數(shù)，其中至少有2個數(shù)為奇偶性不同?！薄　?.. ...　　大家都會認為上面所述結論是正確的。這些結論是依據(jù)什么原理得出的呢？這個原理叫做抽屜原理。它的內容可以用形象的語言表述為：　　“把m個東西任意分放進n個空抽屜里（mn），那么一定有一個抽屜中放進了至少2個東西?！薄　≡谏厦娴牡谝粋€結論中，由于一年最多有366天，因此在367人中至少有2人出生在同月同日。這相當于把367個東西放入 366個抽屜，至少有2個東西在同一抽屜里。在第二個結論中，不妨想象將5雙手套分別編號，即號碼為1，2，...，5的手套各有兩只，同號的兩只是一雙。任取6只手套，它們的編號至多有5種，因此其中至少有兩只的號碼相同。這相當于把6個東西放入5個抽屜，至少有2個東西在同一抽屜里?！　〕閷显淼囊环N更一般的表述為：　　“把多于kn個東西任意分放進n個空抽屜（k是正整數(shù)），那么一定有一個抽屜中放進了至少k+1個東西。”　　利用上述原理容易證明：“任意7個整數(shù)中，至少有3個數(shù)的兩兩之差是3的倍數(shù)?！币驗槿我徽麛?shù)除以3時余數(shù)只有0、2三種可能，所以7個整數(shù)中至少有3個數(shù)除以3所得余數(shù)相同，即它們兩兩之差是3的倍數(shù)。　　如果問題所討論的對象有無限多個，抽屜原理還有另一種表述：　　“把無限多個東西任意分放進n個空抽屜（n是自然數(shù)），那么一定有一個抽屜中放進了無限多個東西?！薄　〕閷显淼膬热莺喢鳂闼兀子诮邮?，它在數(shù)學問題中有重要的作用。許多有關存在性的證明都可用它來解決?！　?958年6/7月號的《美國數(shù)學月刊》上有這樣一道題目：　　“證明在任意6個人的集會上，或者有3個人以前彼此相識，或者有三個人以前彼此不相識?！薄　∵@個問題可以用如下方法簡單明了地證出：　　在平面上用6個點A、B、C、D、E、F分別代表參加集會的任意6個人。如果兩人以前彼此認識，那么就在代表他們的兩點間連成一條紅線；否則連一條藍線。考慮A點與其余各點間的5條連線AB，AC，...，AF，它們的顏色不超過2種。根據(jù)抽屜原理可知其中至少有3條連線同色，不妨設AB，AC，AD同為紅色。如果BC，BD ，CD 3條連線中有一條（不妨設為BC）也為紅色，那么三角形ABC即一個紅色三角形，A、B、C代表的3個人以前彼此相識：如果BC、BD、CD 3條連線全為藍色，那么三角形BCD即一個藍色三角形，B、C、D代表的3個人以前彼此不相識。不論哪種情形發(fā)生，都符合問題的結論?！　×思瘯栴}是組合數(shù)學中著名的拉姆塞定理的一個最簡單的特例，這個簡單問題的證明思想可用來得出另外一些深入的結論。這些結論構成了組合數(shù)學中的重要內容拉姆塞理論。從六人集會問題的證明中，我們又一次看到了抽屜原理的應用。160