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