文档介绍：文档
【组合十讲】
组合构造
陶平生
构造法是解证组合问题的重要方法与基本手段， 使用它， 常常可以将问题化难为易， 化
抽象为直观， 它需要较强的结构转化与知识综合能力．常用的构造方法有：数论构造法；
几何构造法；模型构造法；旋转、置换（群）构造法；图表构造法；图论构造法等．
一、数论构造法
我们通过一些具体例子来说明这一方法的运用．
1、空间有 2011个点，无三点共线，现将每两点之间用一种颜色的线连接，使得对于
其中任意一点而言， 由该点发出的任两条线皆不同色， 问至少需要多少种不同颜色的线？证
明你的结论．若将 2011个点改为 2012 个点，情况又将如何？
解：一般化，将 2011改为 n ，其中正整数 n 2 ，线段颜色数的最小值记为 f (n) ，
易知 f (2) 1, f (3) 3, f (4) 3, f (5) 5 ，⋯ ⋯
今证明，一般情况下有 f (2n 1) 2n 1, f (2n) 2n 1．
设 2n 1 个点为 A0 , A1,L , A2 n ，由于每点都要发出 2n 条线， 诸线不同色， 这样至少需
要 2n 色；
再证 2n 色不够， 若总共只有 2n 色，则每点都要恰好属于各色线的端点一次． 现在设总
共有 k 条红色线，它们总共有 2k 个两两互异端点，于是 2k 2n 1，矛盾！
因此 f (2n 1) 2n ，即 f (2n 1) 2n 1．
下面说明最小值 2n 1 可以取到，采用数论构造法：
用 S0 , S1 ,L , S2n 分别表示这 2n 1 色，而 x 表示整数 x 模 2n 1 的最小非负余数，即
，于是，对
x 0,1,L ,2n ，对于任意两点 Ai , A j (i j ) ，将连线 Ai A j 染第 i j 色 Si j
于任意一点 Ak ，发自 Ak 的任两条线皆不同色．事实上，假若 Ak Ai 与 Ak Aj 同色，则有
k i k j ，即 k i k j (mod 2n 1) ，得 i j (mod 2n 1) ，因 i, j 0,1,L ,2 n ，
故有 i j ，矛盾！故这种染色方案合于条件，因此， f (2n 1) 2n 1．
又对于 2n 2 个点 A0 , A1 ,L , A2 n , A2n 1 ，由于每点都要向其余 2n 1 点共发出 2n 1
条线，诸线不同色，这样至少需要 2n 1 色，只要证， 2n 1 色已足够．
构造，仍用 S0 , S1 ,L , S2 n 分别表示这 2n 1色，暂不考虑点 A2n 1 ，先对前 2n 1个点
A0 , A1 ,L , A2n 两两间的连线依照上述 2n 1 个点的情形染色，我们注意到，对于其中任意
1
文档
两点 Ai , Aj (i j) 的连线 Ai Aj 染色时，要求 i j ，也就是说，由点 Ai 发出的