棋盘染色计数

superacid

1.将n×n棋盘的每个小方格都染上黄白两种颜色之一，满足对任意2×2的小正方形都恰好含两个染黄色，两个染白色。
问：存在多少种染色方法？

2.将n×n棋盘的每个小方格都染上红绿橙蓝四种颜色之一，满足对任意2×2的小正方形都恰好含四种颜色各一种。
问：存在多少种染色方法？


正好是一个魔方的六个面的颜色。

[ 本帖最后由 superacid 于 2009-7-9 19:05 编辑 ]

Osullivan

额~~~~~~~~~~
没看第一题，直接做第二题目，吃亏啊~~~~~~~~~~~~~~~~

Cielo

没仔细想过第二题，来学习一下！

[ 本帖最后由 Cielo 于 2009-7-12 00:14 编辑 ]

superacid

楼上正确，看来第一题还是起到了极大的提示作用。

noski

又算了第二问，答案应该是  3 * 2 ^ (n+2) - 24

说一说我的思路：
第一问，白色和黄色，对于n*n的棋盘格，前两行/列的排列决定了所有的颜色，前两行有2^n种情况，前两列有2^n种情况，再减去重复计算的如国际象棋这种黄白交替的2种情况，最后结果就是 2 ^ (n+1) - 2

第二问是在第一问的基础上做的。我们不妨把红色和橙色都放在第一问的白格子里，把绿色和蓝色放在第一问的黄格子里，就会发现，对应于第一问的每种情况，第二问都会有4种可能，除去下面两种特殊情况：
一是全长条的形状：
1 1 1 1
0 0 0 0
1 1 1 1
0 0 0 0
二是国际象棋棋盘：
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
特殊情况单独考虑，情况一对应 2^n 种可能，情况二对应 2种可能，就不难得到最终结果。

PS：前几天金眼睛发的点灯游戏程序，里面有单灯控制功能，正好用来做这个题~

superacid

如果3*3是这样的：
A B C
C D A
A B C
那么右下角扩展为4*4时只有两种：
A B C X
C D A X
A B C B
X X A D

A B C X
C D A X
A B C D
X X A B

原因就是第3行第一个A产生了影响。

[ 本帖最后由 superacid 于 2009-7-10 11:04 编辑 ]

Osullivan

原帖由 superacid 于 2009-7-10 09:53 发表
可惜答案是错的...

额~~~~~
貌似没有问题吧，那我再考虑考虑~~~~~
不会是还要考虑我里面有重复情况，亦即是n*n棋盘旋转90度后里和原来里面有相同的？~~

[ 本帖最后由 Osullivan 于 2009-7-10 10:07 编辑 ]

superacid

可惜答案是错的...

Osullivan

昨天晚上考虑了下，发现第二题结果为 4！*3^(n-2).下面给出证明：



首先我们看下3*3情况：用ABCD表示4种不同颜色，X表示颜色可以由其它部分推出且颜色确定唯一。
最左上角2*2部分染色有4！种情况，思考方向转系到右下角的2*2棋盘部分，此部分首先考虑最下角位置的染色情况，我们会发现只有3种颜色可供选择，如表中红色部分的BCA表示，此时，每种情况下的2.*2部分另外两格染色就确定唯一了，如图中蓝色字母标识。此部分2.*2染色一旦确定，我们向横纵方向延伸，会发现其它的未完成部分都染色确定唯一，我就不一一标识，用X标识。



再看看4*4的棋盘，思考方法还是右下角2.*2棋盘部分，此时，最右下角位置同样有BCD三种选择，如表中红色字母标识，此三种情况也分别对应三种唯一染色方案。


由此，3*3即为2*2棋盘基础上乘以3，4*4棋盘即3*3基础上乘3，。。。
对于n*n棋盘，可以同样的方法在n-1阶棋盘基础上从最右下方2*2位置考虑起，也同样是在其基础上扩大三倍。

综上：证毕。

[ 本帖最后由 Osullivan 于 2009-7-10 10:05 编辑 ]

superacid

首先要才对答案才行。