組合構(gòu)造答案及講稿

1、1【組合十講組合十講】組合構(gòu)造組合構(gòu)造陶平生構(gòu)造法是解證組合問題的重要方法與基本手段，使用它，常?？梢詫栴}化難為易，化抽象為直觀，它需要較強(qiáng)的結(jié)構(gòu)轉(zhuǎn)化與知識(shí)綜合能力常用的構(gòu)造方法有：數(shù)論構(gòu)造法；幾何構(gòu)造法；模型構(gòu)造法；旋轉(zhuǎn)、置換（群）構(gòu)造法；圖表構(gòu)造法；圖論構(gòu)造法等一、數(shù)論構(gòu)造法我們通過一些具體例子來說明這一方法的運(yùn)用、空間有個(gè)點(diǎn)，無三點(diǎn)共線，現(xiàn)將每?jī)牲c(diǎn)之間用一種顏色的線連接，使得對(duì)于12011其中任意一點(diǎn)而言，由該點(diǎn)發(fā)出的任兩條線皆

2、不同色，問至少需要多少種不同顏色的線？證明你的結(jié)論若將個(gè)點(diǎn)改為個(gè)點(diǎn)，情況又將如何？20112012解：一般化，將改為，其中正整數(shù)，線段顏色數(shù)的最小值記為，2011n2n?()fn易知，……(2)1(3)3(4)3(5)5ffff????今證明，一般情況下有(21)21(2)21fnnfnn?????設(shè)個(gè)點(diǎn)為，由于每點(diǎn)都要發(fā)出條線，諸線不同色，這樣至少21n?012nAAA?2n需要色；2n再證色不夠，若總共只有色，則每點(diǎn)都要恰好屬于各色

3、線的端點(diǎn)一次現(xiàn)在設(shè)2n2n總共有條紅色線，它們總共有個(gè)兩兩互異端點(diǎn)，于是，矛盾！k2k221kn??因此，即(21)2fnn??(21)21fnn???下面說明最小值可以取到，采用數(shù)論構(gòu)造法：21n?用分別表示這色，而表示整數(shù)模的最小非負(fù)余數(shù)，即012nSSS?21n?xx21n?，對(duì)于任意兩點(diǎn)，將連線染第色，于是，對(duì)??012xn??()ijAAij?ijAAij?ijS?于任意一點(diǎn)，發(fā)自的任兩條線皆不同色事實(shí)上，假若與同色，則有kA

4、kAkiAAkjAA，即，得，因，kikj???(mod21)kikjn????(mod21)ijn????012ijn??故有，矛盾！故這種染色方案合于條件，因此，ij?(21)21fnn???又對(duì)于個(gè)點(diǎn)，由于每點(diǎn)都要向其余點(diǎn)共發(fā)出22n?01221nnAAAA??21n?條線，諸線不同色，這樣至少需要色，只要證，色已足夠21n?21n?21n?構(gòu)造，仍用分別表示這色，暫不考慮點(diǎn)，先對(duì)前個(gè)012nSSS?21n?21nA?21n?點(diǎn)兩

5、兩間的連線依照上述個(gè)點(diǎn)的情形染色，我們注意到，對(duì)于其中任012nAAA?21n?3的這個(gè)數(shù)與第三段的數(shù)反序相加，就得到相等的個(gè)和）nn若將第二段的每個(gè)數(shù)各減，問題又化為：若奇數(shù)，存在前個(gè)自然數(shù)n3n?n的兩個(gè)排列：及，使得恰011n??12nxxx?12nyyy?1122nnxyxyxy????好組成個(gè)連續(xù)自然數(shù)；n為此，采用構(gòu)造法，設(shè)個(gè)連續(xù)自然數(shù)中，最小的一數(shù)為n1122nnxyxyxy????，k則此個(gè)數(shù)為，其和為，又據(jù)n11kkk

6、n????(1)2nnkn??，故由，得??1()201(1)(1)niiixynnn???????????(1)(1)2nnknnn????，12nk??這樣，問題化為：若奇數(shù)，存在前個(gè)自然數(shù)的兩個(gè)排列：3n?n011n??及，使得12nxxx?12nyyy?，11221113(1)112222nnnnnnxyxyxyn???????????????為直觀起見，記為；12112212()nnnnxxxxyxyxyyyy????????

7、?????注意到，時(shí)，，而；3n?3112k???123123021(123)102xxxyyy??????????????時(shí)，，而；5n?5122k???123451234502413(23456)21043xxxxxyyyyy??????????????時(shí)，，而；7n?3k?123456712345670246135(3456789)3210654xxxxxxxyyyyyyy??????????????若用記號(hào)表示整數(shù)被除得的最小非