2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《抽屜原理》.doc
《2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《抽屜原理》.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《抽屜原理》.doc(10頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料抽屜原理“抽屜原理”最先是由19世紀(jì)的德國(guó)數(shù)學(xué)家迪里赫萊(Dirichlet)運(yùn)用于解決數(shù)學(xué)問(wèn)題的,所以又稱(chēng)“迪里赫萊原理”,也有稱(chēng)“鴿巢原理”的。這個(gè)原理可以簡(jiǎn)單地?cái)⑹鰹椤鞍?0個(gè)蘋(píng)果,任意分放在9個(gè)抽屜里,則至少有一個(gè)抽屜里含有兩個(gè)或兩個(gè)以上的蘋(píng)果”。這個(gè)道理是非常明顯的,但應(yīng)用它卻可以解決許多有趣的問(wèn)題,并且常常得到一些令人驚異的結(jié)果。抽屜原理是國(guó)際國(guó)內(nèi)各級(jí)各類(lèi)數(shù)學(xué)競(jìng)賽中的重要內(nèi)容,本講就來(lái)學(xué)習(xí)它的有關(guān)知識(shí)及其應(yīng)用。 (一) 抽屜原理的基本形式 定理1、如果把n+1個(gè)元素分成n個(gè)集合,那么不管怎么分,都存在一個(gè)集合,其中至少有兩個(gè)元素。 證明:(用反證法)若不存在至少有兩個(gè)元素的集合,則每個(gè)集合至多1個(gè)元素,從而n個(gè)集合至多有n個(gè)元素,此與共有n+1個(gè)元素矛盾,故命題成立。 在定理1的敘述中,可以把“元素”改為“物件”,把“集合”改成“抽屜”,抽屜原理正是由此得名。 同樣,可以把“元素”改成“鴿子”,把“分成n個(gè)集合”改成“飛進(jìn)n個(gè)鴿籠中”?!傍澔\原理”由此得名。 例題講解1 已知在邊長(zhǎng)為1的等邊三角形內(nèi)(包括邊界)有任意五個(gè)點(diǎn)(圖1)。證明:至少有兩個(gè)點(diǎn)之間的距離不大于2從1-100的自然數(shù)中,任意取出51個(gè)數(shù),證明其中一定有兩個(gè)數(shù),它們中的一個(gè)是另一個(gè)的整數(shù)倍。 3從前25個(gè)自然數(shù)中任意取出7個(gè)數(shù),證明:取出的數(shù)中一定有兩個(gè)數(shù),這兩個(gè)數(shù)中大數(shù)不超過(guò)小數(shù)的1.5倍。4已給一個(gè)由10個(gè)互不相等的兩位十進(jìn)制正整數(shù)組成的集合。求證:這個(gè)集合必有兩個(gè)無(wú)公共元素的子集合,各子集合中各數(shù)之和相等。5在坐標(biāo)平面上任取五個(gè)整點(diǎn)(該點(diǎn)的橫縱坐標(biāo)都取整數(shù)),證明:其中一定存在兩個(gè)整點(diǎn),它們的連線中點(diǎn)仍是整點(diǎn)。6在任意給出的100個(gè)整數(shù)中,都可以找出若干個(gè)數(shù)來(lái)(可以是一個(gè)數(shù)),它們的和可被100整除。7 17名科學(xué)家中每?jī)擅茖W(xué)家都和其他科學(xué)家通信,在他們通信時(shí),只討論三個(gè)題目,而且任意兩名科學(xué)家通信時(shí)只討論一個(gè)題目,證明:其中至少有三名科學(xué)家,他們相互通信時(shí)討論的是同一個(gè)題目。 課后練習(xí)1幼兒園買(mǎi)來(lái)了不少白兔、熊貓、長(zhǎng)頸鹿塑料玩具,每個(gè)小朋友任意選擇兩件,那么不管怎樣挑選,在任意七個(gè)小朋友中總有兩個(gè)彼此選的玩具都相同,試說(shuō)明道理.2正方體各面上涂上紅色或藍(lán)色的油漆(每面只涂一種色),證明正方體一定有三個(gè)面顏色相同.3把1到10的自然數(shù)擺成一個(gè)圓圈,證明一定存在在個(gè)相鄰的數(shù),它們的和數(shù)大于17.4有紅襪2雙,白襪3雙,黑襪4雙,黃襪5雙,藍(lán)襪6雙(每雙襪子包裝在一起)若取出9雙,證明其中必有黑襪或黃襪2雙.5在邊長(zhǎng)為1的正方形內(nèi),任意給定13個(gè)點(diǎn),試證:其中必有4個(gè)點(diǎn),以此4點(diǎn)為頂點(diǎn)的四邊開(kāi)面積不超過(guò)(假定四點(diǎn)在一直線上構(gòu)成面積為零的四邊形).6在一條筆直的馬路旁種樹(shù),從起點(diǎn)起,每隔一米種一棵樹(shù),如果把三塊“愛(ài)護(hù)樹(shù)木”的小牌分別掛在三棵樹(shù)上,那么不管怎樣掛,至少有兩棵掛牌的樹(shù)之間的距離是偶數(shù)(以米為單位),這是為什么?課后練習(xí)答案1.解 從三種玩具中挑選兩件,搭配方式只能是下面六種:(兔、兔),(兔、熊貓),(兔、長(zhǎng)頸鹿),(熊貓、熊貓),(熊貓、長(zhǎng)頸鹿),(長(zhǎng)頸鹿、長(zhǎng)頸鹿)把每種搭配方式看作一個(gè)抽屜,把7個(gè)小朋友看作物體,那么根據(jù)原則1,至少有兩個(gè)物體要放進(jìn)同一個(gè)抽屜里,也就是說(shuō),至少兩人挑選玩具采用同一搭配方式,選的玩具相同.原則2 如果把mn+k(k1)個(gè)物體放進(jìn)n個(gè)抽屜,則至少有一個(gè)抽屜至多放進(jìn)m+1個(gè)物體.證明同原則相仿.若每個(gè)抽屜至多放進(jìn)m個(gè)物體,那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體,與題設(shè)不符,故不可能.原則1可看作原則2的物例(m=1)2.證明把兩種顏色當(dāng)作兩個(gè)抽屜,把正方體六個(gè)面當(dāng)作物體,那么6=22+2,根據(jù)原則二,至少有三個(gè)面涂上相同的顏色.3.證明 如圖12-1,設(shè)a1,a2,a3,a9,a10分別代表不超過(guò)10的十個(gè)自然數(shù),它們圍成一個(gè)圈,三個(gè)相鄰的數(shù)的組成是(a1,a2,a3),(a2,a3,a4),(a3,a4,a5),,(a9,a10,a1),(a10,a1,a2)共十組.現(xiàn)把它們看作十個(gè)抽屜,每個(gè)抽屜的物體數(shù)是a1+a2+a3,a2+a3+a4,a3+a4+a5,a9+a10+a1,a10+a1+a2,由于(a1+a2+a3)+(a2+a3+a4)+(a9+a10+a1)+(a10+a1+a2)=3(a1+a2+a9+a10)=3(1+2+9+10)根據(jù)原則2,至少有一個(gè)括號(hào)內(nèi)的三數(shù)和不少于17,即至少有三個(gè)相鄰的數(shù)的和不小于17.原則1、原則2可歸結(jié)到期更一般形式:原則3把m1+m2+mn+k(k1)個(gè)物體放入n個(gè)抽屜里,那么或在第一個(gè)抽屜里至少放入m1+1個(gè)物體,或在第二個(gè)抽屜里至少放入m2+1個(gè)物體,或在第n個(gè)抽屜里至少放入mn+1個(gè)物體.證明假定第一個(gè)抽屜放入物體的數(shù)不超過(guò)m1個(gè),第二個(gè)抽屜放入物體的數(shù)不超過(guò)m2個(gè),第n個(gè)抽屜放入物體的個(gè)數(shù)不超過(guò)mn,那么放入所有抽屜的物體總數(shù)不超過(guò)m1+m2+mn個(gè),與題設(shè)矛盾.4.證明 除可能取出紅襪、白襪3雙外.還至少?gòu)钠渌N顏色的襪子里取出4雙,根據(jù)原理3,必在黑襪或黃襪、藍(lán)襪里取2雙.上面數(shù)例論證的似乎都是“存在”、“總有”、“至少有”的問(wèn)題,不錯(cuò),這正是抽屜原則的主要作用.需要說(shuō)明的是,運(yùn)用抽屜原則只是肯定了“存在”、“總有”、“至少有”,卻不能確切地指出哪個(gè)抽屜里存在多少.制造抽屜是運(yùn)用原則的一大關(guān)鍵首先要指出的是,對(duì)于同一問(wèn)題,??梢罁?jù)情況,從不同角度設(shè)計(jì)抽屜,從而導(dǎo)致不同的制造抽屜的方式.5.證明如圖12-2把正方形分成四個(gè)相同的小正方形.因13=34+1,根據(jù)原則2,總有4點(diǎn)落在同一個(gè)小正方形內(nèi)(或邊界上),以此4點(diǎn)為頂點(diǎn)的四邊形的面積不超過(guò)小正方形的面積,也就不超過(guò)整個(gè)正方形面積的.事實(shí)上,由于解決問(wèn)題的核心在于將正方形分割成四個(gè)面積相等的部分,所以還可以把正方形按圖12-3(此處無(wú)圖)所示的形式分割.合理地制造抽屜必須建立在充分考慮問(wèn)題自身特點(diǎn)的基礎(chǔ)上.6.解如圖12-4(設(shè)掛牌的三棵樹(shù)依次為A、B、C.AB=a,BC=b,若a、b中有一為偶數(shù),命題得證.否則a、b均為奇數(shù),則AC=a+b為偶數(shù),命題得證.下面我們換一個(gè)角度考慮:給每棵樹(shù)上編上號(hào),于是兩棵樹(shù)之間的距離就是號(hào)碼差,由于樹(shù)的號(hào)碼只能為奇數(shù)和偶數(shù)兩類(lèi),那么掛牌的三棵樹(shù)號(hào)碼至少有兩個(gè)同為奇數(shù)或偶數(shù),它們的差必為偶數(shù),問(wèn)題得證.后一證明十分巧妙,通過(guò)編號(hào)碼,將兩樹(shù)間距離轉(zhuǎn)化為號(hào)碼差.這種轉(zhuǎn)化的思想方法是一種非常重要的數(shù)學(xué)方法例題答案:1分析:5個(gè)點(diǎn)的分布是任意的。如果要證明“在邊長(zhǎng)為1的等邊三角形內(nèi)(包括邊界)有5個(gè)點(diǎn),那么這5個(gè)點(diǎn)中一定有距離不大于的兩點(diǎn)”,則順次連接三角形三邊中點(diǎn),即三角形的三條中位線,可以分原等邊三角形為4個(gè)全等的邊長(zhǎng)為的小等邊三角形,則5個(gè)點(diǎn)中必有2點(diǎn)位于同一個(gè)小等邊三角形中(包括邊界),其距離便不大于。 以上結(jié)論要由定理“三角形內(nèi)(包括邊界)任意兩點(diǎn)間的距離不大于其最大邊長(zhǎng)”來(lái)保證,下面我們就來(lái)證明這個(gè)定理。如圖2,設(shè)BC是ABC的最大邊,P,M是ABC內(nèi)(包括邊界)任意兩點(diǎn),連接PM,過(guò)P分別作AB、BC邊的平行線,過(guò)M作AC邊的平行線,設(shè)各平行線交點(diǎn)為P、Q、N,那么PQN=C,QNP=A 因?yàn)锽CAB,所以AC,則QNPPQN,而QMPQNPPQN(三角形的外角大于不相鄰的內(nèi)角),所以 PQPM。顯然BCPQ,故BCPM。 由此我們可以推知,邊長(zhǎng)為的等邊三角形內(nèi)(包括邊界)兩點(diǎn)間的距離不大于。 說(shuō)明: (1)這里是用等分三角形的方法來(lái)構(gòu)造“抽屜”。類(lèi)似地,還可以利用等分線段、等分正方形的方法來(lái)構(gòu)造“抽屜”。例如“任取n+1個(gè)正數(shù)ai,滿足0ai1(i=1,2,n+1),試證明:這n+1個(gè)數(shù)中必存在兩個(gè)數(shù),其差的絕對(duì)值小于”。又如:“在邊長(zhǎng)為1的正方形內(nèi)任意放置五個(gè)點(diǎn),求證:其中必有兩點(diǎn),這兩點(diǎn)之間的距離不大于。 (2)例1中,如果把條件(包括邊界)去掉,則結(jié)論可以修改為:至少有兩個(gè)點(diǎn)之間的距離小于,請(qǐng)讀者試證之,并比較證明的差別。 (3)用同樣的方法可證明以下結(jié)論: i)在邊長(zhǎng)為1的等邊三角形中有n2+1個(gè)點(diǎn),這n2+1個(gè)點(diǎn)中一定有距離不大于的兩點(diǎn)。 ii)在邊長(zhǎng)為1的等邊三角形內(nèi)有n2+1個(gè)點(diǎn),這n2+1個(gè)點(diǎn)中一定有距離小于的兩點(diǎn)。 (4)將(3)中兩個(gè)命題中的等邊三角形換成正方形,相應(yīng)的結(jié)論中的換成,命題仍然成立。 (5)讀者還可以考慮相反的問(wèn)題:一般地,“至少需要多少個(gè)點(diǎn),才能夠使得邊長(zhǎng)為1的正三角形內(nèi)(包括邊界)有兩點(diǎn)其距離不超過(guò)”。 2分析:本題似乎茫無(wú)頭緒,從何入手?其關(guān)鍵何在?其實(shí)就在“兩個(gè)數(shù)”,其中一個(gè)是另一個(gè)的整數(shù)倍。我們要構(gòu)造“抽屜”,使得每個(gè)抽屜里任取兩個(gè)數(shù),都有一個(gè)是另一個(gè)的整數(shù)倍,這只有把公比是正整數(shù)的整個(gè)等比數(shù)列都放進(jìn)去同一個(gè)抽屜才行,這里用得到一個(gè)自然數(shù)分類(lèi)的基本知識(shí):任何一個(gè)正整數(shù)都可以表示成一個(gè)奇數(shù)與2的方冪的積,即若mN+,KN+,nN,則m=(2k-1)2n,并且這種表示方式是唯一的,如1=12,2=121,3=32, 證明:因?yàn)槿魏我粋€(gè)正整數(shù)都能表示成一個(gè)奇數(shù)乘2的方冪,并且這種表示方法是唯一的,所以我們可把1-100的正整數(shù)分成如下50個(gè)抽屜(因?yàn)?-100中共有50個(gè)奇數(shù)): (1)1,12,122,123,124,125,126;(2)3,32,322,323,324,325;(3)5,52,522,523,524;(4)7,72,722,723;(5)9,92,922,923;(6)11,112,1122,1123;(25)49,492;(26)51;(50)99。 這樣,1-100的正整數(shù)就無(wú)重復(fù),無(wú)遺漏地放進(jìn)這50個(gè)抽屜內(nèi)了。從這100個(gè)數(shù)中任取51個(gè)數(shù),也即從這50個(gè)抽屜內(nèi)任取51個(gè)數(shù),根據(jù)抽屜原則,其中必定至少有兩個(gè)數(shù)屬于同一個(gè)抽屜,即屬于(1)-(25)號(hào)中的某一個(gè)抽屜,顯然,在這25個(gè)抽屜中的任何同一個(gè)抽屜內(nèi)的兩個(gè)數(shù)中,一個(gè)是另一個(gè)的整數(shù)倍。 說(shuō)明: (1)從上面的證明中可以看出,本題能夠推廣到一般情形:從1-2n的自然數(shù)中,任意取出n+1個(gè)數(shù),則其中必有兩個(gè)數(shù),它們中的一個(gè)是另一個(gè)的整數(shù)倍。想一想,為什么?因?yàn)?-2n中共含1,3,2n-1這n個(gè)奇數(shù),因此可以制造n個(gè)抽屜,而n+1n,由抽屜原則,結(jié)論就是必然的了。給n以具體值,就可以構(gòu)造出不同的題目。例2中的n取值是50,還可以編制相反的題目,如:“從前30個(gè)自然數(shù)中最少要(不看這些數(shù)而以任意方式地)取出幾個(gè)數(shù),才能保證取出的數(shù)中能找到兩個(gè)數(shù),其中較大的數(shù)是較小的數(shù)的倍數(shù)?” (2)如下兩個(gè)問(wèn)題的結(jié)論都是否定的(n均為正整數(shù))想一想,為什么? 從2,3,4,2n+1中任取n+1個(gè)數(shù),是否必有兩個(gè)數(shù),它們中的一個(gè)是另一個(gè)的整數(shù)倍? 從1,2,3,2n+1中任取n+1個(gè)數(shù),是否必有兩個(gè)數(shù),它們中的一個(gè)是另一個(gè)的整數(shù)倍?你能舉出反例,證明上述兩個(gè)問(wèn)題的結(jié)論都是否定的嗎? (3)如果將(2)中兩個(gè)問(wèn)題中任取的n+1個(gè)數(shù)增加1個(gè),都改成任取n+2個(gè)數(shù),則它們的結(jié)論是肯定的還是否定的?你能判斷證明嗎? 3證明:把前25個(gè)自然數(shù)分成下面6組: 1; 2,3; 4,5,6; 7,8,9,10; 11,12,13,14,15,16; 17,18,19,20,21,22,23, 因?yàn)閺那?5個(gè)自然數(shù)中任意取出7個(gè)數(shù),所以至少有兩個(gè)數(shù)取自上面第組到第組中的某同一組,這兩個(gè)數(shù)中大數(shù)就不超過(guò)小數(shù)的1.5倍。 說(shuō)明: (1)本題可以改變敘述如下:在前25個(gè)自然數(shù)中任意取出7個(gè)數(shù),求證其中存在兩個(gè)數(shù),它們相互的比值在內(nèi)。 顯然,必須找出一種能把前25個(gè)自然數(shù)分成6(7-1=6)個(gè)集合的方法,不過(guò)分類(lèi)時(shí)有一個(gè)限制條件:同一集合中任兩個(gè)數(shù)的比值在內(nèi),故同一集合中元素的數(shù)值差不得過(guò)大。這樣,我們可以用如上一種特殊的分類(lèi)法:遞推分類(lèi)法: 從1開(kāi)始,顯然1只能單獨(dú)作為1個(gè)集合1;否則不滿足限制條件。 能與2同屬于一個(gè)集合的數(shù)只有3,于是2,3為一集合。 如此依次遞推下去,使若干個(gè)連續(xù)的自然數(shù)屬于同一集合,其中最大的數(shù)不超過(guò)最小的數(shù)的倍,就可以得到滿足條件的六個(gè)集合。 (2)如果我們按照(1)中的遞推方法依次造“抽屜”,則第7個(gè)抽屜為 26,27,28,29,30,31,32,33,34,35,36,37,38,39;第8個(gè)抽屜為:40,41,42,60;第9個(gè)抽屜為:61,62,63,90,91; 那么我們可以將例3改造為如下一系列題目: (1)從前16個(gè)自然數(shù)中任取6個(gè)自然數(shù);(2)從前39個(gè)自然數(shù)中任取8個(gè)自然數(shù);(3)從前60個(gè)自然數(shù)中任取9個(gè)自然數(shù);(4)從前91個(gè)自然數(shù)中任取10個(gè)自然數(shù);都可以得到同一個(gè)結(jié)論:其中存在2個(gè)數(shù),它們相互的比值在內(nèi)。 上述第(4)個(gè)命題,就是前蘇聯(lián)基輔第49屆數(shù)學(xué)競(jìng)賽試題。如果我們改變區(qū)間(pq)端點(diǎn)的值,則又可以構(gòu)造出一系列的新題目來(lái)。 4.分析與解答:一個(gè)有著10個(gè)元素的集合,它共有多少個(gè)可能的子集呢?由于在組成一個(gè)子集的時(shí)候,每一個(gè)元素都有被取過(guò)來(lái)或者不被取過(guò)來(lái)兩種可能,因此,10個(gè)元素的集合就有210=1024個(gè)不同的構(gòu)造子集的方法,也就是,它一共有1024個(gè)不同的子集,包括空集和全集在內(nèi)。空集與全集顯然不是考慮的對(duì)象,所以剩下1024-2=1022個(gè)非空真子集。 再來(lái)看各個(gè)真子集中一切數(shù)字之和。用N來(lái)記這個(gè)和數(shù),很明顯: 10N91+92+93+94+95+96+97+98+99=855這表明N至多只有855-9=846種不同的情況。由于非空真子集的個(gè)數(shù)是1022,1022846,所以一定存在兩個(gè)子集A與B,使得A中各數(shù)之和=B中各數(shù)之和。 若AB=,則命題得證,若AB=C,即A與B有公共元素,這時(shí)只要剔除A與B中的一切公有元素,得出兩個(gè)不相交的子集A1與B1,很顯然 A1中各元素之和=B1中各元素之和,因此A1與B1就是符合題目要求的子集。 說(shuō)明:本例能否推廣為如下命題: 已給一個(gè)由m個(gè)互不相等的n位十進(jìn)制正整數(shù)組成的集合。求證:這個(gè)集合必有兩個(gè)無(wú)公共元素的子集合,各子集合中各數(shù)之和相等。 請(qǐng)讀者自己來(lái)研究這個(gè)問(wèn)題。 5分析與解答:由中點(diǎn)坐標(biāo)公式知,坐標(biāo)平面兩點(diǎn)(x1,y1)、(x2,y2)的中點(diǎn)坐標(biāo)是。欲使都是整數(shù),必須而且只須x1與x2,y1與y2的奇偶性相同。坐標(biāo)平面上的任意整點(diǎn)按照橫縱兩個(gè)坐標(biāo)的奇偶性考慮有且只有如下四種:(奇數(shù)、奇數(shù)),(偶數(shù),偶數(shù)),(奇數(shù),偶數(shù)),(偶數(shù),奇數(shù))以此構(gòu)造四個(gè)“抽屜”,則在坐標(biāo)平面上任取五個(gè)整點(diǎn),那么至少有兩個(gè)整點(diǎn),屬于同一個(gè)“抽屜”因此它們連線的中點(diǎn)就必是整點(diǎn)。 說(shuō)明:我們可以把整點(diǎn)的概念推廣:如果(x1,x2,xn)是n維(元)有序數(shù)組,且x1,x2,xn中的每一個(gè)數(shù)都是整數(shù),則稱(chēng)(x1,x2,xn)是一個(gè)n維整點(diǎn)(整點(diǎn)又稱(chēng)格點(diǎn))。如果對(duì)所有的n維整點(diǎn)按每一個(gè)xi的奇偶性來(lái)分類(lèi),由于每一個(gè)位置上有奇、偶兩種可能性,因此共可分為222=2n個(gè)類(lèi)。這是對(duì)n維整點(diǎn)的一種分類(lèi)方法。當(dāng)n=3時(shí),23=8,此時(shí)可以構(gòu)造命題:“任意給定空間中九個(gè)整點(diǎn),求證它們之中必有兩點(diǎn)存在,使連接這兩點(diǎn)的直線段的內(nèi)部含有整點(diǎn)”。這就是1971年的美國(guó)普特南數(shù)學(xué)競(jìng)賽題。在n=2的情形,也可以構(gòu)造如下的命題:“平面上任意給定5個(gè)整點(diǎn)”,對(duì)“它們連線段中點(diǎn)為整點(diǎn)”的4個(gè)命題中,為真命題的是: (A)最少可為0個(gè),最多只能是5個(gè) (B)最少可為0個(gè),最多可取10個(gè)(C)最少為1個(gè),最多為5個(gè) (D)最少為1個(gè),最多為10個(gè)(正確答案(D) 6分析:本題也似乎是茫無(wú)頭緒,無(wú)從下手,其關(guān)鍵何在?仔細(xì)審題,它們的“和”能“被100整除”應(yīng)是做文章的地方。如果把這100個(gè)數(shù)排成一個(gè)數(shù)列,用Sm記其前m項(xiàng)的和,則其可構(gòu)造S1,S2,S100共100個(gè)和數(shù)。討論這些“和數(shù)”被100除所得的余數(shù)。注意到S1,S2,S100共有100個(gè)數(shù),一個(gè)數(shù)被100除所得的余數(shù)有0,1,2,99共100種可能性?!疤O(píng)果”數(shù)與“抽屜”數(shù)一樣多,如何排除“故障”? 證明:設(shè)已知的整數(shù)為a1,a2,a100考察數(shù)列a1,a2,a100的前n項(xiàng)和構(gòu)成的數(shù)列S1,S2,S100。 如果S1,S2,S100中有某個(gè)數(shù)可被100整除,則命題得證。否則,即S1,S2,S100均不能被100整除,這樣,它們被100除后余數(shù)必是1,2,99中的元素。由抽屜原理I知,S1,S2,S100中必有兩個(gè)數(shù),它們被100除后具有相同的余數(shù)。不妨設(shè)這兩個(gè)數(shù)為Si,Sj(ij),則100(Sj-Si),即100。命題得證。 說(shuō)明:有時(shí)候直接對(duì)所給對(duì)象作某種劃分,是很難構(gòu)造出恰當(dāng)?shù)某閷系?。這時(shí)候,我們需要對(duì)所給對(duì)象先作一些變換,然后對(duì)變換得到的對(duì)象進(jìn)行分類(lèi),就可以構(gòu)造出恰當(dāng)?shù)某閷?。本題直接對(duì)an進(jìn)行分類(lèi)是很難奏效的。但由an構(gòu)造出Sn后,再對(duì)Sn進(jìn)行分類(lèi)就容易得多。 另外,對(duì)Sn按模100的剩余類(lèi)劃分時(shí),只能分成100個(gè)集合,而Sn只有100項(xiàng),似乎不能應(yīng)用抽屜原則。但注意到余數(shù)為0的類(lèi)恰使結(jié)論成立,于是通過(guò)分別情況討論后,就可去掉余數(shù)為0的類(lèi),從而轉(zhuǎn)化為100個(gè)數(shù)分配在剩下的99個(gè)類(lèi)中。這種處理問(wèn)題的方法應(yīng)當(dāng)學(xué)會(huì),它會(huì)助你從“山窮水盡疑無(wú)路”時(shí),走入“柳暗花明又一村”中。 最后,本例的結(jié)論及證明可以推廣到一般情形(而且有加強(qiáng)的環(huán)節(jié)): 在任意給定的n個(gè)整數(shù)中,都可以找出若干個(gè)數(shù)來(lái)(可以是一個(gè)數(shù)),它們的和可被n整除,而且,在任意給定的排定順序的n個(gè)整數(shù)中,都可以找出若干個(gè)連續(xù)的項(xiàng)(可以是一項(xiàng)),它們的和可被n整除。 將以上一般結(jié)論中的n賦以相應(yīng)的年份的值如xx,xx,xx,就可以編出相應(yīng)年份的試題來(lái)。如果再賦以特殊背景,則可以編出非常有趣的數(shù)學(xué)智力題來(lái),如下題: 有100只猴子在吃花生,每只猴子至少吃了1粒花生,多者不限。請(qǐng)你證明:一定有若干只猴子(可以是一只),它們所吃的花生的粒數(shù)總和恰好是100的倍數(shù)。 7證明:視17個(gè)科學(xué)家為17個(gè)點(diǎn),每?jī)蓚€(gè)點(diǎn)之間連一條線表示這兩個(gè)科學(xué)家在討論同一個(gè)問(wèn)題,若討論第一個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連紅線,若討論第2個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連條黃線,若討論第3個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連條藍(lán)線。三名科學(xué)家研究同一個(gè)問(wèn)題就轉(zhuǎn)化為找到一個(gè)三邊同顏色的三角形。 考慮科學(xué)家A,他要與另外的16位科學(xué)家每人通信討論一個(gè)問(wèn)題,相應(yīng)于從A出發(fā)引出16條線段,將它們?nèi)境?種顏色,而16=35+1,因而必有6=5+1條同色,不妨記為AB1,AB2,AB3,AB4,AB5,AB6同紅色,若Bi(i=1,2,6)之間有紅線,則出現(xiàn)紅色三角線,命題已成立;否則B1,B2,B3,B4,B5,B6之間的連線只染有黃藍(lán)兩色。 考慮從B1引出的5條線,B1B2,B1B3,B1B4,B1B5,B1B6,用兩種顏色染色,因?yàn)?=22+1,故必有3=2+1條線段同色,假設(shè)為黃色,并記它們?yōu)锽1B2,B1B3,B1B4。這時(shí)若B2,B3,B4之間有黃線,則有黃色三角形,命題也成立,若B2,B3,B4,之間無(wú)黃線,則B2,B3,B4,必為藍(lán)色三角形,命題仍然成立。 說(shuō)明:(1)本題源于一個(gè)古典問(wèn)題-世界上任意6個(gè)人中必有3人互相認(rèn)識(shí),或互相不認(rèn)識(shí)。(美國(guó)普特南數(shù)學(xué)競(jìng)賽題)。 (2)將互相認(rèn)識(shí)用紅色表示,將互相不認(rèn)識(shí)用藍(lán)色表示,(1)將化為一個(gè)染色問(wèn)題,成為一個(gè)圖論問(wèn)題:空間六個(gè)點(diǎn),任何三點(diǎn)不共線,四點(diǎn)不共面,每?jī)牲c(diǎn)之間連線都涂上紅色或藍(lán)色。求證:存在三點(diǎn),它們所成的三角形三邊同色。 (3)問(wèn)題(2)可以往兩個(gè)方向推廣:其一是顏色的種數(shù),其二是點(diǎn)數(shù)。 本例便是方向一的進(jìn)展,其證明已知上述。如果繼續(xù)沿此方向前進(jìn),可有下題: 在66個(gè)科學(xué)家中,每個(gè)科學(xué)家都和其他科學(xué)家通信,在他們的通信中僅僅討論四個(gè)題目,而任何兩個(gè)科學(xué)家之間僅僅討論一個(gè)題目。證明至少有三個(gè)科學(xué)家,他們互相之間討論同一個(gè)題目。 (4)回顧上面證明過(guò)程,對(duì)于17點(diǎn)染3色問(wèn)題可歸結(jié)為6點(diǎn)染2色問(wèn)題,又可歸結(jié)為3點(diǎn)染一色問(wèn)題。反過(guò)來(lái),我們可以繼續(xù)推廣。從以上(3,1)(6,2)(17,3)的過(guò)程,易發(fā)現(xiàn)6=(3-1)2+2,17=(6-1)3+2,66=(17-1)4+2,同理可得(66-1)5+2=327,(327-1)6+2=1958記為r1=3,r2=6,r3=17,r4=66,r5=327,r6=1958,我們可以得到遞推關(guān)系式:rn=n(rn-1-1)+2,n=2,3,4這樣就可以構(gòu)造出327點(diǎn)染5色問(wèn)題,1958點(diǎn)染6色問(wèn)題,都必出現(xiàn)一個(gè)同色三角形。- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 抽屜原理 2019 2020 年高 數(shù)學(xué) 競(jìng)賽 輔導(dǎo)資料 抽屜 原理
鏈接地址:http://italysoccerbets.com/p-2584778.html