●

(南京市外國(guó)語(yǔ)學(xué)校 江蘇南京 210008)

組合賽題解題思路的探索

●黃志軍

(南京市外國(guó)語(yǔ)學(xué)校 江蘇南京 210008)

組合賽題是國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中的熱點(diǎn)之一,是數(shù)學(xué)競(jìng)賽中難度較大的問(wèn)題,同時(shí)也是考查學(xué)生數(shù)學(xué)思維的典型問(wèn)題.組合問(wèn)題的內(nèi)容非常廣泛,涉及到代數(shù)、幾何、數(shù)論等多個(gè)分支,解法靈活多變.筆者選編了近幾年國(guó)內(nèi)外一些值得欣賞的典型賽題,并給出一些組合賽題的多種解法,以期靈活運(yùn)用數(shù)學(xué)知識(shí)去進(jìn)行探索與嘗試,以展現(xiàn)思維的過(guò)程,盡力尋求更好的解法.

例1設(shè)空間中有2n(n≥2)個(gè)點(diǎn)，其中任何4個(gè)點(diǎn)都不共面，將它們之間任意連接N條線段，這些線段都至少構(gòu)成一個(gè)三角形，求N的最小值．

分析通過(guò)構(gòu)造實(shí)例，說(shuō)明N≥n2+1，進(jìn)而證明當(dāng)N=n2+1時(shí)，若在2n個(gè)點(diǎn)間連有N條線段，則這些線段至少構(gòu)成一個(gè)三角形．

解法1將2n個(gè)已知點(diǎn)均分為集合S和T：

S={A1，A2，…，An}，T={B1，B2，…，Bn}．

現(xiàn)將每對(duì)點(diǎn)Ai和Bj之間都連接一條線段AiBj，而同組的任何2個(gè)點(diǎn)之間均不連線，則共有n2條線段．這時(shí)，2n個(gè)已知點(diǎn)中的任何3個(gè)點(diǎn)中至少有2個(gè)點(diǎn)屬于同一集合，即這2個(gè)點(diǎn)之間沒(méi)有連線．因而n2條線段不能構(gòu)成任何三角形，這意味著N的最小值必大于n2．

下面用數(shù)學(xué)歸納法來(lái)證明：若在2n個(gè)已知點(diǎn)間連有n2+1條線段，則這些線段至少構(gòu)成一個(gè)三角形．

當(dāng)n=2時(shí)，n2+1=5，即4個(gè)點(diǎn)間有5條線段．顯然，這5條線段恰構(gòu)成2個(gè)三角形．設(shè)當(dāng)n=k(k≥2)時(shí)命題成立，當(dāng)n=k+1時(shí)，任取一條線段AB．若從點(diǎn)A，B向其余2k個(gè)點(diǎn)引出的線段條數(shù)之和不小于2k+1，則必定存在一點(diǎn)C，它與點(diǎn)A，B都有連線，從而△ABC即為所求．若從點(diǎn)A，B引出的線段條數(shù)之和不超過(guò)2k，則當(dāng)把點(diǎn)A，B除去后，其余的2k個(gè)點(diǎn)之間至少還有k2+1條線段．由歸納假設(shè)知，它們至少構(gòu)成一個(gè)三角形．

綜上可知，所求N的最小值為n2+1．

解法2設(shè)這2n個(gè)點(diǎn)為A1，A2，…，A2n，可知所求N的最小值不小于n2+1．由于2n個(gè)點(diǎn)之間連有n2+1條線段，平均每個(gè)點(diǎn)引出n條線段還多，故可猜想必定有一條線段的2個(gè)端點(diǎn)引出的線段數(shù)之和不小于2n+1，用反證法證明．

設(shè)從A1，A2，…，A2n引出的線段條數(shù)分別為a1，a2，…，a2n且對(duì)于任一線段AiAj都有ai+aj≤2n.于是，所有線段的2個(gè)端點(diǎn)所引出的線段條數(shù)之和的總數(shù)不超過(guò)2n(n2+1)．但在此計(jì)數(shù)中，點(diǎn)Ai恰被計(jì)算了ai次，故有

(1)

從而

(2)

式(2)與式(1)矛盾．從而證明了必有一條線段，從它的2個(gè)端點(diǎn)引出的線段數(shù)之和不小于2n+1．不妨設(shè)這條線段為A1A2，從而又有Ak(k≥3)，使線段A1Ak，A2Ak都存在，于是△A1A2Ak即為所求．

解法3易知所求N的最小值不小于n2+1．下面用極端原理來(lái)證明，當(dāng)N=n2+1時(shí)，這些線段至少構(gòu)成一個(gè)三角形，從而所求N的最小值為n2+1．

設(shè)2n個(gè)已知點(diǎn)間連有n2+1條線段，且這些線段不構(gòu)成任何三角形.設(shè)A是2n個(gè)點(diǎn)中引出線段條數(shù)最多的一個(gè)點(diǎn)，共引出k條線段{ABj|j=1，2，…，k}.于是{B1,B2,…，Bk}中任何2個(gè)點(diǎn)之間都沒(méi)有連線，否則必構(gòu)成三角形．因而，從任一Bj引出的線段條數(shù)不超過(guò)2n-k．

除了A,B1,B2,…，Bk之外還有2n-k-1個(gè)點(diǎn)，其中任何一點(diǎn)引出的線段條數(shù)不超過(guò)k．于是得到

k(2n-k)≤n2，

矛盾．

評(píng)注本題用了3種方法求解，都是先通過(guò)例子確定出N的一個(gè)下界，然后用不同的方法證明這個(gè)下界是可以達(dá)到的，進(jìn)而求出N的最小值．解法1用數(shù)學(xué)歸納法，解法2運(yùn)用了反證法與柯西不等式，解法3則是運(yùn)用了極端原理．

例2已知平面上一個(gè)含有n個(gè)點(diǎn)的集合S，具有如下性質(zhì)：

(1)S中任意3個(gè)點(diǎn)不共線；

(2)對(duì)S中每個(gè)點(diǎn)P，在S中至少有k個(gè)點(diǎn)到點(diǎn)P的距離相等.

解得

解得

例3300個(gè)工作人員分成3個(gè)部門(mén)，每個(gè)部門(mén)100人,每2個(gè)人或者互相認(rèn)識(shí)，或者互不認(rèn)識(shí)．證明：存在不同部門(mén)的2個(gè)人，使得在第3個(gè)部門(mén)中，或有17個(gè)人都認(rèn)識(shí)他們，或有17個(gè)人都不認(rèn)識(shí)他們．

分析將3個(gè)部門(mén)的工作人員所成的集合分別記為A，B，C，集合中的元素都稱為頂點(diǎn)．在任何2個(gè)不屬于同一集合的頂點(diǎn)之間都連一條邊，2個(gè)人認(rèn)識(shí)時(shí)邊為紅色，不認(rèn)識(shí)時(shí)為藍(lán)色(這稱為雙色三部圖)．共連得1003個(gè)三角形．如果三角形中的某個(gè)角的2條邊同色，就稱為同色角．

評(píng)注化歸是指把要解決的問(wèn)題，通過(guò)某種轉(zhuǎn)化,歸結(jié)到一類已經(jīng)解決或者能比較容易解決的問(wèn)題中去，最終獲得原問(wèn)題的一種解題策略.前蘇聯(lián)數(shù)學(xué)家雅諾夫斯卡婭在回答“解題意味著什么”時(shí)說(shuō)：“解題就是意味著把所要解決的問(wèn)題轉(zhuǎn)化為已經(jīng)解決的問(wèn)題．”

例4設(shè)正整數(shù)n≥3，而a1，a2，…，an是任意n個(gè)互異的實(shí)數(shù)，其和為正數(shù)．若它的一個(gè)排列b1，b2，…，bn滿足：對(duì)任意的k=1，2，…，n，均有b1+b2+…+bk>0，則稱這個(gè)排列是好的，求好的排列個(gè)數(shù)的最小值．

分析考察最壞的情形：要使b1+b2+…+bk>0很難滿足，只需讓負(fù)數(shù)盡可能多,即取a2，a3，…，an均為負(fù)數(shù)，a1=-a2-a3-…-an+1．此時(shí)對(duì)于任何一個(gè)好的排列(b1，b2，…，bn)，均有b1=a1，而b2，b3，…，bn可以是a2，a3，…，an的任意排列，故此時(shí)共有(n-1)!個(gè)好的排列．下面證明至少有(n-1)!個(gè)好的排列．注意到(n-1)!是將a1，a2，…，an排在圓周上的不同圓排列的個(gè)數(shù)，因此首先證明每一個(gè)圓排列對(duì)應(yīng)一個(gè)好排列．為了方便，稱好排列的首項(xiàng)為好數(shù)，下面只需證明每個(gè)圓排列中必存在一個(gè)好數(shù)．

證法1對(duì)n進(jìn)行歸納．當(dāng)n=1時(shí)，結(jié)論顯然成立．假設(shè)對(duì)一切n0，因此a1，a2，…，an中至少存在一個(gè)正數(shù)．將每個(gè)正數(shù)和按逆時(shí)針順序在它之后的下一個(gè)正數(shù)之前的所有數(shù)編為一組，每組至少有一個(gè)數(shù)，由于a1，a2，…，an不是都為正數(shù)，因此至少有一組有2個(gè)數(shù)，故至多有k-1組．對(duì)每組數(shù)求和，得到少于k個(gè)和．將這些和按它們所在組的順序?qū)懺趫A周上，這些和的總和為正，由歸納假設(shè)知，這些和中存在一個(gè)和為好數(shù)．考慮這個(gè)和所在的組中的那個(gè)正數(shù)，則這個(gè)數(shù)是整個(gè)圓排列中的好數(shù)．由歸納假設(shè)，結(jié)論成立．

證法2利用極端性原理．對(duì)任何一個(gè)圓排列(b1，b2，…，bn)，考察所有以bi為首項(xiàng)的部分和：bi+bi+1+…+bi+t，其中大于n的下標(biāo)取模n的余數(shù)，對(duì)所有i=1，2，…，n和所有t=0，1，2，…，n-1，必存在一個(gè)最小的部分和bi+bi+1+…+bi+t，因?yàn)橹辽俅嬖谝粋€(gè)非正數(shù)，所以bi+bi+1+…+bi+t≤0．在所有這樣的最小和中又設(shè)項(xiàng)數(shù)t+1最大的一個(gè)為bi+bi+1+…+bi+t，下面證明bi+t+1是好數(shù)．

實(shí)際上，若存在正整數(shù)k，使

bi+t+1+bi+t+2+…+bi+t+k≤0，

則(bi+bi+1+…+bi+t)+(bi+t+1+bi+t+2+…+

bi+t+k)≤bi+bi+1+…+bi+t,

這與bi+bi+1+…+bi+t的和最小且項(xiàng)數(shù)最多矛盾．

由于共有(n-1)!個(gè)圓排列，而每個(gè)圓排列至少對(duì)應(yīng)一個(gè)好排列，且不同的圓排列對(duì)應(yīng)的好排列是不同的，故至少有(n-1)!個(gè)好排列．綜上所述，所求最小值為(n-1)!.

(注:圖G的2個(gè)不同頂點(diǎn)u,v之間的一條長(zhǎng)度為k的路徑是指一個(gè)頂點(diǎn)序列u=v0,v1,…,vk=v,其中vi與vi+1相鄰,i=0,1,…,k-1.)

證明對(duì)任意2個(gè)不同頂點(diǎn)u,v,若u,v之間的最短路徑長(zhǎng)度為k,則稱它們之間的距離為k.考慮圖G,其頂點(diǎn)集為{x1,x2,…,x3n2-n,y1,y2,…,yn},yi與yj相鄰(1≤i

易知xi與xj的距離不超過(guò)3,圖G符合條件,G共有

條邊.

下面證明滿足題設(shè)條件的圖G=G(V,E)的邊數(shù)至少為N.設(shè)X?V是所有度等于1的頂點(diǎn)的集合,Y?(VX)為剩余頂點(diǎn)中與X中某個(gè)頂點(diǎn)相鄰的所有頂點(diǎn)的集合,Z?V(X∪Y)為剩余頂點(diǎn)中與Y中某個(gè)頂點(diǎn)相鄰的所有頂點(diǎn)的集合,W?V(X∪Y∪Z),可得到以下性質(zhì)：

性質(zhì)1Y中的任意2個(gè)頂點(diǎn)都相鄰.

這是因?yàn)槿魕1,y2∈Y是2個(gè)不同頂點(diǎn),設(shè)x1,x2∈X分別與y1,y2相鄰,由x1與x2的距離不超過(guò)3,可知y1與y2相鄰.

性質(zhì)2W中的頂點(diǎn)與每個(gè)Y中頂點(diǎn)的距離均為2.

若不然設(shè)w0∈W,y0∈Y的距離不小于3(距離顯然不小于2),設(shè)x0∈X與y0相鄰,則w0與x0的距離不小于4,與題設(shè)矛盾.性質(zhì)2成立，由此可知每個(gè)W中的點(diǎn)都與某個(gè)Z中的點(diǎn)相鄰.

當(dāng)y≤n-1時(shí),由于每個(gè)頂點(diǎn)的度不超過(guò)4n,故

x+z≤y[4n-(y-1)]=y(4n+1-y)≤

(n-1)(3n+2)=3n2-n-2,

w≥3n2-y-y(4n+1-y)≥3.

若a>1,則

N;

評(píng)注構(gòu)造與論證是組合極值的2個(gè)方面,構(gòu)造是構(gòu)造合乎條件的對(duì)象或構(gòu)造使命題不成立的反例.論證是論證某種量滿足某個(gè)不等式或論證某些對(duì)象具有某種性質(zhì),兩者都需要靈活的思維、豐富的想象及創(chuàng)造性的構(gòu)想.

數(shù)學(xué)競(jìng)賽是解題的競(jìng)賽,只有通過(guò)問(wèn)題才能學(xué)會(huì)解題.要提高組合解題能力,必須反復(fù)練習(xí),在解各類題中,善于總結(jié),不僅要尋找各種不同的解法，更要找出最佳的方法.我們應(yīng)當(dāng)注意數(shù)學(xué)思想與數(shù)學(xué)審美,不斷提高鑒賞能力.