組合賽題解題思路的探索

●

(南京市外國語學校 江蘇南京 210008)

組合賽題解題思路的探索

●黃志軍

(南京市外國語學校 江蘇南京 210008)

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

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

分析通過構造實例，說明N≥n2+1，進而證明當N=n2+1時，若在2n個點間連有N條線段，則這些線段至少構成一個三角形．

解法1將2n個已知點均分為集合S和T：

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

現將每對點Ai和Bj之間都連接一條線段AiBj，而同組的任何2個點之間均不連線，則共有n2條線段．這時，2n個已知點中的任何3個點中至少有2個點屬于同一集合，即這2個點之間沒有連線．因而n2條線段不能構成任何三角形，這意味著N的最小值必大于n2．

下面用數學歸納法來證明：若在2n個已知點間連有n2+1條線段，則這些線段至少構成一個三角形．

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

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

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

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

(1)

從而

(2)

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

解法3易知所求N的最小值不小于n2+1．下面用極端原理來證明，當N=n2+1時，這些線段至少構成一個三角形，從而所求N的最小值為n2+1．

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

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

k(2n-k)≤n2，

矛盾．

評注本題用了3種方法求解，都是先通過例子確定出N的一個下界，然后用不同的方法證明這個下界是可以達到的，進而求出N的最小值．解法1用數學歸納法，解法2運用了反證法與柯西不等式，解法3則是運用了極端原理．

例2已知平面上一個含有n個點的集合S，具有如下性質：

(1)S中任意3個點不共線；

(2)對S中每個點P，在S中至少有k個點到點P的距離相等.

解得

解得

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

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

評注化歸是指把要解決的問題，通過某種轉化,歸結到一類已經解決或者能比較容易解決的問題中去，最終獲得原問題的一種解題策略.前蘇聯數學家雅諾夫斯卡婭在回答“解題意味著什么”時說：“解題就是意味著把所要解決的問題轉化為已經解決的問題．”

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

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

證法1對n進行歸納．當n=1時，結論顯然成立．假設對一切n0，因此a1，a2，…，an中至少存在一個正數．將每個正數和按逆時針順序在它之后的下一個正數之前的所有數編為一組，每組至少有一個數，由于a1，a2，…，an不是都為正數，因此至少有一組有2個數，故至多有k-1組．對每組數求和，得到少于k個和．將這些和按它們所在組的順序寫在圓周上，這些和的總和為正，由歸納假設知，這些和中存在一個和為好數．考慮這個和所在的組中的那個正數，則這個數是整個圓排列中的好數．由歸納假設，結論成立．

證法2利用極端性原理．對任何一個圓排列(b1，b2，…，bn)，考察所有以bi為首項的部分和：bi+bi+1+…+bi+t，其中大于n的下標取模n的余數，對所有i=1，2，…，n和所有t=0，1，2，…，n-1，必存在一個最小的部分和bi+bi+1+…+bi+t，因為至少存在一個非正數，所以bi+bi+1+…+bi+t≤0．在所有這樣的最小和中又設項數t+1最大的一個為bi+bi+1+…+bi+t，下面證明bi+t+1是好數．

實際上，若存在正整數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的和最小且項數最多矛盾．

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

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

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

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

條邊.

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

性質1Y中的任意2個頂點都相鄰.

這是因為若y1,y2∈Y是2個不同頂點,設x1,x2∈X分別與y1,y2相鄰,由x1與x2的距離不超過3,可知y1與y2相鄰.

性質2W中的頂點與每個Y中頂點的距離均為2.

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

當y≤n-1時,由于每個頂點的度不超過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;

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

數學競賽是解題的競賽,只有通過問題才能學會解題.要提高組合解題能力,必須反復練習,在解各類題中,善于總結,不僅要尋找各種不同的解法，更要找出最佳的方法.我們應當注意數學思想與數學審美,不斷提高鑒賞能力.