組合構造答案及講稿

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

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

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

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

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

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

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