高中數(shù)學奧賽輔導第十講設計與構(gòu)造

1、高中數(shù)學奧賽輔導 第十講 設計與構(gòu)造知識、方法、技能組合數(shù)學問題，從內(nèi)容上講，大體可歸結(jié)為兩大類問題：一類是組合計數(shù)問題，這類問題在前幾講中已經(jīng)充分研究過了；另一類是組合設計問題，我們在本講和下一講對此作深入的探討.組合設計問題的基本含義是，對有限集合A，按照某性質(zhì)P做出“安排”.對這種“安排”，有時是指需要我們設計一個方案，這個方案滿足某些條件；有時是指對組合問題進行構(gòu)造性證明的具體構(gòu)造方法. 這就是我們這一講要講的設計與構(gòu)造. 對這種“安排”，有時不容易給出，需要我們對問題的條件重新調(diào)整，甚至反復調(diào)整；也有時需要對問題的條件重新組閣搭配；這種安排在二人對策（游戲）問題中需要取勝，需要給出至

2、勝策略，這就是我們下一講要研究的調(diào)整與對策.I. 設計有關“設計”的問題近幾年來是熱點競賽問題，例如1999年中國數(shù)學奧林匹克第三大題：MO太空城由99個空間站組成，任兩空間站之間有管形通道相連，規(guī)定其中99條通道為雙向通行的主干道，其余通道嚴格單向通行. 如果某四個空間站可以通過它們之間的通道從其中任一站到達另外任一站，則稱這四個站的集合為一個互通四站組.試為MO太空城設計一個方案，使得互通四站組的數(shù)目最大（請具體算出該最大數(shù)，并證明你的結(jié)論）.像這樣的問題就是一個典型的奧數(shù)組合設計問題. 組合設計問題的特點是（1）來源于實際；（2）組合基礎知識要扎實. 構(gòu)造也就是構(gòu)造方法解決組合問題，是組

3、合問題的解決中一種十分重要、十分奏效的方法. 經(jīng)常需要構(gòu)造的有：構(gòu)造映射，構(gòu)造集合，構(gòu)造恒等式，構(gòu)造組合模型，構(gòu)造集合劃分，構(gòu)造抽屜，構(gòu)造子集類，構(gòu)造圖形，構(gòu)造實例，等等.賽題精講例1：某市有n所中學，第I所中學派出Ci名學生（）來到體育館觀看球賽，全部學生總數(shù)為，看臺上每一橫排有199個座位，要求同一學校的學生必須坐在同一橫排. 問體育館最少要安排多少橫排才能保證全部學生都能坐下？ （1990年全國聯(lián)賽二度題3）【解】讓學生按學校順次入坐，每排坐滿后再轉(zhuǎn)入下一排，共用10（=1990199）排. 這時有的學校學生已坐在同一排，有的學校學生坐在兩排. 后一種學校至多9個. 再增加兩排座位，每排

4、可容納5個學校. 將上述（至多）9個學校移到這兩排，則每個學校的學生都坐在同一排，因此，12排足夠. 另一方面，1990=3458+18. 如果58個學校各有34名學生，1個學校18名學生，那么每排至多安排34名學生的學校5所（346199），11排至多安排34名學生的學校55所，所以11排是不夠的.例2：題目請見“知識、方法、技能”. （1999年中國數(shù)學奧林匹克試題三）【證明】在下面的討論中，設n是大于3的奇數(shù)，并記我們將討論n個空間站和n條雙行主干道的更一般情形. 對于本題而言.（1）如果某四個空間站中，有一個站與其他三站間的通道都從該站單向發(fā)出，那么，這四站的集合必定是不互通的四站組.

5、 約定將所有這樣的不互通四站組歸入S類；并將所有不屬S類的不互通四站組歸入T類. 則互通四站組的總數(shù)為用1，2，n給n個空間站編號. 設從第i號空間站發(fā)出的單行通道數(shù)為Si，則S類不互通四站組的總數(shù)為（2）對于如上定義的，熟知有關系（可直接驗證）：如果，那么，根據(jù)以上探討，通過“調(diào)整法”可以斷定據(jù)此估計互通四站組總數(shù)的上界為（3）如果能設計一個方案，使得S類不互通四站組的數(shù)目降到最少（實際降到0），那么，該方案的互通四站組的數(shù)目達到最大.為此目的，首先將編號為1，2，n的空間站依順時針次序安排在一個圓周上. 下面將給出滿足要求的兩種方案.第一方案 首先將沿圓周相鄰的空間站對之間的通道定為主干道

6、. 這樣設定了n條主干道：1，2，2，3，n1，n，n，1.對于，如果圓周上沿順時針方向從i到j的弧經(jīng)過奇數(shù)個中間站，那么，規(guī)定i號站與j號站之間的通道為ij單行道. 因為n是奇數(shù)，從k到l的順時針圓弧和從l到k的順時針圓弧當中，恰有一條經(jīng)過奇數(shù)個中間站，所以上述單行約定不會導致矛盾情形.按照此方案，從每個空間發(fā)出的單行道都為條，因此，S類不互通四站組總數(shù)降至最小下面將指出，按照此方案|T|=0.如果四站組中某兩站間有主干道相連，那么，四站組中其余任一站都與這兩站互通. 因此，這樣的四站組為互通四站組.考察從四站組的某三站到剩下一站的三條通道都單向通往剩下的一站的情形，設在除去剩下一站D的圓周

7、上，所述的三站按順時針方向依次為A，B，C. 因為AD，BD，CD，根據(jù)方案的單行規(guī)定可以判斷A與B之間和A與D之間的順時針圓弧上各經(jīng)過奇數(shù)個中間站，我們判明通道AB，AC，AD的單行方向，因此，這樣的不互通四站組A，B，C，D應歸入S類.根據(jù)以上的討論，可以斷定|T|=0.最后算出互通四站組數(shù)的最大值 對于n=99，互通四站數(shù)組的最大值為 第二方案（同樣先將編號為1，2，n的空間站按順時針次序安排于一個圓周上.）如果從a號空間站到b號空間站的順時針圓弧恰經(jīng)個或者個中間站，那么，規(guī)定a與b間的通道為雙行主干道. 如果從i號空間站到j號空間站的順時針圓弧經(jīng)過的中間站數(shù)少于，則規(guī)定i和j之間的通道

8、單向從i通往j.按照此方案，從每個空間站發(fā)出的單行通道數(shù)都為條. 因此，S類不互通四站組數(shù)降至最小值|S|=.按照此方案，同樣可證|T|=0. 事實上，與第一方案類似的驗證討論，I351可以判定：如果某四站組中有兩站間的通道是主干道，那么這四站組是互通的. 還可以判定：如果從四站組中某三站到剩下的一站D的通道都單向通往該站，那么這三站在除去D點的圓周上順時針方向排頭的一站A通往其他三站B，C，D的通道都單向發(fā)出：AB，AC，AD. 因此，這類四站組A，B，C，D應歸入S類.因此，按照此方案建造的太空城，沒有T類不互通四站組，并且互通四站組數(shù)達到最大. 剩下的計算同第一方案. 【評述】有一些不正

9、確的設計方案雖然能使各站發(fā)出的單行通道數(shù)目相等，卻不能排除如圖I351所示的那種不互通四站組，因而不能使互通四站組的數(shù)目達到最大.例3：給定空間中的9個點，其中任何4點都不共面，在每一對點之間都連有一條線段，這些線段可染為藍色或紅色，也可不染色. 試求出最小的n值，使得將其中任意n條線段中的每一條任意地染為紅藍二色之一，在這n條線段的集合中都必然包含有一個各邊同色的三角形. （1992IMO333）【解】本題的背景是以兩個熟知的結(jié)果:引理1：對五階完全圖的邊作二染色，存在一種染色方法，使得染色后的圖中沒有單色邊三角形，如圖I352所示，虛、實線分別表示兩種顏色的邊，這時，圖中無單色邊三角形.引

10、理2：對邊作二染色的六階完全圖中一定存在單色邊三角形.為了求解本題，借助于引理1，我們構(gòu)造一個9點圖如圖I353所示，這個圖的頂點編號為1，2，9，其中邊1，3，1，4，2，3，2，4染成紅色（實線），頂點1與2之間沒有邊連接，類似地，圓圈內(nèi)的頂點3與4，頂點5與6，頂點7與8均沒有邊相連，顯然，這個圖中沒有單色邊三角形，容易算出，這個圖中的邊數(shù)是.另一方面，沒染色的線段至少有33條，則由于線段共條，不染色的線段至多3條.若點A1引出不染色的線段，則去掉A1及所引出的線段，若剩下的圖中還有A2引出不染色的線段，則去掉A2及所引出的線段，依此進行，由于不染色的線段至多有3條，所以至多去掉3個頂點（及從它們引出的線段），這時至少剩下6個點. 每兩點之間的連線染上紅色或藍色，由引理2知，必存在一個同色三角形.綜上所述，n的最小值為33.例4：對. 【證明】構(gòu)造集合表示從A中取n個元素的組合數(shù)，即由n個元素組成的A的真子集有個，而A的所有子集數(shù)是 個，故有 又