Question

求解一道高中数学竞赛

一种密码锁的密码设置是在正N方形A1A2A3....An的每个顶点处赋值0和1两个数中的一个，同时在每个顶点处涂染红蓝两色之一，使得任意相邻的两个顶点的数字或颜色中至少有一个相同。问:该种密码锁共有多少种不同的密码设置？

Answer 1

这道题目需要分奇偶两种情况，用数学归纳法来做。
答案是：假设该正边形有n个边，当n为偶数时，有12*7^[(n-2)/2]种;当n为奇数时，有4*7^[(n-1)/2]种。
对偶数情况的证明：当n＝2时，第1个顶点有2*2＝4种情况，不论何种情况下，第2个顶点都有3种可能，因此共有4*3＝12种情况。
详细分析如下：
我们用a代表0和1中的任意1种，而b代表另外1种（你在做的时候可以用“非a”代替，可能会更清楚一些），用x代表红、蓝中的任意1种，而y代表另外一种。如果一个顶点数字是a、颜色是x，我们用ax表示这个点的状态。
第1个顶点有4种情况就不分析了，很容易看出来。假如第1个顶点的状态是ax，则第2个顶点不可以是by，可以是ax、ay、bx中任意一种，也就是说，不管第1个顶点的状态是怎样的，第2个顶点都有3种情况，因此总共有4*3＝12种情况。
而12*7^[(n-2)/2]＝12*7^0＝12，因此n＝2时公式成立。

假设n＝2k（k为自然数）时公式成立，则当n＝2k+2时，我们可以想象一下，任意选取一个符合题目要求的2k边形的两个相邻顶点M和N，与一条新增线段PQ的两端相连，即新增2个顶点和2条边（本来是M、N相邻，新增两个顶点后变成MP相邻、PQ相邻、QN相邻）。
因为M和N至少有一个状态相同，我们先假定它们有且只有一个状态相同，并假定它们的状态分别是ax和ay，那么P的状态可以是ax、ay、bx中的任意一种，Q必须和P、N（ay）都有相同的状态。
P为ax时，结合N为ay，可以分析出，Q可以是ax、ay两种情况
P为ay时，Q可以是ay、ax、by三种情况；
P为bx时，Q可以是by、ax两种情况。
因此，当M、N有且仅有一个状态相同时，P和Q有7种情况（2+3+2）。

同理可以分析，当M、N的状态完全相同时（可以假定二者都是ax），P、Q也有7种情况。

因此，当n＝2k+2时，共有12*7^[(2k-2)/2] *7＝12*7^[(2k+2-2)/2]，可见当n＝2k+2时公式也成立。
根据数学归纳法，n为任意偶自然数时，公式均成立。
（注：题目中写的是正边形，因此n应该是不小于3的，因此严格来说上述分析是错的，不应该从2开始分析而应该从4开始分析，但是考虑到n＝4时稍微繁琐一些，因此才从n＝2开始分析，只要道理懂了，要从4开始分析也是很容易的。）

对奇数情况的证明：
n＝3时，设三个顶点分别是M、P、Q。假设M的状态是ax（共有2*2＝4种情况），则P的状态可以是ax、ay、bx三种。下面分情况考虑Q的状态（Q必须与M、P各至少有一个状态相同）。
当P为ax时，Q可以是ax、ay、bx三种；
当P为ay时，Q可以是ax、ay两种；
当P为bx时，Q可以是ax、bx两种。
因此，在M状态已知的情况下，P、Q可以有7种情况。
因此，n＝3时共有4*7＝28种情况。公式成立。
下面继续用数学归纳法证明，若n＝2k+1时公式成立，则n＝2k+3时公式也成立，从而证明n为不小于3的奇数时，公式恒成立。具体过程就不写了，和偶数情况完全相同。