高中數(shù)學(xué)競(jìng)賽講義組合

/高中數(shù)學(xué)競(jìng)賽講義（十八）──組合一、方法與例題1．抽屜原理。例1

設(shè)整數(shù)n≥412,…是區(qū)間(0,2n)內(nèi)n個(gè)不同的整數(shù)，證明：存在集合{a12,…}的一個(gè)子集，它的所有元素之和能被2n整除。[證明]

（1）若n{a12,…},則n個(gè)不同的數(shù)屬于1個(gè)集合{1,21}，{2,22},…,{11}。由抽屜原理知其中必存在兩個(gè)數(shù)(i≠j)屬于同一集合，從而2n被2n整除；（2）若n∈{a12,…}，不妨設(shè)，從a12,…1(1≥3)中任意取3個(gè)數(shù),,(,<<)，則與中至少有一個(gè)不被n整除，否則()+()≥2n，這與∈(0,2n)矛盾，故a12,…1中必有兩個(gè)數(shù)之差不被n整除；不妨設(shè)a1與a2之差(a21>0)不被n整除，考慮n個(gè)數(shù)a,…12+…1。ⅰ）若這n個(gè)數(shù)中有一個(gè)被n整除，設(shè)此數(shù)等于，若k為偶數(shù)，則結(jié)論成立；若k為奇數(shù)，則加上知結(jié)論成立。ⅱ）若這n個(gè)數(shù)中沒(méi)有一個(gè)被n整除，則它們除以n的余數(shù)只能取1,2,…1這1個(gè)值，由抽屜原理知其中必有兩個(gè)數(shù)除以n的余數(shù)相同，它們之差被n整除，而a21不被n整除，故這個(gè)差必為,,1中若干個(gè)數(shù)之和，同ⅰ）可知結(jié)論成立。2．極端原理。例2

在n×n的方格表的每個(gè)小方格內(nèi)寫有一個(gè)非負(fù)整數(shù)，并且在某一行和某一列的交叉點(diǎn)處如果寫有0，則該行與該列所填的所有數(shù)之和不小于n。證明：表中所有數(shù)之和不小于。[證明]

計(jì)算各行的和、各列的和，這2n個(gè)和中必有最小的，不妨設(shè)第m行的和最小，記和為k，則該行中至少有個(gè)0，這個(gè)0所在的各列的和都不小于，從而這列的數(shù)的總和不小于()2，其余各列的數(shù)的總和不小于k2，從而表中所有數(shù)的總和不小于()22≥3.不變量原理。俗話說(shuō)，變化的是現(xiàn)象，不變的是本質(zhì)，某一事情反復(fù)地進(jìn)行，尋找不變量是一種策略。例3

設(shè)正整數(shù)n是奇數(shù)，在黑板上寫下數(shù)1，2，…，2n，然后取其中任意兩個(gè)數(shù),擦去這兩個(gè)數(shù)，并寫上。證明：最后留下的是一個(gè)奇數(shù)。[證明]

設(shè)S是黑板上所有數(shù)的和，開(kāi)始時(shí)和數(shù)是1+2+…+2(21)，這是一個(gè)奇數(shù)，因?yàn)榕c有相同的奇偶性，故整個(gè)變化過(guò)程中S的奇偶性不變，故最后結(jié)果為奇數(shù)。例4

數(shù)a1,a2,…中每一個(gè)是1或-1，并且有1a2a3a4+a2a3a4a5+…1a2a3=0.證明：4.[證明]

如果把a(bǔ)1,a2,…中任意一個(gè)換成，因?yàn)橛?個(gè)循環(huán)相鄰的項(xiàng)都改變符號(hào)，S模4并不改變，開(kāi)始時(shí)0，即S≡0，即S≡0(4)。經(jīng)有限次變號(hào)可將每個(gè)都變成1，而始終有S≡0(4)，從而有n≡0(4)，所以4。4．構(gòu)造法。例5

是否存在一個(gè)無(wú)窮正整數(shù)數(shù)列a1,<a2<a3<…，使得對(duì)任意整數(shù)A，數(shù)列中僅有有限個(gè)素?cái)?shù)。[證明]

存在。取(n!)3即可。當(dāng)0時(shí)，{}中沒(méi)有素?cái)?shù)；當(dāng)≥2時(shí)，若n≥，則均為的倍數(shù)且大于，不可能為素?cái)?shù)；當(dāng)±1時(shí)，±1=(n!±1)[(n!)2±1]，當(dāng)≥3時(shí)均為合數(shù)。從而當(dāng)A為整數(shù)時(shí)，{(n!)3}中只有有限個(gè)素?cái)?shù)。例6

一個(gè)多面體共有偶數(shù)條棱，試證：可以在它的每條棱上標(biāo)上一個(gè)箭頭，使得對(duì)每個(gè)頂點(diǎn)，指向它的箭頭數(shù)目是偶數(shù)。[證明]

首先任意給每條棱一個(gè)箭頭，如果此時(shí)對(duì)每個(gè)頂點(diǎn)，指向它的箭頭數(shù)均為偶數(shù)，則命題成立。若有某個(gè)頂點(diǎn)A，指向它的箭頭數(shù)為奇數(shù)，則必存在另一個(gè)頂點(diǎn)B，指向它的箭頭數(shù)也為奇數(shù)（因?yàn)槔饪倲?shù)為偶數(shù)），對(duì)于頂點(diǎn)A與B，總有一條由棱組成的“路徑”連結(jié)它們，對(duì)該路徑上的每條棱，改變它們箭頭的方向，于是對(duì)于該路徑上除A，B外的每個(gè)頂點(diǎn)，指向它的箭頭數(shù)的奇偶性不變，而對(duì)頂點(diǎn)A，B，指向它的箭頭數(shù)變成了偶數(shù)。如果這時(shí)仍有頂點(diǎn)，指向它的箭頭數(shù)為奇數(shù)，則重復(fù)上述做法，又可以減少兩個(gè)這樣的頂點(diǎn)，由于多面體頂點(diǎn)數(shù)有限，經(jīng)過(guò)有限次調(diào)整，總能使和是對(duì)每個(gè)頂點(diǎn)，指向它的箭頭數(shù)為偶數(shù)。命題成立。5．染色法。例7

能否在5×5方格表內(nèi)找到一條線路，它由某格中心出發(fā)，經(jīng)過(guò)每個(gè)方格恰好一次，再回到出發(fā)點(diǎn)，并且途中不經(jīng)過(guò)任何方格的頂點(diǎn)？[解]

不可能。將方格表黑白相間染色，不妨設(shè)黑格為13個(gè)，白格為12個(gè)，如果能實(shí)現(xiàn)，因黑白格交替出現(xiàn)，黑白格數(shù)目應(yīng)相等，得出矛盾，故不可能。6．凸包的使用。給定平面點(diǎn)集A，能蓋住A的最小的凸圖形，稱為A的凸包。例8

試證：任何不自交的五邊形都位于它的某條邊的同一側(cè)。[證明]

五邊形的凸五包是凸五邊形、凸四邊形或者是三角形，凸包的頂點(diǎn)中至少有3點(diǎn)是原五邊形的頂點(diǎn)。五邊形共有5個(gè)頂點(diǎn)，故3個(gè)頂點(diǎn)中必有兩點(diǎn)是相鄰頂點(diǎn)。連結(jié)這兩點(diǎn)的邊即為所求。7．賦值方法。例9

由2×2的方格紙去掉一個(gè)方格余下的圖形稱為拐形，用這種拐形去覆蓋5×7的方格板，每個(gè)拐形恰覆蓋3個(gè)方格，可以重疊但不能超出方格板的邊界，問(wèn)：能否使方格板上每個(gè)方格被覆蓋的層數(shù)都相同？說(shuō)明理由。[解]

將5×7方格板的每一個(gè)小方格內(nèi)填寫數(shù)-2和1。如圖18-1所示，每個(gè)拐形覆蓋的三個(gè)數(shù)之和為非負(fù)。因而無(wú)論用多少個(gè)拐形覆蓋多少次，蓋住的所有數(shù)字之和都是非負(fù)的。另一方面，方格板上數(shù)字的總和為12×(-2)+23×11，當(dāng)被覆蓋K層時(shí)，蓋住的數(shù)字之和等于，這表明不存在滿足題中要求的覆蓋。-21-21-21-21111111-21-21-21-21111111-21-21-21-2

8．圖論方法。例10

生產(chǎn)由六種顏色的紗線織成的雙色布，在所生產(chǎn)的雙色布中，每種顏色的紗線至少與其他三種顏色的紗線搭配過(guò)。證明：可以挑出三種不同的雙色布，它們包含所有的顏色。[證明]

用點(diǎn)A1，A2，A3，A4，A5，A6表示六種顏色，若兩種顏色的線搭配過(guò)，則在相應(yīng)的兩點(diǎn)之間連一條邊。由已知，每個(gè)頂點(diǎn)至少連出三條邊。命題等價(jià)于由這些邊和點(diǎn)構(gòu)成的圖中有三條邊兩兩不相鄰（即無(wú)公共頂點(diǎn)）。因?yàn)槊總€(gè)頂點(diǎn)的次數(shù)≥3，所以可以找到兩條邊不相鄰，設(shè)為A1A2，A3A4。（1）若A5與A6連有一條邊，則A1A2，A3A4，A5A6對(duì)應(yīng)的三種雙色布滿足要求。（2）若A5與A6之間沒(méi)有邊相連，不妨設(shè)A5和A1相連，A2與A3相連，若A4和A6相連，則A1A2，A3A4，A5A6對(duì)應(yīng)的雙色布滿足要求；若A4與A6不相連，則A6與A1相連，A2與A3相連，A1A5，A2A6，A3A4對(duì)應(yīng)的雙色布滿足要求。綜上，命題得證。二、習(xí)題精選1．藥房里有若干種藥，其中一部分藥是烈性的。藥劑師用這些藥配成68副藥方，每副藥方中恰有5種藥，其中至少有一種是烈性的，并且使得任選3種藥恰有一副藥方包含它們。試問(wèn)：全部藥方中是否一定有一副藥方至少含有4種烈性藥？（證明或否定）2．21個(gè)女孩和21個(gè)男孩參加一次數(shù)學(xué)競(jìng)賽，（1）每一個(gè)參賽者最多解出6道題；（2）對(duì)每一個(gè)女孩和每一個(gè)男孩至少有一道題被這一對(duì)孩子都解出。求證：有一道題至少有3個(gè)女孩和至少有3個(gè)男孩都解出。3．求證：存在無(wú)窮多個(gè)正整數(shù)n，使得可將3n個(gè)數(shù)1,2,…,3n排成數(shù)表a1,a2…b1,b2…c1,c2…滿足：（1）a111=a222=…=，且為6的倍數(shù)。（2）a12+…b12+…c12+…，且為6的倍數(shù)。4．給定正整數(shù)n，已知克數(shù)都是正整數(shù)的k塊砝碼和一臺(tái)天平可以稱出質(zhì)量為1，2，…，n克的所有物品，求k的最小值f(n)。5．空間中有1989個(gè)點(diǎn)，其中任何3點(diǎn)都不共線，把它們分成點(diǎn)數(shù)各不相同的30組，在任何3個(gè)不同的組中各取一點(diǎn)為頂點(diǎn)作三角形。試問(wèn)：為使這種三角形的總數(shù)最大，各組的點(diǎn)數(shù)應(yīng)分別為多少？6．在平面給定點(diǎn)A0和n個(gè)向量a1，a2，…，，且使a12+…=0。這組向量的每一個(gè)排列都定義一個(gè)點(diǎn)集：A1，A2，…，0，使得求證：存在一個(gè)排列，使由它定義的所有點(diǎn)A1，A2，…，1都在以A0為角頂?shù)哪硞€(gè)600角的內(nèi)部和邊上。7．設(shè)m,n,k∈N，有4個(gè)酒杯，容量分別為和升，允許進(jìn)行如下操作：將一個(gè)杯中的酒倒入另一杯中或者將另一杯倒?jié)M為止。開(kāi)始時(shí)，大杯中裝滿酒而另3個(gè)杯子卻空著，問(wèn)：為使對(duì)任何S∈N，S<，都可經(jīng)過(guò)若干次操作，使得某個(gè)杯子中恰有S升酒的關(guān)于的充分必要條件是什么？8．設(shè)有30個(gè)人坐在一張圓桌的周圍，其中的每個(gè)人都或者是白癡，或