文档介绍：【组合十讲】
组合构造
陶平生
构造法是解证组合问题的重要方法与基本手段，使用它，常常可以将问题化难为易，化 抽象为直观，：数论构造法； 几何构造法；模型构造法；旋转、置换(群)构造法；图表构造法；图论构造法等.
一、数论构造法
我们通过一些具体例子来说明这一方法的运用•
1、空间有2011个点，无三点共线，现将每两点之间用一种颜色的线连接，使得对于 其中任意一点而言，由该点发出的任两条线皆不同色，问至少需要多少种不同颜色的线？证 ，情况又将如何？
解：一般化，将2011改为"，其中正整数n>2,线段颜色数的最小值记为/("),
易知/(2) = 1,/(3) = 3,/(4) = 3,/(5) = 5,……
今证明，一般情况下有/(2h + 1) = 2h + 1,/(2h) = 2n-l.
设2“ + 1个点为4°,舛,…，企”，由于每点都要发出2“条线，诸线不同色，这样至少需 要2“色；
再证2“色不够，若总共只有2“色， 共有k条红色线，它们总共有2E个两两互异端点，于是2k^2n + l,矛盾！
因此 /(2n + l)>2n,即 /(2n+l) > 2n+l.
下面说明最小值2“ + 1可以取到，采用数论构造法：
用So’S】,…，S?”分别表示这2“ + 1色，而元表示整数x模2“ + 1的最小非负余数，即 元w{0,：!,•••,2“},对于任意两点Ai,Aj (z^ j),将连线A"染第芮色S用，于是，对 于任意一点入，，假若A"与4厲同色，则有
k + i = k + j ,即 k + i = k + j (mod2n +1),得 i 三 j (mod2n +1),因 i,je 2“},
故有i = j,矛盾！故这种染色方案合于条件，因此，/(2h + 1) = 2h + 1.
又对于2“ + 2个点…,人2”,人2”+1，由于每点都要向其余2" + 1点共发出2“ + 1
条线，诸线不同色，这样至少需要2“ + 1色，只要证，2“ + 1色已足够.
构造，仍用So，S”・・，S2”分别表示这2“ + 1色，暂不考虑点A2„+1 ,先对前2“ + 1个点
A2„两两间的连线依照上述2“ +1个点的情形染色,我们注意到，对于其中任意
两点A,., A- j)的连线4内染色时，要求心八 也就是说，由点A发出的2“条线的颜 色代号齐}，je{0,l,---,2n}\{z},为模2“ + 1的完系中缺少了一个剩余7+7 = 2/.
现将点A2h+1与前2“ +1个点中任一点£的连线A2n+1A,., (z = 0,1,---,2n)染第f i色 S-,由于当心)时27与2j模2“ + 1不同余，故由点仏”+i发出的加+ 1条线互不同色， 由其它点发出的2“ + 1条线也互不同色，故这种染色方案合于条件.
因此，f(2n+2) = 2n+l,从而f(2n) = 2n-l.
于是对于2011个点或是2012个点，都至少需要2011种颜色的线.
下面的图形是77 = 5和“ =，利用数论构造法给出的染色方案， 优美和谐，浑然天成.
A。
2、证明：可以将集合M= {1,2,•••,2012}中的元素分成671组，使得每组的元素 和相等.
证：我们可一般化为下述命题：若奇数n>l,则集合M ={l,2,---,3n-l}可以分拆 成"个两两不交的元素之和相等的子集之并.
在集合M中添加元素0,并将诸元素依自小到大的顺序排列，然后按每"个数一段分 成三段:0,1, • • •,« — 1, | h, h +1, • • •, 2n — 1, | In, 2n +1, • • •, 3n — 1.
易知，对于两个具有k个项的递增连续自然数数列尢 1，尢2,…，忑及必,丁2,…,九，它们 按相反次序相加的每两项之和为常数：即%! + = x2 +儿一1 = •••=可+ X；
因此只要证，可以将第一段的"个数适当排成再卫2,…,a”，第二段的"个数适当排成 也,^,…/”，使得q + %色+ E，…,a” + bn恰好组成"个连续自然数；(此时只要将所得的 这“个数与第三段的数反序相加，就得到相等的"个和•)
若将第二段的每个数各减"，问题又化为:若奇数n>3,存在前"个自然数0,1,…，"-1 的两个排列：^，兀,…,*”及"，丁2,…，儿，使得丙+",兀+乃,…,X” +儿恰好组成"个连 续自然数；
为此，采用构造法，设"个连续自然数x{ + yvx2 +