第一節(jié)鴿巢基本知識

鴿巢原理及其他第一節(jié)鴿巢原理關(guān)于鴿巢原理的闡釋，粗略地說就是如果有許多鴿子飛進不夠多謝謝閱讀的鴿巢內(nèi)，那么至少要有一個鴿巢被兩個或多個鴿子占據(jù)。精品文檔放心下載一、鴿巢原理的簡單形式1、定理1：如果要把n+1個物體放進n個盒子，那么至少有一個盒精品文檔放心下載子包含兩個或更多的物體。證明：用反證法進行證明。如果這n個盒子中的每一個都至多含有一感謝閱讀個物體，那么物體的總數(shù)最多是 n，這與有n+1個物體矛盾。所以精品文檔放心下載某個盒子至少有兩個物體。2、定理1的說明：無論是鴿巢原理還是它的證明，都不能具體找出謝謝閱讀含有兩個或更多物體的盒子。它只是證明這樣的盒子存在，即如果人謝謝閱讀們檢査每一個盒子.那么他們會發(fā)現(xiàn)有的盒子里面放有多個物體。另感謝閱讀外，當只有n個（或更少）物體時，是無法保證鴿巢原理的結(jié)論的。謝謝閱讀這是因為可以在n個盒子的每一個里面放進一個物體。所以鴿巢原理精品文檔放心下載成立的條件是至少為n+1個物體。3、鴿巢原理的兩個簡單應(yīng)用應(yīng)用1：在13個人中存在兩個人，他們的生日在同一個月份里。感謝閱讀應(yīng)用2：設(shè)有n對己婚大婦。至少要從這2n個人中選出多少人才能感謝閱讀保證能夠選出一對夫婦？為了在這種情形下應(yīng)用鴿巢原理，考慮n個房間，其中一個房間謝謝閱讀對應(yīng)一對夫婦。如果選擇n十1個人并把他們中的每一個人放到他們精品文檔放心下載夫妻所對應(yīng)的那個房間中去，那么就有一個房間含有兩個人；也就是謝謝閱讀說，已經(jīng)選擇了一對已婚夫婦。選擇n個人使他們當中一對夫妻也沒感謝閱讀有的兩種方法是選擇所有的丈夫和選擇所有的妻子，因此，n+1是保證能有一對夫婦被選中的最小的人數(shù)。精品文檔放心下載4、從應(yīng)用2得出的兩個推論推論1：如果將n個物體放入n個盒子并且沒有一個盒子是空的，那么每個盒子恰好有一個物體。感謝閱讀說明：以應(yīng)用2為例，選擇n個人，如果其中有一對夫妻，那么必然有一個房間是空的，為了保證沒有空房間，則必須從每對夫妻中選一個人，即恰好從每對夫妻中選一個人。謝謝閱讀推論2:如果將n個物體放入n個盒子并且沒有盒子被放入多于一個謝謝閱讀的物體，那么每個盒子里恰好有一個物體。說明：以應(yīng)用2為例，選擇n個人，每個房間只能是夫妻中的一個人，謝謝閱讀2n個人，恰好每個從每對夫妻當中選擇一個人。5、例題1：給定m個整數(shù)a1，a2，……，am，存在滿足0≤k≤l≤m的整數(shù)k和l，使得ak+1+ak+2+……+al能夠被m整除。感謝閱讀分析：題目通俗化，即給定m個整數(shù)的序列，其中連續(xù)幾個的和能被m整除。所以考慮序列中連續(xù)和的情況。如果其中任何一個能被感謝閱讀整除，那么結(jié)論就成立了。對此，只能先假設(shè)連續(xù)和不能被整除，即有余數(shù)。謝謝閱讀解：找出鴿子：m個正整數(shù)連續(xù)和，即a1，a1+a2，感謝閱讀a1+a2+a3，……，al+a2+a3+……+am共m個和精品文檔放心下載構(gòu)造鴿巢：連續(xù)和不能被整除，那么余數(shù)必然為 1,2，……，m-1共謝謝閱讀m-1個。如果余數(shù)為0或m，則已經(jīng)整除結(jié)論成立，所以只能是m-1個。感謝閱讀鴿巢原理：m個和，m-1個余數(shù)，那么必然有兩個余數(shù)是相同的。謝謝閱讀因此存在整數(shù)k和l，0≤k≤l≤m，使得a+a+a+……+ak及l(fā)23al+a+a+……+a除以m有相同的余數(shù)，不妨設(shè)23lal+a+a+……+a=cm+r……………①23kal+a+a+……+a=dm+r……………②，其中c，d，r為正整數(shù)。23l②-①可得ak+1+ak+2+……+a=(d-c)ml從而可得ak+1+ak+2+……+a能夠被m整除。l特例如下m=7,且整數(shù)為2,4,6,3,5,5,6。計算上面的和得到2,6,12，15,20,25,31，這些整數(shù)被7除時余數(shù)分別為2,6,5，1，6,4,3。有感謝閱讀兩個等于6的余數(shù)，這意味著結(jié)論：6+3+5=14可被7感謝閱讀整除。2：一位國際象棋大師有11周的時間備戰(zhàn)一場錦標賽，他決定每天至少下一盤棋，但為了不使自己過于疲勞他還決定每周不能下超過感謝閱讀12盤棋。證明存在連續(xù)若干天，期間這位大師恰好下了21盤棋。分析：問題通俗化即連續(xù)若干個正整數(shù)的和恰好為21。實際問題轉(zhuǎn)化為數(shù)學(xué)模型，即構(gòu)造一個用來表示若干天下棋總盤數(shù)的數(shù)列。然后用鴿巢原理證明。精品文檔放心下載證明：找出鴿子：設(shè)a1是在第一天所下的盤數(shù)，a2是在第一天和第二天所下的總盤數(shù)，a3是在第一天、第二天和第三天所下的總盤數(shù)，11周總共77天，以此類推，a77表示77天下的總盤數(shù)。因為每天至少要下一盤棋，故a1≥1，,因為在任意一周最多下12盤棋，所以感謝閱讀a77<12x11=132，則有序列1≤al＜a2＜a3＜……＜a77=132，謝謝閱讀為一個嚴格遞增序列。根據(jù)若+干個正整數(shù)的和為21這一提示，構(gòu)造數(shù)序列al+21＜a2+21＜a3+21＜……＜a77+21，此序列也是嚴謝謝閱讀格遞增序列，由此可得al，a2，a3，……，a77，al+21，a2+21，精品文檔放心下載a3+21，……，a77+21共77+77=154個數(shù)。謝謝閱讀構(gòu)造鴿巢：由1≤al＜a2＜a3＜……＜a77=132，則有，1+21≤感謝閱讀al+21＜a2+21＜a3+21＜……＜a77+21=132+21=153。由此可得謝謝閱讀al，a2，a3，……，a77，al+21，a2+21，a3+21，……，a77+21謝謝閱讀是從1到153的正整數(shù)。鴿巢原理：al，a2，a3，……，a77，al+21，a2+21，a3+21，……，精品文檔放心下載a77+21共154個數(shù)，而這些數(shù)是從1到153的正整數(shù)，從而可知其中必然存在兩個數(shù)是相等的。而al，a2，a3，……，a77嚴格遞謝謝閱讀增，各不相等。al+21，a2+21，a3+21，……，a77+21也嚴格遞謝謝閱讀增且各不相等，那么必然有如下相等的情況存在一個正整數(shù)i和一個正整數(shù)j，使得ai=aj+21。ai為大師在前i天所下的盤數(shù)之和，aj為大師在前j天所下的盤數(shù)之和，ai-aj=21即為大師從第j+1天，第j+2天到第i天，下了21盤棋。謝謝閱讀3：從整數(shù)1,2,…，200中選出101個整數(shù)。證明：在所選的這些整數(shù)之間存在兩個這樣的整數(shù)，其中一個可被另一個整除。謝謝閱讀證明之前，先介紹一種正整數(shù)的表示方法。正整數(shù)有奇數(shù)有偶數(shù)，而感謝閱讀任何一個偶數(shù)，都可以通過提取因數(shù)2，變?yōu)槠鏀?shù)與若干個2乘積的形式，例如8=1x2x2x2,24=3x2x2x2，寫成一般形式即奇數(shù)x2n（其謝謝閱讀n=1,2,3……），而這個奇數(shù)絕不會超過這個偶數(shù)的一半。下面來證明例3。謝謝閱讀證明：找出鴿子：1到200中任意選出的101個整數(shù)。謝謝閱讀構(gòu)造鴿巢：用奇數(shù)x2n的形式，把1到200的整數(shù)全部列出，精品文檔放心下載1，1x21，1x22，…………1x27精品文檔放心下載3，3x21，3x22，………3x26感謝閱讀5，5x21，5x22，……5x25………………99，99x21…………199這樣，就把1到200的全部整數(shù)列出，共100行。謝謝閱讀鴿巢原理：101個整數(shù)放到100行內(nèi)，必然有兩個整數(shù)在同一行，這兩個數(shù)表示為p=ax2m，q=ax2n,其中，a為奇數(shù)，1≤a＜199，m、n為正整數(shù)，不妨設(shè)n＞m感謝閱讀q/p=(ax2n)/(q=ax2m)=2n-m。謝謝閱讀二、鴿巢原理的加強形式1、定理2：如果要把多于mxn（比如mxn+1）個物體放進n個盒精品文檔放心下載子，那么至少有一個盒子包含m+1個或m+1個以上的物體。感謝閱讀4：空間有六個點，其中任何三點都不共線，任何四點都不共面，在每兩點之間連接直線段后涂色，將每一條這樣的線段圖成紅色或藍色，求證：不論如何涂色，一定存在一個三角形，它的三邊有相同的顏色。精品文檔放心下載證明：找出鴿子：從一點出發(fā)，連接的空間直線段有5條，即2x2+1感謝閱讀條。構(gòu)造鴿巢：紅色和藍色。鴿巢原理：根據(jù)定理2，則至少有三條線段的顏色是相同的。如圖：三條實線段顏色相同，虛線連接三條線感謝閱讀段的端點。三條虛線段顏色不同時，則與實現(xiàn)三條實線段構(gòu)成顏色三邊顏色相同的三角形。三條虛線段顏色相同，但與三謝謝閱讀條實線段顏色不同時，由虛線段構(gòu)成的三角形就已經(jīng)符合結(jié)論了。謝謝閱讀2、定理3：設(shè)ql，q2，q3，……，qn是正整數(shù)，如果將ql+q2+……感謝閱讀+qn-n+1個物體體放進n個盒子內(nèi)，那么或者第一個盒子至少包含ql個物體，或者第二個盒子至少包含q2個物體，……，或者第n個盒子至少包含qn個物體。精品文檔放心下載證明：ql+q2+……+qn-n+1=(ql-1)+(q2-1)+……+(qn-1)+1根謝謝閱讀據(jù)鴿巢原理，可得第i個盒子至少包含qi個物體，i=1,2，……精品文檔放心下載反正法：設(shè)第i個盒子含有少于qi個物體物體，那么物體的總數(shù)為(ql-1)+(q2-1)+……+(qn-1)=ql+q2+……+qn-n，比物體總數(shù)少精品文檔放心下載個，與題設(shè)矛盾，故結(jié)論成立。說明：上述結(jié)論中，當物體總數(shù)為 ql+q2+……+qn-n時，則有第i謝謝閱讀個盒子不含有qi或者更多個物體，i=1,2，……，只需將qi-1個物體謝謝閱讀分配到第i個盒子即可實現(xiàn)。例5：—個果籃裝有蘋杲、香蕉和橘子。為了保證籃子中或者至少有謝謝閱讀8個蘋果，或者至少有6個香蕉，或者至少有9個橘子，則放人籃感謝閱讀子中的水果的最小件數(shù)是多少？解：根據(jù)定理3可得，所需的水果最小件數(shù)為8+6+9-3+1=21件。謝謝閱讀3、從定理3得到的一個推論推論3：設(shè)n和r都是正整數(shù)。如果把n(r-1)+1個物體分配到n個盒子中，那么至少有一個盒子含有r或更多個物體。感謝閱讀證明：n(r-1)+1=nr-n+1，令定理3中ql=q2=……=qn=r，則結(jié)謝謝閱讀論成立。4、由推論3得到的3個平均原理qi≥r，i=1,2，……平均原理1：如果n個非負整數(shù)，ql，q2，q3，……，qn的平均謝謝閱讀數(shù)大于r-1，即(ql+q2+……+qn)/n＞(r-1),那么那么這n個數(shù)中，精品文檔放心下載至少有一個整數(shù)大于r-1（即大于或等于r）。分析：根據(jù)推論3，如果n(r-1)+1個物體平均分配到n個盒子中，除一個盒子為r個物體外，其余盒子均為r-1個。反過來，如果平均數(shù)要大于r-1，那個必然一個盒子中的物體數(shù)量要大于或等于r。感謝閱讀證法1：(ql+q2+……+qn)/n=[n(r-1)+1]/n=r-1+1/n ＞(r-1),r∈謝謝閱讀N+,則必有證法2：反證法，不妨設(shè)ql=q2=……=qn=r-1，即設(shè)這n個整數(shù)全精品文檔放心下載部比r小，則有(ql+q2+……+qn)/n=(r-1)，與題設(shè)＞r-1矛盾，所精品文檔放心下載以這n個數(shù)不可能全部小于r，則必至少有一個大于或等于 r。精品文檔放心下載平均原理2：如果n個非負整數(shù)，ql，q2，q3，……，qn的平均感謝閱讀數(shù)小于r+1，即(ql+q2+……+qn)/n＜(r+1),那么那么這n個數(shù)中，感謝閱讀至少有一個整數(shù)小于r+1。分析：根據(jù)推論3，如果n(r+1)-1（因為平均數(shù)小于r+1，所以設(shè)為n(r+1)-1，其平均數(shù)才能小于r+1）個物體平均分配到n個盒子中，除一個盒子為r個物體外，其余盒子均為r+1個。反過來，如果平均數(shù)要小于r+1，那個必然一個盒子中的物體數(shù)量要小于或等于r。精品文檔放心下載證明：(ql+q2+……+qn)/n=[n(r+1)-1]/n=r+1-1/n ＜(r+1),r∈感謝閱讀N+。平均原理3：如果n個非負整數(shù)，ql，q2，q3，……，qn的平均謝謝閱讀數(shù)至少等于r，即(ql+q2+……+qn)/n≥r,那么這n個數(shù)中，至少有精品文檔放心下載一個整數(shù)大于等于r。證明：令平均原理中的r-1=u，則結(jié)論成立。例5：有兩個碟子，其中一個比另一個小，它們都被分成 200個均等精品文檔放心下載的扇形。在大碟子中，任選100個扇形并著成紅色，而其余的100個扇形著成藍色。在小碟子中，每一個扇形或者著成紅色，或者著成藍色，所著紅色扇形和藍色扇形的數(shù)目沒有限制。然后，將小碟子放到大碟子上面使兩個碟子的中心重合。證明：能夠?qū)蓚€碟子的扇形對齊使得小碟子和大碟子上相同顏色重合的扇形的數(shù)目至少是100個。謝謝閱讀證明：設(shè)小碟子藍色扇形的數(shù)量為x，紅色扇形的數(shù)量為y。大碟子不動，轉(zhuǎn)動小碟子，每轉(zhuǎn)2π/200角度，就有一次對應(yīng)，于是共有精品文檔放心下載200次對應(yīng)。大碟子的紅色扇形有100個，小碟子的紅色扇形有x個，那么轉(zhuǎn)動一周，小碟子每個紅色扇形與大碟子對應(yīng)100次，所以紅色扇形對應(yīng)的次數(shù)共有100x次，同理，藍色對應(yīng)的次數(shù)為100y次，顏色相同的對應(yīng)次數(shù)為100x+100y=100(x+y)=100*200=20000精品文檔放心下載次，那么每個位置顏色相同的平均次數(shù)為20000/200=100，根據(jù)平均原理3，感謝閱讀則有某個位置顏色相同的扇形數(shù)目至少為 100個。習(xí) 題1、在邊長為1的正方形內(nèi)任意放置5個點，求證其中必有兩個點，這兩個點之間的距離不大于2/2。感謝閱讀證明：如圖將正方形等分成4份，根據(jù)定理1可知，必然有2個點落在正方形的1/4區(qū)域內(nèi)，這兩點的距離小于1/4小正方形的對角線長2/2。精品文檔放心下載2、在邊長為1的正方形內(nèi)任意放入9個點，證明：以這些點為頂點的許許多多三角形中，必有一個三角形的面積不超過1/8。精品文檔放心下載證明：如圖，將正方形用平行于邊的平行線等分為4分，取1/4。由定理2可知，2x4+1=9個點放入4個盒子內(nèi)，比然有一個盒子內(nèi)有精品文檔放心下載2+1=3個點，現(xiàn)在討論這三個點構(gòu)成的三角形的面積。感謝閱讀S△ABC=S△AA’C+S△AA’B≤1xhx1/2+1x(1/4-h)x1/2=1/8。3、證明：每個由n2+1個實數(shù)構(gòu)成的數(shù)列，a，a，……，an2+112或者含有長度為n+1的遞增子數(shù)列，或者含有長度為n+l的遞減子數(shù)列。謝謝閱讀分析：當n=1時，n2+1=2，即該數(shù)列的長度為2，n+1=2，即含有長度為2的單調(diào)子數(shù)列。兩個實數(shù)構(gòu)成實數(shù)列，必然是單調(diào)的。當n=2時，n2+1=5，即該數(shù)列的長度為5，n+1=3，按題意應(yīng)該能從中找出長度為3的單調(diào)子數(shù)列。這就是題目所要表達的意思。在證明之前，補充一下與數(shù)列相關(guān)的定義。謝謝閱讀數(shù)列：按照一定順序排列起來的數(shù)串a(chǎn)1，a2，……，an，an+1，……，精品文檔放心下載叫數(shù)列。數(shù)列的長度：數(shù)列項數(shù)的數(shù)量成為數(shù)量的長度。有窮數(shù)列：數(shù)列的項數(shù)是有限的稱為有窮數(shù)列。無窮數(shù)列：數(shù)列的項數(shù)是無限的稱為無窮數(shù)列。al≤a2≤a3≤……≤an≤an+1≤……則為單調(diào)遞增數(shù)列。精品文檔放心下載al≥a2≥a3≥……≥an≥an+1≥……則為單調(diào)遞減數(shù)列。謝謝閱讀單調(diào)遞增數(shù)列和單調(diào)遞減數(shù)列統(tǒng)稱為單調(diào)數(shù)列。由相等的數(shù)構(gòu)成的數(shù)列也可稱為單調(diào)數(shù)列。去掉上述單增和單減數(shù)列中的等號，則為嚴格單調(diào)數(shù)列。謝謝閱讀從原數(shù)列中抽出一部分，但不改變它們在原數(shù)列中的先后順序，這樣感謝閱讀得到的一個新數(shù)列稱為原數(shù)列的子數(shù)列。子數(shù)列用ai1，ai2，……，精品文檔放心下載ain，ain+1，……，表示，其腳標必須滿足精品文檔放心下載1≤i1≤i2≤……≤in≤in+1≤……原數(shù)列本身也是其子數(shù)列。原數(shù)列中抽出1項構(gòu)成的數(shù)列也是其子數(shù)謝謝閱讀列。下面證明例3。證明：記原數(shù)列為a1，a2，……，an，an+1，……an2+1。先考慮感謝閱讀遞減的情況。設(shè)以ai為首項的最長遞減數(shù)列的長度為Ni。下面看一個特例，任意寫一個長度為5的數(shù)列如，5,9,88,22,31，以5為首項的遞減數(shù)列的長度為1，以9為首項的遞減數(shù)列的長度為1，以88為首項的遞減數(shù)列的長度為3,……由此可知，Ni≥1，且對于長度為精品文檔放心下載n2+1的數(shù)列，Ni為n2+1個正整數(shù)。如果原數(shù)列中沒有長度為n+1的遞減數(shù)列，則Ni為1到n之間的n2+1個正整數(shù)，根據(jù)定理2可知，其中必然有n+1個數(shù)是相等的。例如，n=3時，n2+1=10，謝謝閱讀個數(shù)分配到1、2、3三個盒子中，必然有4個數(shù)都為1，或者都感謝閱讀2，或者都為3。n+1個數(shù)相等記為Ni1=Ni2=……=Nin+1，其腳標適合1≤i1≤i2≤……≤in≤in+1≤……≤in2+1。這就是說，原數(shù)列中有n+1個遞減子數(shù)列的長度是相等的。任意列出其中兩個如下：精品文檔放心下載ai1，ai5，……，ain，ain+1 ……………①精品文檔放心下載ai2，ai6，……，ain+2，ain+8，……………②精品文檔放心下載其腳標適合1≤i1≤i2≤……≤in≤in+1≤……≤in2+1精品文檔放心下載比較ai1，ai2，兩個不同的實數(shù)比較，必然有大小。作為遞減數(shù)列，謝謝閱讀ai1＞ai2時，必然有數(shù)列①比數(shù)列②多一項。當ai1＜ai2時，必然有數(shù)列②比數(shù)列①多一項。這與Ni1=Ni2=……=Nin+1是矛盾的。所以對于ai1＞ai2的情況，必然有ai1＜ai2成立，以此類推，n+1感謝閱讀個長度相等的遞減數(shù)列必然存在一個長度為n+1的遞增數(shù)列。對于ai1＜ai2的情況也是如此。如果設(shè)原數(shù)列中沒有長度為n+1的遞增子數(shù)列，同理可證必然存在一個長度為n+1的遞減子數(shù)列。謝謝閱讀4、一個國際社團的成員來自6個國家，共有1978人，用1,2，……精品文檔放心下載1978編號，證明：該社團至少有一個成員的編號與他的同胞的編號之和相等或是其一個同胞的編號的兩倍。精品文檔放心下載證明：該題目與下面的敘述是等價的，即把 1,2，……1978按任意方感謝閱讀式分成6組，則必有一組具備這樣的性質(zhì)，其中至少有一個數(shù)或是等于同一組中其它兩數(shù)的和，或是等于另一數(shù)的兩倍。題目改寫是簡化明確題目的一種方法。謝謝閱讀反證法，設(shè)任何一組數(shù)都不具備這樣的性質(zhì)，那么應(yīng)該具備下列性質(zhì)：*同一組中任何兩個數(shù)之差必不在這個組中，若a，b和b-a這三個數(shù)在同一組中，則有a+(b-a)=b,就具備欲證的性質(zhì)了。謝謝閱讀①由1978/6＞329，根據(jù)定理1可知，必然存在一個數(shù)組A，其中至少含有330個數(shù)。對于這330個數(shù)，記最大的為mA,mA減去其精品文檔放心下載329個數(shù)，所得的差是既為正整數(shù)又小于1978的329個數(shù)，根據(jù)性質(zhì)*可知，這329個數(shù)一定不在數(shù)組A中，必然在其它的5個數(shù)組中。精品文檔放心下載②由329/5＞65，根據(jù)定理1，必然存在一個數(shù)組B，其中至少含有上面329個數(shù)中的66個數(shù)。對于這66個數(shù)，記最大的為mB,mB減去其它65個數(shù)，所得的差是既為正整數(shù)又小于1978的65個數(shù)，根據(jù)性質(zhì)*可知，這65個數(shù)一定不在數(shù)組B中，同時也不在數(shù)組A中。假若其中一個數(shù)(mB-b)∈A，其中mB=mA-a1，b=