资源描述：
《关灯游戏中的代数学》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、关灯游戏中的代数学题目考虑下述定义的关灯游戏.给定一个5×5方格的棋盘，如图1所示，每个方格有白色和黑色两种状态，当用鼠标点击其中任何一个方格时，则使这个方格自身及与之相邻的上，下，左，右四个方格都改变状态，即原来是白色的则变为黑色，原来是黑色的则变为白色.对于处于棋盘边缘的16个方格，如图2所示，它们的这四个邻居可能不全存在，那么我们只考虑那些存在的方格.→图1.关灯游戏中的棋盘图2.点击左图中黑色方格后变为右图.(1)假定棋盘的初始状态为所有方格全部为白色，问游戏者是否可以通过点击鼠标将棋盘的所有方格全部变为黑色（称为一个可行策略）？若可以，如何进行游戏，使点击鼠标的
2、次数尽可能少（称为最优策略）.你的方法能否推广到棋盘有n×n个方格的一般情形.(2)假定棋盘的初始状态为一个残局：部分方格为白色，部分方格为黑色，假如你继续点击下去，你能否有一个简明的方法判断，该残局能否最终使所有方格为黑色，或者变成给定的状态，例如是否可以通过有限次的点击图3变为图4？图3.初始状态图4.终止状态1．数学建模我们将此游戏转化成一个二元域上的线性方程组的解的存在性问题，并通过求解这个线性方程组来得知我们最少需要多少次的鼠标点击将棋盘全部变为黑色.我们的方法适用于一般n×n个方格的棋盘.为此下面讨论n×n个方格的棋盘.用0代表白色，1代表黑色.并将所有方格按
3、从左到右，从上到下依次编号为21,2,",n，当n=5时，如图5所示.12345678910111213141516171819202122232425图5.5×5棋盘上方格的编号定义状态空间S为棋盘上所有可能的状态组成的集合，即2S={(e1,e2,",en2)
4、ei=0,1,i=1,2,",n}..显然全白状态为sS={0,0,",0}∈,全黑状态为s={1,1,",1}∈S.定义S上的一个变01换t为t:s=(e1,e2,",en2)→s'=(h1,h2,",hn2),ss,'∈S.其中h=e或者1−e，特别的，定义零变换为恒等变换O:iiiO(e1,e2,",en
5、2)=(e1,e2,",en2).设V是S上所有变换所组成的集合.对任意的f,g∈V，定义V中元素的加法运算为变换合成运算，记为fDg，即fDg(s)=f(g(s)),∀s∈S.并用∑表示关于加法运算D的连加符号.例如25f1Df2D"Df25=∑fi.i=1容易验证该运算满足下述性质：（1）fDg=gDf，∀f,g∈V；（交换律）（2）(fDg)Dt=fD(gDt)，∀f,g,t∈V；（结合律）（3）对∀f∈V，fDf=O.性质（3）告诉我们，任何一种点击方式（变换）连续或间断地重复2次或偶数次，此操作的作用将抵消，为了使点击次数尽可能少，这种重复操作应避免.因此任何一
6、种点击方式最多进行一次，也即任何一种变换最多做一次.为此考虑二元数域F={0,1}.不同于我们常见的实数域R和有理数域Q,F只含有022和1两个元素，但类似于实数域R和有理数域Q，我们同样可以在F上进行加减乘除四则2运算，其运算法则如下所示.⊕01Θ01⊗01÷010010010000无意义01101101011无意义1图6.F上的四则运算表.2那么，我们可以定义二元域F到V上的数乘运算∗如下：21∗f=f，0∗f=O,∀f∈V.容易验证：定理1.V是F上的线性空间.22用g,i=1,2,",n表示鼠标点击第i个方格时所产生的变换，那么将棋盘由全白变成全i2T黑，一次可行
7、的游戏策略对应于一个n列维向量x=(x1,x2,...,xn2)，其中每个分量x=0,1，使得i2n(∑xi∗gi)(s0)=s1,i=1用向量记号，也记为((g1,g2,...,gn2)x)(s0)=s1.（1）T关键是求出x=(x1,x2,...,xn2).2为此定义变换f∈V,i=1,2,",n为ifi(e1,e2,...,ei,...,en2)=(e1,e2,...,1−ei,...,en2).由定义可知，f只会改变第i个方格的状态，而不会影响到其它的方格.并且我们容易验证i22定理2.V是F上维数为n的线性空间,{f
8、i=1,2,",n}是线性空间V的一组基.2
9、i对于V的基{f}，g可以唯一的表示成iig=fDfDfDfDf,iii−ni+ni−1i+12其中，对任意的整数k,若k∉[1,n],定义f=O.我们把上式写成矩阵的形式，即为k(g1,g2,...,gn2)=(f1,f2,...,fn2)An2×n2，（2）其中A22用分块矩阵可表示为n×n⎡HEΟ"Ο⎤⎢⎥EHE"Ο⎢⎥A=⎢#####⎥，（3）⎢⎥⎢Ο"EHE⎥⎢⎣Ο"ΟEH⎥⎦其中每个小方阵都是n×n的矩阵，E为n×n单位矩阵,Ο为n×n零矩阵，及⎡110"0⎤⎢⎥111"0⎢⎥H=⎢#####⎥.⎢⎥⎢0"111⎥
