关灯游戏中的代数学.pdf

关关 灯灯 游游 戏戏 中中 的的 代代 数数 学学 题目题目 考虑下述定义的关灯游戏.给定一个5 5方格的棋盘，如图 1 所示，每个方格有白色和 黑色两种状态， 当用鼠标点击其中任何一个方格时， 则使这个方格自身及与之相邻的上， 下， 左，右四个方格都改变状态，即原来是白色的则变为黑色，原来是黑色的则变为白色. 对于 处于棋盘边缘的 16 个方格，如图 2 所示，它们的这四个邻居可能不全存在，那么我们只考 虑那些存在的方格. 图 1. 关灯游戏中的棋盘 图 2 . 点击左图中黑色方格后变为右图. (1) 假定棋盘的初始状态为所有方格全部为白色，问游戏者是否可以通过点击鼠标将棋 盘的所有方格全部变为黑色（称为一个可行策略）？若可以，如何进行游戏，使点 击鼠标的次数尽可能少（称为最优策略）. 你的方法能否推广到棋盘有个方格 的一般情形. n n (2) 假定棋盘的初始状态为一个残局：部分方格为白色，部分方格为黑色，假如你继续 点击下去，你能否有一个简明的方法判断，该残局能否最终使所有方格为黑色， 或 者变成给定的状态，例如是否可以通过有限次的点击图 3 变为图 4？ 图 3. 初始状态 图 4. 终止状态 1数学建模数学建模 我们将此游戏转化成一个二元域上的线性方程组的解的存在性问题， 并通过求解这个线 性方程组来得知我们最少需要多少次的鼠标点击将棋盘全部变为黑色. 我们的方法适用于 一般n个方格的棋盘.为此下面讨论nn n个方格的棋盘. 用 0 代表白色，1 代表黑色. 并将所有方格按从左到右，从上到下依次编号为 ，当时，如图 5 所示. 2 , 2 , 1n?5n= 1 2 3 4 5 6 7 8 9 10 1112131415 1617181920 2122232425 图 5. 5 5棋盘上方格的编号 定义状态空间为棋盘上所有可能的状态组成的集合，即 S ., 2 , 1, 1 , 0| ),( 2 21 2 nieeeeS i n ?=. 显然全白状态为 0 0,0,0sS=?, 全黑状态为 1 1,1,1sS=?S. 定义上的一个变 换 t 为 ),(),(: 22 2121 nn hhhseeest?= , .s sS 其中，特别的，定义零变换为恒等变换 O: iii eeh=1或者 ),(),( 22 2121 nn eeeeeeO?=. 设V是S上所有变换所组成的集合. 对任意的Vgf,，定义 V 中元素的加法运算为变换 合成运算，记为，即 gf ? ),()(sgfsgf=? Ss. 并用表示关于加法运算 的连加符号. 例如 ? . = = 25 1 2521 i i ffff? 容易验证该运算满足下述性质： （1）fggf?=，Vgf,； （交换律） （2），)()(tgftgf?=Vtgf,； （结合律） （3） 对Vf ，. Off=? 性质（3）告诉我们，任何一种点击方式（变换）连续或间断地重复 2 次或偶数次，此操作 的作用将抵消，为了使点击次数尽可能少，这种重复操作应避免.因此任何一种点击方式最 多进行一次，也即任何一种变换最多做一次. 为此考虑二元数域. 不同于我们常见的实数域 R 和有理数域 Q, 只含有 01 , 0 2 =F 2 F 和 1 两个元素，但类似于实数域 R 和有理数域 Q，我们同样可以在上进行加减乘除四则 运算，其运算法则如下所示. 2 F 0 1 0 无意义 0 1 无意义无意义 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 图 6. 上的四则运算表. 2 F 那么，我们可以定义二元域上的数乘运算 2 FV到如下： ff=1， VfOf=,0. 容易验证： 定理定理 1. V 是上的线性空间. 2 F 用表示鼠标点击第i个方格时所产生的变换， 那么将棋盘由全白变成全 黑，一次可行的游戏策略对应于一个列维向量，其中每个分量 ，使得 2 , 2 , 1,nigi?= 2 n T n xxxx),.,( 2 21 = 1 , 0= i x , 10 1 )( )( 2 ssgx n i ii = = 用向量记号，也记为 1021 )(),.,( 2 ssxggg n =. （1） 关键是求出. T n xxxx),.,( 2 21 = 为此定义变换为 2 , 2 , 1,niVfi?= ),.,1,.,(),.,.,( 22 2121 n i n ii eeeeeeeef=. 由定义可知，只会改变第 i 个方格的状态，而不会影响到其它的方格.并且我们容易验证 i f 定理定理 2. V 是上维数为的线性空间, 是线性空间 V 的一组基. 2 F 2 n, 2 , 1| 2 nifi?= 对于 V 的基 i f，可以唯一的表示成 i g , 11+ = iininiii fffffg? 其中，对任意的整数, 定义, 1 , 2 nkk若Ofk=. 我们把上式写成矩阵的形式，即为 2222 ),.,(),.,( 2121 nnnn Afffggg =， （2） 其中用分块矩阵可表示为 22 nn A = HE EHE EHE EH A ? ? ? ? ? ， （3） 其中每个小方阵都是的矩阵，E 为nnnn单位矩阵, 为nn零矩阵，及 . 1100 1110 0111 0011 = ? ? ? ? ? H 例如当时， 5n = = = HE EHE EHE EHE EH AH, 11000 11100 01110 00111 00011 . 将（2）代入(1)得 1021 )(),.,( 222 ssxAfff nnn = . （4） 另一方面，若取变换 2 21 n fffg?=, （5） ) 1 , 1)(,( 2 1 ? n ff 显然, 即 g 是将全白的棋盘变为全黑的那个变换， 虽然游戏规则规定我们只能使 用，但结合（4） 、 （5）知列维向量应为 0 ()g ss= 1 b , 2 , 1| 2 nigi?= 2 n T n xxxx),.,( 2 21 = 22 nn Ax = （6） 在域上的解，其中. 因此我们有： 2 F( =1 , 1 , 1?b) 定理定理 3 可将个方格的棋盘由全白状态（）变为全黑状态可将个方格的棋盘由全白状态（）变为全黑状态() 当且仅当线性方程 组（ 当且仅当线性方程 组（6）在域上有解）在域上有解, 该方程组的每个解对应一个可行的游戏策略该方程组的每个解对应一个可行的游戏策略. n n 0 s 1 s 2 F 定理 3 对题目中任务（1）的可行游戏策略的存在性做出了回答. 下面讨论题目中任务 （2）的可行游戏策略的存在性. 实际上，上面的方法完全适用. 假设n个方格的棋盘初始状态为， 希望通过点击变为终止状态. 为此与前面稍 微不同的是，将状态中每个格子的颜色全部用 0 表示，状态中每个格子的颜色按如下 方式表示： n 0 s 1 s 0 s 1 s 若中第 i 个格子的颜色与状态中该格子的颜色相同， 则用 0 表示； 否则用 1 表示. 记得到的表示中所有格子的颜色的维列向量为. （7） 1 s 0 s 1 s 2 nb 一次可行的游戏策略对应于一个维列向量， 其中每个分量 ， 使得 2 n T n xxxx),.,( 2 21 = 1 , 0= i x 10 1 )( )( 2 ssgx n i ii = = ， 即 1021 )(),.,( 2 ssxggg n =. 同上推理， 可得 定理定理 4 可将个方格的棋盘由初始状态为，变为终止状态当且仅当线性方程组可将个方格的棋盘由初始状态为，变为终止状态当且仅当线性方程组 在域上有解在域上有解, 该方程组的每个解对应一个可行的游戏策略，该方程组的每个解对应一个可行的游戏策略， 其中其中 A 由（由（3） 式给出，由（ ） 式给出，由（7）给出）给出. n n 0 s 1 s 22 bxA nn = 2 F b 2求解求解 我们就将任务（1）化成了线性方程组（5）的求解问题. 稍稍有点不同的是这个线性 方程组是定义在二元域上，不是我们所熟知的定义在实数域 R 上的线性方程组. 所幸的 是, 上的线性方程组解的存在性理论以及求解方法完全和 R 上的线性方程组一样，甚至 求解过程还要简单，因为远比 R 简单. 2 F 2 F 2 F 将分块为(, 其中每个 I 为列维向量. 为求解线性方程组 （6） ，先给出域上的矩阵运算的定义以及一些概念和性质，他们和实数域上 R 的完全类 似， 只不过数的加法和乘法不同而已. 例如， 设有域两个 ( =1 , 1 , 1?b) III,?n 2 F 2 Fml矩阵 A=, B=, 则)( ij a)( ij b A 与 B 的和仍为一个)( ij cBA=ml矩阵，其中 ijijij bac=. 设有域两个矩阵 A=, B=, 则 A 与 B 的乘积 2 F mlij a )( kmij b )()( ij cBA=仍为一个kl矩阵，其中 mjimjijiij bababac=? 2211 . 同样，可定义矩阵的行列式、秩、可逆矩阵等概念， 具体可参看有关抽象代数的书籍1-3. 现在对()bA nn , 22 进行初等行变换如下 I I I IIH HE EHE EHE EHE HEH I I I I HE EHE EHE EH ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2 () I I IM HE EH EHE P I I I IHH HE EH EHE EHH nn ? ? ? ? ? ? ? ? ? ? ? ? ? 223 令，由以上可知， HPEP= 10 , EHPHPP= 2 012 ， 3 123 HPHPP= 由此可得到一递推公式为 nkPHPP kkk = 2 , 21 ， （8） 并且 nkPPPPM kk =1 , 210 ?. 我们还可以看出 22 nn A 的可逆性完全由的可逆性所决定，而且 n P )() 1()( 22 n nn PRanknnARank+= ， （9） 并且原方程组的解是否存在和唯一等价于n阶线性方程组的解是 否存在和唯一. 22 nn Ax = bIMyP nn = 下面我们着重考虑的情形，此时原方程组化为以下等价形式 5n = = I I I I IM X X X X X HE EHE EHE EHE P 5 5 4 3 2 15 ， (10) 不妨记为bxA =，其中 =HHP 5 5 01101 11100 11011 00111 10110 , ， = 1 0 0 0 1 )( 345 5 IHHHEIM ()51, 5 15 25 35 45 = i x x x x x X i i i i i i . 我们首先来考虑方程组,它是否有解呢？答案是肯定的，因为我们马上就 可以找到它的解. 首先齐次方程 ( =1 , 0 , 0 , 0 , 1 55X P) () 55 0,0,0,0,0P X =的通解 ()() = 25242524242525242322215 ,xxxxxxxxxxxX. ( =1 , 0 , 0 , 0 , 1 55X P)的特解为. 从而( 0 , 0 , 0 , 1 , 1()=1 , 0 , 0 , 0 , 1 55X P得通解为 ()() = 25242524242525242322215 ,1 ,1,xxxxxxxxxxxX， （11） 其中为自由变量， 即 2524,x x10, 10 2524 或或=xx. 这说明原方程组的解是存在的，所以我们一定可以通过有限次的鼠标点击 将全白的棋盘变为全黑. 但究竟最少需要几次点击才能达到目的呢？为了回答这个问题， 我 们必须求出原方程组的所有解. 解方程组 22 nn Ax = b bxA=是容易的, 例如，在（11）中令 0, 0 2524 =xx，得到的解代入（10） ，我们可以求出方程组bxA=的一个特解x为 () =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 x. 并且，我们容易得到齐次方程组0=xA的两个线性无关解(基础解系)为 ()=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 1 y, ()=0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 2 y. 那么原方程组的解共有 4 个，即为 bxA= 2525 ()=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 x， ()=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 1 yx ()=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 2 yx， ()=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 21 yyx. 凑巧的是这四个解都只需要 15(解中 1 的个数)次点击就能将全白的棋盘变为全黑，其实，我 们仔细观察就会发觉这四个解关于棋盘成“中心旋转对称” ，即只要将解x所涉及到的方格 (用“”作标记)绕棋盘的中心依次旋转就得到了其它的三个解，如下图所示 ? 90 图7. x 图8. 1 yx 图9. 2 yx 图10. 21 yyx 而且这四个解是从起点(全白棋盘)通向终点(全黑棋盘)的四条“终南捷径”. 前面已指 出如果考虑任何一条从起点到终点的“可行路径” ，它由有限次的鼠标点击组成，则每个方 格上的偶数次的点击(弯路)叠加起来将会相互抵消，最后一定可以得到这四个解之一，这说 明任何一条可行路径都是由某条“捷径”加上一些“弯路”组成，而这些“弯路”就是施加 在每个方格上的总共偶数次的鼠标点击， 这好比在森林中迷路的人， 总是不自觉的在原地打 圈，而每打一个圈，我们就要付出两次鼠标点击的代价，所以为了走出这片“森林” ，我们 一共要花费走完这条“捷径”所需要的点击次数(15 次)再加上 2k 次.由此，我们得到以下结 论. 定理定理 5. 当当时，为了将全白的棋盘变为全黑，任何一次成功的游戏均需要点击鼠标为了将全白的棋盘变为全黑，任何一次成功的游戏均需要点击鼠标 15+2k 次，次，k 为任意非负整数为任意非负整数.特别的，我们最少只需要点击鼠标特别的，我们最少只需要点击鼠标 15 次即可达到目的次即可达到目的. 5n = 至此，对于的棋盘，我们已经证明了可以通过有限次的鼠标点击将全白的棋盘变 为全黑，并且使用图 7, 8, 9,和 10 所示的方法(点击用“ 55 ”做了标记的方格)，我们最快可以 用 15 次点击达到目的. 下面讨论对于n n的棋盘，在有解的情况下，如何找到用最少鼠标点击次数的游戏策 略.实际上的每个解为一对应IMyP nn =bxA=，也即 22 nn Ax b=的一个解，由于 自由变量的个数为IMyP nn =rPRankn n )(，也就是说方程组最多有个不同的 解，每个解对应一个游戏策略，再从所有不同策略中找出鼠标点击次数最少的.由于 r 可能 为 n，因此可能会出现从个可行游戏策略中找出最优策略的情形，从而算法是指数时间 的. 或许这就是游戏的魅力所在 ：找到可行策略相对容易，而最优策略需要几分智力和几 分运气. r 2 n 2 3解法的改进：任务（解法的改进：任务（2）的求解）的求解 人们在游戏开始前往往关心， 是否存在一个可行游戏策略， 保证能从任给的初始状态变 到所要求的终止状态.本节给出一个简单的判断方法.我们对任务（2）的一般情形进行讨论， 为简单起见，我们首先考虑的棋盘，现任给棋盘的两种状态，如下所示，我们是否可 以通过有限次的点击将图 11 变为图 12？ 55 图 11. 起始状态 图 12. 终止状态 当然，为了回答这个问题，我们仍然可以将它转化为一个线性方程组的求解问题，但每 次都要求解一个线性方程组是一件很烦琐的事情，所以我们试图采用其它的办法. 考察前面将矩阵经过初等行变换后所得到的矩阵 2525 A2525A，由于 = 01101 11100 10110 00000 00000 01101 11100 11011 00111 10110 5 初等行变换 P 于是()()()2345 5 2525 2525 =+= PRankARankARank. 且的第 3 至 25 行组成的 行向量组是线性无关的，由于是对称矩阵，第 3 至 25 列组成的列向量组也是线性无 关的，所以 V 中的向量是线性无关的. 2525 A 2525 A 2543 ,ggg? 设W是 由张 成 的 线 性 子 空 间 ， 显 然， 且 . 25321 ,gggg?dim()23W = ),( 2543 gggLW?= 进一步观察，可知向量也是线性无关的，所以它们也是 V 的一组基. 25242543 ,ffggg? 考虑商空间 V/W， 它也是一个线性空间, 因为是V的一组基， 所 以对任意 使得 25242543 ,ffggg? , 25242543 vvuuuVt?存在唯一 )()()()()( 2525242425254433 fvfvgugugut=?， WfvfvWt?)()( 25252424 = . 所以，商空间由四个陪集组成： WffVWfVWfVWOV?)(, 252442532421 =和. 我们下面将要用到陪集的一些基本性质如下2，37-40： 引理引理 6 (1) ，且 1,2,3,4 i i VV = ji ，= ji VV，这给出了集合 V 的一个分划. (2)WbaWbWaVba?)()()( ,=. (3)41 (,=iVWtVtVt ii ?. (4)WttVttVtt i )(, 122121 ?. 定义从 V 到棋盘的状态空间 S 的映射 T 为 0 :(Tff s)，其中()0 , 0 , 0 0 ?=s. 显然这是个 1-1 映射，设( )41 ,=iSVT ii ，由引理 6（1）可知，那么，且 两两不交，这也给出了的一个分划. 1,2,3,4 i i SS = 4321 ,SSSS和S 定理定理 7. 对任意的，且对任意的，且, s sS 11 1 ( ),( )Tst Tst 2 =，则下面三条等价：，则下面三条等价： ( )1 ； i Vtt 21, ( )2 ； i Sss , ( )3 通过有限次鼠标点击可将通过有限次鼠标点击可将变为变为. ss 证明：由于 T 是 1-1 映射，故显然( )( )12. 下证( )( )3 1. 由 11 12 ( ),( )Tst Tst =知. )(, )( 0201 sstsst=通过有限次 鼠标点击可将变为等价于：存在 ssgW,使得( )g ss=，那么就有 )()()( 020101 ststgstg=?， 由引理 6（4）知.反之如果 )4 , 3 , 2 , 1(, 21 =iVtt ii Vtt 21, ,由引理 6（4）知存在使 得， 从而. 所以 Wg 21 ttg=? 0201 )()()(sststgsg=?( )( )31. 定理 7 告诉我们，属于每个特定的()41 iSi的任意两种状态均可以通过适当的鼠标 点击而相互转化， 而属于不同的()41iSi的两种状态是不能通过鼠标点击而相互转化的. 下面我们来给出每个特定的(41)iSi中的元素所具有的一般规律. 首先我们来考察 与的关系，通过计算可得 ()251 jf j (41iVi) )定理定理 8. 与的关系如下：与的关系如下： ()251 jf j (41iVi .23,20,18,16,10, 8 , 6 , 3,)4( ;25,20, 5 , 1,) 3( ;24,22,15,14,12,11, 4 , 2,)2( ;19,17,13, 9 , 7,) 1 ( 44 33 22 11 = = = = UkVf UkVf UkVf UkVf k k k k 则若 则若 则若 则若 证明：证明：仅以f2 2 V 为例说明如何得到该定理， 其他证明完全类似。由于所以 只需证明存在使得 , 242 WfV?= T uuux),( 2521 ?= ),()()()( 25212425252211242 xgggfguguguff?=。 （12） 由于， 所以由（12）式得 Off= 2424 ? xgggff),( 2521242 ?=. （13） 由（2）式，及， （13）式等价于 T fffff)0 , 1 , 0 , 0 , 1 , 0)(,( 2521242 ?= ， T xA)0 , 1 , 0 , 0 , 1 , 0( 2525 = 也即只需证明（13）式有解. 这可以通过计算直接验证。证毕。 由于对任意的使得 , 2521 uuuVt?存在唯一 = = 4 1 25252211 )()()( kUi ii k fufufufut?. 设 t 在每个上系数不为 0 的下标个数分别为)41 ( kUk i u)41 ( kmk，由定理 8 可知. .)()2(mod()2(mod()2(mod()2(mod( )()()*()*( )*( 252442532421 25242524 4 1 1234 WffmfmfmOm WffuWfuWfuWOu WfuWt UiUiUiUi iiii kUi ii k ? ? ? = = = = 由上式，结合引理 6（3） ，可给出每个特定的()41iVi中的元素的一般规律， 它由 的奇偶性决定，如表 1 所示（容易看出的值对 t 的分类无任何影响）. )41 ( kmk 1 m 1 V 2 V 3 V 4 V 2 m 奇数 偶数 奇数 偶数 奇数 偶数 奇数 偶数 3 m 奇数 偶数 偶数 奇数 偶数 奇数 奇数 偶数 4 m 奇数 偶数 偶数 奇数 奇数 偶数 偶数 奇数 表表 1. 下面我 们 可 以 给 出 每 个 特 定 的()41iSi中 的 元 素 所 具 有 的 一 般 规 律 . 对 照 ，如图 13 所示，在棋盘中用 A, B, C 分别表示格子属于，记标记为 A 的黑色方格的数目为，标记为 B 的黑色方格的数目为，标记为 C 的黑色方格的数 目为. )42( kUk 432 ,VVV )(AN)(BN )(CN BACAB C C C A A AA C C C BACAB 图 13 格子的分类 可得到每个特定的中的元素的一般规律如表 2 所示. (1,2,3,4 i S i =) 1 S 2 S 3 S 4 S )(AN 奇数 偶数 奇数 偶数 奇数 偶数 奇数 偶数 )(BN 奇数 偶数 偶数 奇数 偶数 奇数 奇数 偶数 )(CN 奇数 偶数 偶数 奇数 奇数 偶数 偶数 奇数 表表 2. 由上表可知， 一定可以通过鼠标点击， 将全白状态变为全黑状态， 因为对于,=0, =0， =0. 对于， =8， =4， =8，即. 但我 们无论怎样点击鼠标也不能将图 11 变为图 12，因为在图 11 中， ，故图 11 属于 . 而在图 12 中， 0 s 1 s 0 s)(AN )(BN)(CN 1 s)(AN)(BN)(CN 01 ,s sS 1 6)(=AN3)(=BN 7)(=CN 2 S4)(=AN，4)(=BN，故图 12 5)(=CN 属于. 4 S 依据表 2， 我们可以从每个特定的()1,2,3,4 i S i =中挑选一个形式上最简单的状态作为 代表，不妨记为第一型，第二型，第三型和第四型，如下所示 图 14. 第一型 图 15. 第二型 图 16. 第三型 图 17. 第四型 现在，对5棋盘的任意一种状态，根据表 2，我们可以迅速判断它属于上图中的哪种 类型，并可以通过有限次的鼠标点击将它变换到该简单类型. 5 而对于的棋盘，若矩阵非退化，如n n n P8 ,