2019-2020年高中數(shù)學(xué)競賽教材講義 第十八章 組合.doc

2019-2020年高中數(shù)學(xué)競賽教材講義 第十八章 組合一、方法與例題1抽屜原理。例1 設(shè)整數(shù)n4,a1,a2,an是區(qū)間(0,2n)內(nèi)n個不同的整數(shù)，證明：存在集合a1,a2,an的一個子集，它的所有元素之和能被2n整除。證明 （1）若na1,a2,an,則n個不同的數(shù)屬于n-1個集合1,2n-1，2,2n-2,n-1,n+1。由抽屜原理知其中必存在兩個數(shù)ai,aj(ij)屬于同一集合，從而ai+aj=2n被2n整除；（2）若na1,a2,an，不妨設(shè)an=n，從a1,a2,an-1(n-13)中任意取3個數(shù)ai, aj, ak(ai,<aj< ak)，則aj-ai與ak-ai中至少有一個不被n整除，否則ak-ai=(ak-aj)+(aj-ai)2n，這與ak(0,2n)矛盾，故a1,a2,an-1中必有兩個數(shù)之差不被n整除；不妨設(shè)a1與a2之差(a2-a1>0)不被n整除，考慮n個數(shù)a1,a2,a1+a2,a1+a2+a3,a1+a2+an-1。）若這n個數(shù)中有一個被n整除，設(shè)此數(shù)等于kn，若k為偶數(shù)，則結(jié)論成立；若k為奇數(shù)，則加上an=n知結(jié)論成立。）若這n個數(shù)中沒有一個被n整除，則它們除以n的余數(shù)只能取1,2,n-1這n-1個值，由抽屜原理知其中必有兩個數(shù)除以n的余數(shù)相同，它們之差被n整除，而a2-a1不被n整除，故這個差必為ai, aj, ak-1中若干個數(shù)之和，同）可知結(jié)論成立。2極端原理。例2 在nn的方格表的每個小方格內(nèi)寫有一個非負(fù)整數(shù)，并且在某一行和某一列的交叉點處如果寫有0，那么該行與該列所填的所有數(shù)之和不小于n。證明：表中所有數(shù)之和不小于。證明 計算各行的和、各列的和，這2n個和中必有最小的，不妨設(shè)第m行的和最小，記和為k，則該行中至少有n-k個0，這n-k個0所在的各列的和都不小于n-k，從而這n-k列的數(shù)的總和不小于(n-k)2，其余各列的數(shù)的總和不小于k2，從而表中所有數(shù)的總和不小于(n-k)2+k23.不變量原理。俗話說，變化的是現(xiàn)象，不變的是本質(zhì)，某一事情反復(fù)地進(jìn)行，尋找不變量是一種策略。例3 設(shè)正整數(shù)n是奇數(shù)，在黑板上寫下數(shù)1，2，2n，然后取其中任意兩個數(shù)a,b,擦去這兩個數(shù)，并寫上|a-b|。證明：最后留下的是一個奇數(shù)。證明 設(shè)S是黑板上所有數(shù)的和，開始時和數(shù)是S=1+2+2n=n(2n+1)，這是一個奇數(shù)，因為|a-b|與a+b有相同的奇偶性，故整個變化過程中S的奇偶性不變，故最后結(jié)果為奇數(shù)。例4 數(shù)a1, a2,an中每一個是1或-1，并且有S=a1a2a3a4+ a2a3a4a5+ana1a2a3=0. 證明：4|n.證明 如果把a(bǔ)1, a2,an中任意一個ai換成-ai，因為有4個循環(huán)相鄰的項都改變符號，S模4并不改變，開始時S=0，即S0，即S0(mod4)。經(jīng)有限次變號可將每個ai都變成1，而始終有S0(mod4)，從而有n0(mod4)，所以4|n。4構(gòu)造法。例5 是否存在一個無窮正整數(shù)數(shù)列a1,<a2<a3<，使得對任意整數(shù)A，數(shù)列中僅有有限個素數(shù)。證明 存在。取an=(n!)3即可。當(dāng)A=0時，an中沒有素數(shù)；當(dāng)|A|2時，若n|A|，則an+A均為|A|的倍數(shù)且大于|A|，不可能為素數(shù)；當(dāng)A=1時，an1=(n!1)(n!)2n!+1，當(dāng)3時均為合數(shù)。從而當(dāng)A為整數(shù)時，(n!)3+A中只有有限個素數(shù)。例6 一個多面體共有偶數(shù)條棱，試證：可以在它的每條棱上標(biāo)上一個箭頭，使得對每個頂點，指向它的箭頭數(shù)目是偶數(shù)。證明 首先任意給每條棱一個箭頭，如果此時對每個頂點，指向它的箭頭數(shù)均為偶數(shù)，則命題成立。若有某個頂點A，指向它的箭頭數(shù)為奇數(shù)，則必存在另一個頂點B，指向它的箭頭數(shù)也為奇數(shù)（因為棱總數(shù)為偶數(shù)），對于頂點A與B，總有一條由棱組成的“路徑”連結(jié)它們，對該路徑上的每條棱，改變它們箭頭的方向，于是對于該路徑上除A，B外的每個頂點，指向它的箭頭數(shù)的奇偶性不變，而對頂點A，B，指向它的箭頭數(shù)變成了偶數(shù)。如果這時仍有頂點，指向它的箭頭數(shù)為奇數(shù)，那么重復(fù)上述做法，又可以減少兩個這樣的頂點，由于多面體頂點數(shù)有限，經(jīng)過有限次調(diào)整，總能使和是對每個頂點，指向它的箭頭數(shù)為偶數(shù)。命題成立。5染色法。例7 能否在55方格表內(nèi)找到一條線路，它由某格中心出發(fā)，經(jīng)過每個方格恰好一次，再回到出發(fā)點，并且途中不經(jīng)過任何方格的頂點？解 不可能。將方格表黑白相間染色，不妨設(shè)黑格為13個，白格為12個，如果能實現(xiàn)，因黑白格交替出現(xiàn)，黑白格數(shù)目應(yīng)相等，得出矛盾，故不可能。6凸包的使用。給定平面點集A，能蓋住A的最小的凸圖形，稱為A的凸包。例8 試證：任何不自交的五邊形都位于它的某條邊的同一側(cè)。證明 五邊形的凸五包是凸五邊形、凸四邊形或者是三角形，凸包的頂點中至少有3點是原五邊形的頂點。五邊形共有5個頂點，故3個頂點中必有兩點是相鄰頂點。連結(jié)這兩點的邊即為所求。7賦值方法。例9 由22的方格紙去掉一個方格余下的圖形稱為拐形，用這種拐形去覆蓋57的方格板，每個拐形恰覆蓋3個方格，可以重疊但不能超出方格板的邊界，問：能否使方格板上每個方格被覆蓋的層數(shù)都相同？說明理由。解 將57方格板的每一個小方格內(nèi)填寫數(shù)-2和1。如圖18-1所示，每個拐形覆蓋的三個數(shù)之和為非負(fù)。因而無論用多少個拐形覆蓋多少次，蓋住的所有數(shù)字之和都是非負(fù)的。另一方面，方格板上數(shù)字的總和為12(-2)+231=-1，當(dāng)被覆蓋K層時，蓋住的數(shù)字之和等于-K，這表明不存在滿足題中要求的覆蓋。-21-21-21-21111111-21-21-21-21111111-21-21-21-28圖論方法。例10 生產(chǎn)由六種顏色的紗線織成的雙色布，在所生產(chǎn)的雙色布中，每種顏色的紗線至少與其他三種顏色的紗線搭配過。證明：可以挑出三種不同的雙色布，它們包含所有的顏色。證明 用點A1，A2，A3，A4，A5，A6表示六種顏色，若兩種顏色的線搭配過，則在相應(yīng)的兩點之間連一條邊。由已知，每個頂點至少連出三條邊。命題等價于由這些邊和點構(gòu)成的圖中有三條邊兩兩不相鄰（即無公共頂點）。因為每個頂點的次數(shù)3，所以可以找到兩條邊不相鄰，設(shè)為A1A2，A3A4。（1）若A5與A6連有一條邊，則A1A2，A3A4，A5A6對應(yīng)的三種雙色布滿足要求。（2）若A5與A6之間沒有邊相連，不妨設(shè)A5和A1相連，A2與A3相連，若A4和A6相連，則A1A2，A3A4，A5A6對應(yīng)的雙色布滿足要求；若A4與A6不相連，則A6與A1相連，A2與A3相連，A1A5，A2A6，A3A4對應(yīng)的雙色布滿足要求。綜上，命題得證。二、習(xí)題精選1藥房里有若干種藥，其中一部分藥是烈性的。藥劑師用這些藥配成68副藥方，每副藥方中恰有5種藥，其中至少有一種是烈性的，并且使得任選3種藥恰有一副藥方包含它們。試問：全部藥方中是否一定有一副藥方至少含有4種烈性藥？（證明或否定）221個女孩和21個男孩參加一次數(shù)學(xué)競賽，（1）每一個參賽者最多解出6道題；（2）對每一個女孩和每一個男孩至少有一道題被這一對孩子都解出。求證：有一道題至少有3個女孩和至少有3個男孩都解出。3求證：存在無窮多個正整數(shù)n，使得可將3n個數(shù)1, 2, 3n排成數(shù)表a1, a2anb1, b2bnc1, c2cn滿足：（1）a1+b1+c1= a2+b2+c2= an+bn+cn=，且為6的倍數(shù)。（2）a1+a2+an= b1+b2+bn= c1+c2+cn=，且為6的倍數(shù)。4給定正整數(shù)n，已知克數(shù)都是正整數(shù)的k塊砝碼和一臺天平可以稱出質(zhì)量為1，2，n克的所有物品，求k的最小值f(n)。5空間中有1989個點，其中任何3點都不共線，把它們分成點數(shù)各不相同的30組，在任何3個不同的組中各取一點為頂點作三角形。試問：為使這種三角形的總數(shù)最大，各組的點數(shù)應(yīng)分別為多少？6在平面給定點A0和n個向量a1，a2，an，且使a1+a2+an =0。這組向量的每一個排列都定義一個點集：A1，A2，An=A0，使得求證：存在一個排列，使由它定義的所有點A1，A2，An-1都在以A0為角頂?shù)哪硞€600角的內(nèi)部和邊上。7設(shè)m, n, kN，有4個酒杯，容量分別為m,n,k和m+n+k升，允許進(jìn)行如下操作：將一個杯中的酒倒入另一杯中或者將另一杯倒?jié)M為止。開始時，大杯中裝滿酒而另3個杯子卻空著，問：為使對任何SN，S<m+n+k，都可經(jīng)過若干次操作，使得某個杯子中恰有S升酒的關(guān)于m,n,k的充分必要條件是什么？8設(shè)有30個人坐在一張圓桌的周圍，其中的每個人都或者是白癡，或者是聰明人。對在座的每個人都提問：“你右邊的鄰座是聰明人還是白癡？”聰明人總是給出正確的答案，而白癡既可能回答正確，也可能回答不正確。已知白癡的個數(shù)不超過F，求總可以指出一位聰明人的最大的F。9某班共有30名學(xué)生，每名學(xué)生在班內(nèi)都有同樣多的朋友，期末時任何兩人的成績都可分出優(yōu)劣，沒有相同的。問：比自己的多半朋友的成績都要好的學(xué)生最多能有多少人？