數(shù)論競賽基礎(chǔ)知識

§23抽屜原理在數(shù)學(xué)問題中有一類與“存在性”關(guān)于問題，比如：“13個人中最少有兩個人出生在相同月份”；“某校400名學(xué)生中，一定存在兩名學(xué)生，他們在同一天過生日”；“個人任意分成200個小組，一定存在一組，其組員數(shù)不少于11”；“把[0，1]內(nèi)全部有理數(shù)放到100個集合中，一定存在一個集合，它里面有沒有限多個有理數(shù)”。這類存在性問題中，“存在”含義是“最少有一個”。在處理這類問題時，只要求指明存在，通常并不需要指出哪一個，也不需要確定經(jīng)過什么方式把這個存在東西找出來。這類問題相對來說包括到運算較少，依據(jù)理論也不復(fù)雜，我們把這些理論稱之為“抽屜原理”。“抽屜原理”最先是由19世紀德國數(shù)學(xué)家迪里赫萊（Dirichlet）利用于處理數(shù)學(xué)問題，所以又稱“迪里赫萊原理”，也有稱“鴿巢原理”。這個原理能夠簡單地敘述為“把10個蘋果，任意分放在9個抽屜里，則最少有一個抽屜里含有兩個或兩個以上蘋果”。這個道理是非常顯著，但應(yīng)用它卻能夠處理許多有趣問題，而且經(jīng)常得到一些令人驚異結(jié)果。抽屜原理是國際國內(nèi)各級各類數(shù)學(xué)競賽中主要內(nèi)容，本講就來學(xué)習(xí)它關(guān)于知識及其應(yīng)用。（一）抽屜原理基本形式定理1、假如把n+1個元素分成n個集合，那么不論怎么分，都存在一個集合，其中最少有兩個元素。證實：（用反證法）若不存在最少有兩個元素集合，則每個集合至多1個元素，從而n個集合至多有n個元素，此與共有n+1個元素矛盾，故命題成立。在定理1敘述中，能夠把“元素”改為“物件”，把“集合”改成“抽屜”，抽屜原理正是由此得名。一樣，能夠把“元素”改成“鴿子”，把“分成n個集合”改成“飛進n個鴿籠中”?！傍澔\原理”由此得名。例題講解1．已知在邊長為1等邊三角形內(nèi)（包含邊界）有任意五個點（圖1）。證實：最少有兩個點之間距離小于2．從1-100自然數(shù)中，任意取出51個數(shù)，證實其中一定有兩個數(shù)，它們中一個是另一個整數(shù)倍。3．從前25個自然數(shù)中任意取出7個數(shù)，證實：取出數(shù)中一定有兩個數(shù)，這兩個數(shù)中大數(shù)不超出小數(shù)1.5倍。4．已給一個由10個互不相等兩位十進制正整數(shù)組成集合。求證：這個集合必有兩個無公共元素子集合，各子集合中各數(shù)之和相等。5．在坐標平面上任取五個整點（該點橫縱坐標都取整數(shù)），證實：其中一定存在兩個整點，它們連線中點仍是整點。6．在任意給出100個整數(shù)中，都能夠找出若干個數(shù)來（能夠是一個數(shù)），它們和可被100整除。7．17名科學(xué)家中每兩名科學(xué)家都和其余科學(xué)家通信，在他們通信時，只討論三個題目，而且任意兩名科學(xué)家通信時只討論一個題目，證實：其中最少有三名科學(xué)家，他們相互通信時討論是同一個題目。課后練習(xí)1．幼稚園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個兒童任意選擇兩件，那么不論怎樣挑選，在任意七個兒童中總有兩個彼此選玩具都相同，試說明道理.2．正方體各面上涂上紅色或藍色油漆（每面只涂一個色），證實正方體一定有三個面顏色相同.3．把1到10自然數(shù)擺成一個圓圈，證實一定存在在個相鄰數(shù)，它們和數(shù)大于17.4．有紅襪2雙，白襪3雙，黑襪4雙，黃襪5雙，藍襪6雙（每雙襪子包裝在一起）若取出9雙，證實其中必有黑襪或黃襪2雙.5．在邊長為1正方形內(nèi)，任意給定13個點，試證：其中必有4個點，以此4點為頂點四邊開面積不超出（假定四點在一直線上組成面積為零四邊形）.6．在一條筆直馬路旁種樹，從起點起，每隔一米種一棵樹，假如把三塊“愛護樹木”小牌分別掛在三棵樹上，那么不論怎樣掛，最少有兩棵掛牌樹之間距離是偶數(shù)（以米為單位），這是為何？課后練習(xí)答案1.解從三種玩具中挑選兩件，搭配方式只能是下面六種：（兔、兔），（兔、熊貓），（兔、長頸鹿），（熊貓、熊貓），（熊貓、長頸鹿），（長頸鹿、長頸鹿）把每種搭配方式看作一個抽屜，把7個兒童看作物體，那么依照標準1，最少有兩個物體要放進同一個抽屜里，也就是說，最少兩人挑選玩具采取同一搭配方式，選玩具相同.標準2假如把mn+k(k≥1)個物體放進n個抽屜，則最少有一個抽屜至多放進m+1個物體.證實同標準相仿.若每個抽屜至多放進m個物體,那么n個抽屜至多放進mn個物體,與題設(shè)不符，故不可能.標準1可看作標準2物例（m=1）2.證實把兩種顏色看成兩個抽屜，把正方體六個面看成物體，那么6=2×2+2，依照標準二，最少有三個面涂上相同顏色.3.證實如圖12-1，設(shè)a1，a2，a3，…，a9，a10分別代表不超出10十個自然數(shù)，它們圍成一個圈，三個相鄰數(shù)組成是（a1，a2，a3），（a2，a3，a4），（a3，a4，a5），…,（a9，a10，a1）,（a10，a1，a2）共十組.現(xiàn)把它們看作十個抽屜，每個抽屜物體數(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)依照標準2,最少有一個括號內(nèi)三數(shù)和不少于17,即最少有三個相鄰數(shù)和大于17.標準1、標準2可歸結(jié)到期更通常形式：

標準3把m1+m2+…+mn+k(k≥1)個物體放入n個抽屜里，那么或在第一個抽屜里最少放入m1+1個物體，或在第二個抽屜里最少放入m2+1個物體，……，或在第n個抽屜里最少放入mn+1個物體.證實假定第一個抽屜放入物體數(shù)不超出m1個，第二個抽屜放入物體數(shù)不超出m2個，……，第n個抽屜放入物體個數(shù)不超出mn，那么放入全部抽屜物體總數(shù)不超出m1+m2+…+mn個，與題設(shè)矛盾.4.證實除可能取出紅襪、白襪3雙外.還最少從其它三種顏色襪子里取出4雙，依照原理3，必在黑襪或黃襪、藍襪里取2雙.上面數(shù)例論證似乎都是“存在”、“總有”、“最少有”問題，不錯，這正是抽屜標準主要作用.需要說明是，利用抽屜標準只是必定了“存在”、“總有”、“最少有”，卻不能確切地指出哪個抽屜里存在多少.制造抽屜是利用標準一大關(guān)鍵首先要指出是，對于同一問題，?？梢罁?jù)情況，從不一樣角度設(shè)計抽屜，從而造成不一樣制造抽屜方式.5.證實如圖12-2把正方形分成四個相同小正方形.因13=3×4+1，依照標準2，總有4點落在同一個小正方形內(nèi)（或邊界上），以此4點為頂點四邊形面積不超出小正方形面積，也就不超出整個正方形面積.實際上，因為處理問題關(guān)鍵在于將正方形分割成四個面積相等部分，所以還能夠把正方形按圖12-3（此處無圖）所表示形式分割.合理地制造抽屜必須建立在充分考慮問題本身特點基礎(chǔ)上.6.解如圖12-4（設(shè)掛牌三棵樹依次為A、B、C.AB=a，BC=b，若a、b中有一為偶數(shù)，命題得證.不然a、b均為奇數(shù)，則AC=a+b為偶數(shù)，命題得證.下面我們換一個角度考慮：給每棵樹上編上號，于是兩棵樹之間距離就是號碼差，因為樹號碼只能為奇數(shù)和偶數(shù)兩類，那么掛牌三棵樹號碼最少有兩個同為奇數(shù)或偶數(shù)，它們差必為偶數(shù)，問題得證.后一證實十分巧妙，經(jīng)過編號碼，將兩樹間距離轉(zhuǎn)化為號碼差.這種轉(zhuǎn)化思想方法是一個非常主要數(shù)學(xué)方法例題答案：1．分析：5個點分布是任意。假如要證實“在邊長為1等邊三角形內(nèi)（包含邊界）有5個點，那么這5個點中一定有距離小于兩點”，則順次連接三角形三邊中點，即三角形三條中位線，能夠分原等邊三角形為4個全等邊長為小等邊三角形，則5個點中必有2點位于同一個小等邊三角形中（包含邊界），其距離便小于。以上結(jié)論要由定理“三角形內(nèi)（包含邊界）任意兩點間距離小于其最大邊長”來確保，下面我們就來證實這個定理。如圖2，設(shè)BC是△ABC最大邊，P，M是△ABC內(nèi)（包含邊界）任意兩點，連接PM，過P分別作AB、BC邊平行線，過M作AC邊平行線，設(shè)各平行線交點為P、Q、N，那么∠PQN=∠C，∠QNP=∠A因為BC≥AB，所以∠A≥∠C，則∠QNP≥∠PQN，而∠QMP≥∠QNP≥∠PQN（三角形外角大于不相鄰內(nèi)角），所以PQ≥PM。顯然BC≥PQ，故BC≥PM。由此我們能夠推知，邊長為等邊三角形內(nèi)（包含邊界）兩點間距離小于。說明：（1）這里是用等分三角形方法來結(jié)構(gòu)“抽屜”。類似地，還能夠利用等分線段、等分正方形方法來結(jié)構(gòu)“抽屜”。比如“任取n+1個正數(shù)ai，滿足0＜ai≤1（i=1,2,…,n+1），試證實：這n+1個數(shù)中必存在兩個數(shù)，其差絕對值小于”。又如：“在邊長為1正方形內(nèi)任意放置五個點，求證：其中必有兩點，這兩點之間距離小于。（2）例1中，假如把條件（包含邊界）去掉，則結(jié)論能夠修改為：最少有兩個點之間距離小于"，請讀者試證之，并比較證實差異。（3）用一樣方法可證實以下結(jié)論：i）在邊長為1等邊三角形中有n2+1個點，這n2+1個點中一定有距離小于兩點。ii）在邊長為1等邊三角形內(nèi)有n2+1個點，這n2+1個點中一定有距離小于兩點。（4）將（3）中兩個命題中等邊三角形換成正方形，對應(yīng)結(jié)論中換成，命

題依然成立。（5）讀者還能夠考慮相反問題：通常地，“最少需要多少個點，才能夠使得邊長

為1正三角形內(nèi)（包含邊界）有兩點其距離不超出”。2．分析：本題似乎茫無頭緒，從何入手？其關(guān)鍵何在？其實就在“兩個數(shù)”，其中一個是另一個整數(shù)倍。我們要結(jié)構(gòu)“抽屜”，使得每個抽屜里任取兩個數(shù)，都有一個是另一個整數(shù)倍，這只有把公比是正整數(shù)整個等比數(shù)列都放進去同一個抽屜才行，這里用得到一個自然數(shù)分類基本知識：任何一個正整數(shù)都能夠表示成一個奇數(shù)與2方冪積，即若m∈N+,K∈N+，n∈N,則m=(2k-1)·2n，而且這種表示方式是唯一，如1=1×2°，2=1×21，3=3×2°，……證實：因為任何一個正整數(shù)都能表示成一個奇數(shù)乘2方冪，而且這種表示方法是唯一，所以我們可把1-100正整數(shù)分成以下50個抽屜（因為1-100中共有50個奇數(shù)）：（1）{1，1×2，1×22，1×23，1×24，1×25，1×26}；

（2）{3，3×2，3×22，3×23，3×24，3×25}；

（3）{5，5×2，5×22，5×23，5×24}；

（4）{7，7×2，7×22，7×23}；

（5）{9，9×2，9×22，9×23}；

（6）{11，11×2，11×22，11×23}；

……

（25）{49，49×2}；

（26）{51}；

……

（50）{99}。這么，1-100正整數(shù)就無重復(fù)，無遺漏地放進這50個抽屜內(nèi)了。從這100個數(shù)中任取51個數(shù)，也即從這50個抽屜內(nèi)任取51個數(shù)，依照抽屜標準，其中必定最少有兩個數(shù)屬于同一個抽屜，即屬于（1）-（25）號中某一個抽屜，顯然，在這25個抽屜中任何同一個抽屜內(nèi)兩個數(shù)中，一個是另一個整數(shù)倍。說明：（1）從上面證實中能夠看出，本題能夠推廣到通常情形：從1-2n自然數(shù)中，任意取出n+1個數(shù)，則其中必有兩個數(shù)，它們中一個是另一個整數(shù)倍。想一想，為何？因為1-2n中共含1，3，…，2n-1這n個奇數(shù)，所以能夠制造n個抽屜，而n+1＞n，由抽屜標準，結(jié)論就是必定了。給n以詳細值，就能夠結(jié)構(gòu)出不一樣題目。例2中n取值是50，還能夠編制相反題目，如：“從前30個自然數(shù)中最少要（不看這些數(shù)而以任意方式地）取出幾個數(shù)，才能確保取出數(shù)中能找到兩個數(shù)，其中較大數(shù)是較小數(shù)倍數(shù)？”（2）以下兩個問題結(jié)論都是否定（n均為正整數(shù)）想一想，為何？①從2，3，4，…，2n+1中任取n+1個數(shù)，是否必有兩個數(shù)，它們中一個是另一個整數(shù)倍？②從1，2，3，…，2n+1中任取n+1個數(shù)，是否必有兩個數(shù)，它們中一個是另一個整數(shù)倍？你能舉出反例，證實上述兩個問題結(jié)論都是否定嗎？（3）假如將（2）中兩個問題中任取n+1個數(shù)增加1個，都改成任取n+2個數(shù)，則它們結(jié)論是必定還是否定？你能判斷證實嗎？3．證實：把前25個自然數(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，⑥因為從前25個自然數(shù)中任意取出7個數(shù)，所以最少有兩個數(shù)取自上面第②組到第⑥組中某同一組，這兩個數(shù)中大數(shù)就不超出小數(shù)1.5倍。說明：（1）本題能夠改變敘述以下：在前25個自然數(shù)中任意取出7個數(shù)，求證其中存在兩個數(shù)，它們相互比值在內(nèi)。顯然，必須找出一個能把前25個自然數(shù)分成6（7-1=6）個集合方法，不過分類時有一個限制條件：同一集合中任兩個數(shù)比值在內(nèi)，故同一集合中元素數(shù)值差不得過大。這么，我們能夠用如上一個特殊分類法：遞推分類法：從1開始，顯然1只能單獨作為1個集合{1}；不然不滿足限制條件。能與2同屬于一個集合數(shù)只有3，于是{2，3}為一集合。如此依次遞推下去，使若干個連續(xù)自然數(shù)屬于同一集合，其中最大數(shù)不超出最小數(shù)倍，就能夠得到滿足條件六個集合。（2）假如我們按照（1）中遞推方法依次造“抽屜”，則第7個抽屜為{26，27，28，29，30，31，32，33，34，35，36，37，38，39}；

第8個抽屜為：{40，41，42，…，60}；

第9個抽屜為：{61，62，63，…，90，91}；

……那么我們能夠?qū)⒗?改造為以下一系列題目：（1）從前16個自然數(shù)中任取6個自然數(shù)；

（2）從前39個自然數(shù)中任取8個自然數(shù)；

（3）從前60個自然數(shù)中任取9個自然數(shù)；

（4）從前91個自然數(shù)中任取10個自然數(shù)；…都能夠得到同一個結(jié)論：其中存在2個數(shù)，它們相互比值在]內(nèi)。上述第（4）個命題，就是前蘇聯(lián)基輔第49屆數(shù)學(xué)競賽試題。假如我們改變區(qū)間[]（p＞q）端點值，則又能夠結(jié)構(gòu)出一系列新題目來。4.分析與解答：一個有著10個元素集合，它共有多少個可能子集呢？因為在組成一個子集時候，每一個元素都有被取過來或者不被取過來兩種可能，所以，10個元素集合就有210=1024個不一樣結(jié)構(gòu)子集方法，也就是，它一共有1024個不一樣子集，包含空集和全集在內(nèi)?？占c全集顯然不是考慮對象，所以剩下1024-2=1022個非空真子集。再來看各個真子集中一切數(shù)字之和。用N來記這個和數(shù)，很顯著：10≤N≤91+92+93+94+95+96+97+98+99=855這表明N至多只有855-9=846種不一樣情況。因為非空真子集個數(shù)是1022，1022＞846，所以一定存在兩個子集A與B，使得A中各數(shù)之和=B中各數(shù)之和。若A∩B=φ，則命題得證，若A∩B=C≠φ，即A與B有公共元素，這時只要剔除A與B中一切公有元素，得出兩個不相交子集A1與B1，很顯然A1中各元素之和=B1中各元素之和，所以A1與B1就是符合題目要求子集。說明：本例能否推廣為以下命題：已給一個由m個互不相等n位十進制正整數(shù)組成集合。求證：這個集合必有兩個無公共元素子集合，各子集合中各數(shù)之和相等。請讀者自己來研究這個問題。5．分析與解答：由中點坐標公式知，坐標平面兩點（x1,y1）、（x2,y2）中點坐標是。欲使都是整數(shù)，必須而且只須x1與x2，y1與y2奇偶性相同。坐標平面上任意整點按照橫縱兩個坐標奇偶性考慮有且只有以下四種：（奇數(shù)、奇數(shù)），（偶數(shù)，偶數(shù)），（奇數(shù)，偶數(shù)），（偶數(shù)，奇數(shù)）以此結(jié)構(gòu)四個“抽屜”，則在坐標平面上任取五個整點，那么最少有兩個整點，屬于同一個“抽屜”所以它們連線中點就必是整點。說明：我們能夠把整點概念推廣：假如（x1,x2,…xn）是n維（元）有序數(shù)組，且x1,x2,…xn中每一個數(shù)都是整數(shù)，則稱（x1,x2,…xn）是一個n維整點（整點又稱格點）。假如對全部n維整點按每一個xi奇偶性來分類，因為每一個位置上有奇、偶兩種可能性，所以共可分為2×2×…×2=2n個類。這是對n維整點一個分類方法。當(dāng)n=3時，23=8，此時能夠結(jié)構(gòu)命題：“任意給定空間中九個整點，求證它們之中必有兩點存在，使連接這兩點直線段內(nèi)部含有整點”。這就是1971年美國普特南數(shù)學(xué)競賽題。在n=2情形，也能夠結(jié)構(gòu)以下命題：“平面上任意給定5個整點”，對“它們連線段中點為整點”4個命題中，為真命題是：（A）最少可為0個，最多只能是5個（B）最少可為0個，最多可取10個

（C）最少為1個，最多為5個（D）最少為1個，最多為10個

（正確答案（D））6．分析：本題也似乎是茫無頭緒，無從下手，其關(guān)鍵何在？仔細審題，它們“和”能“被100整除”應(yīng)是做文章地方。假如把這100個數(shù)排成一個數(shù)列，用Sm記其前m項和，則其可結(jié)構(gòu)S1，S2，…S100共100個"和"數(shù)。討論這些“和數(shù)”被100除所得余數(shù)。注意到S1，S2，…S100共有100個數(shù)，一個數(shù)被100除所得余數(shù)有0，1，2，…99共100種可能性?！疤O果”數(shù)與“抽屜”數(shù)一樣多，怎樣排除“故障”？證實：設(shè)已知整數(shù)為a1,a2,…a100考查數(shù)列a1,a2,…a100前n項和組成數(shù)列S1，S2，…S100。假如S1，S2，…S100中有某個數(shù)可被100整除，則命題得證。不然，即S1，S2，…S100均不能被100整除，這么，它們被100除后余數(shù)必是{1，2，…，99}中元素。由抽屜原理I知，S1，S2，…S100中必有兩個數(shù)，它們被100除后具備相同余數(shù)。不妨設(shè)這兩個數(shù)為Si，Sj（i＜j），則100∣（Sj-Si），即100∣。命題得證。說明：有時候直接對所給對象作某種劃分，是極難結(jié)構(gòu)出恰當(dāng)抽屜。這時候，我們需要對所給對象先作一些變換，然后對變換得到對象進行分類，就能夠結(jié)構(gòu)出恰當(dāng)抽屜。本題直接對{an}進行分類是極難奏效。但由{an}結(jié)構(gòu)出{Sn}后，再對{Sn}進行分類就輕易得多。另外，對{Sn}按模100剩下類劃分時，只能分成100個集合，而{Sn}只有100項，似乎不能應(yīng)用抽屜標準。但注意到余數(shù)為0類恰使結(jié)論成立，于是經(jīng)過分別情況討論后，就可去掉余數(shù)為0類，從而轉(zhuǎn)化為100個數(shù)分配在剩下99個類中。這種處理問題方法應(yīng)該學(xué)會，它會助你從“山窮水盡疑無路”時，走入“柳暗花明又一村”中。最終，本例結(jié)論及證實能夠推廣到通常情形（而且有加強步驟）：在任意給定n個整數(shù)中，都能夠找出若干個數(shù)來（能夠是一個數(shù)），它們和可被n整除，而且，在任意給定排定次序n個整數(shù)中，都能夠找出若干個連續(xù)項（能夠是一項），它們和可被n整除。將以上通常結(jié)論中n賦以對應(yīng)年份值如1999，，…，就能夠編出對應(yīng)年份試題來。假如再賦以特殊背景，則能夠編出非常有趣數(shù)學(xué)智力題來，以下題：有100只猴子在吃花生，每只猴子最少吃了1?；ㄉ嗾卟幌?。請你證實：一定有若干只猴子（能夠是一只），它們所吃花生粒數(shù)總和恰好是100倍數(shù)。7．證實：視17個科學(xué)家為17個點，每兩個點之間連一條線表示這兩個科學(xué)家在討論同一個問題，若討論第一個問題則在對應(yīng)兩點連紅線，若討論第2個問題則在對應(yīng)兩點連條黃線，若討論第3個問題則在對應(yīng)兩點連條藍線。三名科學(xué)家研究同一個問題就轉(zhuǎn)化為找到一個三邊同顏色三角形?？紤]科學(xué)家A，他要與另外16位科學(xué)家每人通信討論一個問題，對應(yīng)于從A出發(fā)引出16條線段，將它們?nèi)境?種顏色，而16=3×5+1，因而必有6=5+1條同色，不妨記為AB1，AB2，AB3，AB4，AB5，AB6同紅色，若Bi（i=1，2，…，6）之間有紅線，則出現(xiàn)紅色三角線，命題已成立；不然B1，B2，B3，B4，B5，B6之間連線只染有黃藍兩色?？紤]從B1引出5條線，B1B2，B1B3，B1B4，B1B5，B1B6，用兩種顏色染色，因為5=2×2+1，故必有3=2+1條線段同色，假設(shè)為黃色，并記它們?yōu)锽1B2，B1B3，B1B4。這時若B2，B3，B4之間有黃線，則有黃色三角形，命題也成立，若B2，B3，B4，之間無黃線，則△B2，B3，B4，必為藍色三角形，命題依然成立。說明：（1）本題源于一個古典問題--世界上任意6個人中必有3人相互認識，或相互不認識。（美國普特南數(shù)學(xué)競賽題）。（2）將相互認識用紅色表示，將相互不認識用藍色表示，（1）將化為一個染色問題，成為一個圖論問題：空間六個點，任何三點不共線，四點不共面，每兩點之間連線都涂上紅色或藍色。求證：存在三點，它們所成三角形三邊同色。（3）問題（2）能夠往兩個方向推廣：其一是顏色種數(shù)，其二是點數(shù)。本例便是方向一進展，其證實已知上述。假如繼續(xù)沿此方向前進，可有下題：在66個科學(xué)家中，每個科學(xué)家都和其余科學(xué)家通信，在他們通信中僅僅討論四個題目，而任何兩個科學(xué)家之間僅僅討論一個題目。證實最少有三個科學(xué)家，他們相互之間討論同一個題目。（4）回顧上面證實過程，對于17點染3色問題可歸結(jié)為6點染2色問題，又可歸結(jié)為3點染一色問題。反過來，我們能夠繼續(xù)推廣。從以上（3，1）→（6，2）→（17，3）過程，易發(fā)覺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…這么就能夠結(jié)構(gòu)出327點染5色問題，1958點染6色問題，都必出現(xiàn)一個同色三角形。§24容斥原理相對補集：稱屬于A而不屬于B全體元素，組成集合為B對A相對補集或差集，記作A-B。容斥原理：以表示集合A中元素數(shù)目，我們有，其中為n個集合稱為A階。n階集合全部子集數(shù)目為。例題講解1．對集合{1，2，…，n}及其每一個非空了集，定義一個唯一確定“交替和”以下：按照遞減次序重新排列該子集，然后交替地減或加后繼數(shù)所得結(jié)果，比如，集合“交替和”是9-6+4-2+1=6.“交替和”是6-5=1，交替和是2。那么，對于n=7。求全部子集“交替和”總和。2．某班對數(shù)學(xué)、物理、化學(xué)三科總評成績統(tǒng)計以下：優(yōu)異人數(shù)：數(shù)學(xué)21個，物理19個，化學(xué)20個，數(shù)學(xué)物理都優(yōu)異9人，物理化學(xué)都優(yōu)異7人?；瘜W(xué)數(shù)學(xué)都優(yōu)異8人。這個班有5人任何一科都不優(yōu)異。那么確定這個班人數(shù)以及僅有一科優(yōu)異三科分別有多少個人。3．計算不超出120合數(shù)個數(shù)4．1992位科學(xué)家，每人最少與1329人合作過，那么，其中一定有四位數(shù)學(xué)家兩兩合作過。5．把個元素集合分為若干個兩兩不交子集，按照下述規(guī)則將某一個子集中一些元素挪到另一個子集：從前一子集挪到后一子集元素個數(shù)等于后一子集元素個數(shù)（前一子集元素個數(shù)應(yīng)大于后一子集元素個數(shù)），證實：能夠經(jīng)過有限次挪動，使得到子集與原集合相重合。6．給定1978個集合，每個集合都含有40個元素，已知其中任意兩個集合都恰有一個公共元，證實：存在一個元素，它屬于全部集合。7．在個元素組成集合中取個不一樣三元子集。證實：其中必有兩個，它們恰有一個公共元。課后練習(xí)1．一個集合含有10個互不相同十進制兩位數(shù)，證實：這個集合必有兩個無公共元素子集合，這兩個子集元素和相等。2．是否存在兩個以非頁整數(shù)為元素集合A、B，使得任一個非負整數(shù)都能夠被A、B之中各取一數(shù)之和唯一表出。3．對每個使得在n元集合中，能夠取出k個子集，其中任意兩個交非合。4．能否把分成兩個積相等不交集合。課后練習(xí)答案1．我們能夠發(fā)覺對每個數(shù)，它出現(xiàn)在個子集之中，所以全部子集中和為，那么全部元素在全部子集之中和為。2．利用二進制來考慮此題，小明前9包分別有錢1分（2），10分（2），100分（2），1000分（2），10000分（2），100000分（2），1000000分（2），10000000分（2），分（2），剩下一包裝剩下錢（以上數(shù)皆為二進制）就能夠了。3．不能。反證法。設(shè)存在合乎題中條件一個分法，假如和同屬于一個子集，則記為，不然記為，對，若分在三個集合中則稱為好。都是好。，，而，故在第二組中用代替，故是好。故。由此即，但。矛盾！有這么一個結(jié)論階集合子集若滿足且則最大值為，代入本題得為。例題答案：1．分析；n=7時，集合{7，6，5，4，3，2，1}非空子集有個，即使子集數(shù)目有限，不過逐一計算各自“交替和”再相加，計算量依然巨大，不過，依照“交替和”定義，輕易看到集合{1，2，3，4，5，6，7}與{1，2，3，4，5，6}“交替和”是7；能夠想到把一個不含7集和A與“交替和”之和應(yīng)為7。那么，我們也就很輕易處理這個問題了。解：集合{1，2，3，4，5，6，7}子集中，除去{7}外還有個非空子集合，把這個非空子集兩兩結(jié)組后分別計算每一組中“交替和”之和，結(jié)組標準是設(shè)這是把結(jié)合為一組，顯然，每組中，“交替和”之和應(yīng)為7，共有組.所以,全部“交替和”之和應(yīng)該為。說明：我們在這道題證實過程中用了這類題目最經(jīng)典解法。就是“對應(yīng)”方法，“對應(yīng)”方法在處理相等問題中應(yīng)用得更多。2．分析：自然地設(shè)A={數(shù)學(xué)總評優(yōu)異人}B={物理總評優(yōu)異人}C={化學(xué)總評優(yōu)異人}則已知|A|=21|B|=19|C|=20這表明全班人數(shù)在41至48人之間。僅數(shù)學(xué)優(yōu)異人數(shù)是可見僅數(shù)學(xué)優(yōu)異人數(shù)在4至11人之間。同理僅物理優(yōu)異人數(shù)在3至10人之間。同理僅化學(xué)優(yōu)異人數(shù)在5至12人之間。解：（略）。說明：先將詳細實際生活中問題數(shù)學(xué)化，然后依照數(shù)學(xué)理論來處理這個問題不不過競賽中常見情況，也是在未來學(xué)習(xí)中數(shù)學(xué)真正有用地方。3．分析1：用“篩法”找出不超出120質(zhì)數(shù)(素數(shù))，計算它們個數(shù)，從120中去掉質(zhì)數(shù)，再去掉“1”，剩下即是合數(shù)。解法1：120以內(nèi)：①既不是素數(shù)又不是合數(shù)數(shù)有一個，即“1”；②素數(shù)有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97、101、103、107、109、113、共30個。所以不超出120合數(shù)有120－1－30＝89(個)(附：篩法：從小到大按次序?qū)懗?－120全部自然數(shù)：先劃掉1，保留2，然后劃掉2全部倍數(shù)4,6，…120等；保留3，再劃掉全部3倍數(shù)6,9…117、120等；保留5，再劃掉5全部倍數(shù)10,15，…120；保留7，再劃掉7全部倍數(shù)，…這么，上面數(shù)表中剩下數(shù)就是120以內(nèi)全部素數(shù)，這種方法是最古老尋找素數(shù)方法，叫做“埃斯托拉‘篩法’”)說明：當(dāng)n不很大時，計算1－n中合數(shù)個數(shù)困難不大；但當(dāng)n很大時，利用篩法就很困難、很費時了，必須另覓他途。[分析2]受解法1啟發(fā)，假如能找出1－n中質(zhì)數(shù)個數(shù)m，則n－1－m就是不超出n合數(shù)個數(shù)。由初等數(shù)論中定理：a是大于1整數(shù)。假如全部小于√a質(zhì)數(shù)都不能整除a，那么a是質(zhì)數(shù)。因為120<121＝112，√120<11，所以不超出120合數(shù)必是2或3或5或7倍數(shù)，所以只要分別計算出不超出1202、3、5、7倍數(shù)，再利用“容斥原理”即可。解法2：設(shè)S1＝{a∣1≤3≤120,2∣a}；S2＝{b∣1≤b≤120,3∣b}；S3＝{c∣1≤3≤120,5∣c}；S4={d∣1≤d≤120,7∣d}，則有：card(S1)＝[120/2]=60，card(S2)＝[120/3]＝40，card(S3)＝[120/5]＝24，card(S4)＝[120/7]＝17；([n]表示n整數(shù)部分，比如[2,4]＝2，…)card(S1∩S2)＝[120/2×3]＝20，card(S1∩S3)＝[120/2×5]＝12，

card(S1∩S4)＝[120/2×7]＝8，card(S2∩S3)＝[120/3×5]＝8，

card(S2∩S4)＝[120/3×7]＝5，card(S3∩S4)[120/5×7]＝3，

card(S1∩S2∩S3)[120/2×3×5]＝4，card(S1∩S2∩S4)＝[120/2×3×7]＝2，

card(S1∩S3∩S4)＝[120/2×5×7]＝1，card(S2∩S3∩S4)＝[120/3×5×7]＝1，

card(S1∩S2∩S3∩S4)＝[120/2×3×5×7]＝0∴card(S1∪S2∪S3∪S4)＝card(S1)＋card(S2)＋card(S3)＋card(S4)－card(S1∩S2)－card(S1∩S3)－card(S1∩S4)－card(S2∩S3)－card(S2∩S4)－card(S3∩S4)＋card(S1∩S2∩S3)＋card(S1∩S2∩S4)＋card(S1∩S3∩S4)＋card(S2∩S3∩S4)－card(S1∩S2∩S3∩S4)＝(60＋40＋24＋17)-(20+12+8+8+5+3)+(4+2+1+1)-0＝141-56＋8＝93∵2，3，5，7是質(zhì)數(shù)∴93－4＝89即不超出120合數(shù)共有89個。4．分析：在與一個人A合作人中我們找到B。再說明一定有些人與A和B都合作過為C。最終再說明有些人與A、B、C都合作過為D，那么A、B、C、D就是找人了。證實：一個人A。不妨設(shè)B與之合作。那么。即C與A和B均合作過，分別表示與A、B合作過人集合。一樣地，。所以存在。則A、B、C、D就是所求，證畢。說明：把一個普通敘述性問題轉(zhuǎn)化為集合語言描述問題通常為解題關(guān)鍵之處，也是同學(xué)們需加強。5．分析：首先考慮到是一個很特殊數(shù)，其次我們發(fā)覺若兩個集合元素個數(shù)除以2若干次冪后若為奇數(shù)，那么，它們之間挪后就應(yīng)為偶數(shù)這一事實，若還不能想到解答就試一下，時情況，相信解答就不會難找到了。證實：考慮含奇數(shù)個元素子集（假如有這么子集），因為全部子集所含元素個數(shù)總和是偶數(shù)，所以具備奇數(shù)個元素子集個數(shù)也是偶數(shù)，任意將全部含有奇數(shù)個元素子集配成對，對每對子集按題目要求規(guī)則移動：從較大子集挪出一些元素，添加到較小子集，挪出元素個數(shù)為較小子集元素個數(shù)，于是得到全部子集元素個數(shù)都是偶數(shù)，現(xiàn)在考慮元素個數(shù)不被4整除子集，假如，則總共有兩個元素，它們在同一個子集，所以設(shè)，因為子集元素個數(shù)總數(shù)被4整除，所以這么子集個數(shù)為偶數(shù)，任意將這么子集配成對，對每一對子集施行滿足題目要求挪動，于是得到每個子集數(shù)均可被4整除，依此做下去，最終得到每個子集元素個數(shù)均可被整除，也就是只能有一個子集，它元素個數(shù)為，證畢。說明：這道題證實中隱含了一個單一變量在改變時改變方向相同這一性質(zhì)，就這道題來說，一直在增加就是各子集元素個數(shù)被2多少次冪整除這個冪次數(shù)，這是一大類問題，除了這種改變量，還要經(jīng)?？紤]改變中不變量。6．分析：我們能夠先去找一個屬于很多個集合元素，最好它就是我們要找那一個。證實：考慮給定1978個集合中任意一個集合，它和其它1977個集合都相交，所以，存在，使得它最少屬于其中50個集合，不然，集合中每個元素至多屬于49個集合，而集合恰有40個元素，所以除外至多有1960個集合，不可能，所以設(shè)屬于集合，…，下面證實它屬于給定1978個集合中任一個。對于除了，，…任一個集合，設(shè)，則與，，，…每一個都有最少一個元素交，它們都與不一樣，那么，就最少要有51個元素，不可能，所以屬于每個集合。說明：這種題目最怕把它想難了，想行太難了，就會以為無從下手，做數(shù)學(xué)競賽題就需要首先在做題之前選好方向，另首先就是大膽嘗試去做。7．分析：證實恰有一個公共元可能挺難。那么證只有兩個或零個公共元不可能是否可行呢？假如具備兩個公共元集合與表示為、那么~有傳遞性。是否有用呢？證實：設(shè)結(jié)論不真。則所給3元子集要么不交，要么恰有兩個公共元，假如子集與恰有兩個公共元，則記。設(shè)是三個子集。能夠證實假如，，則，于是全部給定3元子集能夠分類，使得同一類中任意兩個不一樣子集都恰有兩個公共元。而不一樣類子集不相交。于是對每個子集類，有三種可能：（1）恰含3個元素類。（2）恰含4個元素類。（3）最少含5個元素類。在（1）下，3元子集類恰由一個3元子集組成。在（2）下，子集類中至多有4個子集?？紤]（3）設(shè)，，則還有一個，由，，有。所以對子集類中任意子集，由，，它包含與，于是類中子集個數(shù)比類中元素個數(shù)少2，于是，每個類中子集個數(shù)不超出元素個數(shù)，不過題中條件子集數(shù)大于元素個數(shù)，矛盾！說明：此題為1979年美國競賽題。題目難度較大，應(yīng)該說是應(yīng)用了高等代數(shù)中一些思想?！?5奇數(shù)偶數(shù)將全體整數(shù)分為兩類，凡是2倍數(shù)數(shù)稱為偶數(shù)，不然稱為奇數(shù).所以，任一偶數(shù)可表為2m（m∈Z），任一奇數(shù)可表為2m+1或2m－1形式.奇、偶數(shù)具備以下性質(zhì)：（1）奇數(shù)±奇數(shù)=偶數(shù)；偶數(shù)±偶數(shù)=偶數(shù)；奇數(shù)±偶數(shù)=奇數(shù)；偶數(shù)×偶數(shù)=偶數(shù)；奇數(shù)×偶數(shù)=偶數(shù)；奇數(shù)×奇數(shù)=奇數(shù)；（2）奇數(shù)平方都可表為8m+1形式，偶數(shù)平方都可表為8m或8m+4形式（m∈Z）.（3）任何一個正整數(shù)n，都能夠?qū)懗尚问剑渲衜為非負整數(shù)，l為奇數(shù).這些性質(zhì)既簡單又顯著，然而它卻能處理數(shù)學(xué)競賽中一些難題.例題講解1．以下每個算式中，最少有一個奇數(shù)，一個偶數(shù)，那么這12個整數(shù)中，最少有幾個偶數(shù)？□+□=□，□-□=□，□×□＝□，□÷□＝□.2．已知n是偶數(shù)，m是奇數(shù)，方程組解是整數(shù)，那么()（A）p、q都是偶數(shù).

（B）p、q都是奇數(shù).（C）p是偶數(shù)，q是奇數(shù)

（D）p是奇數(shù)，q是偶數(shù)

3．在1，2，3…，1992前面任意添上一個正號和負號，它們代數(shù)和是奇數(shù)還是偶數(shù).4．70個數(shù)排成一行，除了兩頭兩個數(shù)以外，每個數(shù)3倍都恰好等于它兩邊兩個數(shù)和，這一行最左邊幾個數(shù)是這么：0，1，3，8，21，….問最右邊一個數(shù)被6除余幾？5．設(shè)a、b是自然數(shù)，且關(guān)于系式=（11111+a）（11111-b），

①證實a-b是4倍數(shù).--++----+6．在3×3正方格（a）和（b）中，每格填“+”或“-”符號，然后每次將表中任一行或一列各格全部改變試問重復(fù)若干次這么“變號”程序后，能否從一張表改變?yōu)榱硪粡埍?++-++---+bab7．設(shè)正整數(shù)d不等于2，5，13.證實在集合｛2，5，13，d｝中能夠找到兩個元素a,b，使得ab－1不是完全平方數(shù).8．設(shè)a、b、c、d為奇數(shù)，，證實：假如a+d=2k，b+c=2m，k,m為整數(shù)，那么a=1.9．設(shè)是一組數(shù)，它們中每一個都取1或－1，而且a1a2a3a4+a2a3a4a5+…+ana1a2a3=0，證實：n必須是4倍數(shù).課后練習(xí)1.填空題（1）有四個互不相等自然數(shù)，最大數(shù)與最小數(shù)差等于4，最大數(shù)與最小數(shù)積是一個奇數(shù)，而這四個數(shù)和是最小兩位奇數(shù)，那么這四個數(shù)乘積是______.（2）有五個連續(xù)偶數(shù)，已知第三個數(shù)比第一個數(shù)與第五個數(shù)和多18，這五個偶數(shù)之和是____.（3）能否把1993部電話中每一部與其它5部電話相連結(jié)？答____.2.選擇題（1）設(shè)a、b都是整數(shù)，以下命題正確個數(shù)是（

）①若a+5b是偶數(shù)，則a-3b是偶數(shù)；②若a+5b是偶數(shù)，則a-3b是奇數(shù)；③若a+5b是奇數(shù)，則a-3b是奇數(shù)；④若a+5b是奇數(shù)，則a-3b是偶數(shù).（A）1

（B）2

（C）3

（D）4（2）若n是大于1整數(shù)，則值（

）.（A）一定是偶數(shù)

（B）必定是非零偶數(shù)（C）是偶數(shù)但不是2

（D）能夠是偶數(shù)，也能夠是奇數(shù)（3）已知關(guān)于x二次三項式ax2+bx+c（a、b、c為整數(shù)），假如當(dāng)x=0與x=1時，二次三項式值都是奇數(shù)，那么a（

）（A）不能確定奇數(shù)還是偶數(shù)

（B）必定是非零偶數(shù)（C）必定是奇數(shù)

（D）必定是零3.試證實11986+91986+81986+61986是一個偶數(shù).4.請用0到9十個不一樣數(shù)字組成一個能被11整除最小十位數(shù).5.有n個整數(shù)，共積為n，和為零，求證：數(shù)n能被4整除6.在一個凸n邊形內(nèi)，任意給出有限個點，在這些點之間以及這些點與凸n邊形頂點之間，用線段連續(xù)起來，要使這些線段互不相交，而且把原凸n邊形分為只朋角形小塊，試證這種小三我有形個數(shù)與n有相同奇偶性.7.一個四位數(shù)是奇數(shù)，它首位數(shù)字淚地其余各位數(shù)字，而第二位數(shù)字大于其它各位數(shù)字，第三位數(shù)字等于首末兩位數(shù)字和兩倍，求這四位數(shù).

8.試證：3n+1能被2或22整除，而不能被2更高次冪整除.課后練習(xí)答案１．（１）３０．（最小兩位奇數(shù)是１１，最大數(shù)與最小數(shù)同為奇數(shù)）（２）１８０．設(shè)第一個偶數(shù)為ｘ，則后面四個衣次為ｘ＋２，ｘ＋４，ｘ＋６，ｘ＋８．（３）不能．２．Ｂ．Ｂ．Ａ３．１１９８６是奇數(shù)１，９１９８６個位數(shù)字是奇數(shù)１，而８１９８６，６１９８６都是偶數(shù)，故最終為偶數(shù)．４．仿例５

．５．設(shè)ａ１，ａ２，…，ａｎ滿足題設(shè)即ａ１＋ａ２＋…＋ａｎ＝０①ａ１·ａ２……ａｎ＝ｎ②。假如ｎ為奇數(shù)，由②，全部ａｉ皆為奇數(shù)，但奇數(shù)個奇數(shù)之和為奇數(shù)，故這時①不成立，可見ｎ只能為偶數(shù)．因為ｎ為偶數(shù)，由②知ａｉ中必有一個偶數(shù)，由①知ａｉ中必有另一個偶數(shù)．于是ａｉ中必有兩個偶數(shù)，因而由②知ｎ必能被４整除．６．設(shè)小三角形個數(shù)為ｋ，則ｋ個小三角形共有３ｋ條邊，減去ｎ邊形ｎ條邊及重復(fù)計算邊數(shù)扣共有（３ｋ＋ｎ）條線段，顯然只有當(dāng)ｋ與ｎ有相同奇偶性時，（３ｋ－ｎ）才是整數(shù)．７．設(shè)這個四位數(shù)是因為１≤ａ＜ｄ，ｄ是奇數(shù)所以ｄ≥３于是ｃ＝２（ａ＋ｄ）≥８，即ｃ＝８或ｃ＝９．因ｃ是偶數(shù)，所以ｃ＝８，由此得ａ＝１，ｄ＝３．又因ｂ＞ｃ，所以ｂ＝９所以該數(shù)為１９８３．８．當(dāng)ｎ為奇數(shù)時，考慮（４－１）ｎ＋１展開式；當(dāng)ｎ為偶數(shù)時，考慮（２＋１）ｎ＋１展開式．例題答案：1.解因為加法和減法算式中最少各有一個偶數(shù)，乘法和除法算式中最少各有二個偶數(shù)，故這12個整數(shù)中最少有六個偶數(shù).2.分析

因為1988y是偶數(shù)，由第一方程知p=x=n+1988y，所以p是偶數(shù)，將其代入第二方程中，于是11x也為偶數(shù)，從而27y=m-11x為奇數(shù)，所以是y=q奇數(shù)，應(yīng)選（C）都能被7整除；注：3.分析

因為兩個整數(shù)之和與這兩個整數(shù)之差奇偶性相同，所以在題設(shè)數(shù)字前面都添上正號和負號不改變其奇偶性，而1+2+3+…+1992==996×1993為偶數(shù)

于是題設(shè)代數(shù)和應(yīng)為偶數(shù).4.解

設(shè)70個數(shù)依次為a1,a2,a3據(jù)題意有a1=0,

偶a2=1

奇a3=3a2-a1,

奇a4=3a3-a2,

偶a5=3a4-a3,

奇a6=3a5-a4,

奇

………………由此可知：

當(dāng)n被3除余1時，an是偶數(shù)；當(dāng)n被3除余0時，或余2時，an是奇數(shù)，顯然a70是3k+1型偶數(shù)，所以k必須是奇數(shù)，令k=2n+1，則a70=3k+1=3(2n+1)+1=6n+4.5.證實

由①式可知11111（a-b）=ab+4×617

②∵a＞0,b＞0,∴a-b＞0首先，易知a-b是偶數(shù)，不然11111(a-b)是奇數(shù)，從而知ab是奇數(shù)，進而知a、b都是奇數(shù)，可知(11111+a)及(11111-b)都為偶數(shù)，這與式①矛盾其次，從a-b是偶數(shù)，依照②可知ab是偶數(shù)，進而易知a、b皆為偶數(shù)，從而ab+4×617是4倍數(shù)，由②知a-b是4倍數(shù).6.解

按題設(shè)程序，這是不可能做到，考查下面填法：

在黑板所表示2×2正方形表格中，按題設(shè)程序“變號”，“+”號或者不變，或者變成兩個.表(a)中小正方形有四個“+”號，實施變號步驟后，“+”個數(shù)仍是偶數(shù)；但表(b)中小正方形“+”號個數(shù)仍是奇數(shù)，故它不能從一個改變到另一個.顯然，小正方形互變無法實現(xiàn)，3×3大正方形互變，更無法實現(xiàn).7.解

因為2×5－1=32，2×13－1=52，5×13－1=82，所以，只需證實2d－1，5d－1，13d－1中最少有一個不是完全平方數(shù).用反證法，假設(shè)它們都是完全平方數(shù)，令2d－1=x2①5d－1=y2②13d－1=z2③x,y,z∈N*由①知，x是奇數(shù)，設(shè)x=2k－1，于是2d－1=（2k－1）2，即d=2k2－2k+1，這說明d也是奇數(shù).所以，再由②，③知，y,z均是偶數(shù).設(shè)y=2m,z=2n,代入③、④，相減，除以4得，2d=n2－m2=(n+m)(n－m)，從而n2－m2為偶數(shù)，n，m必同是偶數(shù)，于是m+n與m－n都是偶數(shù)，這么2d就是4倍數(shù)，即d為偶數(shù)，這與上述d為奇數(shù)矛盾.故命題得證.8.首先易證：從而.再由因而①顯然，為偶數(shù)，為奇數(shù)，而且只能一個為4n型偶數(shù)，一個為4n+2型偶數(shù)（不然它們差應(yīng)為4倍數(shù)，然而它們差等于2a不是4倍數(shù)），所以,假如設(shè)，其中e,f為奇數(shù)，那么由①式及特征就有（Ⅰ）或（Ⅱ）由得e=1，從而于是（Ⅰ）或（Ⅱ）分別變?yōu)榛蚪庵?，?因a為奇數(shù)，故只能a=1.9.證實:因為每個均為1和－1，從而題中所給等式中每一項也只取1或－1，而這么n項之和等于0，則取1或－1個數(shù)必相等，因而n必須是偶數(shù)，設(shè)n=2m.再深入考查已知等式左端n項之乘積=()4=1，這說明，這n項中?。?項（共m項）也一定是偶數(shù)，即m=2k，從而n是4倍數(shù).§26整除整除是整數(shù)一個主要內(nèi)容，這里僅介紹其中幾個方面：整數(shù)整除性、最大條約數(shù)、最小公倍數(shù)、方冪問題.Ⅰ.整數(shù)整除性初等數(shù)論基本研究對象是自然數(shù)集合及整數(shù)集合.我們知道，整數(shù)集合中能夠作加、減、乘法運算，而且這些運算滿足一些規(guī)律（即加法和乘法結(jié)合律和交換律，加法與乘法分配律），但通常不能做除法，即，如是整除，，則不一定是整數(shù).由此引出初等數(shù)論中第一個基本概念：整數(shù)整除性.定義一：（帶余除法）對于任一整數(shù)和任一整數(shù)，必有惟一一對整數(shù)，使得，，而且整數(shù)和由上述條件惟一確定，則稱為除不完全商，稱為除余數(shù).若，則稱整除，或被整除，或稱倍數(shù)，或稱約數(shù)（又叫因子），記為.不然，|.任何非約數(shù)，叫做真約數(shù).0是任何整數(shù)倍數(shù)，1是任何整數(shù)約數(shù).任一非零整數(shù)是其本身約數(shù)，也是其本身倍數(shù).由整除定義，不難得出整除以下性質(zhì)：（1）若（2）若（3）若，則反之，亦成立.（4）若.所以，若.（5）、互質(zhì)，若（6）為質(zhì)數(shù)，若則必能整除中某一個.尤其地，若為質(zhì)數(shù)，（7）如在等式中除開某一項外，其余各項都是倍數(shù)，則這一項也是倍數(shù).（8）n個連續(xù)整數(shù)中有且只有一個是n倍數(shù).（9）任何n個連續(xù)整數(shù)之積一定是n倍數(shù).本講開始在整除定義同時給出了約數(shù)概念，又由上一講算術(shù)基本定理，我們就能夠討論整數(shù)約數(shù)個數(shù)了.Ⅱ.最大條約數(shù)和最小公倍數(shù)定義二：設(shè)、是兩個不全為0整數(shù).若整數(shù)c滿足：，則稱條約數(shù)，全部條約數(shù)中最大者稱為最大條約數(shù)，記為.假如=1，則稱互質(zhì)或互素.定義三：假如、倍數(shù)，則稱、公倍數(shù).公倍數(shù)中最小正數(shù)稱為最小公倍數(shù)，記為.最大條約數(shù)和最小公倍數(shù)概念能夠推廣到有限多個整數(shù)情形，并用表示最大條約數(shù)，表示最小公倍數(shù).若，則稱互質(zhì)，若中任何兩個都互質(zhì)，則稱它們是兩兩互質(zhì).注意，n個整數(shù)互質(zhì)與n個整數(shù)兩兩互質(zhì)是不一樣概念，前者成立時后者不一定成立（比如，3，15，8互質(zhì)，但不兩兩互質(zhì)）；顯然后者成立時，前者必成立.因為任何正數(shù)都不是0倍數(shù)，所以在討論最小公倍數(shù)時，通常都假定這些整數(shù)不為0.同時，因為有相同條約數(shù)，且（有限多個亦成立），所以，我們總限于在自然數(shù)集合內(nèi)來討論數(shù)最大條約數(shù)和最小公倍數(shù).Ⅲ.方冪問題 一個正整數(shù)能否表成個整數(shù)次方和問題稱為方冪和問題.尤其地，當(dāng)初稱為次方問題，當(dāng)初，稱為平方和問題. 能表為某整數(shù)平方數(shù)稱為完全平方數(shù).簡稱平方數(shù)，關(guān)于平方數(shù)，顯著有以下一些簡單性質(zhì)和結(jié)論： （1）平方數(shù)個位數(shù)字只可能是0，1，4，5，6，9. （2）偶數(shù)平方數(shù)是4倍數(shù)，奇數(shù)平方數(shù)被8除余1，即任何平方數(shù)被4除余數(shù)只能是0或1. （3）奇數(shù)平方十位數(shù)字是偶數(shù). （4）十位數(shù)字是奇數(shù)平方數(shù)個位數(shù)一定是6. （5）不能被3整除數(shù)平方被3除余1，能被3整除數(shù)平方能被3整除.因而，平方數(shù)被9除余數(shù)為0，1，4，7，且此平方數(shù)各位數(shù)字和被9除余數(shù)也只能為0，1，4，7. （6）平方數(shù)約數(shù)個數(shù)為奇數(shù). （7）任何四個連續(xù)整數(shù)乘積加1，必定是一個平方數(shù).例題講解1．證實：對于任何自然數(shù)和，數(shù)都不能分解成若干個連續(xù)正整數(shù)之積.2．設(shè)和均為自然數(shù),使得 證實：可被1979整除.3．對于整數(shù)與，定義求證：可整除4．求一對整數(shù)，滿足：(1)不能被7整除；（2）能被77整除.5．求設(shè)和是兩個正整數(shù)，為大于或等于3質(zhì)數(shù)，），試證：（1）；（2）或6．盒子中各若干個球，每一次在其中個盒中加一球.求證：不論開始分布情況怎樣，總可按上述方法進行有限次加球后使各盒中球數(shù)相等充要條件是7．求全部這么自然數(shù)，使得是一個自然數(shù)平方.課后練習(xí)1．

選擇題（1）若數(shù)n=20·30·40·50·60·70·80·90·100·110·120·130，則不是n因數(shù)最小質(zhì)數(shù)是（

）.（A）19

（B）17

（C）13

（D）非上述答案（2）在整數(shù)0、1、2…、8、9中質(zhì)數(shù)有x個，偶數(shù)有y個，完全平方數(shù)有z個，則x+y+z等于（

）.（A）14

（B）13

（C）12

（D）11

（E）10（3）可除盡311+518最小整數(shù)是（

）.（A）2

（B）3

（C）5

（D）311+518（E）以上都不是2．

填空題（1）把100000表示為兩個整數(shù)乘積，使其中沒有一個是10整倍數(shù)表示式為__________.(2)一個自然數(shù)與3和是5倍數(shù),與3差是6倍數(shù),這么自然數(shù)中最小是_________.(3)在十進制中,各位數(shù)碼是0或1,而且能被225整除最小自然數(shù)是________.3.求使為整數(shù)最小自然數(shù)a值.4.證實:對一切整數(shù)n,n2+2n+12不是121倍數(shù).5.設(shè)是一個四位正整數(shù),已知三位正整數(shù)與246和是一位正整數(shù)d111倍,又是18倍數(shù).求出這個四位數(shù),并寫出推理運算過程.6.能否有正整數(shù)m、n滿足方程m2+1954=n2.7.證實：（1）133|（11n+2+12n+1），其中n為非負整數(shù).(2)若將(1)中11改為任意一個正整數(shù)a,則(1)中12,133將作何改動?證實改動后結(jié)論.8.設(shè)a、b、c是三個互不相等正整數(shù).求證:在a3b-ab3,b3c-bc3,c3a-ca3三個數(shù)中,最少有一個能被10整除.9.100個正整數(shù)之和為101101,則它們最大條約數(shù)最大可能值是多少?證實你結(jié)論.課后練習(xí)答案１．Ｂ．Ｂ．Ａ２．（１）２５·５５．（２）２７．３．由a為一整數(shù)平方可推出a=5．４．反證法．若是１２１倍數(shù)，設(shè)ｎ２＋２ｎ＋１２＝１２１ｋ（ｎ＋１）２＝１１（１１ｋ－１）．∵１１是素數(shù)且除盡（＋１）２，∴１１除盡ｎ＋１１１２除盡（ｎ＋１）２或１１｜１１ｋ－１，不可能．５．由是ｄ１１１倍，可能是１９８，３０９，４２０，５３１，６４２，７５３；又是１８倍數(shù)，∴只能是１９８．而１９８＋２４６＝４４４，∴ｄ＝４，是１９８４．７．（１）１１