关灯游戏中的代数学

1、第73卷第n期数学的实践与认识olv.73 oN.n2007年6月MATHEMATICSIN PRACTICEAND THEORYJune，2007尹，、研究、.“ “ “ “ 沙“关灯”游戏中的代数学周 昊(浙江树人大学基础部，杭州 310015)摘要: 研究的是来自互联网上的一个有趣的数学游戏，运用数学建模的方法给出了其基于有限域上的线性方程组的数学模型，对n=5的情形给出了所有解.并进一步，运用代数学的“分类”方法给出了游戏的四个等价类的直观描述，使游戏者不用解方程组就能立即判断出该“残局t，烤够变为哪个类型.关键词: 线性方程组;有限域;陪集1 引言“关灯”是近年来流行于Interne

2、t上的一个非常有趣的游戏.定义如下，给定一个5x5方格的棋盘，如图1.1所示，每个方格有白色和黑色两种状态，当用鼠标点击其中任何一个方格时，则使这个方格自身及与之相邻的上，下，左，右四个方格都改变状态，即原来是白色的则变为黑色(“关灯”之名由此而来)，原来是黑色的则变为白色.对于处于棋盘边缘的61个方格，如图1.2所示，它们的这四个邻居可能不全存在，那么我们只考虑那些存在的方格.一.一凡丹一.一一图 1.1图1.2 点击左图中黑色方格对于以上定义的游戏规则，试求解以下两个问题:(a)假定棋盘的初始状态为所有方格全部为白色 问游戏者如何点击鼠标将棋盘全部变为黑色，且点击鼠标的次数尽可能少.(b)

3、假定棋盘的初始状态为一个残局:部分方格为白色，部分方格为黑色(如图1.1)，假如你继续点击下去，你能否有一个方法判断，能否使该残局最终变为全白或全黑.2 建模我们将此游戏转化成一个二元域上的线性方程组的解的存在性问题，并通过求解这个线性方程组来得知我们最少需要多少次的鼠标点击将棋盘全部变为黑色.我们的方法适用收稿日期:2003一09一06甚金项目:浙江树人大学校立项二级课题(ZOO6A21003)11期周 昊:“关灯”游戏中的代数学133于一般的nXn个方格的棋盘.为此下面讨论nXn个方格的棋盘.用 0代表白色，1代表黑色.并将所有方格按从左到右，从上到下依次编号为1，2，矛，当n=5时，如图

4、2，1所示.定义状态空间5为棋盘上所有可能的状态组成的集合，且pl23456789l0ll l2 l3 l4 l5l6 l7 l8 l9 205= (e，eZ，enZ)e、=0，1，1=1，2，nZ.显然全白状态为:。二0，0，0任5，全黑状态为:1=1，1，1任5.定义5上的变换t为21 22 23 24 25图 2.1t，5= (el，eZ，eo2)5=(hl，hZ，h，2)， 5，5任5.其中h=亡，或者1一己、，特别的，定义零变换为恒等变换0:0(e，eZ，enZ)= (el，eZ，eo2).设V是5上所有变换所组成的集合.对任意的f，9任V，定义V中元素的加法运算为变换合成运算，即(

5、f+9)(5)=fO9(5)=f(9(5)， V任5.容易验证该运算满足下述性质:1)( f+9=9十f，Vf，geV;(交换律)(2) (f+9)+t=f+(9+t)，Vf，9，t任V; (结合律)3)( 对 Vf任V，f+f=a性质(3)告诉我们，任何一种变换连续或间断地重复 2次或偶数次，此操作的作用将抵消，为了使点击次数尽可能少，这种重复操作应取消.因此任何一种点击方式最多进行一次，也即任何一种变换最多做一次.为此考虑二元数域FZ=0，1.不同于我们常见的实数域R和有理数域Q，F:只含有。和1两个元素，但类似于R和Q，我们同样可以在F:上进行加减乘除四则运算，其运算法则如下所示.奈目.

6、件书011薰010无意义无意义图2.Z F:上的加法表，减法表，乘法表和除法表那么，我们可以定义二元域F:到V上的数乘运算如下:1f=f， 0f=0，Vf任V.容易验证:定理2.I V是FZ上的线性空间.用9，i=1(，2，矛)表示鼠标点击第1个方格时所产生的变换，那么为了将棋盘由全白变成全黑，一次成功的游戏策略对应于一个矛维列向量x=(x1，xZ，x。2尸，其中每个分量x、二0，1(“1”表示点击相应的第“1”个方格，而“0”表示不点击)使得134数 学 的 实 践 与 认 识37卷(x;91)十 (x:92)+ (x，9，)(5。)=5，用向量记号，也记为(9，92，9。，)x)(5。)=

7、51.(2.1)关键是求出x=(x，xZ，x，2)T.为此定义变换关任v(i=1，2，n)为关(el，eZ，e，e，2)=(el，e:，1一e，e，2).由定义可知，关只会改变第1个方格的状态，而不会影响到其它的方格.并且我们容易验证定理2.Z V是F:上维数为矿的线性空间，五卜二1，2，zn是线性空间V的一组基.因为关是V的一组基，所以9可以唯一的表示成9、=关+关一。+关:+十关一1+关+1，其中，对任意的整数k，若k在1，nZ，令人=0，我们把上式写成矩阵的形式，即为(91，92，乱2)二 (fl，几，几2)A，。2、。2， (2.2) 其中A产x。2用分块矩阵可表示为阴EO0，尸1l

8、0n厂1n.1.1|月|阮.1l.|.e.|0十，0elCn子了Ew，e|e.|盯e上.甘s.e|esew|essEe|A:其中Hse.|ee.e|-日-s一e-e.e|s.eels苦|enen阳EHEsn|s一elUee.sewse比es.eewOEHeC1s0 0lsJeLU1人U胜J并且H为nXn矩阵，E为nxn单位矩阵，0为nXn零矩阵.例如当n=5时，几1 000门l|l以00l.l上上|llH冈土J1l土几0lA-.|ls1l冈011e1l|ll团0 0 11l1将(2.2)代人(2.1)，可得阴EOO0几000圣.1.|O.冈100匡HE0.|，EHE0.E阳0 1 0-日.-月

9、厂一一翻旧O.|E月Ell刃比001山OOE H.000因(人，几，几2)AoZx，。Zx)(5。)=51.(2.3)另一方面 ，若取变换9=人 +几 +fnZ=(fl，一，f2)(1，)T1.(.)24显然9(5。)=:，即9是将全白的棋盘变为全黑的那个变换，虽然游戏规则规定我们只能使用9，1=1，2，nZ，但结合(2.3)和(2.4)可知，nZ维列向量x=(x，xZ，x。，)T应为A，x。“x=b(2.5)在域F:上的解，其中b=(1，1，1.)T因此我们有:定理2.3 可将nXn个方格的棋盘由全白状态(5。)变为全黑状态(:1)当且仅当线性方程组(2.)5在域F:上有解.3 求解这样我们

10、就将问题a)(转化成了线性方程组(2.)5的求解问题.稍稍有点不同的是这个线性方程组是定义在二元域FZ上，不是我们所熟知的定义在实数域R上的线性方程组.所幸的是F，上的线性方程组的解的存在性理论以及求解方法完全和R上的线性方程组一样，11期周 昊:“关灯”游戏中的代数学135甚至求解过程更简单，因为FZ远比R简单.将b=(1，1，1)T分块为(厂，厂，尸)T，其中每个1为n维列向量.为求解此线性方程组，现在对(A护、，产，)b进行初等行变换如下阴EoHZ+E HO.HE户口EHE日000oEE向0 H3HZ+E00olHElHEoleE卜eH101000E000比令尸。=E，尸:二H，由以上可

11、知今H“+E，尸3=IPZ十尸，=H，由此可得到一形式递推公式为尸，=H尸*一1十尸卜2， 2镇k镇n.(3.1)并且风一习尸，1成k(，.(3.2)Rank(A。，义。，)=n(n一 1)+Rank(P。)(3.3)这样我们就将求解矛X矛的线性方程组的问题化为求解n个nXn的线性方程组的问题，而这大大的降低了计算复杂性，特别的对于较大的n的情形.下面仅给出n“5时的解，对于n的其它情形可同样求解，当然更好的办法是依据3(.)1和3(.2)，利用MATLAB或Mathematics等数学软件求解，有兴趣的读者可以一试.n=5时，原方程组化为以下等价形式阵s队冈ooo门月el|HEo匡s1|旧e

12、一l伙EHE-|不妨记为A52x52x二b，其中尸:=HS+H 二四比|0EH|洋尸|0o口比E区、JseJ区们自-l110!e一匡e1厂seses1 1 01阳区ws0elw阮一eI101川-(H亏+ H“十 H +E)1 1，而 X，二.(1毛 1成 5).护sM-e一|!J0.0，.!.11人刊s1!阵1|0，叼0!眯土1以JIJ我们首先来考虑方程组尸5X5=(1，0，0，0，1)T，它是否有解呢?答案是肯定的，因为我们马上就可以找到它的解为XS=(.刃:，工2，x23，x:，x25)T=(1+x25，1+xZ，x24+x25，xZ，xZ。)T.这说明原方程组A产、。Zx=b的解是存在的

13、，所以我们一定可以通过有限次的鼠标点击将全136数 学 的 实 践 与 认 识37卷白的棋盘变为全黑.但究竟最少需要几次点击才能达到目的呢?为了回答这个问题，我们必须求出原方程组的所有解.解方程组瓦2x52x=石是容易的，首先我们马上可以求出方程组的一个特解为王=(0，1，1，0，1，0，1，1，1，0，0，0，1，1，1，1，1，0，1，1，1，1，0，0，0)T.并且，我们容易得到齐次方程组A52x52x=0的两个线性无关解(基础解系)为夕1= (1，0，1，0，1，1，0，1，0，1，0，0，0，0，0，1，0，1，0，1，1，0，1，0，1)T少:牛 (0，1，1，1，0，1，0，1，

14、0，1，1，1，0，1，1，1，0，1，0，1，0，1，1，1，0)T，那么原方程组A52、。x=bz的解共有4个，即为牙= (0，1，1，0，1，0，1，1，1，0，0，0，1，1，1，1，1，0，1，1，1，1，0，0，0)T，牙+夕，=(1，1，0，0，0，1，1，0，1，1，0，0，1，1，1，0，1，1，1，0，0，1，1，0，1)T王+夕:=(0，0，0，1，1，1，1，0，1，1，1，1，1，0，0，0，1，1，1，0，1，0，1，1，0)T，王+夕1+夕:=(1，0，1，1，0，0，1，1，1，0，1，1，1，0，0，1，1，0，1，1，0，0，0，1，1)T.这四个解都只需要

15、15(解中“1”的个数)步就能将全白的棋盘变为全黑，其实，我们仔细观察就会发觉这四个解关于棋盘成“中心旋转对称”，即只要将解灭所涉及到的方格(用“X”作标记)绕棋盘的中心依次旋转0“9就得到了其它的三个解，如下图所示.X又只又义XX又X又义义又丫义又又又又丫又火又又X又X又又XX 汉XX又火又XXXK又K火月又又 丫XXX沐又又又义又又X又沐图3.1 王图3.2 王+yl图33 王+脚图3.4 王十y工十为而且这四个解是从起点(全白棋盘)通向终点(全黑棋盘)的四条“终南捷径”.前面已指出如果考虑任何一条从起点到终点的“可行路径”，它由有限次的鼠标点击组成，则每个方格上的偶数次的点击(弯路)叠加

16、起来将会相互抵消，最后一定可以得到这四个解之一，这说明任何一条可行路径都是由某条“捷径”加上一些“弯路”组成，而这些“弯路”就是施加在每个方格上的总共偶数次的鼠标点击，这好比在森林中迷路的人，总是不自觉的在原地打圈，而每打一个圈，我们就要付出两次鼠标点击的代价，所以为了走出这片“森林”，我们一共要花费走完这条“捷径”所需要的点击次数(15次)再加上kZ 次.由此，我们得到以下结论定理3，1 当n=5时，为了将全白的棋盘变为全黑，任何一次成功的游戏均需要点击鼠标5+Zk1次，k为任意非负整数.特别的，我们最少只需要点击鼠标51次即可达到目的.4分类下面，我们来求解问题(b).同理，为简单起见，我

17、们首先只考虑5X5的棋盘，现任给棋11期周 昊:“关灯”游戏中的代数学137盘的两种状态，如下所示，我们是否可以通过有限次的点击将左图变为右图?图 4.1当然，为了回答这个问题，我们仍然可以将它转化为一个线性方程组的求解问题，但每次都要求解一个线性方程组是一件很烦琐的事情，所以我们试图采用其它的办法.我们已经知道0 0 00 0 0初等行变换由(3.3)可得，Rank(AS“xs，)=5X4+Rank(ps)=23，由于AS“、5，是对称矩阵，所以易知(93，94，承5)是线性无关的，设W 是由(91，92，95、5)张成的线性子空间，显然im(W)=d23，且W=L(93，9，gsxs).进

18、一步观察，可知(几，几。，93，9;，gsxs)也是线性无关的，所以(九、，几5，93，9;，95、5)也是V的一组基.考虑V的商空间v=V/W，我们知道V也是线性空间，且V由四个陪集组成，Vl=0W，V:=几4W，V3=几5W 和V;=(九4+几5)W.我们下面将要用到陪集的一些基本性质如下:()V一、。1叼.3.4，V，且V护j，V泛nV，一，这给出了集合V的一个分划(4)(2)Va，b任V，(aW)+(bW)=(a+b)W.(4.2)(3)Vt任V，t任V骨tW 二V，(1簇1蕊 4)(4.3)(4)Vtl，t:任V，t，t:eV，拱(t。一t，)任W(4.4)定义从V到棋盘的状态空间5

19、的映射T为T:ff(5。)，其中5。“(0，0，0).(4.5)显然这是个1一映射，设TV，)一凡，簇镇4由(4)，那么“一，。、1叼、3，;5，泣n“，一0，这也给出了5的一个分划.下面我们来证明以下结论定理4.1 对任意的15，尹任5，且T一(s)=t一1，T一，(5勺=tZ，则下面三条等价(1)tl，t:任 V，. 请参考T.W.Hungerford的“Algebra”第37一40页.138数 学 的 实 践 与 认 识37卷(2)5，sn任 5.(3) 通过有限次鼠标点击可将:变为:.l，证明 由T是1一1映射，故1)(娜(2).若存在9任W，使得9(s)=尹，由4(.)5，那么就有(

20、9+tl)(5。)=t:(5。)，即9=tZ一tl，由(4.4)，tl，t:任V.反之亦然，所以(3)骨(1).定理4.1告诉我们，属子每个特定的5(l簇1簇)4的任意两种状态均可以通过鼠标点击而相互转化，而属于不同的5(1镇1镇)4的两种状态是不能通过鼠标点击而相互转化的.下面我们来给出每个特定的5、l(镇1簇)4中的元素所具有的一般规律.首先我们来考察j(f1(j镇5)2与v，l(镇1成)4的关系，通过计算可得定理4.Z j(1f镇j簇25)与V(1镇1镇4)的关系如下(1)人任Vl，k任UI= 7，9，13，17，19(2)人任V:，k任U:=2，4，11，12，14，15，22，24(

21、3)几V3，kU:= 1，5，20，25(4)人任V4，keU;= 3，6，8，10，16，18，20，23.4由定理2.2，对任意的，任V，一艺习从关，其中“、=。，1.设才在每个u;(1镇k镇4)上孟。lieU壳分量不为。的个数分别为m*(1簇k镇4)，由4(.)2可知4t W =艺(习ufi)w)走=1 1任U乏艺(u0w)+习(u、几4W)+习(:，九5w)UI云UZieUa+习(:“(九4+九5)W)ieU峨=(，n，0+m:几+m3几5+，n4(九4+九5)W.根据4(.3)，由此即可给出每个特定的V(1簇1簇)4中的元素的一般规律为表 1”理2”23”习4V1V21/51/;奇数

22、偶数奇数偶数奇数偶数奇数偶数奇数偶数偶数奇数偶数奇数奇数偶数奇数偶数偶数奇数奇数偶数偶数奇数容易看出ml的值对t的属向无任何影响.根据4(.5)，我们可以给出每个特定的5、1(簇 1簇)4中的元素所具有的一般规律.对照U*(2镇k镇)4 ，如下图所示，记“A”区域中黑色方格的数目为N(A)，“B”区域中黑色方格的数目为N(B)，“C，区域中黑色方格的数目为N(C).由定理4.1，表1及(4.5)，可得到每个特定的5，=1l(，2，3，)4中的元素的一般规律为11期周 昊:“关灯”游戏中的代数学139N(A)N(B)N(C)B A C A BCCCA AA ACCCB A C A B图 4.3表

23、 2SlS2S3S咭奇数偶数奇数偶数奇数偶数奇数偶数奇数偶数偶数奇数偶数奇数奇数偶数奇数偶数偶数奇数奇数偶数偶数奇数由上表可知，一定可以通过鼠标点击，将全白状态:。变为全黑状态:，因为对于:。，N(A)=0，N(丑)=0，N(C)=0.对于:1，N(八)=8，N(B)=4，N(C)=8，即5。，:1任51.但我们无论怎样点击鼠标也不能将图4.1变为图4.2，因为在图4.1中，N(A)=6，N(B)=3，N(C)=7，故图4.1属于52.而在图4.2中，N(A)=4，N(B)=4，N(C)=5，故图4.2属于54.依据表2，我们可以从每个特定的5、i=1(，2，3，)4中挑选一个形式上最简单的状态作为代表，不妨记为第一型，第二型，第三型和第四型，如下所示.图4.4 第一型图4.5 第二型图4.6 第三型图4.7 第四型现在，对5x5棋盘的任意一种状态，根据图4.3和表2，我们可以迅速判断它属于上图中的哪种类型，并可以通过有限次的鼠标点击将它变换到该简