棋盘染色计数

superacid

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

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


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

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

noski

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

superacid

正确！

Cielo

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

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

Osullivan

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

lulijie

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

Osullivan

原帖由 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

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

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