_关灯_游戏中的代数学.doc

 “关灯”游戏中的代数学 周 昊 ( 浙江树人大学 基础部, 杭州 310015) 摘要: 研究的是来自互联网上的一个有趣的数学游戏, 运用数学建模的方法给出了其基于有限域上的线 性方程组的数学模型, 对n = 5 的情形给出了所有解. 并进一步, 运用代数学的“分类”方法给出了游戏的四个 等价类的直观描述, 使游戏者不用解方程组就能立即判断出该“残局”能够变为哪个类型. 关键词: 线性方程组; 有限域; 陪集 1 引 言 “关灯”是近年来流行于 In te rn e t 上的一个非常有趣的游戏. 定义如下, 给定一个 5×5 方格的棋盘, 如图 1. 1 所示, 每个方格有白色和黑色两种状态, 当用鼠标点击其中任何一个 方格时, 则使这个方格自身及与之相邻的上, 下, 左, 右四个方格都改变状态, 即原来是白色 的则变为黑色“( 关灯”之名由此而来) , 原来是黑色的则变为白色. 对于处于棋盘边缘的 16 个方格, 如图 112 所示, 它们的这四个邻居可能不全存在, 那么我们只考虑那些存在的方格. 图 1. 1 图 1. 2 点击左图中黑色方格 对于以上定义的游戏规则, 试求解以下两个问题: ( a ) 假定棋盘的初始状态为所有方格全部为白色, 问游戏者如何点击鼠标将棋盘全部 变为黑色, 且点击鼠标的次数尽可能少. (b ) 假定棋盘的初始状态为一个残局: 部分方格为白色, 部分方格为黑色 (如图 111) , 假 如你继续点击下去, 你能否有一个方法判断, 能否使该残局最终变为全白或全黑. 建 模 2 我们将此游戏转化成一个二元域上的线性方程组的解的存在性问题, 并通过求解这个 线性方程组来得知我们最少需要多少次的鼠标点击将棋盘全部变为黑色. 我们的方法适用 收稿日期: 2003209206 基金项目: 浙江树人大学校立项二级课题( 2006A 21003) 研 究 11 期 周 昊:“关灯”游戏中的代数学 133 于一般的n ×n 个方格的棋盘. 为此下面讨论 n ×n 个方格的 棋盘. 用 0 代表白色, 1 代表黑色. 并将所有方格按从左到右, , n 2 , 当n = 5 时, 如图 211 所示. 从上到下依次编号为 1, 2, 定义状态空间S 为棋盘上所有可能的状态组成的集合, 即 S = { (e1 , e2 , , en 2 ) I ei = , n 2 }. 0, 1, i = 1, 2, 显然全白状态为s0 = {0, 0}∈S , 全黑状态为s1 = {1, 0, , 图 2. 1 , 1}∈S. 定义S 上的变换 t 为 t∶s= (e1 , e2 , = (h 1 , h 2 , 1, , en2 ) → s′ , h n2 ) , s, s′∈ S . 其中h i = ei 或者 1- ei , 特别的, 定义零变换为恒等变换O : O (e1 , e2 , 设V 是S 上所有变换所组成的集合. 成运算, 即 (f + g ) (s) = 容易验证该运算满足下述性质: , en2 ) = (e1 , e2 , , en2 ). 对任意的f , g ∈V , 定义V 中元素的加法运算为变换合 Π s ∈ S . f g (s) = f (g (s) ) , (1) (2) (3) f + g = g + f , Π f , g ∈V ; (交换律) (结合律) (f + g ) + t = f 对 Π f ∈V , f + + (g + t) , Π f , g , t ∈V ; f = O. 性质 ( 3) 告诉我们, 任何一种变换连续或间断地重复 2 次或偶数次, 此操作的作用将抵消, 为了使点击次数尽可能少, 这种重复操作应取消. 因此任何一种点击方式最多进行一次, 也即任何一种变换最多做一次. 为此考虑二元数域F 2 = {0, 1}. 不同于我们常见的实数域R 和有理数域Q , F 2 只含有 0 和 1 两个元素, 但类似于R 和Q , 我们同样可以在 F 2 上进行加减乘除四则运算, 其运算法则 如下所示. 图 2. 2 F 2 上的加法表, 减法表, 乘法表和除法表 那么, 我们可以定义二元域F 2 到V 上的数乘运算如下: 0 I f = O , Π f ∈V . 1 I f = f , 容易验证: 定理 2. 1 V 是F 2 上的线性空间. 用g i ( i= 1, 2, , n 2 ) 表示鼠标点击第 i 个方格时所产生的变换, 那么为了将棋盘由全白 变成全黑, 一次成功的