魔方吧·中文魔方俱乐部

标题: 棋盘染色计数 [打印本页]

作者: superacid 时间: 2009-7-9 14:49:08 标题: 棋盘染色计数

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

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

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

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

作者: noski 时间: 2009-7-9 16:17:41

占楼 lol
第一题答案应该是 2的（n+1）次方减2 ；

作者: superacid 时间: 2009-7-9 16:27:08

正确！

作者: Cielo 时间: 2009-7-9 16:59:06

一开始联想到那道”每个小正方形内的数之和为偶数“的题。
但还是不会做……

看到2楼的答案才想到方法！

作者: Osullivan 时间: 2009-7-9 19:56:04

占楼思考~~~~~~~~~~~~

作者: lulijie 时间: 2009-7-9 21:47:27

第二题：
n＝2，24种
n＝3，24*3＝72种
n＝4，72*3=216种
.........
观察规律：
好像通项为 24*3^(n-2)种。

作者: Osullivan 时间: 2009-7-9 21:54:55

原帖由 lulijie 于 2009-7-9 21:47 发表
第二题：
n＝2，24种
n＝3，24*3＝72种
n＝4，72*3=216种
.........
观察规律：
好像通项为 24*3^(n-2)种。

我感觉先随便定个顶角2*2 4块颜色，然后向四周扩展，打算用排列组合算，应该可以算出来，等会拿笔算算~~

作者: lulijie 时间: 2009-7-9 22:06:21

我觉得可以用数学归纳法。

作者: superacid 时间: 2009-7-10 09:23:38

首先要才对答案才行。

作者: Osullivan 时间: 2009-7-10 09:30:47

昨天晚上考虑了下，发现第二题结果为 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 编辑 ]

附件: 1.jpg (2009-7-10 09:30:47, 8.89 KB) / 下载次数 38
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTg3MDh8OWQxZWFmOTh8MTczMTM3MTgxM3wwfDA%3D

附件: 2.jpg (2009-7-10 09:30:47, 14.55 KB) / 下载次数 42
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTg3MDl8YWFiZTZjZTZ8MTczMTM3MTgxM3wwfDA%3D

作者: superacid 时间: 2009-7-10 09:53:50

可惜答案是错的...

作者: Osullivan 时间: 2009-7-10 10:03:05

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

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

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

作者: superacid 时间: 2009-7-10 10:33:08

如果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 编辑 ]

作者: noski 时间: 2009-7-10 13:40:36

又算了第二问，答案应该是 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 时间: 2009-7-10 16:24:57

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

作者: Cielo 时间: 2009-7-12 00:12:00

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

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

作者: Osullivan 时间: 2009-7-12 15:02:40

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)