Question

【题目】圆周上依次排列着共2013个不同的点，每个点染红、蓝、绿三色之一.在以任意两个同色点为端点的圆弧上，与此两端点异色的点的个数为偶数的染色方法称为“好染色”问：所有好染色方法有多少种？

Answer 1

【答案】

【解析】

考虑一般的情形：

圆周上有n（奇数，）个不同的点时的好染色种数.

显然，三种单色染色方法是好染色.

接下来求非单色好染色.

设Y表示圆周上n个不同点时非单色好染色的集合，X表示圆周上n个不同点时任意相邻两点异色的染色方法的集合.

可建立集合X与Y之间的一一对应.

考虑圆周上2n（n为奇数）边形.设奇顶点的染色属于集合定义每个偶顶点的颜色与其相邻奇顶点不同.则得偶顶点的染色方法是好染色.

若以两个同色点为端点的某一段圆弧之间没有与端点同色的点，则称这两点为“最近同色点

显然，一个染色方法为好染色点的充分必要条件为任意两个最近同色点之间的异色点个数为偶数.

先证明偶顶点的染色方法为一个好染色，即证明任意两个最近同色点的偶顶点之间包含的偶顶点的个数为偶数.

设M、N为任意两个最近同色点的偶顶点（不妨设为红色），且包含在M、N之间的偶顶点为k个.

当k=0时，则结论成立；

当时，记k个偶顶点为，则在M、N之间还包含k+1个奇顶点，记为，排列如下：.

因为点均不为红色，所以，点A与的颜色不能为蓝、绿（或绿、蓝）（若出现上述两种情形，则为红色，与假设矛盾）.又点与不同色，则点中一个隔一个的为红色.由点M、N为红色，知点A、不为红色.于是，点为红色.从而，k为偶数，即M、N中包含的异色顶点为偶数个.因此，偶顶点染色方法为好染色.故得到一个从集合X到Y的映射f.

再证明：f为一一对应.

（1）f为单射.记圆周上2n边形（为奇顶点，为偶顶点，其中i=1，2，…，n）.

设，且.

若，因为为非单色好染色，所以，存在两个相邻异色偶顶点（不妨设为、）.从而，得到a、b的对应这两偶顶点之间的奇顶点的颜色相同.

由a、b及f的定义，知（，规定）三个顶点所染的颜色不同，换言之，为所染的颜色由、唯一确定，这样由点、在a、b及f下所染颜色分别相同得所染颜色也相同，再由、所染颜色分别相同得所染的颜色也相同，依此类推，在a、b下，点所染的颜色分别相同，即，这与假设矛盾.

因此，f为单射.

（2）f为满射.

对，设M、N是c中的相邻异色偶顶点，则定义位于M、N之间的奇顶点不同于M、N的颜色.

若为c中一串连续同色（不妨设为红色）偶顶点，它们位于偶顶点M、N间.若M、N同色（不妨设为蓝色），则k为偶数（若为奇数，则两同色点之间的异色点个数为奇数，与好染色矛盾），此时，定义M、N之间所有奇顶点的的颜色依次为绿、蓝、绿、……蓝、绿.

若M、N异色（不妨设M为蓝色，N为绿色），则k为奇数（若不然，k为偶数，则每一段连续同色点的偶顶点为偶数个.否则，不妨设沿方向存在点，若点与N重合，则n为偶数，与n为奇数矛盾.若点与N不重合，则与相邻的点C与M、N或之一同色，其之间所包含的异色点为奇数.矛盾）.此时，定义M、N之间所有奇顶点的的颜色依次为绿、蓝、绿、……蓝.如此定义的奇顶点染色方法，相邻两个奇顶点颜色相异.

最后计算集合X中元素的个数.记表示对圆周上n个点的好的染色法的个数.

由，，则

故好染色方法总数为